Unrolled linked list

連結リストと配列の中間に位置するハイブリッドなデータ構造です。
連結リストのように要素の追加や削除が簡単で、配列のように省メモリであるという特長がある。
（逆に連結リストはメモリのオーバーヘッドが大きく、CPUキャッシュヒットミスもしやすいデータ構造で、配列は要素の追加と削除がしにくいデータ構造です。）

Unrolledとは、おそらく loop unrolling （ループ展開）に掛けているのだと思う。
よって、「Unrolled linked list」和訳を考えるなら、「展開連結リスト」。

以降は、http://blogs.msdn.com/b/devdev/archive/2005/08/22/454887.aspx の日本語訳です。

Today I'll be...

今日は、Unrolled linked list について話しましょう。
Unrolled linked listは、Linked list（連結リスト）の単純なバリエーションです。
しかも近代的なPCにおいて、見違えるほどのパフォーマンスを引き出してくれます。

In elementary data...

データ構造についての初等教育では、よく配列や Linked list（連結リスト）について、
それぞれの間に次のようなトレードオフがあると教えられます。

• 配列は、k番目の要素をすばやく取り出せるが、しかし配列の途中にデータを追加することは非常に遅い。
• Linked listは、その逆に、k番目の要素を取り出すのは遅いが、途中にデータを追加するのは速い。

しかし、配列には他にも次のような特長があります。

• 配列は、コンパクトです。配列は、データ全体とほとんど同じ量のメモリを消費しますが、Linked list（連結リスト）は、実際のデータを整理するために、ポインタやメモリアロケーションに関するメタデータやアラインメントなど、多くのメモリが必要となります。
• 近代的な PC は、他段階のキャッシュ構造を持っていますので、要素に順序良くアクセスする場合、非常に高速です。キャッシュにヒットすることで、非常に高速なアクセスができます。つまり、キャッシュに関してセンシティブな解析は必要なく、ただ、キャッシュミスをカウントすれば良いのです。たとえば、キャッシュラインのサイズがBだとすると、キャッシュミスの回数は大よそ、n/Bとなります。Linked list （連結リスト）の場合、最悪、ノードアクセスのたびにキャッシュミスします。Linked list（連結リスト） は、最高の場合でさえ、つまり偶然にも各要素が連続メモリに配置された場合でも、その要素サイズが配列の要素サイズに比べ大きいため、キャッシュミスは必然的に配列よりも多くなります。

Let's make this concreate

さて、具体的にやってみましょう。
環境は次のとおりです。

OS

Gentoo Linux

Compiler

gcc

CPU

Pentium4 3.5GHz

私は、6000万個の整数を持つ Linked list と配列を構築しました。
そして、最大限の最適化オプションをつけてコンパイルしました。
結果、すべての要素にアクセスするのにかかった時間は次のとおりでした。

Linked list

0.48秒

配列

0.04秒

実に12倍です。
試しに、フラグメンテーション状態のメモリ領域に対して、同じ実験を行ったところ、配列の優位性は50倍以上にもなりました。
Linked listは、配列より約4倍のメモリを必要とします。内2倍は、次の要素を指すポインタを持つために必要で、内2倍はメモリ確保のために必要となった埋め込みデータのために必要とされます。

Don't throw out your linked lists...

でも、まだ Linked list を捨てないでください。先ほどの 6000万個の要素を持つ配列に対して、途中の位置に要素を追加したら、その処理に数週間かかります。キャッシュがあるにもかかわらず、です。
もし、あなたのアプリケーションが途中に位置に要素を追加したり、途中の要素を消したりすることを頻繁に行うのであれば、配列は使えないでしょう。また配列の要素数を増やすにも遅く、メモリが断片化した状態では、確保に失敗することすらあります。
私たちは、配列のようにキャッシュの恩恵にあずかれて、Linked listのように素早く挿入や拡張ができる何かが必要です。

Enter the unrolled linked list

では、いよいよ Unrolled linked list の話をしましょう。
簡単に説明すれば、Unrolled linked list は、要素数Nの配列の Linked list です。
それぞれの配列は、挿入や削除を高速に行うには十分に小さいサイズです。大きくないため、キャッシュラインにも十分乗ります。
リストを指すイテレータは、ノードへのポインタと、そのノードのインデックスで表します。

Let's consider insertion...

まず、挿入について考えましょう。
値を挿入したいと考えたとき、もし各ノードの配列に空きスペースがあった場合、挿入にかかる時間は、O(N)となる。（Nは、Unrolled linked list のノード内配列の要素数です。）
もし、すでに配列内にN個の値が格納されている場合、新たなノードを作成する必要があります。新たなノードを作り、現在のノードの配列に格納されている半分の要素を新しいノードへ移します。これで現在のノードに新しい値を格納するための空きスペースができます。このときの処理にかかる時間もやはり、O(N) です。

