-
-
Notifications
You must be signed in to change notification settings - Fork 1.6k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
(WIP) Optimize String#gsub with block #6397
(WIP) Optimize String#gsub with block #6397
Conversation
@@ -354,6 +354,26 @@ struct Slice(T) | |||
source.move_to(self) | |||
end | |||
|
|||
def gsub(buffer, &block : T -> _) |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
This only compiles if T
is UInt8
. Are we sure we want this on slice instead of string?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
It looks like a similar problem as in #6389 where we have methods that make sense only for Slice(UInt8)
, right?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
It's somewhat similar. But in contrast to #6389, this method conceptually fits for any slice. It's only that the buffer
API is currently implemented by IO
which is based on UInt8
. But you can implement such a receiver for any type.
I'm not entirely sure about it's usefulnes, so maybe it's still better to move it to String
as a private method.
I don't understand your benchmarks: new is always slower than old ?! |
if old is always better than new in the non-ascii-only case, then why not keep the old implementation in that case? |
I'm not sure why the non-ascii performance is so bad. In my initial benchmarks, it showed significant improvement. And the implementation is basically the same as for ascii-only. This needs investigation. |
6911db6
to
85bb74c
Compare
@straight-shoota in the past I've also had benchmarking issues, but sometimes it actually helped to clear the cache: |
Yeah, there's a problem with how the compiler's cache works, I think in release it doesn't work quite well. I'll have to investigate, but I'll need reproducible code(s). |
When replacing characters in a string, typically only a minority of characters are changed like most most escaping or encoding use-cases. Currently,
String#gsub
loops through the string, yields each character and writes the return to an IO. However, these single-character writes are not as efficient as writing a larger slice.The best example for this is a string with no replacement. In the previous implementation, it would be copied byte-by-byte (or rather char-by-char) to a new string. If some characters need to be replaced, the size of the slices that can be copied as whole is smaller, but it's still considerably faster than writing byte-by-byte.
An algorithm that only writes replaced chars and copies a series of unchanged characters in bulk can improve performance considerably.
This approach was previously used by a custom implementation in
JSON::Builder#string
.In this PR, the proposed implementation of
String#gsub
yields each char and only writes the returned value if it is notnil
. When using this method, returningnil
signals that the current character can be copied as is and multiplenil
returns are combined to a larger slice copy.I also added a method variant receiving an
io
for better integration. And there is a similarSlice#gsub
method, which is utilized for ascii-only strings (ore replacements). This method is part of the public API ofSlice
because it could be useful for any slice to replace some elements. It requires some sort of builder with anIO
API, so currently it's only effectively usable forSlice(UInt8)
.I also tested
JSON::Builder#string
and the new gsub is even slightly faster than the previous implementation because it doesn't need to decode multibyte chars (they won't be replaced anyway).Obviously, there are cases where the previous, simple implementation is equal or even more performant then the proposed batch copy. This is typically the case when there is a high amount and equal distribution of replaced chars, especially in ascii-only strings. For some use cases, a customized replace loop can achieve more performance than this generalized
String#gsub
.In total, I expect this to be an improvement (backed by the benchmarks) because replacements are usually less frequent in most applications.