apache / apache/lucene

Make ForUtil Vectorized

Open
#12,396 53 comments 0 reactions 0 assignees Claimed by @tang-hi View on GitHub
type:enhancement
Dominant language
Java
Stars
3.6k
Forks
1.4k
Avg merge
2d 11h
Merged PRs (30d)
88

Description

### Description

Since the introduction of Vector API into Lucene via #12311, I have found it to be an interesting tool. As a result, I have attempted to use it to rewrite the [ForUtil.java](lucene/core/src/java/org/apache/lucene/codecs/lucene90/ForUtil.java) file. Initially, I attempted to port [simdcomp](https://github.com/lemire/simdcomp/blob/0c900190bbc0970f4342f2ea778564c95ca725cf/src/simdbitpacking.c) and implement pack and unpack for bitPerValue values that were less than or equal to 8. The results of my efforts can be seen below.
| Benchmark | Mode | Cnt | Score | Error | Units |
|-----------------------------|------|-------------|----------------|---------------|-------|
| VectorizeBenchmark.decode1 | thrpt | 15 | 58293945.447 | ± 1524549.587 | ops/s |
| VectorizeBenchmark.decode2 | thrpt | 15 | 55598229.538 | ± 4516920.135 | ops/s |
| VectorizeBenchmark.decode3 | thrpt | 15 | 57163871.965 | ± 1566246.490 | ops/s |
| VectorizeBenchmark.decode4 | thrpt | 15 | 55128874.528 | ± 4752397.170 | ops/s |
| VectorizeBenchmark.decode5 | thrpt | 15 | 53822335.729 | ± 4599217.489 | ops/s |
| VectorizeBenchmark.decode6 | thrpt | 15 | 48155246.120 | ± 7519360.551 | ops/s |
| VectorizeBenchmark.decode7 | thrpt | 15 | 50253799.192 | ± 820075.648 | ops/s |
| VectorizeBenchmark.decode8 | thrpt | 15 | 68849728.856 | ± 1818468.973 | ops/s |
| VectorizeBenchmark.encode1 | thrpt | 15 | 33998510.772 | ± 2924618.992 | ops/s |
| VectorizeBenchmark.encode2 | thrpt | 15 | 43238190.552 | ± 810373.966 | ops/s |
| VectorizeBenchmark.encode3 | thrpt | 15 | 36613553.485 | ± 483115.838 | ops/s |
| VectorizeBenchmark.encode4 | thrpt | 15 | 45675726.831 | ± 1081153.655 | ops/s |
| VectorizeBenchmark.encode5 | thrpt | 15 | 33591855.278 | ± 1084009.112 | ops/s |
| VectorizeBenchmark.encode6 | thrpt | 15 | 36110726.127 | ± 767075.709 | ops/s |
| VectorizeBenchmark.encode7 | thrpt | 15 | 34754339.379 | ± 275025.123 | ops/s |
| VectorizeBenchmark.encode8 | thrpt | 15 | 55075742.358 | ± 991165.320 | ops/s |
| VectorizeBenchmark.vectorizedDecode1 | thrpt | 15 | 43878020.796 | ± 7148545.623 | ops/s |
| VectorizeBenchmark.vectorizedDecode2 | thrpt | 15 | 103091446.773 | ± 44115190.011 | ops/s |
| VectorizeBenchmark.vectorizedDecode3 | thrpt | 15 | 83168059.373 | ± 24930903.852 | ops/s |
| VectorizeBenchmark.vectorizedDecode4 | thrpt | 15 | 63156089.355 | ± 15039408.293 | ops/s |
| VectorizeBenchmark.vectorizedDecode5 | thrpt | 15 | 96567546.695 | ± 37142784.493 | ops/s |
| VectorizeBenchmark.vectorizedDecode6 | thrpt | 15 | 73897063.180 | ± 11549757.437 | ops/s |
| VectorizeBenchmark.vectorizedDecode7 | thrpt | 15 | 79716185.567 | ± 29990852.039 | ops/s |
| VectorizeBenchmark.vectorizedDecode8 | thrpt | 15 | 92621676.617 | ± 29702056.667 | ops/s |
| VectorizeBenchmark.vectorizedEncode1 | thrpt | 15 | 51140300.852 | ± 139758.385 | ops/s |
| VectorizeBenchmark.vectorizedEncode2 | thrpt | 15 | 82646100.574 | ± 1289600.954 | ops/s |
| VectorizeBenchmark.vectorizedEncode3 | thrpt | 15 | 88124485.953 | ± 742170.198 | ops/s |
| VectorizeBenchmark.vectorizedEncode4 | thrpt | 15 | 91029285.467 | ± 5594858.437 | ops/s |
| VectorizeBenchmark.vectorizedEncode5 | thrpt | 15 | 96843051.648 | ± 8024430.836 | ops/s |
| VectorizeBenchmark.vectorizedEncode6 | thrpt | 15 | 98596724.128 | ± 10068466.227 | ops/s |
| VectorizeBenchmark.vectorizedEncode7 | thrpt | 15 | 85885746.715 | ± 6031740.563 | ops/s |
| VectorizeBenchmark.vectorizedEncode8 | thrpt | 15 | 117139889.194 | ± 8721517.095 | ops/s |

