apache / apache/lucene

large indexing slowdown after increasing HNSW beam width [LUCENE-10128]

Open
#11,165 10 comments 0 reactions 0 assignees View on GitHub
legacy-jira-priority:Major type:task
Dominant language
Java
Stars
3.6k
Forks
1.4k
Avg merge
2d 12h
Merged PRs (30d)
86

Description

Just opening a ticket in case there is anything we could/should do about it. Looking at Mike's nightly benchmarks, I see a large (like 4x) drop in indexing perf with vectors after #11146.

There's some new stuff in the top CPU offenders:
```
PERCENT CPU SAMPLES STACK
19.93% 821395 org.apache.lucene.util.VectorUtil#dotProduct()
13.80% 568786 org.apache.lucene.util.LongHeap#downHeap()
11.06% 455711 org.apache.lucene.codecs.KnnVectorsWriter$VectorValuesMerger$MergerRandomAccess#vectorValue()
9.84% 405678 org.apache.lucene.util.LongHeap#upHeap()
6.72% 276931 java.util.concurrent.atomic.AtomicLong#get()
5.30% 218564 org.apache.lucene.util.LongHeap$2#lessThan()
2.69% 110872 java.util.Arrays#binarySearch0()
2.58% 106294 org.apache.lucene.util.hnsw.HnswGraph#search()
1.90% 78254 org.apache.lucene.util.LongHeap#push()
```

compared to before where the profile stacks looked like this:
```
PERCENT CPU SAMPLES STACK
13.58% 171575 org.apache.lucene.util.VectorUtil#dotProduct()
10.13% 127904 org.apache.lucene.util.LongHeap#downHeap()
9.84% 124257 org.apache.lucene.util.LongHeap#upHeap()
6.26% 79125 java.util.ArrayList#elementData()
4.34% 54831 java.util.Random#nextInt()
3.98% 50255 org.apache.lucene.util.BytesRefHash#equals()
3.69% 46594 org.apache.lucene.util.ByteBlockPool#allocSlice()
2.62% 33118 org.apache.lucene.util.BytesRefHash#findHash()
2.24% 28275 org.apache.lucene.analysis.standard.StandardTokenizerImpl#getNextToken()
2.14% 27033 org.apache.lucene.analysis.standard.StandardTokenizer#incrementToken()
```

At a glance, it seems to me that although some perf differences should be expected, merging itself may have become more costly. Maybe there is some stuff we can optimize about it.

![Screen_Shot_2021-09-28_at_09.10.15.png](https://apache.github.io/lucene-jira-archive/attachments/LUCENE-10128/Screen_Shot_2021-09-28_at_09.10.15.png)

---
Migrated from [LUCENE-10128](https://issues.apache.org/jira/browse/LUCENE-10128) by Robert Muir (@rmuir), updated Oct 02 2021
Attachments: [LUCENE-10128_remove_sparse_fixed_bitset_reflection.patch](https://apache.github.io/lucene-jira-archive/attachments/LUCENE-10128/LUCENE-10128_remove_sparse_fixed_bitset_reflection.patch), [Screen_Shot_2021-09-28_at_09.10.15.png](https://apache.github.io/lucene-jira-archive/attachments/LUCENE-10128/Screen_Shot_2021-09-28_at_09.10.15.png)

Contributor guide

Open the contributing guide

Research direction

Start by reproducing the vector indexing benchmark before and after #11146, then inspect the profiling hotspots in HnswGraph#search, VectorValuesMerger, VectorUtil, and LongHeap. Compare the attached profiles and determine whether merging accounts for the regression. Done means identifying and validating an optimization that improves the reported indexing slowdown.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
search
Issue type
Bug
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.