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:
      None

      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

          Issue Links

            Activity

            Hide
            martin Martin Buchholz added a comment -
            Interior removes are not important, and the queue management code is hairy, so this may be left unfixed, but it would be nice to do better.
            Show
            martin Martin Buchholz added a comment - Interior removes are not important, and the queue management code is hairy, so this may be left unfixed, but it would be nice to do better.
            Hide
            martin Martin Buchholz added a comment -
            Looking more closely at the implementation, I see that the sweepvotes mechanism does not seem to be triggered at all.

            I think we should get rid of sweep voting entirely, and change the implementation to not be afraid to unlink dead nodes, even when the predecessor may be dead. If we have Nodes

            A -> B -> C

            and B is dead (matched or cancelled), then it is always legit to A.casNext(B, C), whether or not A is dead or still in use in some other traversal. As in ConcurrentLinkedQueue.
            Show
            martin Martin Buchholz added a comment - Looking more closely at the implementation, I see that the sweepvotes mechanism does not seem to be triggered at all. I think we should get rid of sweep voting entirely, and change the implementation to not be afraid to unlink dead nodes, even when the predecessor may be dead. If we have Nodes A -> B -> C and B is dead (matched or cancelled), then it is always legit to A.casNext(B, C), whether or not A is dead or still in use in some other traversal. As in ConcurrentLinkedQueue.
            Hide
            martin Martin Buchholz added a comment -
            We can port bulk remove code from other concurrent collections to LinkedTransferQueue. It is trickier because of dual mode and the possibility of concurrent mode change.
            Show
            martin Martin Buchholz added a comment - We can port bulk remove code from other concurrent collections to LinkedTransferQueue. It is trickier because of dual mode and the possibility of concurrent mode change.
            Hide
            hgupdate HG Updates added a comment -
            URL: http://hg.openjdk.java.net/jdk9/dev/jdk/rev/06bdfec766f4
            User: martin
            Date: 2017-02-03 21:32:18 +0000
            Show
            hgupdate HG Updates added a comment - URL: http://hg.openjdk.java.net/jdk9/dev/jdk/rev/06bdfec766f4 User: martin Date: 2017-02-03 21:32:18 +0000
            Hide
            hgupdate HG Updates added a comment -
            URL: http://hg.openjdk.java.net/jdk9/jdk9/jdk/rev/06bdfec766f4
            User: lana
            Date: 2017-02-08 19:31:50 +0000
            Show
            hgupdate HG Updates added a comment - URL: http://hg.openjdk.java.net/jdk9/jdk9/jdk/rev/06bdfec766f4 User: lana Date: 2017-02-08 19:31:50 +0000

              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: