Inefficient indexOf called inside of CopyOnWriteArrayList$COWSubList.remove(Object)

[Сергей Цыпанов]

Hi,

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