[PR] OAK-12456: Template.getPropertyTemplate: binary search instead of linear scan [jackrabbit-oak]

["nfsantos (via GitHub)" <gi...@apache.org>]

nfsantos opened a new pull request, #3212:
URL: https://github.com/apache/jackrabbit-oak/pull/3212

   See [OAK-12456](https://issues.apache.org/jira/browse/OAK-12456).
   
   ## Summary
   - `Template.getPropertyTemplate(String)` scanned `properties[]` linearly to find the first entry whose name hash is not smaller than the target hash. The array is already sorted by name hash, so this is replaced by a binary search for the lower bound (new private helper `lowerBoundByHash(int)`).
   - The hash-collision run walk that follows the search is unchanged, so behavior (including tie-breaking on hash collisions) is identical.
   
   ## Motivation
   The method is called on every property read/write of every segment node (`SegmentNodeState.hasProperty/getProperty/...`, `DefaultSegmentWriter.writeNodeUncached`). `writeNodeUncached` does one lookup per property template, so writing a node with n properties costs O(n²) hash comparisons. With binary search it is O(n log n).
   
   ## Benchmark
   JMH microbenchmark (not included in this PR; JMH 1.37, JDK 25), per-lookup cost when sweeping all properties:
   
   | properties | linear scan | binary search | speedup |
   |---|---|---|---|
   | 1 | 3.3 ns | 3.6 ns | ~1x (noise) |
   | 8 | 4.6 ns | 5.0 ns | linear slightly faster |
   | 32 | 9.4 ns | 7.2 ns | 1.3x |
   | 128 | 42.0 ns | 10.6 ns | 4.0x |
   | 1,024 | 346.5 ns | 46.5 ns | 7.5x |
   | 8,192 | 2,790 ns | 83.6 ns | 33x |
   | 40,000 | 13,826 ns | 117 ns | 118x |
   
   Below ~16-32 properties the two are within noise; the crossover is decisive by 128 properties.
   
   In an internal test that commits a node with ~10,000 properties every 15 minutes, write throughput during the large write went from collapsing to ~5% of baseline for 3+ minutes to a ~20-30 second dip, and commit latency dropped from 2.9-6.1 s to under 0.5 s.
   
   ## Tests
   New tests in `TemplateTest` cover no properties, a single property, multiple properties, and a hash collision (`"Aa"` / `"BB"`).
   `mvn test -pl oak-segment-tar -Dtest=TemplateTest` passes (7 tests).
   


-- 
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: oak-dev-unsubscribe@jackrabbit.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

Re: [PR] OAK-12456: Template.getPropertyTemplate: binary search instead of linear scan [jackrabbit-oak]

["joerghoh (via GitHub)" <gi...@apache.org>]

joerghoh commented on PR #3212:
URL: https://github.com/apache/jackrabbit-oak/pull/3212#issuecomment-6126952398

   @nfsantos nice finding. While in general I appreciate every optimization to the ``.getProperty()`` resp ``.hasProperty()`` code path, I am not sure if for the majority of cases (in Sling) the number of properties per node get that large that this optimization plays a relevant role.


-- 
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: oak-dev-unsubscribe@jackrabbit.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org