This is an automated email from the ASF dual-hosted git repository.
pjfanning pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/pekko.git
The following commit(s) were added to refs/heads/main by this push:
new 3d32394c3a perf: faster ByteString equality and fragment lookup (#3463)
3d32394c3a is described below
commit 3d32394c3a9c5fd922157cf7e868a4a5763cda55
Author: PJ Fanning <[email protected]>
AuthorDate: Fri Aug 28 07:31:04 2026 +0100
perf: faster ByteString equality and fragment lookup (#3463)
* perf: compare ByteString bytes directly in equals
ByteString inherited equality from Seq, which compares element by element
through `iterator` and boxes every Byte. Comparing two 64KB ByteStrings
was around 60x slower than java.util.Arrays.equals on the same bytes.
Override `equals` to compare the underlying arrays. The comparison is
driven from whichever side is a single compacted array so it can reuse
the existing SWAR-based `matchesAt`; when neither side is, the new
`compareBytesTo` walks the fragments in place rather than compacting.
Two fragmented ByteStrings are compared with independent cursors so
neither side has to re-locate a fragment for each run of bytes.
`ByteStrings` also gains a `matchesAt` override, so the existing
`indexOfSlice`/`startsWith` paths no longer fall back to the per-byte
implementation inherited from ByteString.
`hashCode` is unchanged: it is content based and independent of the
internal layout, so it continues to agree with the new `equals`.
Tests cover every internal representation (compacted, sliced,
two-fragment and multi-fragment) against each other, the hashCode
agreement, content differing in the first and last byte, differing
lengths, equality with other Seq[Byte] implementations, and Set
membership across representations.
* perf: memoise the fragment lookup in ByteStrings
`ByteStrings.apply` resolved an index by scanning the fragment vector
from the start on every call, and `byteAtUnchecked` was not overridden at
all, so it fell back to `apply`. Any operation that walks a fragmented
ByteString by index was therefore quadratic in the number of fragments:
traversing a 1024-fragment ByteString took around 410ms, against 3ms
once the lookup is memoised.
`byteAtUnchecked` now remembers the fragment resolved by the previous
call. Sequential access -- the dominant pattern -- either stays inside
that fragment or resumes the scan from it. `apply` becomes a bounds check
in front of `byteAtUnchecked`, so both share the memoised lookup and the
duplicated scan is gone.
The remembered triple is held in a single immutable object and published
by one reference write. Readers take a single reference and can never
observe the start of one fragment paired with the index of another, which
three separate int fields would allow. The field is deliberately not
volatile: it is 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.
This also speeds up the artery TCP framing path: `ByteStringParser`'s
`ByteReader` reads sequentially with `apply`, and the `read*Unchecked`
helpers that `ByteStrings` does not override are built from `apply`.
Tests cover forward, backward, repeated and alternating access, the
agreement with `toArray` and the iterator, out of range indices, and
concurrent reads from several threads.
* perf: pack the ByteStrings fragment hint into a long
The memoised fragment lookup held its (index, start, end) triple in a
small object, allocating a fresh one every time the resolved fragment
changed. Traversing a ByteString of 1024 single-byte fragments allocated
24 bytes per read; even with 64-byte fragments it was 24 bytes per
fragment crossing.
Pack the index and start offset into a single long field instead: index
in the high 32 bits, start in the low 32. A single read still yields a
consistent pair, so a reader can never combine the index of one fragment
with the start of another, which separate int fields would allow. The end
offset is no longer stored and is recomputed as start + fragment.length,
a cheap array read on the miss path only.
Allocation on the traversal path drops to zero. Throughput is unchanged:
the two forms measure within run-to-run noise of each other, so this is
about allocation rather than speed.
---
.../org/apache/pekko/util/ByteStringSpec.scala | 198 +++++++++++++++++++++
.../scala/org/apache/pekko/util/ByteString.scala | 195 ++++++++++++++++++--
.../ByteString_byteAtUnchecked_Benchmark.scala | 114 ++++++++++++
.../pekko/util/ByteString_equals_Benchmark.scala | 110 ++++++++++++
4 files changed, 606 insertions(+), 11 deletions(-)
diff --git
a/actor-tests/src/test/scala/org/apache/pekko/util/ByteStringSpec.scala
b/actor-tests/src/test/scala/org/apache/pekko/util/ByteStringSpec.scala
index 70d3e3e06e..56e5c6a46d 100644
--- a/actor-tests/src/test/scala/org/apache/pekko/util/ByteStringSpec.scala
+++ b/actor-tests/src/test/scala/org/apache/pekko/util/ByteStringSpec.scala
@@ -1744,6 +1744,204 @@ class ByteStringSpec extends AnyWordSpec with Matchers
with Checkers {
}
}
+ "ByteString equality" must {
+ // Builds the same content in every internal representation: compacted
(ByteString1C),
+ // a slice of a larger array (ByteString1), a two-fragment pair
(ByteString2) and a
+ // many-fragment rope (ByteStrings). equals must not depend on which one
it is handed.
+ def allRepresentations(bytes: Array[Byte]): List[(String, ByteString)] = {
+ val n = bytes.length
+ val whole = ByteString(bytes)
+ var result = List("compact" -> whole.compact, "whole" -> whole)
+ if (n >= 1) {
+ val padded = ByteString(Array[Byte](0x7F, 0x7F)) ++ whole ++
ByteString(Array[Byte](0x7F))
+ result ::= "sliced" -> padded.drop(2).dropRight(1)
+ result ::= "per-byte rope" -> bytes.map(b =>
ByteString(Array(b))).reduce(_ ++ _)
+ }
+ if (n >= 2) result ::= "two fragments" -> (ByteString(bytes.take(1)) ++
ByteString(bytes.drop(1)))
+ if (n >= 4) {
+ val q = n / 4
+ result ::= "four fragments" -> (ByteString(bytes.slice(0, q)) ++
ByteString(bytes.slice(q, 2 * q)) ++
+ ByteString(bytes.slice(2 * q, 3 * q)) ++ ByteString(bytes.slice(3 * q,
n)))
+ result ::= "uneven fragments" -> (ByteString(bytes.slice(0, 1)) ++
ByteString(bytes.slice(1, 3)) ++
+ ByteString(bytes.slice(3, n)))
+ }
+ result
+ }
+
+ val sizes = List(0, 1, 2, 3, 7, 8, 9, 15, 16, 17, 31, 32, 33, 64, 127,
128, 1000)
+
+ def sample(n: Int): Array[Byte] = Array.tabulate[Byte](n)(i => ((i * 31 +
7) % 251).toByte)
+
+ "hold between all internal representations of the same content" in {
+ for {
+ n <- sizes
+ bytes = sample(n)
+ (leftName, left) <- allRepresentations(bytes)
+ (rightName, right) <- allRepresentations(bytes)
+ } withClue(s"size $n, $leftName vs $rightName: ") {
+ left should ===(right)
+ right should ===(left)
+ }
+ }
+
+ "agree with hashCode for all internal representations" in {
+ for {
+ n <- sizes
+ bytes = sample(n)
+ (leftName, left) <- allRepresentations(bytes)
+ (rightName, right) <- allRepresentations(bytes)
+ } withClue(s"size $n, $leftName vs $rightName: ") {
+ left.hashCode should ===(right.hashCode)
+ }
+ }
+
+ "distinguish content that differs in the first byte" in {
+ for (n <- sizes if n > 0) {
+ val bytes = sample(n)
+ val differing = bytes.clone()
+ differing(0) = (differing(0) ^ 0xFF).toByte
+ for {
+ (leftName, left) <- allRepresentations(bytes)
+ (rightName, right) <- allRepresentations(differing)
+ } withClue(s"size $n, $leftName vs $rightName: ") {
+ left should !==(right)
+ right should !==(left)
+ }
+ }
+ }
+
+ "distinguish content that differs in the last byte" in {
+ for (n <- sizes if n > 0) {
+ val bytes = sample(n)
+ val differing = bytes.clone()
+ differing(n - 1) = (differing(n - 1) ^ 0xFF).toByte
+ for {
+ (leftName, left) <- allRepresentations(bytes)
+ (rightName, right) <- allRepresentations(differing)
+ } withClue(s"size $n, $leftName vs $rightName: ") {
+ left should !==(right)
+ }
+ }
+ }
+
+ "distinguish content of different lengths" in {
+ for (n <- sizes) {
+ val bytes = sample(n)
+ val longer = ByteString(bytes :+ 1.toByte)
+ for ((name, bs) <- allRepresentations(bytes)) withClue(s"size $n,
$name: ") {
+ bs should !==(longer)
+ longer should !==(bs)
+ }
+ }
+ }
+
+ "hold against other Seq[Byte] implementations" in {
+ for {
+ n <- sizes
+ bytes = sample(n)
+ (name, bs) <- allRepresentations(bytes)
+ } withClue(s"size $n, $name: ") {
+ bs should ===(bytes.toVector)
+ bytes.toVector should ===(bs)
+ bs should ===(bytes.toList)
+ bs.hashCode should ===(bytes.toVector.hashCode)
+ }
+ }
+
+ "not consider a ByteString equal to a non-Seq value" in {
+ val bs = ByteString(sample(8))
+ bs.equals("not a ByteString") should ===(false)
+ bs.equals(null) should ===(false)
+ bs.equals(42) should ===(false)
+ }
+
+ "let equal ByteStrings of different representations share a Set entry" in {
+ for (n <- sizes if n > 0) {
+ val representations = allRepresentations(sample(n)).map(_._2)
+ withClue(s"size $n: ")(representations.toSet should have size 1)
+ }
+ }
+ }
+
+ "ByteStrings.byteAtUnchecked" must {
+ // byteAtUnchecked memoises the fragment resolved by the previous call, so
these exercise
+ // forward, backward and random access as well as the transitions between
them.
+ val fragmentLengths = List(1, 5, 2, 8, 1, 16, 3)
+ val expected: Array[Byte] = {
+ var next = 0
+ fragmentLengths.flatMap { len =>
+ val chunk = Array.tabulate[Byte](len)(i => (next + i).toByte)
+ next += len
+ chunk
+ }.toArray
+ }
+ val rope: ByteString = fragmentLengths
+ .foldLeft((ByteString.empty, 0)) { case ((acc, offset), len) =>
+ (acc ++ ByteString(expected.slice(offset, offset + len)), offset + len)
+ }
+ ._1
+
+ "return the right byte when read forwards" in {
+ for (i <- expected.indices) withClue(s"index $i: ")(rope(i) should
===(expected(i)))
+ }
+
+ "return the right byte when read backwards" in {
+ for (i <- expected.indices.reverse) withClue(s"index $i: ")(rope(i)
should ===(expected(i)))
+ }
+
+ "return the right byte for repeated reads of the same index" in {
+ for (i <- expected.indices) {
+ rope(i) should ===(expected(i))
+ rope(i) should ===(expected(i))
+ }
+ }
+
+ "return the right byte when alternating between the ends" in {
+ val last = expected.length - 1
+ for (i <- 0 to last / 2) {
+ rope(i) should ===(expected(i))
+ rope(last - i) should ===(expected(last - i))
+ }
+ }
+
+ "produce the same bytes as toArray and the iterator" in {
+ rope.toArray should ===(expected)
+ rope.iterator.toArray should ===(expected)
+ }
+
+ "still reject out of range indices" in {
+ an[IndexOutOfBoundsException] should be thrownBy rope(-1)
+ an[IndexOutOfBoundsException] should be thrownBy rope(expected.length)
+ }
+
+ "return the right byte when read concurrently from several threads" in {
+ // The memoised fragment is shared mutable state read without
synchronisation, so a torn
+ // or stale value must never produce a wrong byte.
+ val threads = 8
+ val readsPerThread = 20000
+ val mismatches = new java.util.concurrent.atomic.AtomicInteger(0)
+ val workers = (0 until threads).map { t =>
+ val thread = new Thread(() => {
+ val random = new scala.util.Random(t)
+ var read = 0
+ while (read < readsPerThread) {
+ val i = t % 3 match {
+ case 0 => random.nextInt(expected.length)
+ case 1 => read % expected.length
+ case _ => expected.length - 1 - (read % expected.length)
+ }
+ if (rope(i) != expected(i)) mismatches.incrementAndGet()
+ read += 1
+ }
+ })
+ thread.start()
+ thread
+ }
+ workers.foreach(_.join())
+ mismatches.get should ===(0)
+ }
+ }
+
"A ByteString" must {
"have correct size" when {
"concatenating" in { check((a: ByteString, b: ByteString) => (a ++
b).size == a.size + b.size) }
diff --git a/actor/src/main/scala/org/apache/pekko/util/ByteString.scala
b/actor/src/main/scala/org/apache/pekko/util/ByteString.scala
index 73ffdc6d53..bbc47fb3a5 100644
--- a/actor/src/main/scala/org/apache/pekko/util/ByteString.scala
+++ b/actor/src/main/scala/org/apache/pekko/util/ByteString.scala
@@ -416,6 +416,9 @@ object ByteString {
* INTERNAL API: compare `len` bytes from this ByteString starting at
`haystackOffset`
* against `needle[needleOffset..needleOffset+len)`.
*/
+ private[pekko] override def compareBytesTo(that: ByteString, thatOffset:
Int): Boolean =
+ that.matchesAt(thatOffset, bytes, 0, length)
+
private[pekko] override def matchesAt(
haystackOffset: Int, needle: Array[Byte], needleOffset: Int, len:
Int): Boolean = {
var hIdx = haystackOffset
@@ -832,6 +835,18 @@ object ByteString {
* INTERNAL API: compare `len` bytes from this ByteString starting at
logical `haystackOffset`
* against `needle[needleOffset..needleOffset+len)`.
*/
+ private[pekko] override def compareBytesTo(that: ByteString, thatOffset:
Int): Boolean =
+ that.matchesAt(thatOffset, bytes, startIndex, length)
+
+ /**
+ * INTERNAL API: compares `len` bytes of this fragment starting at
`thisOffset` against
+ * `other` starting at `otherOffset`. Both sides are single arrays, so
this goes straight to
+ * the SWAR-based `matchesAt` with no fragment lookup.
+ */
+ private[pekko] def matchesFragmentAt(
+ thisOffset: Int, other: ByteString1, otherOffset: Int, len: Int):
Boolean =
+ other.matchesAt(otherOffset, bytes, startIndex + thisOffset, len)
+
private[pekko] override def matchesAt(
haystackOffset: Int, needle: Array[Byte], needleOffset: Int, len:
Int): Boolean = {
var hIdx = startIndex + haystackOffset
@@ -900,6 +915,14 @@ object ByteString {
}
private[pekko] object ByteStrings extends Companion {
+
+ /**
+ * INTERNAL API: sentinel for `ByteStrings.fragmentHint` meaning "nothing
resolved yet".
+ * The high 32 bits hold -1, so the hit test and the forward-resume path
both fail and the
+ * lookup scans from fragment 0.
+ */
+ private[ByteString] final val NoHint: Long = -1L << 32
+
def apply(bytestrings: Vector[ByteString1]): ByteString =
apply(bytestrings, bytestrings.foldLeft(0)(_ + _.length))
@@ -1468,18 +1491,120 @@ object ByteString {
if (bytestrings.isEmpty) throw new IllegalArgumentException("bytestrings
must not be empty")
if (bytestrings.head.isEmpty) throw new
IllegalArgumentException("bytestrings.head must not be empty")
- def apply(idx: Int): Byte = {
- if (0 <= idx && idx < length) {
- var pos = 0
- var seen = 0
- var frag = bytestrings(pos)
- while (idx >= seen + frag.length) {
- seen += frag.length
- pos += 1
- frag = bytestrings(pos)
+ def apply(idx: Int): Byte =
+ if (0 <= idx && idx < length) byteAtUnchecked(idx)
+ else throw new IndexOutOfBoundsException(idx.toString)
+
+ // Remembers the fragment resolved by the last byteAtUnchecked call, so
sequential access --
+ // the dominant pattern -- stays on the same fragment or steps to the next
one instead of
+ // rescanning the fragment vector from index 0 for every byte.
+ //
+ // Packed into a single long so the triple is read and written atomically:
the fragment index
+ // in the high 32 bits and its start offset in the low 32. A reader can
therefore never pair
+ // the index of one fragment with the start of another, which separate int
fields would allow.
+ // The end offset is not stored; it is recomputed as start +
fragment.length, which is a
+ // cheap array read. The field is deliberately not volatile: it is 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.
+ private[this] var fragmentHint: Long = ByteStrings.NoHint
+
+ private[pekko] override def byteAtUnchecked(offset: Int): Byte = {
+ val hint = fragmentHint // single read: index and start below are
mutually consistent
+ val hintIdx = (hint >>> 32).toInt
+ val hintStart = hint.toInt
+ if (hintIdx >= 0) {
+ val frag = bytestrings(hintIdx)
+ if (offset >= hintStart && offset - hintStart < frag.length)
+ return frag.byteAtUnchecked(offset - hintStart)
+ }
+ resolveAndRead(offset, hintIdx, hintStart)
+ }
+
+ private def resolveAndRead(offset: Int, hintIdx: Int, hintStart: Int):
Byte = {
+ var pos = 0
+ var seen = 0
+ if (hintIdx >= 0) {
+ val hintEnd = hintStart + bytestrings(hintIdx).length
+ if (offset >= hintEnd && hintIdx + 1 < bytestrings.length) {
+ // moving forward past the remembered fragment: resume the scan from
it
+ pos = hintIdx + 1
+ seen = hintEnd
}
- frag(idx - seen)
- } else throw new IndexOutOfBoundsException(idx.toString)
+ }
+ var frag = bytestrings(pos)
+ while (offset >= seen + frag.length) {
+ seen += frag.length
+ pos += 1
+ frag = bytestrings(pos)
+ }
+ fragmentHint = (pos.toLong << 32) | (seen.toLong & 0xFFFFFFFFL)
+ frag.byteAtUnchecked(offset - seen)
+ }
+
+ private[pekko] override def compareBytesTo(that: ByteString, thatOffset:
Int): Boolean =
+ that match {
+ case bss: ByteStrings if thatOffset == 0 =>
+ // both sides fragmented: walk them with independent cursors so
neither side has to
+ // re-locate a fragment by scanning from the start
+ compareFragmented(bss)
+ case _ =>
+ var offset = thatOffset
+ var i = 0
+ while (i < bytestrings.length) {
+ val frag = bytestrings(i)
+ if (!frag.compareBytesTo(that, offset)) return false
+ offset += frag.length
+ i += 1
+ }
+ true
+ }
+
+ /** Compares two equally-sized fragmented ByteStrings in a single pass
over both. */
+ private def compareFragmented(that: ByteStrings): Boolean = {
+ val mine = this.bytestrings
+ val theirs = that.bytestrings
+ var i = 0
+ var j = 0
+ var iOff = 0
+ var jOff = 0
+ while (i < mine.length) {
+ val a = mine(i)
+ val b = theirs(j)
+ val toCmp = math.min(a.length - iOff, b.length - jOff)
+ if (!a.matchesFragmentAt(iOff, b, jOff, toCmp)) return false
+ iOff += toCmp
+ jOff += toCmp
+ if (iOff == a.length) { i += 1; iOff = 0 }
+ if (jOff == b.length) { j += 1; jOff = 0 }
+ }
+ true
+ }
+
+ /**
+ * Compares against `needle` by walking the fragments covering
+ * `[haystackOffset, haystackOffset + len)`, so each contiguous run uses
the fragment's own
+ * SWAR-based `matchesAt` instead of the inherited per-byte fallback.
+ */
+ private[pekko] override def matchesAt(
+ haystackOffset: Int, needle: Array[Byte], needleOffset: Int, len:
Int): Boolean = {
+ if (len == 0) return true
+ var fragIdx = 0
+ var fragOffset = haystackOffset
+ while (fragIdx < bytestrings.length && fragOffset >=
bytestrings(fragIdx).length) {
+ fragOffset -= bytestrings(fragIdx).length
+ fragIdx += 1
+ }
+ var nIdx = needleOffset
+ val end = needleOffset + len
+ while (nIdx < end) {
+ val frag = bytestrings(fragIdx)
+ val toCmp = math.min(end - nIdx, frag.length - fragOffset)
+ if (!frag.matchesAt(fragOffset, needle, nIdx, toCmp)) return false
+ nIdx += toCmp
+ fragIdx += 1
+ fragOffset = 0
+ }
+ true
}
/** Avoid `iterator` in performance sensitive code, call ops directly on
ByteString instead */
@@ -1944,6 +2069,54 @@ object ByteString {
// Cache the hash code since ByteString is immutable
override lazy val hashCode: Int = super.hashCode()
+ /**
+ * Compares this ByteString to another for equality.
+ *
+ * The inherited `Seq` implementation compares element by element through
`iterator`, boxing
+ * every `Byte`. This override compares the underlying byte arrays directly,
reusing the
+ * SWAR-based [[matchesAt]] so that fragmented ByteStrings are compared
without being compacted.
+ *
+ * Equality with other `Seq[Byte]` implementations is preserved by falling
back to the inherited
+ * implementation for non-ByteString arguments.
+ */
+ override def equals(other: Any): Boolean = other match {
+ case that: ByteString => (this eq that) || (this.length == that.length &&
sameBytesAs(that))
+ case _ => super.equals(other)
+ }
+
+ /**
+ * INTERNAL API: compares the bytes of two ByteStrings already known to have
the same length.
+ *
+ * Drives the comparison from whichever side is a single compacted array so
[[matchesAt]] can
+ * compare 8 bytes at a time; otherwise delegates to [[compareBytesTo]],
which walks fragments
+ * in place rather than compacting either side.
+ */
+ private def sameBytesAs(that: ByteString): Boolean =
+ if (length == 0) true
+ else
+ that match {
+ case b: ByteString.ByteString1C => this.matchesAt(0,
b.toArrayUnsafe(), 0, length)
+ case _ =>
+ this match {
+ case b: ByteString.ByteString1C => that.matchesAt(0,
b.toArrayUnsafe(), 0, length)
+ case _ => that.compareBytesTo(this, 0)
+ }
+ }
+
+ /**
+ * INTERNAL API: compares all `length` bytes of this ByteString against
`that` starting at
+ * `thatOffset`. Overridden by the concrete layouts so each contiguous run
is compared with
+ * [[matchesAt]] instead of byte by byte.
+ */
+ private[pekko] def compareBytesTo(that: ByteString, thatOffset: Int):
Boolean = {
+ var i = 0
+ while (i < length) {
+ if (byteAtUnchecked(i) != that.byteAtUnchecked(thatOffset + i)) return
false
+ i += 1
+ }
+ true
+ }
+
// override protected[this] def newBuilder: ByteStringBuilder =
ByteString.newBuilder
// *must* be overridden by derived classes. This construction is necessary
diff --git
a/bench-jmh/src/main/scala/org/apache/pekko/util/ByteString_byteAtUnchecked_Benchmark.scala
b/bench-jmh/src/main/scala/org/apache/pekko/util/ByteString_byteAtUnchecked_Benchmark.scala
new file mode 100644
index 0000000000..95e2e89325
--- /dev/null
+++
b/bench-jmh/src/main/scala/org/apache/pekko/util/ByteString_byteAtUnchecked_Benchmark.scala
@@ -0,0 +1,114 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.pekko.util
+
+import java.util.concurrent.TimeUnit
+
+import org.openjdk.jmh.annotations._
+
+import org.apache.pekko
+import pekko.util.ByteString.{ ByteString1, ByteStrings }
+
+/**
+ * Exercises `ByteStrings.byteAtUnchecked`, which resolves an absolute offset
to a fragment.
+ *
+ * `ByteStrings.apply` delegates to `byteAtUnchecked` after a bounds check, so
indexed access,
+ * sequential traversal and `map` all share the memoised fragment lookup.
+ */
+@State(Scope.Benchmark)
+@Measurement(timeUnit = TimeUnit.MILLISECONDS)
+class ByteString_byteAtUnchecked_Benchmark {
+
+ // 1024 single-byte fragments: the worst case for locating a fragment by
offset
+ val manyFragments: ByteString = ByteStrings(Vector.tabulate(1024)(i =>
ByteString1(Array((i % 251).toByte))))
+
+ // same content, 64 fragments of 16 bytes
+ val fewFragments: ByteString =
+ ByteStrings(Vector.tabulate(64)(i =>
ByteString1(Array.tabulate[Byte](16)(j => ((i * 16 + j) % 251).toByte))))
+
+ val identity: Byte => Byte = b => b
+
+ /*
+ Measured with: bench-jmh/jmh:run -f1 -wi 3 -i 3 -w 1s -r 1s
.*ByteString_byteAtUnchecked.*
+ (short run; the error bars are wide, but the sequential difference is far
larger than the noise)
+
+ Before -- every offset was resolved by scanning the fragment vector from the
start:
+
+ fewFragments_map thrpt 3 392361.866 ± 1027423.684 ops/s
+ manyFragments_map thrpt 3 91349.440 ± 123062.017 ops/s
+ manyFragments_random thrpt 3 508.262 ± 291.734 ops/s
+ manyFragments_reverse thrpt 3 638.345 ± 498.546 ops/s
+ manyFragments_sequential thrpt 3 650.823 ± 584.320 ops/s
+
+ After -- byteAtUnchecked remembers the fragment resolved by the previous
call:
+
+ fewFragments_map thrpt 3 369418.384 ± 890396.160 ops/s
+ manyFragments_map thrpt 3 104726.270 ± 117780.717 ops/s
+ manyFragments_random thrpt 3 596.351 ± 783.657 ops/s
+ manyFragments_reverse thrpt 3 401.330 ± 52.761 ops/s
+ manyFragments_sequential thrpt 3 54838.759 ± 29275.476 ops/s
+
+ Sequential access is roughly 84x faster. Random access is unchanged (the
hint never hits) and
+ reverse access does not benefit either, since each step lands before the
remembered fragment
+ and falls back to a scan from the start -- both stay within the noise of the
previous numbers.
+ */
+
+ private val randomIndices: Array[Int] = {
+ val random = new scala.util.Random(0)
+ Array.fill(1024)(random.nextInt(1024))
+ }
+
+ @Benchmark
+ def manyFragments_sequential: Int = {
+ var sum = 0
+ var i = 0
+ while (i < manyFragments.length) {
+ sum += manyFragments(i)
+ i += 1
+ }
+ sum
+ }
+
+ @Benchmark
+ def manyFragments_reverse: Int = {
+ var sum = 0
+ var i = manyFragments.length - 1
+ while (i >= 0) {
+ sum += manyFragments(i)
+ i -= 1
+ }
+ sum
+ }
+
+ @Benchmark
+ def manyFragments_random: Int = {
+ var sum = 0
+ var i = 0
+ while (i < randomIndices.length) {
+ sum += manyFragments(randomIndices(i))
+ i += 1
+ }
+ sum
+ }
+
+ @Benchmark
+ def manyFragments_map: ByteString = manyFragments.map(identity)
+
+ @Benchmark
+ def fewFragments_map: ByteString = fewFragments.map(identity)
+}
diff --git
a/bench-jmh/src/main/scala/org/apache/pekko/util/ByteString_equals_Benchmark.scala
b/bench-jmh/src/main/scala/org/apache/pekko/util/ByteString_equals_Benchmark.scala
new file mode 100644
index 0000000000..092532d462
--- /dev/null
+++
b/bench-jmh/src/main/scala/org/apache/pekko/util/ByteString_equals_Benchmark.scala
@@ -0,0 +1,110 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.pekko.util
+
+import java.util.concurrent.TimeUnit
+
+import org.openjdk.jmh.annotations._
+
+@State(Scope.Benchmark)
+@Measurement(timeUnit = TimeUnit.MILLISECONDS)
+class ByteString_equals_Benchmark {
+
+ private def bytes(n: Int): Array[Byte] = Array.tabulate[Byte](n)(i => (i %
251).toByte)
+
+ private def fragmented(fragments: Int, fragmentSize: Int): ByteString = (0
until fragments).foldLeft(
+ ByteString.empty) { (acc, i) =>
+ acc ++ ByteString(Array.tabulate[Byte](fragmentSize)(j => ((i *
fragmentSize + j) % 251).toByte))
+ }
+
+ // compacted, single backing array
+ val flatA: ByteString = ByteString(bytes(64 * 1024)).compact
+ val flatB: ByteString = ByteString(bytes(64 * 1024)).compact
+
+ // same content, but spread over 1024 fragments
+ val ropeA: ByteString = fragmented(1024, 64)
+ val ropeB: ByteString = fragmented(1024, 64)
+
+ // differs in the very first byte: measures the early-exit path
+ val flatDiffersFirst: ByteString = {
+ val b = bytes(64 * 1024)
+ b(0) = (b(0) ^ 0xFF).toByte
+ ByteString(b).compact
+ }
+
+ // differs only in the last byte: forces a full scan before returning false
+ val flatDiffersLast: ByteString = {
+ val b = bytes(64 * 1024)
+ b(b.length - 1) = (b(b.length - 1) ^ 0xFF).toByte
+ ByteString(b).compact
+ }
+
+ val smallA: ByteString = ByteString(bytes(8))
+ val smallB: ByteString = ByteString(bytes(8))
+
+ /*
+ Measured with: bench-jmh/jmh:run -f1 -wi 3 -i 3 -w 1s -r 1s
.*ByteString_equals.*
+ (short run; the wide error bars reflect the low iteration count, the
differences are far larger)
+
+ Before -- equality inherited from Seq, comparing element by element through
iterator and
+ boxing every Byte:
+
+ ByteString_equals_Benchmark.flat_differs_first thrpt 3 181247559.958 ±
61693364.344 ops/s
+ ByteString_equals_Benchmark.flat_differs_last thrpt 3 6427.248 ±
4360.116 ops/s
+ ByteString_equals_Benchmark.flat_equal_flat thrpt 3 17772.167 ±
6425.067 ops/s
+ ByteString_equals_Benchmark.flat_equal_rope thrpt 3 1938.294 ±
1108.938 ops/s
+ ByteString_equals_Benchmark.rope_equal_rope thrpt 3 959.603 ±
2045.986 ops/s
+ ByteString_equals_Benchmark.small_equal thrpt 3 53499809.406 ±
21113673.795 ops/s
+
+ After -- array comparison reusing the SWAR-based matchesAt, plus the
memoised fragment
+ lookup in ByteStrings.byteAtUnchecked:
+
+ ByteString_equals_Benchmark.flat_differs_first thrpt 3 289835597.355 ±
76041571.839 ops/s
+ ByteString_equals_Benchmark.flat_differs_last thrpt 3 92604.106 ±
50614.043 ops/s
+ ByteString_equals_Benchmark.flat_equal_flat thrpt 3 70767.215 ±
47918.719 ops/s
+ ByteString_equals_Benchmark.flat_equal_rope thrpt 3 32567.330 ±
16392.230 ops/s
+ ByteString_equals_Benchmark.rope_equal_rope thrpt 3 25819.355 ±
15453.821 ops/s
+ ByteString_equals_Benchmark.small_equal thrpt 3 106841120.007 ±
11546486.517 ops/s
+
+ hashCode is unchanged by this work and is included only to show it stays
flat.
+ */
+
+ @Benchmark
+ def flat_equal_flat: Boolean = flatA == flatB
+
+ @Benchmark
+ def rope_equal_rope: Boolean = ropeA == ropeB
+
+ @Benchmark
+ def flat_equal_rope: Boolean = flatA == ropeB
+
+ @Benchmark
+ def flat_differs_first: Boolean = flatA == flatDiffersFirst
+
+ @Benchmark
+ def flat_differs_last: Boolean = flatA == flatDiffersLast
+
+ @Benchmark
+ def small_equal: Boolean = smallA == smallB
+
+ @Benchmark
+ def flat_hashCode: Int = flatA.hashCode
+
+ @Benchmark
+ def rope_hashCode: Int = ropeA.hashCode
+}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
