Improve CopyOnWriteArrayList subList code

core-libs dev thread
https://openjdk.markmail.org/thread/3o2aeicaou6m24ss

Сергей Цыпанов <sergei.tsypanov@yandex.ru> writes:

on the 10th of March I wrote here about duplicated code of idnexOf/lastIndexOf methods in array-based collections.

http://mail.openjdk.java.net/pipermail/core-libs-dev/2018-March/051968.html

Later I've found one more related issue. Here's the code of CopyOnWriteArrayList$COWSubList.remove(Object) as of JDK 9/10/11:

public boolean remove(Object o) {
    synchronized (l.lock) {
        checkForComodification();
        int index = indexOf(o);
        if (index == -1)
            return false;
        remove(index);
        return true;
    }
}

Here indexOf() is inherited from j.u.AbstractList and allocates an instance of ListIterator then using hasNext()/next() to iterate over it. However, CopyOnWriteArrayList itself has private static indexOf(Object o, Object[] elements, int index, int fence) which can do the search with simple counter loop. But COWSubList is static and has no access to the methods of enclosing class.

So to get rid of calling inherited method we can either override indexOf() in COWSubList and copy-paste the contents of CopyOnWriteArrayList.indexOf(Object o, Object[] elements, int index, int fence) into it (introducing more duplicated code into JDK), or extract the code into utility method of j.u.Arrays as it's suggested in my patch above.

I used the second approach and patched COWSubList like this:

CopyOnWriteArrayList$COWSubList {
  //...

public boolean remove(Object o) {
    synchronized (l.lock) {
        checkForComodification();
        int index = indexOf(o);
        if (index == -1)
            return false;
        remove(index);
        return true;
    }
}

public int indexOf(Object o) {
    return Arrays.indexOf(o, expectedArray, offset, size); //method in my patched JDK similar to what we have in CopyOnWriteArrayList.indexOf(Object o, Object[] elements, int index, int fence)
}

//...

}

Then I compared the performance of COWSubList.remove(Object) with benchmark below. It deliberately removes no element in order to measure only the cost of finding element to be removed in CopyOnWriteArrayList$COWSubList.

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@Fork(jvmArgsAppend = {"-XX:+UseParallelGC", "-Xms1g", "-Xmx1g"})
public class CowSubListRemoveBenchmark {

    @Benchmark
    public boolean removeFromJdkCowSubList(Data data) {
        return data.subListFromJdkCowList.remove(data.integer);
    }

    @Benchmark
    public boolean removeFromPatchedCowSubList(Data data) {
        return data.subListFromPatchedJdkCowList.remove(data.integer);
    }

    @State(Scope.Thread)
    public static class Data {
        @Param({"10", "100", "1000"})
        private int size;

        private List<Integer> subListFromJdkCowList;
        private List<Integer> subListFromPatchedJdkCowList;

        private Integer integer = -1; //element is always missing from the list, so we iterate over it up to the end

        @Setup
        public void setup() {
            Integer[] integers = IntStream.range(0, size).boxed().toArray(Integer[]::new);

            subListFromJdkCowList = new CopyOnWriteArrayList<>(integers).subList(0, size / 2);
            subListFromPatchedJdkCowList = new PatchedCopyOnWriteArrayList<>(integers).subList(0, size / 2); //patched by overriding indexOf() right after remove(Object)
        }
    }
}


Output for JDK 10 (release), 5 forks, 5 warmup and 10 measurement iterations 1 s each:

Benchmark (size) Mode Cnt Score Error Units
CowSubListRemoveBenchmark.removeFromJdkCowSubList 10 avgt 50 43,585 ± 12,385 ns/op
CowSubListRemoveBenchmark.removeFromJdkCowSubList 100 avgt 50 169,230 ± 13,360 ns/op
CowSubListRemoveBenchmark.removeFromJdkCowSubList 1000 avgt 50 1167,155 ± 92,585 ns/op
CowSubListRemoveBenchmark.removeFromPatchedCowSubList 10 avgt 50 13,101 ± 0,271 ns/op
CowSubListRemoveBenchmark.removeFromPatchedCowSubList 100 avgt 50 47,641 ± 0,609 ns/op
CowSubListRemoveBenchmark.removeFromPatchedCowSubList 1000 avgt 50 479,789 ± 38,448 ns/op

Same for JDK 11 (build 11-ea+5):

Benchmark (size) Mode Cnt Score Error Units
CowSubListRemoveBenchmark.removeFromJdkCowSubList 10 avgt 50 34,510 ± 3,236 ns/op
CowSubListRemoveBenchmark.removeFromJdkCowSubList 100 avgt 50 203,669 ± 12,882 ns/op
CowSubListRemoveBenchmark.removeFromJdkCowSubList 1000 avgt 50 1194,524 ± 91,524 ns/op
CowSubListRemoveBenchmark.removeFromPatchedCowSubList 10 avgt 50 13,551 ± 0,724 ns/op
CowSubListRemoveBenchmark.removeFromPatchedCowSubList 100 avgt 50 54,565 ± 5,679 ns/op
CowSubListRemoveBenchmark.removeFromPatchedCowSubList 1000 avgt 50 425,273 ± 24,665 ns/op

So, my proposal is the same: duplicated code of indexOf()/lastIndexOf() should be moved into static utility methods of j.u.Arrays.

Regards,
Sergey Tsypanov