Numeric (and accumulators)

[Doug Lea]

On 09/17/12 11:37, Brian Goetz wrote:

>> public abstract class LongAccumulator implements Numeric<Long> {
>
> I like these.  I believe that they all assume commutative combination functions,
> not simply associative (what are sometimes called abelian monoids, rather than
> ordinary monoids)?

Starting with meta-answer (sorry :-)
The impact of commutativity is in part a matter of usage
of a function, not just the function. For example,
suppose the accumulation were list-append, which is
not commutative. But further suppose that you don't
care about the order of the elements in the result.
In which case, maybe you shouldn't have used a List,
but instead a Bag (which you can think of as a list in
which order doesn't matter). But we have no Bag interface/classes.

And on the other side, an Accumulator itself doesn't/can't
know if it is being called in a way that guarantees
any further properties beyond basic thread-safety
consequences of choosing sequential, locked, or optimistic.
In particular, the optimistic versions may invoke the
combining function multiple times (on CAS failures), so may
act surprisingly if the functions are not idempotent.
Yet even here there is no absolute requirement. A function
that introduces random noise to results using a per-invocation
random number is not strictly idempotent but may be completely
fine in an Accumulator.

These kinds of issues/cases arise a lot. So I don't
think you can do more than clearly explain them in
javadoc specs.

>
>> In some testing I've done using them; as in:
>>    for each element x in parallel { adder.update(x); }
>> is only around 25% slower than clever reduction schemes even
>> on machines with lots of cores and updates. This is worth
>> avoiding when possible, but the option is worth providing
>> for the cases where people don't know of an appropriate reduction.
>
> Can you clarify what you mean by "clever reduction scheme"?
>

For example, CHM.reduceValuesToLong that uses a tree-like reduction
scheme is only about 25% faster in some tests/machines than
implementing it as forEach(x -> adder.add(x)). Around 25% is
about the best case I've seen, but I haven't seen any worse
than 100% (i.e., twice as slow), which is still not terrible
given that you still get scalability, so stays half as fast
even on a hundred or so cores. So having this scheme available
as a backup option for reductions on data structures that resist
tree-based reductions seems like a good idea.

-Doug