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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
