[
https://issues.apache.org/jira/browse/CASSANDRA-13444?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15967288#comment-15967288
]
Fuud commented on CASSANDRA-13444:
----------------------------------
[~jjirsa] please review
> Fast and garbage-free Streaming Histogram
> -----------------------------------------
>
> Key: CASSANDRA-13444
> URL: https://issues.apache.org/jira/browse/CASSANDRA-13444
> Project: Cassandra
> Issue Type: Improvement
> Components: Compaction
> Reporter: Fuud
> Attachments: results.csv, results.xlsx
>
>
> 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.
> Dependends of payload time is reduced up to 90%.
> 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
(v6.3.15#6346)
