accumulate locally and mutatively but combine concurrently (a use case)

Doug Lea dl at
Sat May 11 03:41:57 PDT 2013

On 05/10/13 21:40, John Rose wrote:
> On May 10, 2013, at 4:59 PM, Doug Lea <dl at
> <mailto:dl at>> wrote:
>> Parallel reduction/accumulation is of course an old and well-studied
>> area, so there are many known good ways and even more known bad ways
>> to handle particular cases. But for collecting into hash tables,
>> we're pretty sure that using CHM in CONCURRENT mode is the best
>> available choice.
> I accept that, with pleasure, assuming there are more table keys than processors.
> The case I'm asking about is the keyless case, which seems to benefit from
> buffering before inter-processor communication.  In this case, there is no need
> to move the data once it has been buffered.

... although most techniques that avoid copying entail
associating keys with elements (for array-based, an index serves as key).
Expanding the kinds of cases where this can apply (such as using
hash-based buffers for non-Map, non-Set elements) is also among
potential improvements. Hash-based are nice because the
probability of contention is (less than) the probability of
collision. See the JDK8 ConcurrentHashMap internal docs for
some details on this.) Array-index-based are even nicer if you can
structurally guarantee that each partition only uses a
non-overlapping index range.


More information about the lambda-dev mailing list