godotengine
Add `String::replace_char(s)` methods for performance and convenience
Will try do some performance comparison soon, but these replace in-place essentially, avoiding any COW or other manipulation, and also avoids creating any temporaries etc.
The multi-character one is optional but added for completeness for a few cases where multiple cases are replaced at once
Can expose to scripting if desired, but generally using characters is a bit more complicated in scripting so haven't added yet
Kept as separate commits for ease of editing until approval
See https://github.com/godotengine/godot/pull/92433#discussion_r1616931394
A few more complex cases like String::validate_filename, OS::get_safe_dir_name, and get_csharp_project_name could be replaced using this, instead using a vector of characters, but for right now I keep this to the simple cases (mostly, see AnimationLibrary::validate_library_name for an exception)
See also:
- https://github.com/godotengine/godot/pull/92476
Impressive work!!
I did some quick performance testing. I'm concern with the fact that each characters are copied one by one in the replace_char function even if the character is never found. With some testing, if the character is not found, the new replace_char function is slower then the current replace string. I put some suggestions in a version below for replace_char (note: I did not do extensive optimization on this code).
Test 1 (character replaced 14 times):
Source string: "C:\Projects\godot-jolt\build\windows-msvc-x64\External\Build\jolt\CMakeFiles_CMakeLTOTest-CXX\bin\CMakeFiles\boo.dir\Debug\main.cpp.obj"
Iterations: 1000000 times
Replacing \ for X
Using replace (string): 1200ms
Your version of replace_char: 320ms
Alternative version (see below): 300ms
Test 2 (character not replaced):
Source string: "C:\Projects\godot-jolt\build\windows-msvc-x64\External\Build\jolt\CMakeFiles_CMakeLTOTest-CXX\bin\CMakeFiles\boo.dir\Debug\main.cpp.obj"
Iterations: 1000000 times
Replacing * for X
Using replace (string): 160ms
Your version of replace_char: 320ms
Alternative version (see below): 140ms
Test 3 (small string 1 replace):
Source string: "te_st"
Iterations: 1000000 times
Replacing _ for X
Using replace (string): 425ms
Your version of replace_char: 150ms
Alternative version (see below): 140ms
Test 4 (small string and character not replaced):
Source string: "test"
Iterations: 1000000 times
Replacing _ for X
Using replace (string): 52ms
Your version of replace_char: 150ms
Alternative version (see below): 52ms
Alternative suggested version that does not update the string if search char not found and using memcpy:
String String::replace_char(char32_t p_key, char32_t p_with) const {
ERR_FAIL_COND_V_MSG(p_with == 0, String(), "`with` must not be null.");
int len = length();
if (p_key == 0 || len == 0) {
return *this;
}
int index = 0;
const char32_t *old_ptr = ptr();
for (; index < len; index++) {
if (*old_ptr == p_key) {
break;
}
++old_ptr;
}
if (index == len) {
return *this;
}
String new_string;
new_string.resize(len + 1);
char32_t *new_ptrw = new_string.ptrw();
memcpy(new_ptrw, ptr(), len * sizeof(char32_t));
new_ptrw += index;
*new_ptrw = p_with;
++new_ptrw;
++old_ptr;
while (*old_ptr) {
if (*old_ptr == p_key) {
*new_ptrw = p_with;
}
++new_ptrw;
++old_ptr;
}
*new_ptrw = _null;
return new_string;
}
I'll take a look and measure some between these, I have some theories, I feel a method checking for existence and then using my method for replacement might be faster as it accesses twice not thrice, but will see and compare
Thank you!
I tested String::replace_char(s) with emojis and it seems to fail. 🤔
diff --git a/tests/core/string/test_string.h b/tests/core/string/test_string.h
index 697347b409..2183e4ce0f 100644
--- a/tests/core/string/test_string.h
+++ b/tests/core/string/test_string.h
@@ -433,6 +433,7 @@ TEST_CASE("[String] replace_char") {
String s = "Banana";
CHECK(s.replace_char('n', 'x') == "Baxaxa");
CHECK(s.replace_char('\0', 'x') == "Banana");
+ CHECK(s.replace_char('n', U'🍌') == "Ba🍌a🍌a");
ERR_PRINT_OFF
CHECK(s.replace_char('n', '\0') == "");
ERR_PRINT_ON
@@ -442,6 +443,7 @@ TEST_CASE("[String] replace_chars") {
String s = "Banana";
CHECK(s.replace_chars({ 'B', 'n' }, 'x') == "xaxaxa");
CHECK(s.replace_chars({}, 'x') == "Banana");
+ CHECK(s.replace_chars({ 'B', 'n' }, U'🍌') == "🍌a🍌a🍌a");
ERR_PRINT_OFF
CHECK(s.replace_chars({ 'B', 'n' }, '\0') == "");
ERR_PRINT_ON
===============================================================================
./tests/core/string/test_string.h:432:
TEST CASE: [String] replace_char
./tests/core/string/test_string.h:436: ERROR: CHECK( s.replace_char('n', U'🍌') == "Ba🍌a🍌a" ) is NOT correct!
values: CHECK( Ba🍌a🍌a == Ba🍌a🍌a )
===============================================================================
./tests/core/string/test_string.h:442:
TEST CASE: [String] replace_chars
./tests/core/string/test_string.h:446: ERROR: CHECK( s.replace_chars({ 'B', 'n' }, U'🍌') == "🍌a🍌a🍌a" ) is NOT correct!
values: CHECK( 🍌a🍌a🍌a == 🍌a🍌a🍌a )
I think that's because you missed the U on the right, try:
diff --git a/tests/core/string/test_string.h b/tests/core/string/test_string.h
index 697347b409..2183e4ce0f 100644
--- a/tests/core/string/test_string.h
+++ b/tests/core/string/test_string.h
@@ -433,6 +433,7 @@ TEST_CASE("[String] replace_char") {
String s = "Banana";
CHECK(s.replace_char('n', 'x') == "Baxaxa");
CHECK(s.replace_char('\0', 'x') == "Banana");
+ CHECK(s.replace_char('n', U'🍌') == U"Ba🍌a🍌a");
ERR_PRINT_OFF
CHECK(s.replace_char('n', '\0') == "");
ERR_PRINT_ON
@@ -442,6 +443,7 @@ TEST_CASE("[String] replace_chars") {
String s = "Banana";
CHECK(s.replace_chars({ 'B', 'n' }, 'x') == "xaxaxa");
CHECK(s.replace_chars({}, 'x') == "Banana");
+ CHECK(s.replace_chars({ 'B', 'n' }, U'🍌') == U"🍌a🍌a🍌a");
ERR_PRINT_OFF
CHECK(s.replace_chars({ 'B', 'n' }, '\0') == "");
ERR_PRINT_ON
Using plain string literals are treated as ASCII: https://github.com/godotengine/godot/blob/2ad452ad5b513a72cce9713938deb8be230ed950/core/string/ustring.cpp#L630-L658
Uploaded an alternative approach based on the avove, any benchmarking would be appreciated!
Ah, I just about forgot: I think it would be good to check the string length for 1 (and !is_case_insensitive) in _replace_common, and if true, switch to use the replace_char implementation. This should help GDScript also benefit from the single-char implementation, since it has no char data type and cannot otherwise call it.
Missed the earlier review but went over that, will push some changes in a few hours
Using String as an input for the keys might actually be a good idea, will look into it as an improvement and binding the method as it'd be useful there
Will investigate using variations on String for the keys and add binds for these as optional additions, as I think these would be especially useful for extensions, but will keep them separate so they can be split off if desired
Covered the above suggestions, but leaving the change to replace_chars for the time being, it's a bit convoluted to add some of the details but should probably be worth it to do it, but keeping this from expanding too far into things
Improvements on that side can be part of a followup if desired, together with exposing this
Edit: worked out the String/char * versions so will clean this up and move to the alternative solution and push tonight or tomorrow, it works well and using that format is far more convenient in my testing
Been busy but will push a cleaned up and improved version in the next few days
Edit: Testing the new code and will push soon
This reminds me, we should document the best way to get an ASCII/Unicode integer from a character string in GDScript. I've used "A".to_ascii_buffer()[0] but I'm sure there's something cleaner available. I remember ord() in the Godot 3.x days which was the oppposite of chr() (char() in 4.x).
Thank you for the benchmark! And good idea will look at documenting that too
Will go ahead and squash tomorrow
Will investigate the idea of deferring to this method on length 1 strings in a follow-up, as it becomes redundant in general (mostly relevant in dynamic input cases and scripting, but would deserve some dedicated performance checks etc.)
Edit: Forgot to add the delegate in replace_chars on single element keys, will update
Edit 2: Tested with delegate to replace_char in replace_chars and it was slower, so will check that in a follow-up, and will do some further performance testing to see how to make this faster
This reminds me, we should document the best way to get an ASCII/Unicode integer from a character string in GDScript. I've used
"A".to_ascii_buffer()[0]but I'm sure there's something cleaner available. I rememberord()in the Godot 3.x days which was the oppposite ofchr()(char()in 4.x).
There's String.unicode_at method.
While testing this I ran into some interesting performance differences, so will do some testing before this is ready (probably related to redundancies in find_char and CowData::find, testing not using find_char at all for performance)
Edit: Will look at improving some performance in CowData::find as well
While testing this I ran into some interesting performance differences, so will do some testing before this is ready (probably related to redundancies in
find_charandCowData::find, testing not usingfind_charat all for performance)Edit: Will look at improving some performance in
CowData::findas well
Oh, right, I found that bottleneck once too but completely forgot about it. Pretty sure the culprit is CRASH_BAD_INDEX(p_index, size()); being used unnecessarily inside the loop (through get), preventing vectorization.
This should definitely be addressed; however I would propose to do that in another PR and just keep using find_char in this one.
I'll drop the use of find_char in this, it's already adding unnecessary size checks so just unnecessary, it only saves a bit of boilerplate, it causes a slowdown of around 13% in this, and unsure how much of that is just in the unnecessary checks in CowData::find.
Will also open a PR to address the performance issue in CowData::(r)find and CowData::contains
I'll drop the use of
find_charin this, it's already adding unnecessary size checks so just unnecessary, it only saves a bit of boilerplate, it causes a slowdown of around 13% in this, and unsure how much of that is just in the unnecessary checks inCowData::find.
As discussed in my other PR, the unnecessary size checks in the start are almost free since it's predictable branches on stack variables :) The true culprit is sure to be the loop inefficiency.
But it's fine. I'd like to ask you to comment on the boilerplate you're adding that it's basically find_char but you're not using it for performance concerns. I plan to rewrite some of those APIs anyway to streamline them (at better performance) — once we have the Span PR merged.
The performance in debug builds is significantly faster with this PR just using the current implementation, there's no need to use find_char, but some of that boilerplate is checks against size etc., so it's not necessary to depend on fixes to CowData, there's no specific need to use find_char here so just best to not use it IMO
Benchmarked again with the above project:
PC specifications:
- OS: Windows 11 (build 22631)
- GPU: AMD Radeon RX 6750 XT (Advanced Micro Devices, Inc.; 31.0.24002.92)
- CPU: AMD Ryzen 9 7900X 12-Core Processor (24 threads)
- RAM: 32 GB
Tested with a release build
String.replace(): 553670 usec for 5000000 iterations
String.replace_char(): 214130 usec for 5000000 iterations
String.replace() twice: 945503 usec for 5000000 iterations
String.replace_chars(): 227822 usec for 5000000 iterations
I am still kind of unsure if these methods should even be exposed.
I can definitely see replace_chars being useful to access from GDScript, instead of users having to write:
string.replace_char(ord("a"), ord("_")).replace_char(ord("b"), ord("_")).replace_char(ord("c"), ord("_"))
it would be
string.replace_chars("abc", ord("_"))`
replace_char is a harder sell, because replace() already delegates to replace_char for single char arguments.
replace_charis a harder sell, becausereplace()already delegates toreplace_charfor single char arguments.
It does not, that delegate was removed due to reductions in performance, will investigate doing that in a follow-up however
