apache / apache/lucene

Optimize layout computation in SimpleTextBKDWriter.rotateToTree to O(1) per node

Open
#16,353 0 comments 0 reactions 0 assignees View on GitHub
type:enhancement
Dominant language
Java
Stars
3.6k
Forks
1.4k
Avg merge
2d 11h
Merged PRs (30d)
88

Description

### Description
In `SimpleTextBKDWriter.java`, the `rotateToTree` method is responsible for reorganizing a sorted, flat list of split/start values into a flat array representation of a complete balanced binary search tree during 1D field index finalization.

#### The Problem
Currently, to divide the binary tree and find the boundary/size of the left subtree (`leftHalf`) at each recursive stack frame, `rotateToTree` employs an iterative `while(true)` loop:

```java
int countAtLevel = 1;
int totalCount = 0;
while (true) {
int countLeft = count - totalCount;
if (countLeft <= countAtLevel) {
int lastLeftCount = Math.min(countAtLevel / 2, countLeft);
int leftHalf = (totalCount - 1) / 2 + lastLeftCount;
// ...
}
totalCount += countAtLevel;
countAtLevel *= 2;
}
```
This partition loop runs in O(log(count)) operations for every subsegment. Since this recursion runs for every node in the tree, the overall mathematical overhead to lay out a tree of N nodes is O(NlogN).

This loop is mathematically redundant because a complete binary search tree has a rigid, deterministic shape where the exact size of the left subtree can be computed in constant O(1) time.

### Proposed Optimization
We can completely eliminate the iterative loop by calculating the size of the left subtree (leftHalf) in `O(1)` constant time using simple bitwise shifts and standard bitwise operations:

```
int h = Integer.highestOneBit(count);
int halfH = h >>> 1;
int leftHalf = halfH - 1 + Math.min(count - h + 1, halfH);
```

### Additional Cleanups

- Unified Array Copying: The previous code duplicated the System.arraycopy calls for leaf nodes (count == 1) and internal nodes (count > 1). These can be unified under a single arraycopy step using the newly derived constant-time rootOffset.
- Redundant Comment/Print Cleanup: Remove deprecated debug statements and outdated "TODO: there must be a simpler way?" comments.
- This optimization improves BKD index building efficiency for 1D fields, reduces CPU cycles on the recursion path, and simplifies the codebase.

Ref: https://github.com/apache/lucene/blob/8fe701c0873de37b95fabd4a0feafa2e16f30097/lucene/codecs/src/java/org/apache/lucene/codecs/simpletext/SimpleTextBKDWriter.java#L553

Contributor guide

Open the contributing guide

Research direction

Start in lucene/codecs/src/java/org/apache/lucene/codecs/simpletext/SimpleTextBKDWriter.java at rotateToTree, linked from the issue. Read how the method lays out the complete balanced tree, then verify the constant-time leftHalf calculation and unified arraycopy against the existing behavior. Done means the loop and obsolete debug/TODO text are removed without changing the resulting layout.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
search
Issue type
Refactor
Difficulty
3/5
Estimated time
1-2 days
Activity status
Quiet
Clarity
Clearly specified
Newbie friendliness
72/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.