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

LinkedTransferQueue bulk remove is O(n^2)

    XMLWordPrintable

Details

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

    Backports

      Description

        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

        Attachments

          Issue Links

            Activity

              People

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

                Dates

                  Created:
                  Updated:
                  Resolved: