ArrayListのソースを読んでみた

JJUGナイト・セミナーで発表しました

2016年11月21日に概要をお話ししました。スライドはこちらです。

ArrayListをじっくり読んでみた - JavaコアSDKを読む会を社内でやって気づいたこと - from JustSystems Corporation

以下は詳細版となります。

なぜいまArrayListのソースを読むのか

JavaコアSDKのソースを読もうと思った

ソースレビューで幾度となく指摘するnullチェックや、長すぎるメソッド、複雑だったり重複していたりするコードに業を煮やし、これはいっちょJavaコアSDKのソースを読む会とかを開催すると、「ほ～なるほど」と気づきが得られて、スキルのベースアップに役立つだろう、と思って社内で読コード会をやってみた。

↓社内Qiitaでの参加者募集の記事（抜粋）

ArrayListを選んだ理由

• 皆が使う
• java.lang.Stringはテクニックがすごすぎてたぶん重い
• ほどよいボリューム

実際にやってみたらば

JDK 1.8.0_102 の java.util.ArrayList のコードは1460行。これを先頭から1行ずつ読んでいく。1回1時間で、第6回で完走。

全然人気がなかった・・・

初回こそまあまあ人が集まったものの2回目からは結構寒い状況に…。Lombokとか便利なものがある今日この頃、コアSDKのソースを読むというのはちょっとマニアックすぎたか…。
終わってから何人かに話を聞いてみたら、読コード会の様子を毎回Qiitaに詳しくレポートしたので、それを見るだけで参加しなくてもOKそうだと思った人もいるとか…むむむ。

でも気づきはいろいろあった

リソースの節約方法や、パフォーマンスを考慮しての実装など、うなるポイントが発見できたのは収穫。
疑問点については読コード会の様子のQiita投稿に対して識者からコメントがもらえたりしてフォローしてもらえたので、自分の知識レベルの向上にも役に立った。

読コード会の様子

どういう風に読み進めていったのか、議論のポイントをメモしました。
おなかいっぱいになること請け合い。

第1回 (LL.1-220)

サマリー

• コメントが超しっかりしている
• 省力化すげー
• 関連クラスのソースまで読むのも大事

詳細

• LL.2-3: Copyright のコメントいるよね

 * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved.
 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.

• LL.4-23: この20行は * とだけ書かれているがこれはなんのため？
  • OpenJDK8 のソースではその場所に GPL2 に従うってことが書いてあるので、OpenJDK8 と行番号を合わせるため？
• L.27 packageとimportの間の空行がいいね

package java.util;

import java.util.function.Consumer;
import java.util.function.Predicate;
import java.util.function.UnaryOperator;

• LL.28-30 importに*を使っていないというのも大事。*を使っているとソースを追えなくなる。
• L.33 <tt>～</tt>とすると等幅フォントに。でも今は{@code ～}と書くね。
  • 実際L.88で使っている。統一されていない。
