Fun with Spliterators

[Doug Lea]

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