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

LinkedTransferQueue bulk remove is O(n^2)

    Details

    • Type: Bug
    • Status: Resolved
    • Priority: P3
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 9
    • Component/s: core-libs
    • Labels:

      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

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

                  Dates

                  • Created:
                    Updated:
                    Resolved: