Re-implement Buffer.rangeEquals on Buffer.indexOf #1628
Merged
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
The old rangeEquals function was embarassingly inefficient, using a full scan of the segments linked-list for each element. That optimization is already done in indexOf(), which has almost all of what we need for rangeEquals(). This adds an offset and count slice to the input ByteString in indexOf(), and then leverages that to simplify rangeEquals().
swankjesse
commented
May 26, 2025
| if (data[pos] == b0 && rangeEquals(s, pos + 1, targetByteArray, 1, bytesSize)) { | ||
| if ( | ||
| data[pos] == b0 && | ||
| rangeEquals(s, pos + 1, targetByteArray, bytesOffset + 1, byteCount) |
There was a problem hiding this comment.
Note that this rangeEquals() is fast, because it accepts a Segment for navigation.
| return false | ||
| } | ||
| for (i in 0 until byteCount) { | ||
| if (this[offset + i] != bytes[bytesOffset + i]) { |
There was a problem hiding this comment.
This was slow . . . walking through the segments linked list N times.
There was a problem hiding this comment.
Would this likely make the original buffering issue a non issue even before the okhttpo fixes landed?
Or just a performance win?
There was a problem hiding this comment.
Just a performance win.
swankjesse
commented
May 26, 2025
| @@ -418,19 +441,18 @@ internal inline fun RealBufferedSource.commonRangeEquals( | |||
| ): Boolean { | |||
There was a problem hiding this comment.
Also reimplement BufferedSource.rangeEquals() on BufferedSource.indexOf(). Of course.
yschimke
approved these changes
May 27, 2025
JakeWharton
approved these changes
May 27, 2025
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
The old rangeEquals function was embarassingly inefficient, using a full scan of the segments linked-list for each element. That optimization is already done in indexOf(), which has almost all of what we need for rangeEquals().
This adds an offset and count slice to the input ByteString in indexOf(), and then leverages that to simplify rangeEquals().