clearspring/stream-lib — pull request #35 by cykl (2013-06-02 20:26:46+00:00)
Title: Faster hll

I'm using HLL in a batch analytics application which does a load of merges. Hprof showed that this operation is quite slow and is our current bottleneck.

This pull request updates RegisterSet and HLL(+) to improve the performance of `merge` and `offer*`. It removes extra-calls to Math.floor in RegisterSet, and add `merge` and `updateIfGreater` methods. The `merge` method allows to have an easily predictable and efficient memory access pattern compared to the previous external version.

`HLL.merge` is now almost 10 times faster and `offer` 20%. This patch set does not change the values returned by `getBits` or the `M` array. It is 100% backward compatible.

My benchmark and its results are available in [this gist](https://gist.github.com/cykl/5694413)

I believe that it would be possible to write a much faster implementation if we are allowed to change the `M` array. It implies that we have to break the serialization format compatibility or to write a wrapper to ensure compatibility. I had like to hear your input and thoughts on that. I plan to write a POC to see how much faster it could be.