Deletion is similar...

削除もこれに似ています。配列から値を削除するだけです。（★訳者注意：配列途中の値を削除する場合、つまりN要素の配列において、2番目の要素など末尾でない要素を削除などした場合に、３個目にあった要素を２個目にコピー（移動）、４個目の要素を３個目にコピーしていく処理が必要です）。
配列内の有効な要素数がN/2を下回った場合は、隣接するノードに要素を移します。もし、その隣接するノード内の配列の要素数がN/2の場合、代わりに隣接の配列とマージします。（★訳者注意：なるべく配列にはN/2以上の要素が詰まっている状態にしたいので、要素数がN/2未満になったら、そのノードを削除し、隣接ノードへ要素をコピー（移動）する。ただ、移動先のノードに移動する際に、要素数の上限値を超えてしまう場合は、逆方向、つまり隣接ノードから削除しようとしていたノードに要素をコピー（移動）する。）
これらの操作は、B木の操作性に類似性があります。

Your first reaction may be...

これまでの話を聞いて、あなたは配列内の半分の要素が無駄になってしまうと感じたのではないでしょうか。
しかしながら、実際には配列は平均で約70％が満たされています。最悪のケースでさえ、普通の Linked list と同等で、要求されるのは要素ごとのオーバーヘッドは、少なくとも１ワード、多くとも４ワードか５ワードとなります。いくつかの要素にかかるオーバヘッドを償却することによって、Unrolled linked list は、単純な配列のようにコンパクトになります。要素ごとのオーバーヘッドは、1/N に比例し、実際のところは、要素ごとに数ビットのオーバーヘッドとなります。
私たちは、コンパクトさと処理時間のトレードオフによって、Nを定めることができます。スペースの有利性は、文字やビットのように小さな値をリストにした場合、より大きくなります。最後に、もしマージや分割が頻繁に起こるようであれば、必要に応じて、隣接配列とのマージ処理を50％ではなく、50％以上としても構いません。

Although space is critical...

しかし、多くのアプリケーションにとって、消費メモリは重要な課題です。Unrolled linked listの主な利点は、キャッシュの動作にあります。
もし各ノードのサイズが、キャッシュラインのサイズの倍数で、ノードの各要素にデータが詰まっている場合、Bをキャッシュラインサイズとすると、我々は、各ノードを最適な形で行き来できます(N/B回キャッシュミスする※訳者注意：Nはノード内の配列要素数）。また、リストへの走査は、(n/N+1)(N/B)回キャッシュミスし、これは実数Nについて、最適なn/B回のキャッシュミスという理想形に近づきます。（※訳者注意：正直意味不明。多分、小文字のnは走査の回数）。
平均的には、配列走査よりも40％超多くのキャッシュミスがあり、最悪のケースでは２回発生しますが、１４～５０回発生するよりはるかにマシです（訳者注意：正直意味不明）。

In practice...

経験的に、複雑性と引き換えに若干のオーバーヘッドがあります。私は少し実験をしました。
実験では、最初に書いたのと同じ６千万個の整数リストを用いて行いました。
Unrolled linked listの各ノードは124個の整数を持つようにしました。
すべてのノードが満たされていて、メモリプールがフラグメント状態の時、リスト作成に0.64秒、リスト走査に0.10秒かかりました。これは配列に比べ2.5倍遅く、これはL2キャッシュが有効に働いていることを物語っています。ノードの50％が満たされている時、0.15秒必要でした。すべてのノードが満たされている場合、配列に比べ17％多くメモリを消費していました。もちろん50％の使用率であれば、さらに２倍の多くのメモリを消費します。メモリプールによって、配列とのメモリ消費量の際を狭められました。

One small issue...

Unrolled linked listに関して、一つ小さな問題は、各配列の要素数のトラックをキープすることです。一つ簡単で、メモリ消費量的にも有効な方法で、有用な方法は、未使用の配列スロットを満たすために "null" 値を予約として扱うことです。ノードをそろえるには、時々、要素数をそのポインタの低ビットに格納できます。そうでなければ、少し、ノードごとのオーバーヘッドを追加します。

I hope...

この記事があなたの助けとなることを願っています。また、今後もキャッシュに関するデータ構造について話をする機会があればと思います。もし質問があれば尋ねてください。

ではでは。
Derrick Coetzee
この記事は、「現状有姿」のまま、何ら保証なく提供されています。