Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-8169748

LinkedTransferQueue bulk remove is O(n^2)

XMLWordPrintable

    • Icon: Bug Bug
    • Resolution: Fixed
    • Icon: P3 P3
    • 9
    • None
    • core-libs

        We have a new microbenchmark RemoveMicroBenchmark, that demonstrates that bulk remove operations in LinkedTransferQueue scale quadratically, while clear() scales linearly.

        /home/martin/jdk/jdk9/bin/java -XX:+UseParallelGC RemoveMicroBenchmark filter=TransferQueue warmup=0 size=100
        Method Millis Ratio
        LinkedTransferQueue .removeIf 369 1.000
        LinkedTransferQueue .removeAll 329 0.892
        LinkedTransferQueue .retainAll 319 0.865
        LinkedTransferQueue Iterator.remove 322 0.872
        LinkedTransferQueue clear 80 0.218
        /home/martin/jdk/jdk9/bin/java -XX:+UseParallelGC RemoveMicroBenchmark filter=TransferQueue warmup=0 size=200
        Method Millis Ratio
        LinkedTransferQueue .removeIf 4065 1.000
        LinkedTransferQueue .removeAll 1126 0.277
        LinkedTransferQueue .retainAll 1191 0.293
        LinkedTransferQueue Iterator.remove 1233 0.303
        LinkedTransferQueue clear 135 0.033
        /home/martin/jdk/jdk9/bin/java -XX:+UseParallelGC RemoveMicroBenchmark filter=TransferQueue warmup=0 size=400
        Method Millis Ratio
        LinkedTransferQueue .removeIf 7134 1.000
        LinkedTransferQueue .removeAll 4996 0.700
        LinkedTransferQueue .retainAll 5078 0.712
        LinkedTransferQueue Iterator.remove 4654 0.652
        LinkedTransferQueue clear 301 0.042

              martin Martin Buchholz
              martin Martin Buchholz
              Votes:
              0 Vote for this issue
              Watchers:
              4 Start watching this issue

                Created:
                Updated:
                Resolved: