この記事は

Why and when you should use SoA ·

を自分用に訳したものを 許可を得て 公開するものである。 コードのコメントも一部翻訳されている。 ところどころ訳が怪しいところがあるので、なにか見つけた人はcontributeだ!


SoAとは何か?

SoAとは単に配列の構造体(Structure of arrays)を意味します。

//AoS: 構造体の配列(Array of structures)
struct Vec2{
    float x;
    float y;
}
Array!Vec2 vectors;
//SoA: 配列の構造体
struct Vec2{
    float[] x;
    float[] y;
}

なぜSoAは便利なのか?

クライアント・サーバー・アーキテクチャーで小さなudpゲームサーバーを書くことを想像してみてください。 あなたにはクライアントが接続できるサーバーがあります。 サーバーは現在接続しているクライアントたちを覚えておく必要があります。 サーバーはメッセージをrecvfromでポールし、あなたがudpをよく知らない場合、 recvfromはソケットにバインドされたポートとアドレスへ送られるパケットを返します。

パケットが来たとき、最初に知りたいのはパケットが接続しているクライアントから来たかどうかかもしれません。 あなたにはそれをこのように書く傾向があることでしょう:

struct Server{
    struct RemoteClient{
        Address address;
        SysTime lastReceivedPacket;
        //more data
    }
    Array!RemoteClient remoteClients;

    void poll(){
        //Address address
        //recvfrom(buffer, address);
    }
}

どのクライアントがパッケージを送ったのか知りたい時、正しいremoteClientを探すために単にremoteClients配列を使うことができます。 問題はアドレスフィールドにしか興味がないが、RemoteClientをイテレートする必要があるということです。 これはそれが必要ないとしても、lastReceivedPacketのような他のすべてのデータを不必要にロードしているということを意味します。

そして実際のアプリケーションでRemoteClientの中にどれくらいのデータがありうるか知りたいなら、 こちらがEnet Peerの構造体です。 これはPeerでありRemoteClientではないためフェアな比較ではないかもしれませんが、 これはデータがかなり大きくなるかもしれないということを示しています。

typedef struct _ENetPeer
{ 
   ENetListNode  dispatchList;
   struct _ENetHost * host;
   enet_uint16   outgoingPeerID;
   enet_uint16   incomingPeerID;
   enet_uint32   connectID;
   enet_uint8    outgoingSessionID;
   enet_uint8    incomingSessionID;
   ENetAddress   address;            /**< Internet address of the peer */
   void *        data;               /**< Application private data, may be freely modified */
   ENetPeerState state;
   ENetChannel * channels;
   size_t        channelCount;       /**< Number of channels allocated for communication with peer */
   enet_uint32   incomingBandwidth;  /**< Downstream bandwidth of the client in bytes/second */
   enet_uint32   outgoingBandwidth;  /**< Upstream bandwidth of the client in bytes/second */
   enet_uint32   incomingBandwidthThrottleEpoch;
   enet_uint32   outgoingBandwidthThrottleEpoch;
   enet_uint32   incomingDataTotal;
   enet_uint32   outgoingDataTotal;
   enet_uint32   lastSendTime;
   enet_uint32   lastReceiveTime;
   enet_uint32   nextTimeout;
   enet_uint32   earliestTimeout;
   enet_uint32   packetLossEpoch;
   enet_uint32   packetsSent;
   enet_uint32   packetsLost;
   enet_uint32   packetLoss;          /**< mean packet loss of reliable packets as a ratio with respect to the constant ENET_PEER_PACKET_LOSS_SCALE */
   enet_uint32   packetLossVariance;
   enet_uint32   packetThrottle;
   enet_uint32   packetThrottleLimit;
   enet_uint32   packetThrottleCounter;
   enet_uint32   packetThrottleEpoch;
   enet_uint32   packetThrottleAcceleration;
   enet_uint32   packetThrottleDeceleration;
   enet_uint32   packetThrottleInterval;
   enet_uint32   pingInterval;
   enet_uint32   timeoutLimit;
   enet_uint32   timeoutMinimum;
   enet_uint32   timeoutMaximum;
   enet_uint32   lastRoundTripTime;
   enet_uint32   lowestRoundTripTime;
   enet_uint32   lastRoundTripTimeVariance;
   enet_uint32   highestRoundTripTimeVariance;
   enet_uint32   roundTripTime;
   enet_uint32   roundTripTimeVariance;
   enet_uint32   mtu;
   enet_uint32   windowSize;
   enet_uint32   reliableDataInTransit;
   enet_uint16   outgoingReliableSequenceNumber;
   ENetList      acknowledgements;
   ENetList      sentReliableCommands;
   ENetList      sentUnreliableCommands;
   ENetList      outgoingReliableCommands;
   ENetList      outgoingUnreliableCommands;
   ENetList      dispatchedCommands;
   int           needsDispatch;
   enet_uint16   incomingUnsequencedGroup;
   enet_uint16   outgoingUnsequencedGroup;
   enet_uint32   unsequencedWindow [ENET_PEER_UNSEQUENCED_WINDOW_SIZE / 32]; 
   enet_uint32   eventData;
   size_t        totalWaitingData;
} ENetPeer;

