You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@druid.apache.org by "clintropolis (via GitHub)" <gi...@apache.org> on 2023/02/27 10:05:33 UTC
[GitHub] [druid] clintropolis commented on pull request #13854: add an "incremental" buckets option to FrontCodedIndexed
clintropolis commented on PR #13854:
URL: https://github.com/apache/druid/pull/13854#issuecomment-1446042187
I marked this PR WIP since I'm still working on improving the performance of `get`, which is currently reading every value when seeking a particular value because it was the easiest way to get things working correctly, but I think I can do better by keeping a stack of prefix lengths and buffer positions and working my way backwards to fill the value buffer. Current benchmarks (which really aren't terrible):
```
Benchmark (indexType) (numElements) (numOperations) (width) Mode Cnt Score Error Units
FrontCodedIndexedBenchmark.get generic 10000 10000 16 avgt 5 15.300 ± 0.077 ns/op
FrontCodedIndexedBenchmark.get generic 100000 10000 16 avgt 5 16.860 ± 0.036 ns/op
FrontCodedIndexedBenchmark.get front-coded-4 10000 10000 16 avgt 5 35.312 ± 0.059 ns/op
FrontCodedIndexedBenchmark.get front-coded-4 100000 10000 16 avgt 5 38.921 ± 0.817 ns/op
FrontCodedIndexedBenchmark.get front-coded-16 10000 10000 16 avgt 5 49.355 ± 0.301 ns/op
FrontCodedIndexedBenchmark.get front-coded-16 100000 10000 16 avgt 5 53.588 ± 0.149 ns/op
FrontCodedIndexedBenchmark.get front-coded-incremental-buckets-4 10000 10000 16 avgt 5 44.787 ± 0.825 ns/op
FrontCodedIndexedBenchmark.get front-coded-incremental-buckets-4 100000 10000 16 avgt 5 62.222 ± 7.047 ns/op
FrontCodedIndexedBenchmark.get front-coded-incremental-buckets-16 10000 10000 16 avgt 5 113.985 ± 0.302 ns/op
FrontCodedIndexedBenchmark.get front-coded-incremental-buckets-16 100000 10000 16 avgt 5 143.425 ± 0.562 ns/op
FrontCodedIndexedBenchmark.indexOf generic 10000 10000 16 avgt 5 147.326 ± 0.472 ns/op
FrontCodedIndexedBenchmark.indexOf generic 100000 10000 16 avgt 5 214.154 ± 9.449 ns/op
FrontCodedIndexedBenchmark.indexOf front-coded-4 10000 10000 16 avgt 5 267.560 ± 1.318 ns/op
FrontCodedIndexedBenchmark.indexOf front-coded-4 100000 10000 16 avgt 5 260.044 ± 13.423 ns/op
FrontCodedIndexedBenchmark.indexOf front-coded-16 10000 10000 16 avgt 5 281.611 ± 1.649 ns/op
FrontCodedIndexedBenchmark.indexOf front-coded-16 100000 10000 16 avgt 5 321.547 ± 2.826 ns/op
FrontCodedIndexedBenchmark.indexOf front-coded-incremental-buckets-4 10000 10000 16 avgt 5 265.893 ± 22.296 ns/op
FrontCodedIndexedBenchmark.indexOf front-coded-incremental-buckets-4 100000 10000 16 avgt 5 300.960 ± 27.500 ns/op
FrontCodedIndexedBenchmark.indexOf front-coded-incremental-buckets-16 10000 10000 16 avgt 5 250.964 ± 2.252 ns/op
FrontCodedIndexedBenchmark.indexOf front-coded-incremental-buckets-16 100000 10000 16 avgt 5 317.990 ± 1.194 ns/op
FrontCodedIndexedBenchmark.iterator generic 10000 10000 16 avgt 5 26.014 ± 0.062 ns/op
FrontCodedIndexedBenchmark.iterator generic 100000 10000 16 avgt 5 267.468 ± 1.349 ns/op
FrontCodedIndexedBenchmark.iterator front-coded-4 10000 10000 16 avgt 5 89.531 ± 4.409 ns/op
FrontCodedIndexedBenchmark.iterator front-coded-4 100000 10000 16 avgt 5 1007.466 ± 42.022 ns/op
FrontCodedIndexedBenchmark.iterator front-coded-16 10000 10000 16 avgt 5 63.249 ± 2.705 ns/op
FrontCodedIndexedBenchmark.iterator front-coded-16 100000 10000 16 avgt 5 628.595 ± 35.804 ns/op
FrontCodedIndexedBenchmark.iterator front-coded-incremental-buckets-4 10000 10000 16 avgt 5 81.262 ± 3.462 ns/op
FrontCodedIndexedBenchmark.iterator front-coded-incremental-buckets-4 100000 10000 16 avgt 5 570.711 ± 14.082 ns/op
FrontCodedIndexedBenchmark.iterator front-coded-incremental-buckets-16 10000 10000 16 avgt 5 49.487 ± 20.310 ns/op
FrontCodedIndexedBenchmark.iterator front-coded-incremental-buckets-16 100000 10000 16 avgt 5 509.281 ± 7.377 ns/op
```
sizes:
```
FrontCodedIndexedBenchmark.get:encoded size generic 10000 10000 16 avgt 5 240010.000 bytes
FrontCodedIndexedBenchmark.get:encoded size generic 100000 10000 16 avgt 5 2400010.000 bytes
FrontCodedIndexedBenchmark.get:encoded size front-coded-4 10000 10000 16 avgt 5 169907.000 bytes
FrontCodedIndexedBenchmark.get:encoded size front-coded-4 100000 10000 16 avgt 5 1636647.000 bytes
FrontCodedIndexedBenchmark.get:encoded size front-coded-16 10000 10000 16 avgt 5 164100.000 bytes
FrontCodedIndexedBenchmark.get:encoded size front-coded-16 100000 10000 16 avgt 5 1564982.000 bytes
FrontCodedIndexedBenchmark.get:encoded size front-coded-incremental-buckets-4 10000 10000 16 avgt 5 167426.000 bytes
FrontCodedIndexedBenchmark.get:encoded size front-coded-incremental-buckets-4 100000 10000 16 avgt 5 1612792.000 bytes
FrontCodedIndexedBenchmark.get:encoded size front-coded-incremental-buckets-16 10000 10000 16 avgt 5 156782.000 bytes
FrontCodedIndexedBenchmark.get:encoded size front-coded-incremental-buckets-16 100000 10000 16 avgt 5 1491159.000 bytes
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org