Lucene SIMD Codec Benchmark and Future Steps
We are happy to share results of our Lucene SIMD research announced earlier.
Ivan integrated https://github.com/lemire/simdcomp as Lucene Codec and we could observe 18% gain on standard Lucene benchmark. Here are the fork, deck, recording from BerlinBuzzwords.
Tech notes
The prototype is limited to postings (IndexOptions.DOCS), so far it doesn’t support freqs, positions, payloads. Thus, full idf-tf scoring is not possible so far.
The heap problem
Currently, the bottleneck of the search performance is the scoring heap. Heap is hard for vectorization, and even hard to compute with regular instructions. Thus, benchmark retrieves only top 10 docs to limit efforts for managing heap.
Here is a profiler snapshot for the default Lucene code, decoding takes more than collecting.
This is hotspots with the SIMD codec, note that collecting is prevailing now and ForUtil takes relatively smaller time for decoding.
Edge cases
There are few special code paths which bypass generic FOR decoding which make it harder to observe vectorization gain. Very dense stopwords postings are encoded as a sequence of increasing numbers with by just specifying length of the sequence (see ForUtil.ALL_VALUES_EQUAL). Thus, we excluded stopwords from the benchmark to better observe the gain in FOR decoding.
Another edge case is shortening postings on high segmentation. FOR compression is applied on blocks, and remaining tail is encoded by vInt. Thus, to observe the gain in FOR decoding, we merge segments to the single one.
Due to the same reason, rare terms with short postings list is not a good use case to show a gain.
Further Plans
Here are some directions which we consider:
- provide codec and benchmark as a separate modules;
- apply SIMD codec for DocValues and Norms - it should improve generic sorting, scoring and faceting. Because ordinals in DocValues are not increasing like postings, https://github.com/lemire/FastPFor should be incorporated;
- complete codec for supporting frequencies, offsets and positions to make it fully functional;
- presumably, SIMD facet component might get some gain from vectorization, however decoding ordinals might not be the biggest problem in faceting, like it’s described here;
- execute binary operations like intersections on compressed data with SIMD instructions https://github.com/lemire/SIMDCompressionAndIntersection;
- native code might access mmapped index files without boundary checks or copying to heap arrays;
- implementing roaring bitmaps might help with dense postings;
Which of of those directions are relevant your challenges? Leave a comment below!
Here are still questions to clarify:
Here are still questions to clarify:
- will critical natives work for Java 9 and further?
- couldn’t it happen that vectorization heuristic by JIT makes explicit SIMD codec redundant?
We’d like to thank all people who contributed their researches and let us to conduct ours.
Lucene
Opinions expressed by DZone contributors are their own.