Fun with Spliterators
Doug Lea
dl at cs.oswego.edu
Sat Nov 2 18:43:11 UTC 2024
On 10/31/24 16:59, Dr Heinz M. Kabutz wrote:
> Hi Doug,
>
> I've been looking at the spliterators in the LBQ and other concurrent
> classes. I'm aware that the likelihood of anyone ever wanting to
> parallel stream over one of these is extremely remote, so this is just
> a curiosity.
>
I was about to reply with the following, but while doing so I noticed
the ConcurrentSkipList problem, at probably about the same time you
did! Ignoring that for now...
We have some tests of supposedly all Spliterator-based paralelStreams,
including the one at:
https://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/jsr166/src/test/loops/IntegerSum.java?view=log
(The supposedly part is because some of them were commented out in my
routine test suite to reduce test loads. Oops.) A run of them all
adding a million integers is pasted below (only the "p" numbers,
nanosecs per element are informative).
All singly-linked data structures are slower than others because the
Spliterators don't can't balance: they can only roughly approximate this
by putting out increasing-sized batches. And performance across them is
roughly similar, People who want better performance and can tolerate
copy overhead should do so on C.toArray. I don't think we say this
anywhere, and probably should. But the sense was that people naively
calling parallelStream on strictly sequential data structures should not
expect much anyway?
-Doug
n:1000000 i: 10.05 s: 4.67 p: 0.87 Arrays.asList.keys
n:1000000 i: 15.53 s: 8.13 p: 1.06 Arrays.asList.values
n:1000000 i: 24.44 s: 15.21 p: 0.98 ArrayList
n:1000000 i: 14.01 s: 8.59 p: 0.84 ArrayList
n:1000000 i: 21.51 s: 9.02 p: 0.83 Vector
n:1000000 i: 28.29 s: 15.07 p: 1.18 Vector
n:1000000 i: 25.63 s: 17.90 p: 0.98 ArrayDeque
n:1000000 i: 14.05 s: 9.27 p: 0.84 ArrayDeque
n:1000000 i: 17.10 s: 8.79 p: 0.84 CopyOnWriteArrayList
n:1000000 i: 22.77 s: 14.38 p: 1.17 CopyOnWriteArrayList
n:1000000 i: 29.21 s: 21.85 p: 1.10 PriorityQueue
n:1000000 i: 19.91 s: 12.19 p: 0.89 PriorityQueue
n:1000000 i: 35.81 s: 23.34 p: 1.59 HashSet
n:1000000 i: 77.48 s: 79.30 p: 2.72 HashSet
n:1000000 i: 15.09 s: 11.80 p: 2.37 ConcurrentHashMap$KeySetView
n:1000000 i: 31.58 s: 10.07 p: 2.29 ConcurrentHashMap$KeySetView
n:1000000 i: 51.67 s: 19.06 p: 3.41 TreeSet
n:1000000 i: 127.58 s: 123.33 p: 2.40 TreeSet
n:1000000 i: 21.82 s: 14.62 p: 3.38 ConcurrentSkipListSet
n:1000000 i: 103.25 s: 102.54 p: 3.64 ConcurrentSkipListSet
n:1000000 i: 14.21 s: 10.84 p: 1.97 HashMap.keys
n:1000000 i: 63.92 s: 49.16 p: 2.14 HashMap.vals
n:1000000 i: 44.50 s: 31.97 p: 1.51 IdentityHashMap.keys
n:1000000 i: 47.72 s: 30.90 p: 1.50 IdentityHashMap.vals
n:1000000 i: 30.30 s: 21.01 p: 2.27 WeakHashMap.keys
n:1000000 i: 94.88 s: 51.68 p: 2.43 WeakHashMap.vals
n:1000000 i: 13.46 s: 9.07 p: 1.59 ConcurrentHashMap.keys
n:1000000 i: 60.72 s: 45.22 p: 2.22 ConcurrentHashMap.vals
n:1000000 i: 37.80 s: 27.82 p: 2.12 TreeMap.keys
n:1000000 i: 63.91 s: 39.49 p: 4.01 TreeMap.vals
n:1000000 i: 11.05 s: 5.77 p: 2.40 ConcurrentSkipListMap.keys
n:1000000 i: 47.51 s: 29.44 p: 2.82 ConcurrentSkipListMap.vals
n:1000000 i: 12.55 s: 13.75 p: 22.59 Hashtable.keys
n:1000000 i: 55.58 s: 76.51 p: 25.36 Hashtable.vals
n:1000000 i: 11.42 s: 12.06 p: 16.10 LinkedHashMap.keys
n:1000000 i: 45.33 s: 47.96 p: 15.85 LinkedHashMap.vals
n:1000000 i: 11.37 s: 12.81 p: 16.68 LinkedHashSet
n:1000000 i: 52.61 s: 54.13 p: 17.09 LinkedHashSet
n:1000000 i: 11.95 s: 4.83 p: 10.32 LinkedList
n:1000000 i: 39.85 s: 23.24 p: 8.22 LinkedList
n:1000000 i: 11.38 s: 4.70 p: 6.74 ConcurrentLinkedQueue
n:1000000 i: 42.81 s: 24.56 p: 7.42 ConcurrentLinkedQueue
n:1000000 i: 15.18 s: 8.83 p: 12.62 ConcurrentLinkedDeque
n:1000000 i: 44.88 s: 32.77 p: 17.48 ConcurrentLinkedDeque
n:1000000 i: 25.58 s: 7.71 p: 7.57 LinkedBlockingQueue
n:1000000 i: 63.58 s: 32.49 p: 8.18 LinkedBlockingQueue
n:1000000 i: 16.52 s: 8.29 p: 6.71 LinkedBlockingDeque
n:1000000 i: 50.93 s: 29.11 p: 7.75 LinkedBlockingDeque
n:1000000 i: 12.22 s: 5.00 p: 7.48 LinkedTransferQueue
n:1000000 i: 48.98 s: 26.73 p: 8.17 LinkedTransferQueue
n:1000000 i: 19.58 s: 5.68 p: 29.51 ArrayBlockingQueue
n:1000000 i: 36.46 s: 18.63 p: 30.79 ArrayBlockingQueue
n:1000000 i: 12.36 s: 5.91 p: 2.04 PriorityBlockingQueue
n:1000000 i: 28.46 s: 19.43 p: 1.94 PriorityBlockingQueue
More information about the concurrency-discuss
mailing list