The standard implementation of String.replace is VERY poor performance-wise.
See package kotlin.text, StringsJVM.kt:
public actual fun String.replace(oldValue: String, newValue: String, ignoreCase: Boolean = false): String =
splitToSequence(oldValue, ignoreCase = ignoreCase).joinToString(separator = newValue)
The code is just horrible from a performance point of view.
If the string contains 50 times “Hello” and we want to replace it with “World”, the code above will create 51 strings and join them.
The number of unnecessary memory allocations and memory copy operations is killing performance!
What a pity that the standard library contains such poorly optimized code :(.
Replacing this code with something decent (for example similar to what is found in Java StringUtils.replace) made the string replacements in our web application an order of magnitude (10x) faster.
I hope you can do the same in the standard Kotlin library.
Did you really measured what it’s slower than other implementations? And you should measure it with the right tool such as JMH. Modern JDKs (14 for example) have very strong optimizations, and code that was written 10 years ago may no longer be the fastest. Also, creating a new String doesn’t mean allocating new char (or byte) array, they could share it. And even new object allocation can be optimized by “escape analysis”.
fun String.replace(oldChar: Char, newChar: Char, ignoreCase: Boolean = false): String {
var i = indexOf(oldChar, ignoreCase = ignoreCase)
if (i == -1) return this
val buffer = StringBuffer(length)
var tail = 0 // remaining after last substitution
do {
buffer.append(this, tail, i)
buffer.append(newChar)
tail = i + 1
i = indexOf(oldChar, tail, ignoreCase)
} while (i >= 0)
buffer.append(this, tail, this.length)
return buffer.toString()
}
fun String.replace(oldValue: String, newValue: String, ignoreCase: Boolean = false): String {
var i = indexOf(oldValue, ignoreCase = ignoreCase)
if (i == -1) return this
val buffer = StringBuffer(length)
var tail = 0 // remaining after last substitution
do {
buffer.append(this, tail, i)
buffer.append(newValue)
tail = i + oldValue.length
i = indexOf(oldValue, tail, ignoreCase)
} while (i >= 0)
buffer.append(this, tail, this.length)
return buffer.toString()
}
I made some pull requests but they was refused and copy-pasted.
Wait, you replaced String.replace with StringUtils.replace and your web application runs 10x faster, really?
Your pure Kotlin proposal is nearly identical to what we are currently using. (We use a StringBuilder instead of a StringBuffer, and we initially reserve some extra capacity to take into account possible longer replacements).
Wait, you replaced String.replace with StringUtils.replace and your web application runs 10x faster, really?
That’s not what I wrote. The string replacements in our web application are an order of magnitude (10x) faster. Your proposed code achieves exactly that.
Did you really measured what it’s slower than other implementations?
Yes, we did.
Also, creating a new String doesn’t mean allocating new char (or byte) array, they could share it.
Explain how splitting a string can be achieved without allocating and copying. AFAIK Kotlin/Java doesn’t have native “substring” capabilities.
Even without measuring it’s easy to see the major flaw in the current code.
Replacing by splitting a string and then joining all the substrings is probably the worst algorithm you could imagine.
The gain strongly depends on the strings you submit.
You won’t see any benefit if you’re replacing one character in a string of length 10.
On the other hand, replacing multiple substrings in strings that are, for example, 50_000 characters long (a typical web page) will easily produce a significant speed gain.
In our use-case the average time spent on string replacement in a test page went down from 7 msec to 0.6 msec, we gained about 15% on the total page generation time (which is around 50 msec).
Just out of interest, what version of java are you running. String performance (java.lang.String.replace included) was greatly improved with java 9 and java 13.
There is a SO thread discussing comparisons between java.lang.String.replace and StringUtils.replace here: java - Commons Lang StringUtils.replace performance vs String.replace - Stack Overflow
It would be nice to know why the kotlin team decided to use a custom implementation over the java version (which is replaced by the jvm with a native implementation for performance). This function is implemented in the jvm specific part of the stdlib so it’s not just because it’s the generic MPP version. By the way the char version of replace already uses the java implementation.
We’re using Java 11, but that’s not relevant. The issue is the Kotlin code I posted in the initial message of this thread, which uses a very poor algorithm.
Whoever included this in the standard library was very unaware or very uninterested in performance.
My question was in regards to @fvasco’s test, since he couldn’t verify your results. I’m aware that your problem is with the kotlin implementation. That said depending on what java version is used java.lang.String.replace might be faster or slower (depending on the input text). Before java 9 the java implementation used regex which comes with it’s own performance problems, so this could be the reason that kotlin didn’t use the jvm implementation. That said, the current implementation is slow for long strings as you pointed out.
I think the next step to solve this would be to create an issue at https://kotl.in/issue. Also I think it would be helpful to have actual benchmark tests, with the current implementation, a new kotlin implementation (like the one above) and the java implementation for different string lengths on jvm version 6, 8, 9, and 13. 6 and 8 are the 2 bytecode targets for kotlin so this is interesting to compare and important so that we don’t have performance problems (especially since many android devices still use java 6, I think) and the newer jvm versions for the improved string implementations.
I might be able to write a benchmark tomorrow. I just finished my final exam for this semester and I wanted to take a look at JMH for a while now.
How long would you say are your strings when you get a 10x speed improvement? Just so I have an idea what lenghts we’re talking about.
Hi, @Wasabi375,
I plan to provide a repository with my draft and to submit a PR, I hope you (and other) want to collaborate.
Unfortunately @rho refuses to share anything useful, so I mark its statemets as “not reproducible”.
Crazy, isn’t it?
We’re doing a big migration project for a web server previously written in Delphi, and rather naively I expected to find highly optimized libraries in Kotlin/Java.
I guess the performance mainly depends on splitToSequence() and joinToString(), but it does not have to be horrible. It could very well be optimized by the compiler. And such optimization could benefit other pieces of code.
Indeed, the problem lies mainly in splitToSequence(), AFAICS it actually creates substrings of the original string.
Of course the JIT compiler could magically remove these substring allocations and work directly with substrings indexed on the original string without actually allocating the substring, but currently that is not the case.
This kind of optimization would be a lot easier if the language provided a SubString class that doesn’t have any string allocation but is just a range in another string. We actually are using this approach for ByteArrays, we’ve created a SubByteArray class that is a range in another ByteArray and can be used to work with substrings without actually copying the string data.
