Improve implementation of RealSum

[minnerbe]

Problem

While profiling an application that uses ImgLib2, I learned that multiple threads concurrently summing up large arrays using net.imglib2.util.RealSum are responsible for a big chunk of CPU-time.

Proposed changes

Subsequently, I researched numerically stable ways of summing up floating point numbers, and learned that the current implementation could be improved by using a variant of the Kahan summation algorithm.

I implemented this algorithm in RealSum, keeping the API stable. Since there is no capacity anymore, I also deprecated the constructor that takes an int and deleted the corresponding test.

Improvements

I added a simple test that fails for the current implementation, but passes for the proposed implementation using the improved Kahan algorithm. Furthermore, the new implementation is substantially faster than the old one. These are the results from a benchmark adding 10M random numbers (lower is better):

Benchmark                               Mode  Cnt   Score   Error  Units
CompensatedSummation.newImplementation  avgt    5  12.175 ± 0.413  ms/op
CompensatedSummation.oldImplementation  avgt    5  27.491 ± 2.794  ms/op

Further suggestions

Looking at RealSumTest, I'm not entirely sure what the point of the testDoubleSum() and testDoubleAdd() methods is. It looks to me as if they are only trying to assert that the reference result obtained from summing BigDecimals "does the correct thing". Am I missing something here? If my interpretation is correct, I suggest to delete those tests since they are not related to RealSum at all.

[minnerbe]

Hi @tpietzsch, have you had a chance to look at this PR already? I'm happy to also work on the further suggestions (which are trivial, anyway).

[tpietzsch]

Looks great!

I agree: Those tests can be removed. Also, I would remove the for ( int t = 0; t < 20; ++t ) loop from testAdd(). (Maybe the test was also used for benchmarking, which would also explain the presence of testDoubleSum() and testDoubleAdd() methods).

Could you add your JMH benchmark too? (just benchmarking RealSum, not old vs new implementation)

[minnerbe]

Thanks for the feedback, @tpietzsch! According to your suggestions, I cleaned up the test and added my benchmark.

The benchmark compares RealSum with naive double summation, but I'm happy to remove the latter if you don't want it there. The parameters are taken from the only other benchmark in that directory (FlatCollectionsBenchmark).

Let me know if I can do anything else.

[tpietzsch]

Awesome, thanks!