[External] : Re: Fun with Spliterators

Mon Nov 4 15:50:43 UTC 2024

Also, I think that processing a parallel stream over a concurrently-modified(*)  collection might raise some questions pertaining expected semantics during processing.

* As opposed to "only" concurrently-modifiable

Cheers,
√

Viktor Klang
Software Architect, Java Platform Group
Oracle
________________________________
From: Dr Heinz M. Kabutz <heinz at javaspecialists.eu>
Sent: Saturday, 2 November 2024 20:44
To: Doug Lea <dl at cs.oswego.edu>
Cc: Viktor Klang <viktor.klang at oracle.com>; Stuart Marks <stuart.marks at oracle.com>; concurrency-discuss at openjdk.org <concurrency-discuss at openjdk.org>
Subject: [External] : Re: Fun with Spliterators

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://urldefense.com/v3/__https://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/jsr166/src/test/loops/IntegerSum.java?view=log__;!!ACWV5N9M2RV99hQ!KnVeXGYMy82l1bm2FKj3_a063UUickSrlHA8F4WzyzNUPQBQVNyOxtmUso4WEqBKHXxKJZh_OpgfeLVLUYNjygSL$
> (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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mail.openjdk.org/pipermail/concurrency-discuss/attachments/20241104/b4ff55b0/attachment-0001.htm>