ではSoAではどのようになるか見てみましょう。

struct Server{
    struct RemoteClients{
        size_t length;
        Address[] address;
        SysTime[] lastReceivedPacket;
        //more data
    }
    RemoteClients remoteClients;

    void poll(){
        //Address address
        //recvfrom(buffer, address);
    }
}

すべてのremoteClients.addressのアドレスにアクセスでき、不必要なデータをキャッシュにロードする必要はありません。

SoAは使いにくくないのか?

多くの言語ではそのとおりです。

struct RemoteClients{
    size_t length;
    Address[] address;
    SysTime[] lastReceivedPacket;
    //more data
}

配列を割り当て、それが動的配列の場合は拡張しなければならないために定義は単純化されています。 要素の挿入と削除についても気にかける必要もあります、 lastReceivedPacketを追加せずにアドレスだけをRemoteClientsに追加するようなことがあってはいけません。 データはゆるく対になっているためです。 以前のAoSの時はRemoteClientremoteClients[index]でアクセスできましたが、 今はRemoteClientにその要素remoteClients.addresses[index]remoteClients.lastReceivedPacket[index]でアクセスします。

DでのSoAの実装

まずデモンストレーションから始めましょう。

struct Vec2{
    float x;
    float y;
}
auto s = SOA!(Vec2)();

s.insertBack(1.0f, 2.0f);
s.insertBack(Vec2(1.0, 2.0f));
writeln(s.x); // [1, 1]
writeln(s.y); // [2, 2]

データで構造体を作ることができ、SOAは構造体をみて内部的に適切な配列を作ります。 持っているフィールドと同じ数の配列があるため、insertBackはちょっと普通の配列と異なります。 これはinsertBackが可変長である必要があることを意味します。 insertBackはかわりにそれ自身の構造体も受け入れます。

以下のコードは実際に使うことを意図して書かれたコードではなく、単なる概念実証です。

struct SOA(T){
    import std.experimental.allocator;
    import std.experimental.allocator.mallocator;

    import std.meta: staticMap;
    import std.typecons: Tuple;
    import std.traits: FieldNameTuple;

    alias toArray(T) = T[];
    alias toType(string s) = typeof(__traits(getMember, T, s));

    alias MemberNames = FieldNameTuple!T;
    alias Types = staticMap!(toType, MemberNames);
    alias ArrayTypes = staticMap!(toArray, Types);

    this(size_t _size, IAllocator _alloc = allocatorObject(Mallocator.instance)){
        alloc = _alloc;
        size = _size;
        allocate(size);
    }

    ref auto opDispatch(string name)(){
        import std.meta: staticIndexOf;
        alias index = staticIndexOf!(name, MemberNames);
        static assert(index >= 0);
        return containers[index];
    }

    void insertBack(Types types){
        if(length == size) grow;
        foreach(index, ref container; containers){
            container[length] = types[index];
        }
        length = length + 1;
    }

    void insertBack(T t){
        if(length == size) grow;
        foreach(index, _; Types){
            containers[index][length] = __traits(getMember, t, MemberNames[index]);
        }
        length = length + 1;
    }

    size_t length() const @property{
        return _length;
    }

    ~this(){
        if(alloc is null) return;
        foreach(ref container; containers){
            alloc.dispose(container);
        }
    }

private:
    void length(size_t len)@property{
        _length = len;
    }

    Tuple!ArrayTypes containers;
    IAllocator alloc;

    size_t _length = 0;
    size_t size = 0;
    short growFactor = 2;

    void allocate(size_t size){
        if(alloc is null){
            alloc = allocatorObject(Mallocator.instance);
        }
        foreach(index, ref container; containers){
            container = alloc.makeArray!(Types[index])(size);
        }
    }

    void grow(){
        import std.algorithm: max;
        size_t newSize = max(1,size * growFactor);
        size_t expandSize = newSize - size;

        if(size is 0){
            allocate(newSize);
        }
        else{
            foreach(ref container; containers){
                alloc.expandArray(container, expandSize);
            }
        }
        size = newSize;
    }
}
alias toArray(T) = T[];
alias toType(string s) = typeof(__traits(getMember, T, s));

alias MemberNames = FieldNameTuple!T;
alias Types = staticMap!(toType, MemberNames);
alias ArrayTypes = staticMap!(toArray, Types);

MemberNamesは単なるフィールドの名前群です。 たとえば構造体 Vec2{float x; float y}は型AliasSeq!("x", "y")になります。 toTypeはメンバ名をとり実際の型にします。 例として上のtoType!("x")は型floatを返します。

