Jackie-Jiang opened a new pull request, #8878:
URL: https://github.com/apache/pinot/pull/8878
We use binary search to look up a string/byte[] from an immutable
dictionary. Currently we read the whole value before comparing it with the look
up value, which is not needed because we can early terminate after finding the
first different byte. For string dictionary, because UTF-8 bytes preserve the
same order as the code points, we don't need to decode the string before the
comparison.
This PR optimizes it by comparing values byte by byte and early terminate.
For a dictionary with 200K values, we get up to 3x performance:
Before:
```
Benchmark (_maxValueLength) Mode Cnt
Score Error Units
BenchmarkStringDictionary.stringDictionaryRead 8 avgt 5
792.757 ± 33.316 ms/op
BenchmarkStringDictionary.stringDictionaryRead 16 avgt 5
898.899 ± 27.318 ms/op
BenchmarkStringDictionary.stringDictionaryRead 32 avgt 5
1096.918 ± 139.193 ms/op
BenchmarkStringDictionary.stringDictionaryRead 64 avgt 5
1250.916 ± 44.909 ms/op
BenchmarkStringDictionary.stringDictionaryRead 128 avgt 5
1694.212 ± 39.061 ms/op
BenchmarkStringDictionary.stringDictionaryRead 256 avgt 5
2264.023 ± 81.728 ms/op
BenchmarkStringDictionary.stringDictionaryRead 512 avgt 5
3544.365 ± 63.660 ms/op
BenchmarkStringDictionary.stringDictionaryRead 1024 avgt 5
5568.589 ± 112.454 ms/op
```
After:
```
Benchmark (_maxValueLength) Mode Cnt
Score Error Units
BenchmarkStringDictionary.stringDictionaryRead 8 avgt 5
307.097 ± 24.020 ms/op
BenchmarkStringDictionary.stringDictionaryRead 16 avgt 5
344.153 ± 62.155 ms/op
BenchmarkStringDictionary.stringDictionaryRead 32 avgt 5
434.944 ± 10.180 ms/op
BenchmarkStringDictionary.stringDictionaryRead 64 avgt 5
532.598 ± 19.969 ms/op
BenchmarkStringDictionary.stringDictionaryRead 128 avgt 5
623.685 ± 7.924 ms/op
BenchmarkStringDictionary.stringDictionaryRead 256 avgt 5
891.540 ± 33.219 ms/op
BenchmarkStringDictionary.stringDictionaryRead 512 avgt 5
1297.558 ± 16.707 ms/op
BenchmarkStringDictionary.stringDictionaryRead 1024 avgt 5
1938.732 ± 14.882 ms/op
```
--
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]
