pjfanning opened a new pull request, #3526:
URL: https://github.com/apache/pekko/pull/3526
### Motivation
`ByteStrings.resolveFragment` resumes the fragment scan from the remembered
fragment only
when the requested offset is *past* it; an offset before the remembered
fragment rescans
the fragment vector from index 0. Byte-wise backward traversal therefore
pays a full
prefix scan at every fragment boundary it crosses — O(fragments²) steps over
the whole
rope. That is the access pattern of `reverseIterator` (the inherited
IndexedSeq
implementation drives `apply` with descending indices) and of
`lastIndexOfSlice`
candidate verification, whose candidate windows move backward through the
rope.
The benchmark comment in `ByteString_byteAtUnchecked_Benchmark` has
documented this
asymmetry since the hint was introduced in #3463: "reverse access does not
benefit
either, since each step lands before the remembered fragment and falls back
to a scan
from the start".
### Modification
When a valid hint exists and the offset is before the remembered fragment's
start,
`resolveFragment` now walks backward from that fragment instead of scanning
from index 0.
The walk keeps the invariant that `seen` is the start of fragment `pos`,
terminates at
fragment 0 at the latest (fragment 0 starts at 0 and `offset >= 0`, so the
branch cannot
even be entered when the hint is fragment 0), and is never longer than the
from-zero scan
it replaces — so backward resume is unconditional, with no distance
heuristic to tune.
The hit test (already direction-agnostic), the forward resume, and the
packed-long
racy-hint design are unchanged; the backward branch writes the same
internally-consistent
packed pair.
### Result
Backward traversal is O(1) amortised per boundary crossing, matching
forward. Measured
with the existing benchmark on one machine (short run, wide error bars,
recorded in the
benchmark file per its convention):
| benchmark | before | after |
| --- | --- | --- |
| `manyFragments_reverse` | 386 ops/s | 39,969 ops/s |
| `manyFragments_sequential` | 43,415 ops/s | 44,624 ops/s |
Reverse access is roughly 100x faster and on par with sequential; sequential
is unchanged
within the noise.
### Tests
- `sbt "actor-tests/testOnly org.apache.pekko.util.ByteStringSpec"` — 244
passed
- The existing `ByteStrings.byteAtUnchecked` block already exercises
backward, alternating
and multi-threaded access (those guard correctness — this change cannot be
discriminated
behaviourally, only by the measurements above, since the old code was
correct but slow).
One new test lands exactly on the first and last byte of every fragment
from a far-end
hint — the boundary arithmetic the backward walk recomputes.
- `manyFragments_reverse` / `manyFragments_sequential` from
`ByteString_byteAtUnchecked_Benchmark` run before and after on the same
machine; the
benchmark file's results comment is updated with both.
- `sbt "actor/scalafmtCheckAll" "actor-tests/scalafmtCheckAll"
"bench-jmh/scalafmtCheckAll"` — clean
- MiMa left to the `Check / Binary Compatibility` job; the change is a
`private` method on
an `@InternalApi` class.
### References
Refs #3463 — extends the fragment hint introduced there.
--
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]
