cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "ASF GitHub Bot (JIRA)" <>
Subject [jira] [Commented] (CASSANDRA-13444) Fast and garbage-free Streaming Histogram
Date Thu, 13 Apr 2017 08:31:41 GMT


ASF GitHub Bot commented on CASSANDRA-13444:

GitHub user Fuud opened a pull request:

    Fast streaming hist

    PR for CASSANDRA-13444

You can merge this pull request into a Git repository by running:

    $ git pull fast-streaming-hist

Alternatively you can review and apply these changes as the patch at:

To close this pull request, make a commit to your master/trunk branch
with (at least) the following in the commit message:

    This closes #106
commit 3d7ce27aa9bc28c792502ffa5732e5e606e305b9
Author: Fedor Bobin <>
Date:   2017-04-12T05:10:03Z

    Benchmark refactoring

commit 5a87a7f3d08c582b690e7e6718a07e3b843cc108
Author: Fedor Bobin <>
Date:   2017-04-12T05:40:20Z

    computeIfAbsent instead of get->put chain

commit 64438350d640489bd8891305709253c7ee0d9fb6
Author: Fedor Bobin <>
Date:   2017-04-12T06:09:45Z

    fast streaming histogram: round on merge

commit d99ea1afcc7791637873d4cd71afe6d08fb69f01
Author: Fedor Bobin <>
Date:   2017-04-12T06:40:56Z

    fast stream histogram: explicitly same type everywhere: Integer instead of Number{Integer,

commit 2f7c3ac64305c7e792ff910d4e424a3f4aff7d15
Author: Fedor Bobin <>
Date:   2017-04-12T07:14:03Z

    Use Set with distances to eliminate full-scan when merging

commit c6ea73429dcc1f4efd0409709241a79d8442e7eb
Author: Fedor Bobin <>
Date:   2017-04-12T10:19:15Z

    fast stream histogram: Use sorted arrays instead of Sets.

commit 95c238ccaadc27f51b29a03ee85e301c6ebcd4c1
Author: Fedor Bobin <>
Date:   2017-04-13T07:17:26Z

    fast stream histogram: Use open address primitive map as spool.


> Fast and garbage-free Streaming Histogram
> -----------------------------------------
>                 Key: CASSANDRA-13444
>                 URL:
>             Project: Cassandra
>          Issue Type: Improvement
>          Components: Compaction
>            Reporter: Fuud
> StreamingHistogram is cause of high cpu usage and GC pressure.
> It was improved at CASSANDRA-13038 by introducing intermediate buffer to try accumulate
different values into the big map before merging them into smaller one.
> But there was not enought for TTL's distributed within large time. Rounding (also introduced
at 13038) can help but it reduce histogram precision specially in case where TTL's does not
distributed uniformly.
> There are several improvements that can help to reduce cpu and gc usage. Them all included
in the pool-request as separate revisions thus you can test them independently.
> Improvements list:
> # Use Map.computeIfAbsent instead of get->checkIfNull->put chain. In this way "add-or-accumulate"
operation takes one map operation instead of two. But this method (default-defined in interface
Map) is overriden in HashMap but not in TreeMap. Thus I changed spool type to HashMap.
> # As we round incoming values to _roundSeconds_ we can also round value on merge. It
will enlarge hit rate for bin operations.
> # Because we inserted only integers into Histogram and rounding values to integers we
can use *int* type everywhere.
> # Histogram takes huge amount of time merging values. In merge method largest amount
of time taken by finding nearest points. It can be eliminated by holding additional TreeSet
with differences, sorted from smalest to greatest.
> # Because we know max size of _bin_ and _differences_ maps we can replace them with sorted
arrays. Search can be done with _Arrays.binarySearch_ and insertion/deletions can be done
by _System.arraycopy_. Also it helps to merge some operations into one.
> # Because spool map is also limited we can replace it with open address primitive map.
It's finaly reduce allocation rate to zero.
> You can see gain given by each step in the attached file. First number is time for one
benchmark invocation and second - is allocation rate in Mb per operation.
> Overall gain:
> |.|.|Payload/SpoolSize|.|.|.|% from original
> |.|.|.|original|.|optimized|
> |.|.|secondInMonth/0|.|.|.|
> |time ms/op|.|.|10747,684|.|5545,063|51,6
> |allocation Mb/op|.|.|2441,38858|.|0,002105713|0
> |.|.|.|.|.|.|
> |.|.|secondInMonth/1000|.|.|.|
> |time ms/op|.|.|8988,578|.|5791,179|64,4
> |allocation Mb/op|.|.|2440,951141|.|0,017715454|0
> |.|.|.|.|.|.|
> |.|.|secondInMonth/10000|.|.|.|
> |time ms/op|.|.|10711,671|.|5765,243|53,8
> |allocation Mb/op|.|.|2437,022537|.|0,264083862|0
> |.|.|.|.|.|.|
> |.|.|secondInMonth/100000|.|.|.|
> |time ms/op|.|.|13001,841|.|5638,069|43,4
> |allocation Mb/op|.|.|2396,947113|.|2,003662109|0,1
> |.|.|.|.|.|.|
> |.|.|secondInDay/0|.|.|.|
> |time ms/op|.|.|10381,833|.|5497,804|53
> |allocation Mb/op|.|.|2441,166107|.|0,002105713|0
> |.|.|.|.|.|.|
> |.|.|secondInDay/1000|.|.|.|
> |time ms/op|.|.|8522,157|.|5929,871|69,6
> |allocation Mb/op|.|.|1973,112381|.|0,017715454|0
> |.|.|.|.|.|.|
> |.|.|secondInDay/10000|.|.|.|
> |time ms/op|.|.|10234,978|.|5480,077|53,5
> |allocation Mb/op|.|.|2306,057404|.|0,262969971|0
> |.|.|.|.|.|.|
> |.|.|secondInDay/100000|.|.|.|
> |time ms/op|.|.|2971,178|.|139,079|4,7
> |allocation Mb/op|.|.|172,1276245|.|2,001721191|1,2
> |.|.|.|.|.|.|
> |.|.|secondIn3Hour/0|.|.|.|
> |time ms/op|.|.|10663,123|.|5605,672|52,6
> |allocation Mb/op|.|.|2439,456818|.|0,002105713|0
> |.|.|.|.|.|.|
> |.|.|secondIn3Hour/1000|.|.|.|
> |time ms/op|.|.|9029,788|.|5838,618|64,7
> |allocation Mb/op|.|.|2331,839249|.|0,180664063|0
> |.|.|.|.|.|.|
> |.|.|secondIn3Hour/10000|.|.|.|
> |time ms/op|.|.|4862,409|.|89,001|1,8
> |allocation Mb/op|.|.|965,4871887|.|0,251711652|0
> |.|.|.|.|.|.|
> |.|.|secondIn3Hour/100000|.|.|.|
> |time ms/op|.|.|1484,454|.|95,044|6,4
> |allocation Mb/op|.|.|153,2464722|.|2,001712809|1,3
> |.|.|.|.|.|.|
> |.|.|secondInMin/0|.|.|.|
> |time ms/op|.|.|875,118|.|424,11|48,5
> |allocation Mb/op|.|.|610,3554993|.|0,001776123|0
> |.|.|.|.|.|.|
> |.|.|secondInMin/1000|.|.|.|
> |time ms/op|.|.|568,7|.|84,208|14,8
> |allocation Mb/op|.|.|0,007598114|.|0,01810023|238,2
> |.|.|.|.|.|.|
> |.|.|secondInMin/10000|.|.|.|
> |time ms/op|.|.|573,595|.|83,862|14,6
> |allocation Mb/op|.|.|0,007597351|.|0,252473872|3323,2
> |.|.|.|.|.|.|
> |.|.|secondInMin/100000|.|.|.|
> |time ms/op|.|.|584,457|.|86,554|14,8
> |allocation Mb/op|.|.|0,007595825|.|2,002506106|26363,2
> You may notice increased allocation rate for secondInMin payload. It is because test
use small values and Integer.valueOf use cache for them. In real case where incoming values
will be timestamps this cache will not work. Also constant memory 2 Mb per StreamingHistogram
is quite good.

This message was sent by Atlassian JIRA

View raw message