Fun with Spliterators
Dr Heinz M. Kabutz
heinz at javaspecialists.eu
Sat Nov 2 19:44:47 UTC 2024
On 2024-11-02 20:43, Doug Lea wrote:
> 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
The test I would like to add to the OpenJDK would create a collection of
reasonable size (100k should be enough) and then call trySplit() on it.
This would fail if the result is null, because that would mean that the
collection won't be able to have a parallel stream.
And yes, I do think that we should encourage those that need to process
elements in parallel to copy them to an array based structure, or even
to an array directly. ArrayList is probably OK, so new
ArrayList<>(collection).parallelStream() instead of using
collection.parallelStream() directly for a sequential structure.
Heinz
More information about the concurrency-discuss
mailing list