should we add a test and fix #459 at the same time (you added another copy of this bug in this PR)?

Also, can we add a test to specifically test this path? Like make a scalacheck generator that only generates sparse values, and verify that when we add them, either the count is exact or we have a CMSInstance?

@johnynek Didn't know #459 before. Will fix it in this PR along with some tests.

This is related to #390 (kind of forgot about that, sorry folks). I guess this will supercede that one.

This all looks good, but now looking back at #390, one thing I see that is different is that there was a parameter added to control how big the sparse CMS got, rather than just always doing width * depth (which I guess could use MUCH more than a CMS if the key is a String or BigInt, for instance).

Maybe we should copy that approach of adding a parameter (and perhaps have it default to something very small, like max(width * depth / 100, 10) or something.

@johnynek Is this good to go?

Seems the coverage/coveralls test is taking forever to finish. Is there a way to turn it off or somehow?

@johnynek Is this good to go :)

Sorry my bad, git foo on cmd line broke stuff and closed all of these

@johnynek @DanielleSucher Here you go!

How does this effect our CMS benchmarks?

@ianoc Could you share some more details about the current CMS benchmarks? Not very familiar with it. But given the default maxExactCount is quite small, I believe it won't affect it too much.

The algebird-benchmark project has some benchmarks like
https://github.com/twitter/algebird/blob/develop/algebird-benchmark/src/main/scala/com/twitter/algebird/benchmark/CMSBenchmark.scala

It would be good to run these on develop vs this branch to ensure no regressions.

Even if your code doesn't in theory effect the higher density CMS's, if it for instances blocks any specialization then that would have a large impact everywhere.

@ianoc
On my branch: [success] Total time: 3255 s, completed Aug 10, 2015 1:36:09 PM
On develop: [success] Total time: 3269 s, completed Aug 10, 2015 2:41:02 PM

It's not a super clean comparison, because I'm doing other stuffs on my computer while the benchmarks are running. So the develop even took slightly more time than branch. But I guess it proves they are within the same performance level?

Thats not the benchmark timing? the benchmark should be a matrix of output timing. That looks like the output from sbt? see the docs in the readme at the root or the sbt-jmh plugin docs

Here you go.
My brach:

develop:

That suggests about 4% slow down in all the expensive jobs there right?

I reran my branch's benchmark and compared it with develop. This time, some of them are better whole others are still slower than develop. I guess there are some variances in different benchmark runs.
I think the toDense() def of SparseCMS will add some additional cost, since it goes over all (k,v) items once. But that should not be too much. Any suggestions?

I'm not sure, 4% loss in perf while not huge, is non-trival to me. Can you profile one of consistently 4% slower ones and see where it spends the time?

Are any of them significantly faster than develop?

@ianoc I think the reason of previous slowness is that the MaxExactCount (key-count) set for SparseCMS is too low (at most 10). So in the benchmark easily a SparseCMS need to be converted to a CMSInstance, and therefore each element needs to be added to the new CMS CountTable one by one. That brings the cost. If I set MaxExactCount to 50, my branch has comparable performance as develop.
Do we think key space 50 is a good deal for a SparseCMS key size?

Branch

Develop

That seems reasonable to me, even 50 might wind up being too low. But given we have comparable performance at that level and its a configurable parameter. LGTM.

Any others issues @johnynek & @DanielleSucher ?

@johnynek & @DanielleSucher, any suggestions?

@ianoc Is this good to go? Thanks!

Merged thanks