動的配列について – JavaのLinkedListとArrayListを分析・比較する

私はSkienaの『Algorithm Design Manual』(訳注:『アルゴリズム設計マニュアル』 上巻下巻) を読んでいました。ところでこの本は素晴らしい本で、連結リストと配列についてこんな比較をしていました(chapter 3.1.3)。

連結リストが静的配列に勝る相対的な長所には以下のものがあります。:
• メモリが本当にいっぱいにならない限り、連結構造にオーバーフローが生じない。
• 連続的な(配列)リストに比べて、挿入と削除が単純である。
• 大きなレコードを扱う場合、要素自体を動かすよりもポインタを動かすほうが容易かつ高速である。

一方で、配列の相対的な長所には以下のものがあります。
• 連結構造には、ポインタのフィールドを格納するための余計な領域が必要となる。
• 連結リストでは、要素に対する効率的なランダムアクセスができない。
• 配列は、ランダムなポインタのジャンプに比べてメモリ局所性やキャッシュパフォーマンスが優れている。

Skiena氏は包括的な比較をしてくれているのですが、残念ながら最後のポイントについての重きの置き方が十分ではありません。私はシステムプログラマとして、「メモリアクセスパターンや効率的なキャッシュ、効率的なCPUパイプラインの利用が大きな影響力を持ち得る・持つ」ということを知っており、ここではそれを示したいと思っています。

簡単なテストをしてみて、連結リストと動的配列のデータ構造での基本的な操作(挿入や検索など)のパフォーマンスを比較してみましょう。

コンピュータ・サイエンスの場における完璧なツールとして、私はJavaを使うことにします。JavaにはLinkedListArrayListの両方があります。これらはそれぞれ連結リストと動的配列を実装しており、両方が同じListインターフェイスを実装しています。

テストには以下のものを含みます。

  1. 100万個のランダムな要素の挿入によるメモリ割り当て。
  2. ランダムな箇所への10000個の要素挿入。
  3. 先頭への10000個の要素挿入。
  4. 末尾への10000個の要素挿入。
  5. 10000個のランダムな要素の検索。
  6. 全ての要素の削除。

ソースは私のCS playgoundリポジトリのds/list-perf ディレクトリ

Sources are at my CS playground in ds/list-perf ディレクトリにあります。これはMavenプロジェクトなので、mvn packageするだけでjarを入手可能です。テストは極めてシンプルで、例えば以下がランダム挿入のテストです。

package com.dzyoba.alex;

import java.util.List;
import java.util.Random;

public class TestInsert implements Runnable {
    private List<Integer> list;
    private int listSize;
    private int randomOps;

    public TestInsert(List<Integer> list, int randomOps) {
        this.list = list;
        this.randomOps = randomOps;
    }

    public void run() {
        int index, element;
        int listSize = list.size();
        Random randGen = new Random();
        for (int i = 0; i < randomOps; i++) {
            index = randGen.nextInt(listSize);
            element = randGen.nextInt(listSize);
            list.add(index, element);
        }
    }
}

これはListインターフェイスを利用して動作しており(そうです、ポリモーフィズムです!)、何も変更せずともLinkedListArrayListの両方を渡すことができます。テストは先ほど書いた通りの順番(割り当て→挿入→検索→削除)で複数回実行され、全ての結果の最小値/中央値/最大値を計算します。

さあ、説明はこれで十分でしょうから、実行してみましょう!

$ time java -cp target/TestList-1.0-SNAPSHOT.jar com.dzyoba.alex.TestList
Testing LinkedList
Allocation: 7/22/442 ms
Insert: 9428/11125/23574 ms
InsertHead: 0/1/3 ms
InsertTail: 0/1/2 ms
Search: 25069/27087/50759 ms
Delete: 6/7/13 ms
------------------

Testing ArrayList
Allocation: 6/8/29 ms
Insert: 1676/1761/2254 ms
InsertHead: 4333/4615/5855 ms
InsertTail: 0/0/2 ms
Search: 9321/9579/11140 ms
Delete: 0/1/5 ms

real    10m31.750s
user    10m36.737s
sys 0m1.011s

ぱっと見て分かる通り、LinkedListが劣っています。しかし、素晴らしい箱ひげ図をご覧になって下さい。

Allocation and delete in LinkedList and ArrayList
LinkedListとArrayListでの割り当てと削除

Insert in LinkedList and ArrayList
LinkedListとArrayListでの挿入

Search in LinkedList and ArrayList
LinkedListとArrayListでの検索

そして、全てのテストをまとめたリンクもあります。

全ての操作において、LinkedListが恐ろしく劣っています。唯一の例外が先頭への挿入ですが、それでも動的配列の最悪のケースと勝負しているだけです。このケースにおいて、動的配列は配列全体を毎回コピーしなければならないからです。

これを説明するために、実装について少し深く見ていきます。Java 8のOpenJDKのソースを使います。

ArrayListLinkedListのソースはsrc/share/classes/java/utilにあります。

JavaのLinkedListは、Node内部クラスを通じた双方向リストとして実装されています。

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

では、シンプルな割り当てテストの状況下で何が起こっているのかを見てみましょう。

for (int i = 0; i < listSize; i++) {
    list.add(i);
}

これは、addメソッドを
呼び出し、さらにaddメソッドはJDKのlinkLastメソッドを呼び出します。

public boolean add(E e) {
    linkLast(e);
    return true;
}

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

基本的に、LinkedListでの割り当ては定数時間の操作となります。LinkedListクラスは末尾のポインタを保持しているため、挿入のために必要なのは「新しいオブジェクトの割り当て」「2つのポインタの更新」のみとなります。これがそんなに遅くなるはずがないのです! では、なぜ実際は遅くなっているのでしょう?ArrayListと比較してみましょう。

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

