rajat315315 opened a new pull request, #16354:
URL: https://github.com/apache/lucene/pull/16354
### Description
This PR optimizes the `rotateToTree` method in `SimpleTextBKDWriter` to
avoid iterative loop overhead when calculating binary tree partitions.
`rotateToTree` converts a sorted, flat list of leaf block split/start values
into a flat array structure representing a balanced complete binary search tree.
#### The Problem / Bottleneck
To partition nodes for the left subtree (`leftHalf`) at each level of
recursion, the method previously used an iterative `while(true)` loop to
calculate the level-by-level boundaries. This loop ran in O(log(count)) time at
each step of the recursion. Since recursion occurs for every node in the tree,
the overall mathematical partition computation overhead was O(N log N) for N
inner nodes.
#### The Optimization
1. **O(1) Left Subtree Count:** We replaced the iterative `while(true)` loop
with a bitwise constant-time O(1) calculation to determine the exact number of
nodes in the left subtree of a complete binary tree:
```java
int h = Integer.highestOneBit(count);
int halfH = h >>> 1;
int leftHalf = halfH - 1 + Math.min(count - h + 1, halfH);
This leverages the fact that complete binary trees have a mathematically
rigid structure that can be derived in constant time using bit-shifts.
3. Unified Array Copying: We consolidated the System.arraycopy code to
handle both leaf and internal nodes under a single, unified execution path,
reducing code duplication and branch prediction overhead.
4. Dead Code Cleanup: Removed legacy debug output and outdated comments.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
