Can we optimize BytesRefHash? [LUCENE-10572]
- Dominant language
- Java
- Stars
- 3.6k
- Forks
- 1.4k
- Avg merge
- 2d 11h
- Merged PRs (30d)
- 88
Description
I was poking around in our nightly benchmarks () and noticed in the JFR profiling that the hottest method is this:
```
PERCENT CPU SAMPLES STACK
9.28% 53848 org.apache.lucene.util.BytesRefHash#equals()
at org.apache.lucene.util.BytesRefHash#findHash()
at org.apache.lucene.util.BytesRefHash#add()
at org.apache.lucene.index.TermsHashPerField#add()
at org.apache.lucene.index.IndexingChain$PerField#invert()
at org.apache.lucene.index.IndexingChain#processField()
at org.apache.lucene.index.IndexingChain#processDocument()
at org.apache.lucene.index.DocumentsWriterPerThread#updateDocuments()
```
This is kinda crazy – comparing if the term to be inserted into the inverted index hash equals the term already added to `BytesRefHash` is the hottest method during nightly benchmarks.
Discussing offline with @rmuir and @jpountz they noticed a few questionable things about our current implementation:
- Why are we using a 1 or 2 byte `vInt` to encode the length of the inserted term into the hash? Let's just use two bytes always, since IW limits term length to 32 K (< 64K that an unsigned short can cover)
- Why are we doing byte swapping in this deep hotspot using `VarHandles` (BitUtil.VH_BE_SHORT.get)
- Is it possible our growth strategy for `BytesRefHash` (on rehash) is not aggressive enough? Or the initial sizing of the hash is too small?
- Maybe `MurmurHash` is not great (causing too many conflicts, and too many `equals` calls as a result?) – `Fnv` and `xxhash` are possible "upgrades"?
- If we stick with `MurmurHash`}, why are we using the 32 bit version (`murmurhash3_x86_32`})?
- Are we using the JVM's intrinsics to compare multiple bytes in a single SIMD instruction (@rmuir is quite sure we are indeed)?
- @jpountz suggested maybe the hash insert is simply memory bound
- `TermsHashPerField.writeByte` is also depressingly slow (\~5% of total CPU cost)
I pulled these observations from a recent (5/6/22) profiler output:
Maybe we can improve our performance on this crazy hotspot?
Or maybe this is a "healthy" hotspot and we should leave it be!
---
Migrated from [LUCENE-10572](https://issues.apache.org/jira/browse/LUCENE-10572) by Michael McCandless (@mikemccand), updated May 18 2022
Attachments: [Screen Shot 2022-05-16 at 10.28.22 AM.png](https://apache.github.io/lucene-jira-archive/attachments/LUCENE-10572/Screen%20Shot%202022-05-16%20at%2010.28.22%20AM.png)
Pull requests: https://github.com/apache/lucene/pull/888
Contributor guide
Research direction
Start with org.apache.lucene.util.BytesRefHash#equals, findHash, and add, then trace the cited TermsHashPerField and indexing call path. Review the nightly benchmark and JFR output, including the linked pull request, before evaluating the listed hashing, sizing, and memory-cost questions. Done requires a measured performance conclusion or improvement for the reported hotspot.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- java
- Domain
- search
- Issue type
- Refactor
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 20/100