The GitHub Actions job "Link Validator" on pekko.git/main has failed. Run started by GitHub user pjfanning (triggered by pjfanning).
Head commit for run: 5fd306e27a2ed9a7af2ff396ba10188aa370d8fe / PJ Fanning <[email protected]> perf: resume the ByteStrings fragment hint backward as well as forward (#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". Review turned up a second problem, in the hint itself. `fragmentHint` packs a fragment index and that fragment's start offset into one non-volatile long. JLS 17.7 permits a non-volatile 64-bit field to be read as two 32-bit halves, so the index can come from one write and the start from another. `byteAtUnchecked`'s fast path then tests the offset against the wrong fragment's length, and that test can pass: the call returns a byte from the wrong fragment. Concurrent readers of one `ByteString` are ordinary in Pekko — a broadcast or pub-sub fan-out has several consumers reading the same instance, and every read updates the hint — so this is a wrong-answer bug, not a theoretical one. The packing was introduced to keep the pair together; its comment claimed that made the pair atomic, which packing alone does not do. 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`, and terminates at fragment 0 at the latest, since fragment 0 starts at 0 and `offset >= 0`. The walk costs at most `hintIdx` steps — the same O(fragments) bound per call as the from-zero scan it replaces, but *not* always fewer steps than it: a hint near the end paired with an offset near the start walks further than a from-zero scan would. No distance heuristic guards against that, because it is the random-access pattern that neither strategy serves, while backward *sequential* access — what this branch is for — costs one step whatever the fragment count. `fragmentHint` is now volatile, which is what actually makes a 64-bit read atomic. Volatile is for that atomicity, not for ordering: the value is still only a hint, so a reader that misses another thread's update simply rescans, and `ByteString` is immutable, so a resolved mapping never becomes wrong. The cost lands on the write, which happens only when a lookup misses — once per fragment crossed, not once per byte — while the hit path stays a plain read on x86. The hit test (already direction-agnostic) and the forward resume are unchanged. Result: Backward traversal is O(1) amortised per boundary crossing, matching forward, and no reader can pair one fragment's index with another's start. 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. Making the hint volatile costs nothing measurable outside the one-byte-fragment sequential case. Paired run toggling only the `@volatile` keyword, `-f2 -wi 5 -i 5`, with `manyFragments_map` — which walks the fragments directly and never consults the hint — as an in-run control: | benchmark | plain long | volatile | | --- | --- | --- | | `manyFragments_map` *(control)* | 143,209 ± 8,645 ops/s | 139,764 ± 9,328 ops/s | | `manyFragments_random` | 912 ± 76 ops/s | 902 ± 155 ops/s | | `manyFragments_reverse` | 43,962 ± 9,780 ops/s | 42,858 ± 949 ops/s | | `manyFragments_sequential` | 48,990 ± 6,973 ops/s | 41,100 ± 3,683 ops/s | Random and reverse move by about as much as the control (~2%); only sequential shows a possible cost, and its intervals barely separate. Those 1024 one-byte fragments are the worst case for it, since the hint is then written on every single access — at realistic fragment sizes the write is amortised over the whole fragment. 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. 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, including its longest case, a far-end hint followed by offset 0. - No directional test for the torn read: `fragmentHint` is `private[this]`, so a spec cannot poison it deterministically, and the tear does not reproduce on a 64-bit VM. The multi-threaded block above remains the only cover. - `manyFragments_reverse` / `manyFragments_sequential` from `ByteString_byteAtUnchecked_Benchmark` run before and after on the same machine, plus the paired volatile comparison above; the benchmark file's results comment records both. - `sbt "actor/scalafmtCheckAll" "actor-tests/scalafmtCheckAll" "bench-jmh/scalafmtCheckAll"` — clean - MiMa left to the `Check / Binary Compatibility` job: `resolveFragment` is a `private` method and `fragmentHint` a `private[this]` field on an `@InternalApi` class, and `ByteStrings` serialises through `SerializationProxy`, so the added modifier cannot reach the wire. References: Refs #3463 — extends the fragment hint introduced there. Report URL: https://github.com/apache/pekko/actions/runs/37908464689 With regards, GitHub Actions via GitBox --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