However, I noticed that the compression format used in [ForUtil.java](lucene/core/src/java/org/apache/lucene/codecs/lucene90/ForUtil.java) was different. It employed some tricks to speed up the process, such as simd. Therefore, I attempted to vectorize it while maintaining the compression format. The results can be seen below.
| Benchmark | Mode | Cnt | Score | Error | Units |
|-----------------------------|------|-----|----------------|----------------|-------|
| Benchmark.encode1 | thrpt | 15 | 38017254.040 | ± 3905466.628 | ops/s |
| Benchmark.encode2 | thrpt | 15 | 45170109.395 | ± 1539203.478 | ops/s |
| Benchmark.encode3 | thrpt | 15 | 38757256.653 | ± 1044709.221 | ops/s |
| Benchmark.encode4 | thrpt | 15 | 49307206.891 | ± 799168.007 | ops/s |
| Benchmark.encode5 | thrpt | 15 | 35130626.548 | ± 792210.817 | ops/s |
| Benchmark.encode6 | thrpt | 15 | 38326892.073 | ± 981865.963 | ops/s |
| Benchmark.encode7 | thrpt | 15 | 37372342.721 | ± 1177478.683 | ops/s |
| Benchmark.encode8 | thrpt | 15 | 60757390.416 | ± 458876.638 | ops/s |
| Benchmark.vectorizedEncode1 | thrpt | 15 | 56413094.655 | ± 435917.201 | ops/s |
| Benchmark.vectorizedEncode2 | thrpt | 15 | 88770400.646 | ± 11183716.176 | ops/s |
| Benchmark.vectorizedEncode3 | thrpt | 15 | 39932842.378 | ± 2366921.921 | ops/s |
| Benchmark.vectorizedEncode4 | thrpt | 15 | 85888128.739 | ± 5499354.172 | ops/s |
| Benchmark.vectorizedEncode5 | thrpt | 15 | 34402027.732 | ± 1414839.159 | ops/s |
| Benchmark.vectorizedEncode6 | thrpt | 15 | 35794303.501 | ± 782940.005 | ops/s |
| Benchmark.vectorizedEncode7 | thrpt | 15 | 33845690.180 | ± 2586648.353 | ops/s |
| Benchmark.vectorizedEncode8 | thrpt | 15 | 97914288.675 | ± 8971857.035 | ops/s |

I have only implemented bitPerValue values of 1, 2, 4, and 8. I am curious if it is possible to change the compression format. Additionally, do you have any best practices for integrating vectorized code into Lucene? Any suggestions would be appreciated.

Currently, I am working on my own [repo](https://github.com/tang-hi/forutil). However, the code is still in a rough state and lacks documentation.

Contributor guide

Open the contributing guide

Research direction

Start by reading lucene/core/src/java/org/apache/lucene/codecs/lucene90/ForUtil.java, then compare the proposed approach in the linked pull request #12417 with the author's forutil repository. The issue does not define an accepted compression format, supported bit-per-value cases, or completion criteria, so those decisions must be settled before implementation.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
backend, performance
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
20/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.