Issues with CMS Overflow Detection and Handling

[kylekyle]

If a CMS increment causes an overflow, an error is thrown. There are a few issues with that:

First, the increment has to return UINT32_MAX exactly to trigger the error. A larger-than-one increment might skip right over that value to an overflowed value of, for example, zero. A more reliable way of checking for overflow might be to check that the count returned from the increment is greater than or equal to the amount that you incremented by. That should always be true unless an overflow occurred.

Second, the error is thrown before all the counts in that increment call are committed. That leaves the sketch in an unknown state where some increments may have been applied and others may have not. The increment should finish committing counts before throwing an overflow error.

Finally, throwing an error doesn't tell you which keys are effected since you have no idea which keys will hash to the overflowed counter (and the counter will likely have a low value, causing under-estimation).

If possible, it would be better to simply refuse to increment a counter beyond UINT32_MAX. That way effected keys would always return UINT32_MAX for their counts and receiving a UINT32_MAX count would be a reliable indicator that you've saturated the sketch.

[ashtul]

@kylekyle Thanks for the suggestions.
related #418