• LL.33-103 クラスのコメントがここまでかというくらい書いてある。利用者がどうすべきかしっかり書かれているのでいい。
• LL.97-98 @authorはメンテされればいいけど、編集した人がここに追加しなかったり、ひどいと別の人がコピペして作ったクラスで@authorがそのままになっているとか最悪。
• L.103 @sinceはプロダクトのバージョンを入れればいい
• L.107 なぜjava.io.SerializableだけFQCN表記？
  • ここでしか出てこないから？

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{

• L.108 クラスの開始の{だけで1行。これは コーディング規約 にあってないのでは。
• L.109 serialVersionUIDはserialverコマンドで出力したっぽい数字。
  • serialverコマンドの出力結果はマイナスになることもあるが？→そういうものなので無問題。ただの64bitの数字。
  • serialVersionUID = 1Lとする流儀もあるが…うーむポリシー次第？
• LL.111-113など privateでもjavadocがちゃんとある。
• LL.114 private static finalはちゃんと変数名が全部大文字になっている。serialVersionUIDはこう書くことが決まっているので例外。
• LL.116-126 EMPTY_ELEMENTDATAとDEFAULTCAPACITY_EMPTY_ELEMENTDATAの違いがよくわからない。読み進んでいけばわかるか。
  • とはいえ後者のjavadocにちゃんと「こういう違いだよ」と書いてくれてはいる。そういうコメントは大事。けど、まだそれが理解しきれていない。
• L.134 privateじゃない変数elementData。ちゃんと、なぜprivateじゃないかの説明がコメントにある。
  • でもなんでelementDataがtransientなんだろう？→未解決

    /**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     */
    transient Object[] elementData; // non-private to simplify nested class access

• L.139 javadocコメント@serialがここはあるのはなぜ？→未解決

    /**
     * The size of the ArrayList (the number of elements it contains).
     *
     * @serial
     */
    private int size;

• LL.143-159 このコンストラクタ、ちゃんと@throwsのjavadocコメントに例外の説明があるのにコンストラクタはthrows宣言していない。これはjavadocコマンドで警告が出るはず。→今は出ない?

     * @throws IllegalArgumentException if the specified initial capacity
     *         is negative
     */
    public ArrayList(int initialCapacity) {

• L.154 EMPTY_ELEMENTDATAはcapacityが0 のときに共有の配列を割り当てることでインスタンスの生成コストを節約しているのかなるほどーー。
• LL.156-157 157行目のインデントが空白4文字ではなく直前の行の(の後ろまで取っている
  • それなら156行目で(の次に改行すべきでは。

            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);

• L.165 デフォルトコンストラクタが他のコンストラクタを呼ばずに処理完結している。これはthis(DEFAULT_CAPACITY)としていないのがすごい。省力化が徹底している。

    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

• LL.179-181 Object[]でない場合のこの特別な処理はなぜ必要か？
  • BugParadeの番号っぽいのがあるからたぶん回避策→やはりそうだった
  • Object[]の場合は最初のtoArray()で完結しているので対処不要
  • 2つめのif文では{と}でくくっていない
    • Appleのあのバグを教訓に、1行であってもくくるべき
  • 最初のelementDataはthisがついていないのが気持ち悪い。よく見たらついていたりついていなかったり統一されていない。

    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }

• L.194 このmodCountは何だ？ いきなり出てきたぞ？
  • スーパークラスで宣言されている。Iteratorのための変更カウンタ。25行のjavadocコメントで解説されている。→解説があるとわかるのでよい
  • サブクラスを作るときに親クラスのコードをちゃんと読んでいるか？

    public void trimToSize() {
        modCount++;

• L.218 ensureExplicitCapacity()とは？→時間切れ

第2回 (LL.221-413)

サマリー

• キャパシティの調整周りは謎だらけで未解決。
• 普段使わないメソッドが。なるほど。

詳細

• L.97 （前回のところ） これもしかしてEffective Javaの著者のJoshua Blochでは？？

 * @author  Josh Bloch

• L.233: overflow-concsious codeってあるけど、何が言いたいのか？
  • オーバーフローが考慮されていると言うこと？ わざわざコメントに書くのはなぜ？
    • overflow-consciousは、計算の結果minCapacityが文字通りオーバーフローしても、していないのと大小関係が保たれるということ。intの最大値付近 → 1.5倍してオーバーフローしてかなり小さい負の値となった場合、a>bだと判定ミスるけど、a-b>0だと（オーバーフローの程度に依りますが）大丈夫。hugeCapacityで負の数をチェックしているのも同じ理屈かと。

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

• L.234 minCapacity > elementData.lenth ではなく、わざわざ引き算しているのは、0との比較だと早い（アセンブラコードを意識）から？
• L.244 なぜ8なのか不明。
  • javadocコメントでこれ以上大きいサイズをアロケートしようとするとOutOfMemoryErrorとあるけど、必ずしもメモリ不足なわけではないだろうのになぜOutOfMemoryErrorなのか？
    • 読む会の後での気づき：「必ずしも」ではないから、mayなのか。それならまあなるほど。

    /**
     * The maximum size of array to allocate.
     * Some VMs reserve some header words in an array.
     * Attempts to allocate larger arrays may result in
     * OutOfMemoryError: Requested array size exceeds VM limit
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

• L.255 これoldCapacityの1.5倍ということだよね？ はー、こうするもんですか。この方が早いということか。

        int newCapacity = oldCapacity + (oldCapacity >> 1);

• L.260 このコメントの意図がわからない。これでオッケー、ということ？

        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);

• LL.264-270 このメソッドの意味が分からない。→未解決
  • L.244でInteger.MAX_VALUE - 8とか言っておきながらここでInteger.MAX_VALUEを返すのはなんで？
  • minCapcityが負になるのはここまでの呼び出し方ではありえない。どういう場合を想定しているのか不明。

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

• LL.310-321 いきなりforでまわるのではなくて引数によってループを変えている。こうすることでループ中のif判定を減らすということか。なるほど。

    public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

• L.351 ArrayList<?>の<?>って何だっけ？→どのクラスでもよいということ。
  • なぜ<T>ではなく<?>なのか？→そういえばelementDataもTではなくObjectで宣言されている。実際に収まる型がなんでもいようにしている工夫か。

    public Object clone() {
        try {
            ArrayList<?> v = (ArrayList<?>) super.clone();
            v.elementData = Arrays.copyOf(elementData, size);
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            throw new InternalError(e);
        }
    }

• LL.355-358 これはObject.clone()がCloneNotSupportedExceptionをスローし、かつこの例外がchecked exceptionというのが果たして妥当だったのか疑問。

  • ともあれ、コメントの通り、ここで例外が発生することはない。こんなときにthrow new InternalError(e);がコアSDKの中ではイディオム化している。プロダクトコードでも絶対に来ないところではこうするようにしている。

• LL.365-367 1文目はわかりづらいけど、カッコ内でちゃんと言い換えてくれているのでそっちで理解。はあなるほど。

     * <p>The returned array will be "safe" in that no references to it are
     * maintained by this list.  (In other words, this method must allocate
     * a new array).  The caller is thus free to modify the returned array.

• LL.387-392 immedeiately following the end of the collectionとあるので、nullを代入するのは最後の要素の次。番兵ということか。カッコの説明にもあるけど、null番兵が使えるシーンは限定的。中途半端な。
  • 「なら残り全部null入れろよ」とも思うが代入するのもコストなので必要最小限ということか。

     * <p>If the list fits in the specified array with room to spare
     * (i.e., the array has more elements than the list), the element in
     * the array immediately following the end of the collection is set to
     * <tt>null</tt>.  (This is useful in determining the length of the
     * list <i>only</i> if the caller knows that the list does not contain
     * any null elements.)

• L.408 System.arraycopy()は初めて見た。→古く(1.0)からある。今は便利なユーティリティがあるので自分で使うことはまずない。ちなみにこのメソッドはnativeメソッド。

第3回 (LL.414-743)

サマリー

• バグらしき挙動を発見！
• batchRemove()は読解が難しい（真似してはいけない）

詳細

• LL.428-432 rangeCheck()でサイズオーバーのチェック、elementData()（の中の配列アクセス）で負の値のチェックがされている。言い換えると、elementData()で負の値がチェックされるので、rangeCheck()で負の値のチェックをする必要がない。（そして実際にチェックしていない）

    public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

• LL.446-447: 参照はメソッド経由なのに代入は配列に直アクセスしている・・・。

    public E set(int index, E element) {
        rangeCheck(index);

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

• L.458 ここでmodCountをインクリメントしているのでこのメソッドではインクリメントしなくてよいんだよ、と読む人の心理を先読みしたコメント。いいね。

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!

• L.499-500 System.arraycopy()では、srcやdstがちゃんと待避されているのかな。そうじゃないとこのコードだと、後にコピーするインデックスを上書きしてしまうことになる。

            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);

• LL.540-547 fastRemove()は、通常のremove()に比べてrangeCheck()と元の値のコピーをリターンする以外全く一緒。なるほどそこを省略するために別のメソッドを設けるものか。

        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);

• LL.576-583 これはバグっぽい。引数cの大きさが0の時、modCountはインクリメントされるが、戻り値はfalse（つまり変更なしを意味する）となる。変更なしなのにmodCountがインクリメントされて、IteratorでConcurrentModificationExceptionが発生する。変更されたのかされていないのかが動きとして統一されていない。
  • ただし、実害はまずない。

    public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }

• LL.666-667 このコメントで何がいいたいのか？ ベストというならベストの理由を書いて欲しい。

    /**
     * Constructs an IndexOutOfBoundsException detail message.
     * Of the many possible refactorings of the error handling code,
     * this "outlining" performs best with both server and client VMs.
     */
    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+size;
    }

• L.714-730 ここ(メソッドの先頭～finallyの前半)はちょっと難しい。変数名も分かりづらいしコメントも不十分。
  • rは読んだインデックス、wは書いたインデックス、であろう
  • わざわざtry-finallyでかこっているということはここで例外がスローされるということ。被疑箇所はc.contains()しかない。
    • たぶんビンゴ。finallyのコメントにif c.contains() throwsとある。
    • 裏付け：このコードでr != sizeとなるのは、ループの途中でエラーになる場合しかない
    • 呼び出し元のコードの@throws NullPointerExceptionの説明にif this list contains a null element and the specified collection does not permit null elements というコメントがあるので、ここで起こりうるのは自分のリストのエレメントにnullがあった場合のNullPointerExceptionということだろう。
  • arraycopy()で、読んでないインデックスに対して、書き込んだインデックス以降のデータをコピーしているサイズ合わせ？
    • でも中身をロールバックしているわけでもない。互換性を保たなければいけない挙動とはいったい何なのか？

    private boolean batchRemove(Collection<?> c, boolean complement) {
        final Object[] elementData = this.elementData;
        int r = 0, w = 0;
        boolean modified = false;
        try {
            for (; r < size; r++)
                if (c.contains(elementData[r]) == complement)
                    elementData[w++] = elementData[r];
        } finally {
            // Preserve behavioral compatibility with AbstractCollection,
            // even if c.contains() throws.
            if (r != size) {
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
                w += size - r;
            }
            if (w != size) {
                // clear to let GC do its work
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w;
                size = w;
                modified = true;
            }
        }
        return modified;
    }

• （上記謎への応答）もし ArrayList.removeAll() を実装してオーバーライドしなければ、AbstractCollection.removeAll() が呼び出される。Iterator#remove() を使って各要素を削除しているので、 ArrayList だったら成功しても途中で失敗しても削除分だけリストが詰められる。これを配列で実装したのが finally 節ということでしょう。

    public boolean removeAll(Collection<?> c) {
        Objects.requireNonNull(c);
        boolean modified = false;
        Iterator<?> it = iterator();
        while (it.hasNext()) {
            if (c.contains(it.next())) {
                it.remove();
                modified = true;
            }
        }
        return modified;
    }

• L.720 ここで引数にもらったフラグで判定。removeAll()とretainAll()は、ロジックは似ているけど真逆の操作なのでここでフラグ制御して重複コードをなくしている。なるほど。

第4回 (LL.744-1024)

サマリー

• シリアライズの伏線は回収された・・・か？！
• 新たなる難敵SubListの登場

詳細

• LL.754-767 writeObject()中も変更チェックするのね。へぇ～。

    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException{
        // Write out element count, and any hidden stuff
        int expectedModCount = modCount;
        s.defaultWriteObject();

        // Write out size as capacity for behavioural compatibility with clone()
        s.writeInt(size);

        // Write out all elements in the proper order.
        for (int i=0; i<size; i++) {
            s.writeObject(elementData[i]);
        }

        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }

• LL.760-763 elementDataをわざわざtransientにしてdefaultWriteObject()で書き出さないようにしているのは、elementDataのsize以上分のところを無駄に書き出さないようにするためでは？！

• L.758: sizeは直前のdefaultWriteObject()で書き出されているのにわざわざもう1回書いている。clone()の互換性の振る舞いのためってのがよくわからない。モヤッとボール。

• L.782 なんで読み込んだ値(s.readInt())を無視しているんだろう。謎。それならなんでwriteObject()の時にわざわざwriteInt(size)したのか？ つまりダミーで値を書き込んでおく必要があった？ 伏線の回収部分と思われるが理由が不明確。

    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        elementData = EMPTY_ELEMENTDATA;

        // Read in size, and any hidden stuff
        s.defaultReadObject();

        // Read in capacity
        s.readInt(); // ignored

        if (size > 0) {
            // be like clone(), allocate array based upon size not capacity
            ensureCapacityInternal(size);

            Object[] a = elementData;
            // Read in all elements in the proper order.
            for (int i=0; i<size; i++) {
                a[i] = s.readObject();
            }
        }
    }

• L.788 なぜわざわざaという変数を宣言して使うのかが不明。直接elementDataのまま使えばいいのに。

  • aに代入しておくと若干速くなる(可能性がある)のかも知れません。elementdata は this.elementdata なので、この先頭のアドレスを取得するには以下のように一度メインメモリーにアクセスする必要があります。これを変数に取っておけばCPUレジスターへのアクセスになりメモリーにアクセスする回数が減りそうです。コピーのような大きなループでは差が出るかも知れません。とは言っても、いまどきのCPUならL1キャッシュにヒットするだろうし、オプティマイザも頑張るでしょうから、差はほとんど出ないんじゃないかと思います。
    • (this のアドレス + elementdataのオフセット) の先に格納されている値
      • C言語だと &(this -> elementdata) でしょうか。

• L.890-896 本来whileループの中でcursorとlastRetを更新しなければいけないはずなのに、ヒープメモリへのアクセスを押さえるために最後の1回だけしか代入しない。いいのこれ？ ArrayListはスレッドアンセーフだからユルいということ？

        @Override
        @SuppressWarnings("unchecked")
        public void forEachRemaining(Consumer<? super E> consumer) {
            Objects.requireNonNull(consumer);
            final int size = ArrayList.this.size;
            int i = cursor;
            if (i >= size) {
                return;
            }
            final Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length) {
                throw new ConcurrentModificationException();
            }
            while (i != size && modCount == expectedModCount) {
                consumer.accept((E) elementData[i++]);
            }
            // update once at end of iteration to reduce heap write traffic
            cursor = i;
            lastRet = i - 1;
            checkForComodification();
        }

• LL.939-949 インナークラスListItrのset()は、expectedModCountの更新をしていない。何で？（下に記載のadd()との違いに注目されたい）
  • ArrayListのset()でもmodCountは変わらない。だから、ここでexpectedModCountを代入し直す必要がないと言うことか。ほうほうなるほど。

        public void set(E e) {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayList.this.set(lastRet, e);
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        public void add(E e) {
            checkForComodification();

            try {
                int i = cursor;
                ArrayList.this.add(i, e);
                cursor = i + 1;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

• LL.1025-1031 ここを読んだところで内容読解の前に時間切れ。次回このメソッドから再度読む。

        public E set(int index, E e) {
            rangeCheck(index);
            checkForComodification();
            E oldValue = ArrayList.this.elementData(offset + index);
            ArrayList.this.elementData[offset + index] = e;
            return oldValue;
        }

第5回 (LL.1025-1322)

サマリー

• SubList#listIterator()が返す匿名クラスのメソッドでArrayList.thisだったりSubList.thisだったりなんで？
• さらなる強敵Spliterator現る

詳細

• LL.1044,1069 add()はvoidなのにaddAll()がboolean`なのはなぜ？
  • add()は確実に要素を追加するけど、addAll()は引数のコレクションのサイズが0だと要素を追加しないので追加したかどうかの判定が必要だから？

        public void add(int index, E e) {

        public boolean addAll(Collection<? extends E> c) {

• LL.1073-1077 1文字変数名は分かりづらい。cSizeがcのサイズ。で、cって何だっけ？ ってなりそう。そうでもない？

        public boolean addAll(int index, Collection<? extends E> c) {
            rangeCheckForAdd(index);
            int cSize = c.size();
            if (cSize==0)
                return false;

• L.1097 lastRetは何を表しているのか？ index of LAST RETurned element ってこと？

• L.1151 なぜforEach()だけcheckForComodification()の呼び出しが最後になるのか？ 他のメソッドでは操作の前にチェックしている。

                @SuppressWarnings("unchecked")
                public void forEachRemaining(Consumer<? super E> consumer) {
                    Objects.requireNonNull(consumer);
                    final int size = SubList.this.size;
                    int i = cursor;
                    if (i >= size) {
                        return;
                    }
                    final Object[] elementData = ArrayList.this.elementData;
                    if (offset + i >= elementData.length) {
                        throw new ConcurrentModificationException();
                    }
                    while (i != size && modCount == expectedModCount) {
                        consumer.accept((E) elementData[offset + (i++)]);
                    }
                    // update once at end of iteration to reduce heap write traffic
                    lastRet = cursor = i;
                    checkForComodification();
                }

• L.1147 これはVisitorパターン

• LL.1171,1183 ArrayList.thisなのはなぜ？ SubList.thisなんじゃないの？

  • SubList.this.remove()なのに、modCountはArrayList.thisを参照。そりゃ同じ値なんだろうけど。
  • ListIteratorが2つ以上作られて、片方で変更があった時にもう一方でそれを検出できるようにするためか？

                public void remove() {
                    if (lastRet < 0)
                        throw new IllegalStateException();
                    checkForComodification();

                    try {
                        SubList.this.remove(lastRet);
                        cursor = lastRet;
                        lastRet = -1;
                        expectedModCount = ArrayList.this.modCount;
                    } catch (IndexOutOfBoundsException ex) {
                        throw new ConcurrentModificationException();
                    }
                }

                public void set(E e) {
                    if (lastRet < 0)
                        throw new IllegalStateException();
                    checkForComodification();

                    try {
                        ArrayList.this.set(offset + lastRet, e);
                    } catch (IndexOutOfBoundsException ex) {
                        throw new ConcurrentModificationException();
                    }
                }

• L.1196 add()したときにlastRetを-1にしているのはなぜ？

                public void add(E e) {
                    checkForComodification();

                    try {
                        int i = cursor;
                        SubList.this.add(i, e);
                        cursor = i + 1;
                        lastRet = -1;
                        expectedModCount = ArrayList.this.modCount;
                    } catch (IndexOutOfBoundsException ex) {
                        throw new ConcurrentModificationException();
                    }
                }

• L.1270 Spliteratorって何だ？
  • （ググる）
  • おお、ストリームAPIの中で動いているやつなのね、ほ～なるほど。

    @Override
    public Spliterator<E> spliterator() {
        return new ArrayListSpliterator<>(this, 0, -1, 0);
    }

    /** Index-based split-by-two, lazily initialized Spliterator */
    static final class ArrayListSpliterator<E> implements Spliterator<E> {

• LL.1277-1307 長いコメント。このクラスの実装方針について事細かに書かれている。なるほど～。

第6回 (LL.1323-1460)

サマリー

• 値の参照と代入を同時にやるのが読みにくい。けど読み出しが1回になるから効率はいいのかな。

詳細

• L.1323 そもそもここのfenceってなに？
  • 渡されたリストのうちアクセスする上限のインデックスを指しているようだ。

        private int getFence() { // initialize fence to size on first use
            int hi; // (a specialized variant appears in method forEach)
            ArrayList<E> lst;
            if ((hi = fence) < 0) {
                if ((lst = list) == null)
                    hi = fence = 0;
                else {
                    expectedModCount = lst.modCount;
                    hi = fence = lst.size;
                }
            }
            return hi;
        }

• L.1326 hiをfenceで初期化。fenceはコンストラクタに渡されているもので、これは-1がきているから初回はこのif文に入る。

  • の参照と代入を同時にやるのが読みにくい。けど、これを2行で書くと読み出しが2回。1回ですみそうなこちらの方が速いしメモリの使用効率もいいということか。

• LL.1337-1342 lo >= midでみているので、自分よりも下に分割できるかどうか。そして、自分自身は、index = midとしているので、上側に変身。なんというトリック。

  • 下側に分割するインスタンスを作るnewのところで、上側となる自分自身も同時に設定している。( index = mid とすることにより。） こうすることで1行で「分割」をやってのけているのがほえ～～、という感じ。

        public ArrayListSpliterator<E> trySplit() {
            int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
            return (lo >= mid) ? null : // divide range in half unless too small
                new ArrayListSpliterator<E>(list, lo, index = mid,
                                            expectedModCount);
        }

• L.1360 今回も出てきた、インスタンス変数をローカル変数に代入するテクニック。コメントを見る限りやはりループ中からインスタンス変数にアクセスしたくない意図が読み取れる。

            int i, hi, mc; // hoist accesses and checks from loop

• LL.1371,1375 i = index、つまり自分のインデックスでiを初期化して、さらにindex = hiで、ループ後の状態を先回りして代入してしまっている。
  • 本来ならループ中でindex = iとすべきだが、毎回値を代入するのを省略して代入を1回にしてマシンリソースと時間を「稼いで」いる。
  • このあたり、前回読んだ、長々と書いてあるコメントの設計方針が、なんで長々と書いているのかが裏付けられているようだ。

                if ((i = index) >= 0 && (index = hi) <= a.length) {
                    for (; i < hi; ++i) {
                        @SuppressWarnings("unchecked") E e = (E) a[i];
                        action.accept(e);
                    }

• LL.1387-1389 characteristics()というのはインタフェースSpliteratorに定義されているので実装しなければいけないメソッド。どういうリスト化の特徴を示す。SIZEDとSUBSIZEDはどう使い分けるのだろう？ SIZEDだけどSUBSIZEDではないってどういうもの？

        public int characteristics() {
            return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
        }

• LL.1418-1421 removeSet、つまり、削除対象のもの。これのnextClearBit()ということはビットが立っていないもの。つまり、削除しない＝生き残るもの。これを左から詰めている。なんか二重否定みたいでわかりにくい。

            for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
                i = removeSet.nextClearBit(i);
                elementData[j] = elementData[i];
            }

• LL.1450-1459 ソートはArrays.sort()を使っているのね。
  • Arrays.sort()をちょっと追っかけたら、ソート対象によってアルゴリズムがいろいろあって面白そう。（かなり深そうなので読むのは見送り）

    @Override
    @SuppressWarnings("unchecked")
    public void sort(Comparator<? super E> c) {
        final int expectedModCount = modCount;
        Arrays.sort((E[]) elementData, 0, size, c);
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
        modCount++;
    }