You are viewing a plain text version of this content. The canonical link for it is here.
Posted to notifications@pekko.apache.org by "pjfanning (via GitHub)" <gi...@apache.org> on 2025/09/05 14:34:55 UTC
[PR] [WIP] Support SWAR lookup in ByteString indexOf [pekko]
pjfanning opened a new pull request, #2148:
URL: https://github.com/apache/pekko/pull/2148
* follow up to https://github.com/apache/pekko/pull/1247
* WIP
* So far, just Scala 2.13 version of ByteString updated
* I haven't changed the ByteStrings impl either. That is going to be somewhat more complicated
* I haven't yet changed the `indexOf[B >: Byte](elem: B, from: Int)` because some bitwise functions don't work unless you convert the elem to a Byte and that may not be something we want
* aim is first to see if this breaks any tests and then to try the benchmarks to see if this even helps
* based on Netty SWAR code and if this proves useful, I will update our LICENSE and NOTICE to acknowledge the borrowed code
--
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: notifications-unsubscribe@pekko.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: notifications-unsubscribe@pekko.apache.org
For additional commands, e-mail: notifications-help@pekko.apache.org
Re: [PR] [WIP] Support SWAR lookup in ByteString indexOf [pekko]
Posted by "He-Pin (via GitHub)" <gi...@apache.org>.
He-Pin commented on PR #2148:
URL: https://github.com/apache/pekko/pull/2148#issuecomment-3259065549
Maybe it works better on x86?
--
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: notifications-unsubscribe@pekko.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: notifications-unsubscribe@pekko.apache.org
For additional commands, e-mail: notifications-help@pekko.apache.org
Re: [PR] [WIP] Support SWAR lookup in ByteString indexOf [pekko]
Posted by "pjfanning (via GitHub)" <gi...@apache.org>.
pjfanning commented on PR #2148:
URL: https://github.com/apache/pekko/pull/2148#issuecomment-3259087876
> Maybe it works better on x86?
My computer has an Intel chipset (x86) as opposed to Silicon.
--
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: notifications-unsubscribe@pekko.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: notifications-unsubscribe@pekko.apache.org
For additional commands, e-mail: notifications-help@pekko.apache.org
Re: [PR] Support SWAR lookup in ByteString indexOf [pekko]
Posted by "pjfanning (via GitHub)" <gi...@apache.org>.
pjfanning merged PR #2148:
URL: https://github.com/apache/pekko/pull/2148
--
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: notifications-unsubscribe@pekko.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: notifications-unsubscribe@pekko.apache.org
For additional commands, e-mail: notifications-help@pekko.apache.org
Re: [PR] [WIP] Support SWAR lookup in ByteString indexOf [pekko]
Posted by "samueleresca (via GitHub)" <gi...@apache.org>.
samueleresca commented on PR #2148:
URL: https://github.com/apache/pekko/pull/2148#issuecomment-3258701541
Also related to #1264
--
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: notifications-unsubscribe@pekko.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: notifications-unsubscribe@pekko.apache.org
For additional commands, e-mail: notifications-help@pekko.apache.org
Re: [PR] [WIP] Support SWAR lookup in ByteString indexOf [pekko]
Posted by "He-Pin (via GitHub)" <gi...@apache.org>.
He-Pin commented on code in PR #2148:
URL: https://github.com/apache/pekko/pull/2148#discussion_r2326563205
##########
actor/src/main/scala-2.12/org/apache/pekko/util/ByteString.scala:
##########
@@ -247,17 +247,58 @@ object ByteString {
}
override def indexOf(elem: Byte): Int = indexOf(elem, 0)
+
+ @nowarn
override def indexOf(elem: Byte, from: Int): Int = {
- if (from >= length) -1
- else {
- var found = -1
- var i = math.max(from, 0)
- while (i < length && found == -1) {
- if (bytes(i) == elem) found = i
- i += 1
- }
- found
+ val fromIndex = math.max(0, from)
+ if (fromIndex >= length) return -1
+ val searchLength = length - fromIndex
+ var offset = fromIndex
+ val byteCount = searchLength & 7
+ if (byteCount > 0) {
+ val index = unrolledFirstIndexOf(fromIndex, byteCount, elem)
+ if (index != -1) return index
+ offset += byteCount
+ if (offset == length) return -1
}
+ val longCount = searchLength >>> 3
+ val pattern = SWARUtil.compilePattern(elem)
+ for (_ <- 0 until longCount) {
Review Comment:
use while loop
--
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: notifications-unsubscribe@pekko.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: notifications-unsubscribe@pekko.apache.org
For additional commands, e-mail: notifications-help@pekko.apache.org
Re: [PR] [WIP] Support SWAR lookup in ByteString indexOf [pekko]
Posted by "He-Pin (via GitHub)" <gi...@apache.org>.
He-Pin commented on PR #2148:
URL: https://github.com/apache/pekko/pull/2148#issuecomment-3259182343
With:
```
[info] Benchmark Mode Cnt Score Error Units
[info] ByteString_indexOf_Benchmark.bs1_indexOf_from thrpt 3 1785097375.391 ± 182378344.836 ops/s
[info] ByteString_indexOf_Benchmark.bss_indexOf_from_best_case thrpt 3 685545093.571 ± 264766382.135 ops/s
[info] ByteString_indexOf_Benchmark.bss_indexOf_from_far_index_case thrpt 3 80055734.964 ± 2937203.034 ops/s
[info] ByteString_indexOf_Benchmark.bss_indexOf_from_worst_case thrpt 3 15881169.831 ± 916173.885 ops/s
```
Without:
```
[info] Benchmark Mode Cnt Score Error Units
[info] ByteString_indexOf_Benchmark.bs1_indexOf_from thrpt 3 1755173535.795 ± 62100085.834 ops/s
[info] ByteString_indexOf_Benchmark.bss_indexOf_from_best_case thrpt 3 701982305.218 ± 31373002.224 ops/s
[info] ByteString_indexOf_Benchmark.bss_indexOf_from_far_index_case thrpt 3 78040798.676 ± 4238186.477 ops/s
[info] ByteString_indexOf_Benchmark.bss_indexOf_from_worst_case thrpt 3 15570358.974 ± 551811.638 ops/s
```
--
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: notifications-unsubscribe@pekko.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: notifications-unsubscribe@pekko.apache.org
For additional commands, e-mail: notifications-help@pekko.apache.org
Re: [PR] [WIP] Support SWAR lookup in ByteString indexOf [pekko]
Posted by "He-Pin (via GitHub)" <gi...@apache.org>.
He-Pin commented on code in PR #2148:
URL: https://github.com/apache/pekko/pull/2148#discussion_r2326563466
##########
actor/src/main/scala-2.13/org/apache/pekko/util/ByteString.scala:
##########
@@ -243,17 +243,57 @@ object ByteString {
}
}
+ @nowarn
override def indexOf(elem: Byte, from: Int): Int = {
- if (from >= length) -1
- else {
- var found = -1
- var i = math.max(from, 0)
- while (i < length && found == -1) {
- if (bytes(i) == elem) found = i
- i += 1
- }
- found
+ val fromIndex = math.max(0, from)
+ if (fromIndex >= length) return -1
+ val searchLength = length - fromIndex
+ var offset = fromIndex
+ val byteCount = searchLength & 7
+ if (byteCount > 0) {
+ val index = unrolledFirstIndexOf(fromIndex, byteCount, elem)
+ if (index != -1) return index
+ offset += byteCount
+ if (offset == length) return -1
}
+ val longCount = searchLength >>> 3
+ val pattern = SWARUtil.compilePattern(elem)
+ for (_ <- 0 until longCount) {
Review Comment:
use while loop
##########
actor/src/main/scala-2.13/org/apache/pekko/util/ByteString.scala:
##########
@@ -447,17 +487,59 @@ object ByteString {
}
}
+ @nowarn
override def indexOf(elem: Byte, from: Int): Int = {
- if (from >= length) -1
- else {
- var found = -1
- var i = math.max(from, 0)
- while (i < length && found == -1) {
- if (bytes(startIndex + i) == elem) found = i
- i += 1
- }
- found
+ val fromIndex = startIndex + math.max(0, from)
+ if (fromIndex >= length) return -1
+ val searchLength = length - fromIndex
+ var offset = fromIndex
+ val byteCount = searchLength & 7
+ if (byteCount > 0) {
+ val index = unrolledFirstIndexOf(fromIndex, byteCount, elem)
+ if (index != -1) return index
+ offset += byteCount
+ if (offset == length) return -1
}
+ val longCount = searchLength >>> 3
+ val pattern = SWARUtil.compilePattern(elem)
+ for (_ <- 0 until longCount) {
Review Comment:
use while loop
--
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: notifications-unsubscribe@pekko.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: notifications-unsubscribe@pekko.apache.org
For additional commands, e-mail: notifications-help@pekko.apache.org
Re: [PR] [WIP] Support SWAR lookup in ByteString indexOf [pekko]
Posted by "pjfanning (via GitHub)" <gi...@apache.org>.
pjfanning commented on code in PR #2148:
URL: https://github.com/apache/pekko/pull/2148#discussion_r2327366761
##########
actor/src/main/scala-2.12/org/apache/pekko/util/ByteString.scala:
##########
@@ -247,17 +247,48 @@ object ByteString {
}
override def indexOf(elem: Byte): Int = indexOf(elem, 0)
+
+ @nowarn
override def indexOf(elem: Byte, from: Int): Int = {
- if (from >= length) -1
- else {
- var found = -1
- var i = math.max(from, 0)
- while (i < length && found == -1) {
- if (bytes(i) == elem) found = i
- i += 1
- }
- found
+ val fromIndex = math.max(0, from)
+ if (fromIndex >= length) return -1
+ val searchLength = length - fromIndex
+ var offset = fromIndex
+ val byteCount = searchLength & 7
+ if (byteCount > 0) {
Review Comment:
this is not a line by line port of the Netty code - I am pulling out manageable chunks for the Netty code.
PlatformDependent and PlatformDependent0 are very large classes and I'm trying to avoid porting too much.
In the end of the day, we might want to consider options like allowing an optional ByteString implementation that wraps a ByteBuf or generally allowing ByteString to be something where users can create their own as long as they implement a defined trait/interface.
--
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: notifications-unsubscribe@pekko.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: notifications-unsubscribe@pekko.apache.org
For additional commands, e-mail: notifications-help@pekko.apache.org
Re: [PR] [WIP] Support SWAR lookup in ByteString indexOf [pekko]
Posted by "pjfanning (via GitHub)" <gi...@apache.org>.
pjfanning commented on PR #2148:
URL: https://github.com/apache/pekko/pull/2148#issuecomment-3258825593
> IIRC, there is a reverse order searching in Netty, but it seems that will not be needed here?
I can find no code in Pekko that allows Little Endian ordering in ByteStrings.
--
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: notifications-unsubscribe@pekko.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: notifications-unsubscribe@pekko.apache.org
For additional commands, e-mail: notifications-help@pekko.apache.org
Re: [PR] [WIP] Support SWAR lookup in ByteString indexOf [pekko]
Posted by "pjfanning (via GitHub)" <gi...@apache.org>.
pjfanning commented on PR #2148:
URL: https://github.com/apache/pekko/pull/2148#issuecomment-3259034060
Benchmarks show possible small gains. I can try more Java versions and Scala versions later. I'm using an old Macbook to run this.
```
sbt "bench-jmh/Jmh/run -i 3 -wi 3 -f 1 .*ByteString_indexOf_Benchmark"
```
```
Scala 2.13 with SWAR changes (Java 17.0.16)
[info] Benchmark Mode Cnt Score Error Units
[info] ByteString_indexOf_Benchmark.bs1_indexOf_from thrpt 3 760238669.404 ± 767807134.762 ops/s
[info] ByteString_indexOf_Benchmark.bss_indexOf_from_best_case thrpt 3 217038390.875 ± 209292888.785 ops/s
[info] ByteString_indexOf_Benchmark.bss_indexOf_from_far_index_case thrpt 3 17367673.994 ± 1163638.424 ops/s
[info] ByteString_indexOf_Benchmark.bss_indexOf_from_worst_case thrpt 3 5519954.663 ± 441205.202 ops/s
[success] Total time: 497 s (0:08:17.0), completed 5 Sep 2025, 17:23:18
Scala 2.13 main branch without SWAR changes (Java 17.0.16)
Score Error Units
[info] ByteString_indexOf_Benchmark.bs1_indexOf_from thrpt 3 698656851.582 ± 823327975.698 ops/s
[info] ByteString_indexOf_Benchmark.bss_indexOf_from_best_case thrpt 3 186356562.647 ± 321470798.822 ops/s
[info] ByteString_indexOf_Benchmark.bss_indexOf_from_far_index_case thrpt 3 17710312.697 ± 9020140.588 ops/s
[info] ByteString_indexOf_Benchmark.bss_indexOf_from_worst_case thrpt 3 5291631.416 ± 3775859.071 ops/s
[success] Total time: 449 s (0:07:29.0), completed 5 Sep 2025, 17:33:31
```
--
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: notifications-unsubscribe@pekko.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: notifications-unsubscribe@pekko.apache.org
For additional commands, e-mail: notifications-help@pekko.apache.org
Re: [PR] [WIP] Support SWAR lookup in ByteString indexOf [pekko]
Posted by "He-Pin (via GitHub)" <gi...@apache.org>.
He-Pin commented on PR #2148:
URL: https://github.com/apache/pekko/pull/2148#issuecomment-3262327731
this pr:
```
[info] ByteString_indexOf_Benchmark.bs1_indexOf_from thrpt 3 358044494.401 ± 17655714.900 ops/s
[info] ByteString_indexOf_Benchmark.bs1_indexOf_from_byte thrpt 3 436359932.389 ± 16001047.436 ops/s
[info] ByteString_indexOf_Benchmark.bss_indexOf_from_best_case thrpt 3 719490945.475 ± 2818152.500 ops/s
[info] ByteString_indexOf_Benchmark.bss_indexOf_from_far_index_case thrpt 3 80651601.465 ± 383482.242 ops/s
[info] ByteString_indexOf_Benchmark.bss_indexOf_from_far_index_case_byte thrpt 3 94930732.028 ± 2978254.988 ops/s
[info] ByteString_indexOf_Benchmark.bss_indexOf_from_worst_case thrpt 3 15904622.198 ± 346781.287 ops/s
```
main branch:
```
[info] ByteString_indexOf_Benchmark.bs1_indexOf_from thrpt 3 358040661.743 ± 19373949.865 ops/s
[info] ByteString_indexOf_Benchmark.bs1_indexOf_from_byte thrpt 3 357099482.894 ± 15214151.081 ops/s
[info] ByteString_indexOf_Benchmark.bss_indexOf_from_best_case thrpt 3 715997840.783 ± 64178398.777 ops/s
[info] ByteString_indexOf_Benchmark.bss_indexOf_from_far_index_case thrpt 3 79917094.452 ± 777032.287 ops/s
[info] ByteString_indexOf_Benchmark.bss_indexOf_from_far_index_case_byte thrpt 3 79582115.983 ± 4717928.601 ops/s
[info] ByteString_indexOf_Benchmark.bss_indexOf_from_worst_case thrpt 3 15816252.146 ± 2784757.621 ops/s
```
--
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: notifications-unsubscribe@pekko.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: notifications-unsubscribe@pekko.apache.org
For additional commands, e-mail: notifications-help@pekko.apache.org
Re: [PR] [WIP] Support SWAR lookup in ByteString indexOf [pekko]
Posted by "He-Pin (via GitHub)" <gi...@apache.org>.
He-Pin commented on PR #2148:
URL: https://github.com/apache/pekko/pull/2148#issuecomment-3333471643
Yeah, we may learn some from Netty's Http parser too.
--
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: notifications-unsubscribe@pekko.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: notifications-unsubscribe@pekko.apache.org
For additional commands, e-mail: notifications-help@pekko.apache.org
Re: [PR] Support SWAR lookup in ByteString indexOf [pekko]
Posted by "pjfanning (via GitHub)" <gi...@apache.org>.
pjfanning commented on PR #2148:
URL: https://github.com/apache/pekko/pull/2148#issuecomment-3340493952
@He-Pin wdyt? There appears to be a performance benefit from the SWAR implementation in this PR.
I ran the Framing Benchmarks used in #1247 and on my old laptop, the results are a bit up and down, on balance, the changes seem to speed up the searches.
--
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: notifications-unsubscribe@pekko.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: notifications-unsubscribe@pekko.apache.org
For additional commands, e-mail: notifications-help@pekko.apache.org
Re: [PR] [WIP] Support SWAR lookup in ByteString indexOf [pekko]
Posted by "He-Pin (via GitHub)" <gi...@apache.org>.
He-Pin commented on PR #2148:
URL: https://github.com/apache/pekko/pull/2148#issuecomment-3332315654
@pjfanning I just checked pekko-http, where `scanHeaderNameAndReturnIndexOfColon` should be replaced with `indexOf` I think
--
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: notifications-unsubscribe@pekko.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: notifications-unsubscribe@pekko.apache.org
For additional commands, e-mail: notifications-help@pekko.apache.org
Re: [PR] [WIP] Support SWAR lookup in ByteString indexOf [pekko]
Posted by "He-Pin (via GitHub)" <gi...@apache.org>.
He-Pin commented on PR #2148:
URL: https://github.com/apache/pekko/pull/2148#issuecomment-3259102510
There is an https://github.com/netty/netty/pull/13942 for the `lastIndexOf`
--
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: notifications-unsubscribe@pekko.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: notifications-unsubscribe@pekko.apache.org
For additional commands, e-mail: notifications-help@pekko.apache.org
Re: [PR] [WIP] Support SWAR lookup in ByteString indexOf [pekko]
Posted by "He-Pin (via GitHub)" <gi...@apache.org>.
He-Pin commented on code in PR #2148:
URL: https://github.com/apache/pekko/pull/2148#discussion_r2326563770
##########
actor/src/main/scala-3/org/apache/pekko/util/ByteString.scala:
##########
@@ -244,17 +244,57 @@ object ByteString {
}
}
+ @nowarn
override def indexOf(elem: Byte, from: Int): Int = {
- if (from >= length) -1
- else {
- var found = -1
- var i = math.max(from, 0)
- while (i < length && found == -1) {
- if (bytes(i) == elem) found = i
- i += 1
- }
- found
+ val fromIndex = math.max(0, from)
+ if (fromIndex >= length) return -1
+ val searchLength = length - fromIndex
+ var offset = fromIndex
+ val byteCount = searchLength & 7
+ if (byteCount > 0) {
+ val index = unrolledFirstIndexOf(fromIndex, byteCount, elem)
+ if (index != -1) return index
+ offset += byteCount
+ if (offset == length) return -1
}
+ val longCount = searchLength >>> 3
+ val pattern = SWARUtil.compilePattern(elem)
+ for (_ <- 0 until longCount) {
Review Comment:
use while loop
##########
actor/src/main/scala-3/org/apache/pekko/util/ByteString.scala:
##########
@@ -448,17 +488,59 @@ object ByteString {
}
}
+ @nowarn
override def indexOf(elem: Byte, from: Int): Int = {
- if (from >= length) -1
- else {
- var found = -1
- var i = math.max(from, 0)
- while (i < length && found == -1) {
- if (bytes(startIndex + i) == elem) found = i
- i += 1
- }
- found
+ val fromIndex = startIndex + math.max(0, from)
+ if (fromIndex >= length) return -1
+ val searchLength = length - fromIndex
+ var offset = fromIndex
+ val byteCount = searchLength & 7
+ if (byteCount > 0) {
+ val index = unrolledFirstIndexOf(fromIndex, byteCount, elem)
+ if (index != -1) return index
+ offset += byteCount
+ if (offset == length) return -1
}
+ val longCount = searchLength >>> 3
+ val pattern = SWARUtil.compilePattern(elem)
+ for (_ <- 0 until longCount) {
Review Comment:
use while loop
--
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: notifications-unsubscribe@pekko.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: notifications-unsubscribe@pekko.apache.org
For additional commands, e-mail: notifications-help@pekko.apache.org
Re: [PR] [WIP] Support SWAR lookup in ByteString indexOf [pekko]
Posted by "pjfanning (via GitHub)" <gi...@apache.org>.
pjfanning commented on PR #2148:
URL: https://github.com/apache/pekko/pull/2148#issuecomment-3259235402
> There is an [netty/netty#13942](https://github.com/netty/netty/pull/13942) for the `lastIndexOf`
Pekko ByteString doesn't have a lastIndexOf API.
--
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: notifications-unsubscribe@pekko.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: notifications-unsubscribe@pekko.apache.org
For additional commands, e-mail: notifications-help@pekko.apache.org
Re: [PR] [WIP] Support SWAR lookup in ByteString indexOf [pekko]
Posted by "pjfanning (via GitHub)" <gi...@apache.org>.
pjfanning commented on PR #2148:
URL: https://github.com/apache/pekko/pull/2148#issuecomment-3262275444
Latest Benchmarks
```
Scala 2.13 with latest SWAR improvements (Java 17.0.16)
[info] Benchmark Mode Cnt Score Error Units
[info] ByteString_indexOf_Benchmark.bs1_indexOf_from thrpt 3 142007750.335 ± 11451280.353 ops/s
[info] ByteString_indexOf_Benchmark.bs1_indexOf_from_byte thrpt 3 201839375.500 ± 8883178.639 ops/s
[info] ByteString_indexOf_Benchmark.bss_indexOf_from_best_case thrpt 3 229591381.126 ± 9493019.937 ops/s
[info] ByteString_indexOf_Benchmark.bss_indexOf_from_far_index_case thrpt 3 19255457.957 ± 1756254.380 ops/s
[info] ByteString_indexOf_Benchmark.bss_indexOf_from_far_index_case_byte thrpt 3 17272232.840 ± 1025593.701 ops/s
[info] ByteString_indexOf_Benchmark.bss_indexOf_from_worst_case thrpt 3 5558092.504 ± 261288.813 ops/s
[success] Total time: 529 s (0:08:49.0), completed 6 Sep 2025, 14:50:44
Scala 2.13 with latest SWAR improvements (Java 17.0.16)
[info] Benchmark Mode Cnt Score Error Units
[info] ByteString_indexOf_Benchmark.bs1_indexOf_from thrpt 3 141756145.114 ± 30369828.227 ops/s
[info] ByteString_indexOf_Benchmark.bs1_indexOf_from_byte thrpt 3 144978259.405 ± 28884724.074 ops/s
[info] ByteString_indexOf_Benchmark.bss_indexOf_from_best_case thrpt 3 229556876.670 ± 15205367.331 ops/s
[info] ByteString_indexOf_Benchmark.bss_indexOf_from_far_index_case thrpt 3 17614264.657 ± 731800.955 ops/s
[info] ByteString_indexOf_Benchmark.bss_indexOf_from_far_index_case_byte thrpt 3 17853870.144 ± 179729.781 ops/s
[info] ByteString_indexOf_Benchmark.bss_indexOf_from_worst_case thrpt 3 5516083.125 ± 438304.618 ops/s
[success] Total time: 553 s (0:09:13.0), completed 6 Sep 2025, 15:05:48
```
The changes show some promise but I'm concerned about the ByteString_indexOf_Benchmark.bss_indexOf_from_far_index_case_byte case where the performance trails off after a few iterations (the warmup is faster than the recorded runs).
@He-Pin if you time, could you retry the benchmark runs on your machine with the latest code in this PR and the main branch.
The main change today is that I'm using a VarHandle to fetch long values from the byte array instead of using the code that gets 8 bytes explicitly and that does bitwise manipulations on the bytes. (SWARUtil.getLong).
--
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: notifications-unsubscribe@pekko.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: notifications-unsubscribe@pekko.apache.org
For additional commands, e-mail: notifications-help@pekko.apache.org
Re: [PR] [WIP] Support SWAR lookup in ByteString indexOf [pekko]
Posted by "pjfanning (via GitHub)" <gi...@apache.org>.
pjfanning commented on PR #2148:
URL: https://github.com/apache/pekko/pull/2148#issuecomment-3333052773
> @pjfanning I just checked pekko-http, where `scanHeaderNameAndReturnIndexOfColon` should be replaced with `indexOf` I think, so does the `scanHeaderValue`
That HttpHeaderParser class might possibly benefit from using ByteString indexOf but I suspect we will need a new overload for indexOf that allows you to specify from and to for the search. So far, we only support an overload that takes a from location.
So we have:
```
def indexOf(b: Byte)
def indexOf(b: Byte, from: Int)
def indexOf(b: Byte, from: Int, to: Int) // new API that we can use in scanHeaderNameAndReturnIndexOfColon
```
--
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: notifications-unsubscribe@pekko.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: notifications-unsubscribe@pekko.apache.org
For additional commands, e-mail: notifications-help@pekko.apache.org
Re: [PR] [WIP] Support SWAR lookup in ByteString indexOf [pekko]
Posted by "pjfanning (via GitHub)" <gi...@apache.org>.
pjfanning commented on PR #2148:
URL: https://github.com/apache/pekko/pull/2148#issuecomment-3329705791
@He-Pin Do you know where the ByteString indexOf is actually used? I had a look at the pekko and pekko-http code and couldn't really find any Pekko code that calls ByteString indexOf.
--
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: notifications-unsubscribe@pekko.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: notifications-unsubscribe@pekko.apache.org
For additional commands, e-mail: notifications-help@pekko.apache.org
Re: [PR] [WIP] Support SWAR lookup in ByteString indexOf [pekko]
Posted by "He-Pin (via GitHub)" <gi...@apache.org>.
He-Pin commented on PR #2148:
URL: https://github.com/apache/pekko/pull/2148#issuecomment-3258819561
IIRC, there is a reverse order searching in Netty, but it seems that will not be needed here?
--
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: notifications-unsubscribe@pekko.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: notifications-unsubscribe@pekko.apache.org
For additional commands, e-mail: notifications-help@pekko.apache.org
Re: [PR] [WIP] Support SWAR lookup in ByteString indexOf [pekko]
Posted by "He-Pin (via GitHub)" <gi...@apache.org>.
He-Pin commented on code in PR #2148:
URL: https://github.com/apache/pekko/pull/2148#discussion_r2326563305
##########
actor/src/main/scala-2.12/org/apache/pekko/util/ByteString.scala:
##########
@@ -448,17 +489,60 @@ object ByteString {
}
override def indexOf(elem: Byte): Int = indexOf(elem, 0)
+
+ @nowarn
override def indexOf(elem: Byte, from: Int): Int = {
- if (from >= length) -1
- else {
- var found = -1
- var i = math.max(from, 0)
- while (i < length && found == -1) {
- if (bytes(startIndex + i) == elem) found = i
- i += 1
- }
- found
+ val fromIndex = startIndex + math.max(0, from)
+ if (fromIndex >= length) return -1
+ val searchLength = length - fromIndex
+ var offset = fromIndex
+ val byteCount = searchLength & 7
+ if (byteCount > 0) {
+ val index = unrolledFirstIndexOf(fromIndex, byteCount, elem)
+ if (index != -1) return index
+ offset += byteCount
+ if (offset == length) return -1
}
+ val longCount = searchLength >>> 3
+ val pattern = SWARUtil.compilePattern(elem)
+ for (_ <- 0 until longCount) {
Review Comment:
use while loop
--
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: notifications-unsubscribe@pekko.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: notifications-unsubscribe@pekko.apache.org
For additional commands, e-mail: notifications-help@pekko.apache.org
Re: [PR] [WIP] Support SWAR lookup in ByteString indexOf [pekko]
Posted by "He-Pin (via GitHub)" <gi...@apache.org>.
He-Pin commented on PR #2148:
URL: https://github.com/apache/pekko/pull/2148#issuecomment-3259244321
@pjfanning It has, in the `Seq` trait.
--
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: notifications-unsubscribe@pekko.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: notifications-unsubscribe@pekko.apache.org
For additional commands, e-mail: notifications-help@pekko.apache.org
Re: [PR] [WIP] Support SWAR lookup in ByteString indexOf [pekko]
Posted by "He-Pin (via GitHub)" <gi...@apache.org>.
He-Pin commented on code in PR #2148:
URL: https://github.com/apache/pekko/pull/2148#discussion_r2327350146
##########
actor/src/main/scala-2.12/org/apache/pekko/util/ByteString.scala:
##########
@@ -247,17 +247,48 @@ object ByteString {
}
override def indexOf(elem: Byte): Int = indexOf(elem, 0)
+
+ @nowarn
override def indexOf(elem: Byte, from: Int): Int = {
- if (from >= length) -1
- else {
- var found = -1
- var i = math.max(from, 0)
- while (i < length && found == -1) {
- if (bytes(i) == elem) found = i
- i += 1
- }
- found
+ val fromIndex = math.max(0, from)
+ if (fromIndex >= length) return -1
+ val searchLength = length - fromIndex
+ var offset = fromIndex
+ val byteCount = searchLength & 7
+ if (byteCount > 0) {
Review Comment:
in Netty, the unrolled one is only done after PlatformDependent.isUnaligned() check, otherwise just use the old search
--
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: notifications-unsubscribe@pekko.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: notifications-unsubscribe@pekko.apache.org
For additional commands, e-mail: notifications-help@pekko.apache.org
Re: [PR] [WIP] Support SWAR lookup in ByteString indexOf [pekko]
Posted by "He-Pin (via GitHub)" <gi...@apache.org>.
He-Pin commented on code in PR #2148:
URL: https://github.com/apache/pekko/pull/2148#discussion_r2327380596
##########
actor/src/main/scala-2.12/org/apache/pekko/util/ByteString.scala:
##########
@@ -247,17 +247,48 @@ object ByteString {
}
override def indexOf(elem: Byte): Int = indexOf(elem, 0)
+
+ @nowarn
override def indexOf(elem: Byte, from: Int): Int = {
- if (from >= length) -1
- else {
- var found = -1
- var i = math.max(from, 0)
- while (i < length && found == -1) {
- if (bytes(i) == elem) found = i
- i += 1
- }
- found
+ val fromIndex = math.max(0, from)
+ if (fromIndex >= length) return -1
+ val searchLength = length - fromIndex
+ var offset = fromIndex
+ val byteCount = searchLength & 7
+ if (byteCount > 0) {
Review Comment:
`java.nio.Bits#unaligned` seems on most platform, current code is right.
--
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: notifications-unsubscribe@pekko.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: notifications-unsubscribe@pekko.apache.org
For additional commands, e-mail: notifications-help@pekko.apache.org
Re: [PR] [WIP] Support SWAR lookup in ByteString indexOf [pekko]
Posted by "He-Pin (via GitHub)" <gi...@apache.org>.
He-Pin commented on PR #2148:
URL: https://github.com/apache/pekko/pull/2148#issuecomment-3331308845
It should be used for finding the \n for sse or http protocol for streaming parsing
--
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: notifications-unsubscribe@pekko.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: notifications-unsubscribe@pekko.apache.org
For additional commands, e-mail: notifications-help@pekko.apache.org