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