JavaのArrayListは実のところ、「初期設定として10個までの容量を持ち、容量を増やす際には毎回1.5倍に増やす」という動作をする動的配列なのです。//overflow-conscious codeという記述も実におかしです。なぜこのようになっているのかという理由は、こちらで読むことができます。

自身のリサイズはArrays.copyOfを通じて行われており、これはJavaのネイティブメソッドであるSystem.arraycopyを呼び出します。ネイティブメソッドの実装はJDKの一部ではないため、これはJVM固有の機能となります。HotSpotのソースを探し出し、見てみましょう。

簡潔にまとめると以下の通りです―この機能はTypeArrayKlass:copy_arrayメソッド内にあり、これはCopy:conjoint_memory_atomicを呼び出します。このメソッドはアラインメントを探しますが、見ての通りメソッド内にはコピーメソッドのlong、int、short、bytes(アラインメントがない場合)向けのバリエーションがあります。int向けのメソッドであるconjoint_jints_atomicを見てみますが、これはpd_conjoint_jints_atomicのラッパであり、OSとCPUに固有のものとなります。Linux用のバリエーションを探してみると、_Copy_conjoint_jints_atomicへの呼び出しが見つかります。最後に待ち受けているのはアセンブリの獣です!

        # Support for void Copy::conjoint_jints_atomic(void* from,
        #                                              void* to,
        #                                              size_t count)
        # Equivalent to
        #   arrayof_conjoint_jints
        .p2align 4,,15
    .type    _Copy_conjoint_jints_atomic,@function
    .type    _Copy_arrayof_conjoint_jints,@function
_Copy_conjoint_jints_atomic:
_Copy_arrayof_conjoint_jints:
        pushl    %esi
        movl     4+12(%esp),%ecx      # count
        pushl    %edi
        movl     8+ 4(%esp),%esi      # from
        movl     8+ 8(%esp),%edi      # to
        cmpl     %esi,%edi
        leal     -4(%esi,%ecx,4),%eax # from + count*4 - 4
        jbe      ci_CopyRight
        cmpl     %eax,%edi
        jbe      ci_CopyLeft 
ci_CopyRight:
        cmpl     $32,%ecx
        jbe      2f                   # <= 32 dwords
        rep;     smovl
        popl     %edi
        popl     %esi
        ret
        .space 10
2:      subl     %esi,%edi
        jmp      4f
        .p2align 4,,15
3:      movl     (%esi),%edx
        movl     %edx,(%edi,%esi,1)
        addl     $4,%esi
4:      subl     $1,%ecx
        jge      3b
        popl     %edi
        popl     %esi
        ret
ci_CopyLeft:
        std
        leal     -4(%edi,%ecx,4),%edi # to + count*4 - 4
        cmpl     $32,%ecx
        ja       4f                   # > 32 dwords
        subl     %eax,%edi            # eax == from + count*4 - 4
        jmp      3f
        .p2align 4,,15
2:      movl     (%eax),%edx
        movl     %edx,(%edi,%eax,1)
        subl     $4,%eax
3:      subl     $1,%ecx
        jge      2b
        cld
        popl     %edi
        popl     %esi
        ret
4:      movl     %eax,%esi            # from + count*4 - 4
        rep;     smovl
        cld
        popl     %edi
        popl     %esi
        ret

ポイントは、VM言語が遅いことにあるのではなく、ランダムメモリアクセスがパフォーマンスを低下させていることにありました。conjoint_jints_atomicの肝はrep; smovl1です。そして、CPUが本当に好むのものがあるとすれば、それはrep命令です。これに対して、CPUはパイプラインやプリフェッチ、キャッシュなど、この命令のために構築された全ての物―ストリーミング計算と予測的メモリアクセスを利用することができます。«Modern Microprocessors. A 90 Minute Guide!»をお読みください。

これの意味するところは、アプリケーションに対してrep smovlは実際には線形時間の操作ではなく、やや定数時間寄りの操作である、ということです。最後のポイントを見ていきましょう。100万個の要素のリストについて、先頭に100、1000、10000個の要素を挿入してみましょう。私のマシンでは、以下のサンプルが得られました。

  • 100 TestInsertHead: [41, 42, 42, 43, 46]
  • 1000 TestInsertHead: [409, 409, 411, 411, 412]
  • 10000 TestInsertHead: [4163, 4166, 4175, 4198, 4204]

10倍にするごとに、計算も10倍になっていますね。これは10 * O(1)だからです。

熟練の開発者はエンジニアであり、そういった人々はコンピュータサイエンスはソフトウェアエンジニアリングではないというのを御存じでしょう。理論上は良いものが、全てのファクターを考慮しないことにより実践では悪くなるということもあります。実世界で成功するためには、下部を支えるシステムとその動作に関する理解がとても重要になり、影響力を持ちます。

そしてこれは私だけの意見ではなく、数年前2からRedditにこんなリンクがありました―「Bjarne Stroustrup: Why you should avoid LinkedLists」というものです。私は彼の論旨に同意しています。しかし、勿論、気を確かに持って、誰かや何かを盲目的に信じることのないようにしましょう。計測、計測、計測です。

私の今までで一番のお気に入りであるJames Mickensの『The Night Watch』を添えてお別れしたいと思います。


  1. GNUアセンブラでは、rep命令は2行に渡って書かなければなりませんが、セミコロンを使うことでこれを回避できます。 

  2. おお、私はまだこのリンクを覚えていました!