JDK-8169748 : LinkedTransferQueue bulk remove is O(n^2)
  • Type: Bug
  • Component: core-libs
  • Sub-Component: java.util.concurrent
  • Priority: P3
  • Status: Resolved
  • Resolution: Fixed
  • Submitted: 2016-11-16
  • Updated: 2017-07-18
  • Resolved: 2017-02-03
The Version table provides details related to the release that this issue/RFE will be addressed.

Unresolved : Release in which this issue/RFE will be addressed.
Resolved: Release in which this issue/RFE has been resolved.
Fixed : Release in which this issue/RFE has been fixed. The release containing this fix may be available for download as an Early Access Release or a General Availability Release.

To download the current JDK release, click here.
JDK 10 JDK 9
10Fixed 9 b156Fixed
Related Reports
Relates :  
JDK-8181580 - No CCC for LinkedBlockingDeque#addAll
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
Comments
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.
30-12-2016
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.
29-11-2016
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.
16-11-2016