staticMapの助けを得てメンバ名を実際の型に変換することができます。 たとえば上のAliasSeq!("x", "y")AliasSeq!(float, float)に変わります。

もうすぐ型を配列に変換する必要が出てきます。 AliasSeq!(float, float)AliasSeq!(float[], float[])にです。 それをtoArraystaticMapでします。

その後配列のタプルを作ることができます。

Tuple!ArrayTypes containers;

要素の挿入はかなり簡単です。

void insertBack()(Types types){
    if(length == size) grow;
    foreach(index, ref container; containers){
        container[length] = types[index];
    }
    length = length + 1;
}

insertBackが受け入れるべき型はすでにわかっています。 構造体のフィールド郡の型をうけいれるべきです。 そして配列のタプルであるcontainersをコンパイル時にイテレートします。

それから適切なargumenttypes[index]でアクセスし、それを配列に挿入するだけです。

構造体そのものを挿入することもできます。

void insertBack(T t){
    if(length == size) grow;
    foreach(index, _; Types){
        containers[index][length] = __traits(getMember, t, MemberNames[index]);
    }
    length = length + 1;
}

indexを取得するために型をイテレートします。 indexを適切なコンテナを得るためと、構造体の適切なフィールド名を見つけるために使います。 順序は常に同じためこれは動作します。

上のコードをVec2ようにするとだいたいこんなふうになります。

void insertBack(Vec2 t){
    if(length == size) grow;
    containers[0][length] = t.x;
    containers[1][length] = t.y;
    length = length + 1;
}

配列にフィールド名でアクセスできます。 DでこれはopDispatchによって非常に簡単にできます。

ref auto opDispatch(string name)(){
    import std.meta: staticIndexOf;
    alias index = staticIndexOf!(name, MemberNames);
    static assert(index >= 0);
    return containers[index];
}

上のサンプルをVec2用にした場合ではすべてのxの配列をs.x、すべてのyの配列をs.yで得ることができます。 s.xを呼んだ場合opDispatchはコンパイル時にこんな感じになります。

ref auto opDispatch(){
    import std.meta: staticIndexOf;
    alias index = staticIndexOf!("x", MemberNames);
    static assert(index >= 0);
    return containers[index];
}

MemberNames opDispatch内が失敗しなかった場合、opDispatch nameのインデックスをMemberNamesから取得します。 MemberNames内にあればそのインデックスで適切なコンテナにアクセスします。

struct Server{
    struct RemoteClients{
        Address address;
        SysTime lastReceivedPacket;
        //more data
    }
    SOA!RemoteClient remoteClients;

    void poll(){
        //Address address
        //recvfrom(buffer, address);
    }
}

SoAを使うときはいつか

まず第一にSoAは銀の弾丸ではなく、あなたのコードベースのすべてのAoSSoAに置き換えるべきというわけではありません。

SoAに意味があるのはこのような時です:

  • データを1つの配列に保持したくなるとわかっているとき
  • 部分的にデータにアクセスしたいとき

しかし時にはデータのすべてのコンポーネントにアクセスしたい時もあるでしょう。 例としてベクトルが挙げられます。

struct Vec3{
    float x;
    float y;
    float z;
}

加算、減算、ドット積、距離その他いろいろのほとんどの操作はすべてのコンポーネントを使うでしょう。 たとえ最終的に

struct Vec3{
    float x;
    float y;
    float z;
}

Array!Vec3 positions;

positions[].filter!(v => v.x < 10.0f);

x コンポーネント10.0fより小さいすべてのベクトルをフィルタしたくなっても、2つのfloatが余分に読み込まれるだけです。 Vec3は大きくならず、これ以外の他のデータ構造が成長し、将来のボトルネックになるかもしれません。

SoAは「時期尚早な最適化」ではないのか?

私の意見は違います。 AoSの問題は、それが将来パフォーマンスボトルネックになった場合、多くのコードをリファクタしなければならないというところです。 たとえばあなたはこのように構造体hotとcoldにデータをパックするかもしれません:

struct Bar{
    struct Hot{
        Data1 d1;
        Data2 d2;
        ...
    }
    struct Cold{
        Data3 d3;
        Data4 d4;
        ...
    }

    Hot* hot;
    Cold* cold;
}

しかし言語によってはまだまだ多くのコードをリファクタしなければならないかもしれません。 早い段階でデータアクセスについて考えることで手間が省けるかもしれません。

Jonathan Blowには名無し変数とSoAをカバーする言語デモンストレーションがあります。 Quick note:Jonathan BlowのやりかたはDのalias thisとよく似ています。

使う言語によっては、SoAAoSと比べてそんなに悪くはありません。

//AoS
remoteClients[index].address;

//vs 

//SoA
remoteClients.address[index];

しかしSoAはキャッシュからの関係ない不必要なローディングなしにデータに部分的なアクセスができるため、よりスケールします。