[PATCH v2 0/2] MR10804: Draft: unicode: optimize memicmp_strW by doing case-sensitive comparision first
Call to slow `to_lower` can be avoided, if characters already match case-sensitive. This cuts the time for wine boot in half `17.165 s` -> `8879.9 ms` Wine-bug: https://bugs.winehq.org/show_bug.cgi?id=59695 -- v2: registry: optimize `find_subkey` for sorted data https://gitlab.winehq.org/wine/wine/-/merge_requests/10804
From: Stephan Seitz <stephan.seitz@fau.de> Call to slow `to_lower` can be avoided, if characters already match case-sensitive. This cuts the time for wine boot in half `17.165 s` -> `8879.9 ms` Wine-bug: https://bugs.winehq.org/show_bug.cgi?id=59695 --- server/unicode.c | 7 ++++++- 1 file changed, 6 insertions(+), 1 deletion(-) diff --git a/server/unicode.c b/server/unicode.c index bb39b55e50c..62b52191610 100644 --- a/server/unicode.c +++ b/server/unicode.c @@ -75,8 +75,13 @@ int memicmp_strW( const WCHAR *str1, const WCHAR *str2, data_size_t len ) { int ret = 0; - for (len /= sizeof(WCHAR); len; str1++, str2++, len--) + for (len /= sizeof(WCHAR); len; str1++, str2++, len--) { + // when chars match case-sensitive, we can avoid slow to_lower + if (*str1 == *str2) { + continue; + } if ((ret = to_lower(*str1) - to_lower(*str2))) break; + } return ret; } -- GitLab https://gitlab.winehq.org/wine/wine/-/merge_requests/10804
From: Stephan Seitz <stephan.seitz@fau.de> `load_init_registry_from_file` usually loads files with sorted keys to optimize for this case we should check for the append/last_subkey case first before continuing with normal binary search. Wine-bug: https://bugs.winehq.org/show_bug.cgi?id=59695 --- server/registry.c | 5 ++++- 1 file changed, 4 insertions(+), 1 deletion(-) diff --git a/server/registry.c b/server/registry.c index 91b3265e8f7..199e9a6d4ef 100644 --- a/server/registry.c +++ b/server/registry.c @@ -294,12 +294,15 @@ static struct key *find_subkey( const struct key *key, const struct unicode_str { int i, min, max, res; data_size_t len; + bool first_comparison = true; min = 0; max = key->last_subkey; while (min <= max) { - i = (min + max) / 2; + /* when loading from sorted data, most entries are inserted at the last position */ + i = first_comparison ? max : (min + max) / 2; + first_comparison = false; len = min( key->subkeys[i]->obj.name->len, name->len ); res = memicmp_strW( key->subkeys[i]->obj.name->name, name->str, len ); if (!res) res = key->subkeys[i]->obj.name->len - name->len; -- GitLab https://gitlab.winehq.org/wine/wine/-/merge_requests/10804
On Sat May 2 13:29:01 2026 +0000, Alfred Agrell wrote:
I assume this can be improved further I'd assume the same. I don't have your 492M chonker of a registry, so I can't test my theory, but I'd check the last array entry first in find_subkey, and if the given key is greater or equal, return that and skip the binary search. I think the registry is stored in sorted form, so that check will succeed every time during boot. This would give an extra string compare on actual insertions, but that's probably worth it. (I can think of a few other possible optimizations, but I think they'd pessimize the case of normal-sized registries, be annoyingly complex, and/or do nothing if the above is in place, so I'll omit them for now. No point posting walls of unnecessary text.) Your suggestion brings down the time to 3.5s.
However, I corrupted my registry in the first attempt of the change so it is not necessarily 100% the same as before (so master branch still times at 16.8s) -- https://gitlab.winehq.org/wine/wine/-/merge_requests/10804#note_138646
On Sat May 2 15:09:11 2026 +0000, Stephan Seitz wrote:
Your suggestion brings down the time to 3.5s. However, I corrupted my registry in the first attempt of the change so it is not necessarily 100% the same as before (so master branch still times at 16.8s) {width=900 height=184}
-- https://gitlab.winehq.org/wine/wine/-/merge_requests/10804#note_138649
On Sat May 2 15:20:38 2026 +0000, Stephan Seitz wrote:
{width=900 height=184} I found the culprit of my bloated registry. There were variations of the same string repeated over an over. After deleting it, my registry is now 20MiB
-- https://gitlab.winehq.org/wine/wine/-/merge_requests/10804#note_138650
Stephan Seitz (@theHamsta) commented about server/registry.c:
{ int i, min, max, res; data_size_t len; + bool first_comparison = true;
min = 0; max = key->last_subkey; while (min <= max) { - i = (min + max) / 2; + /* when loading from sorted data, most entries are inserted at the last position */ + i = first_comparison ? max : (min + max) / 2; we could do that extra comparison only on registry loading.
-- https://gitlab.winehq.org/wine/wine/-/merge_requests/10804#note_138653
On Sat May 2 15:51:01 2026 +0000, Stephan Seitz wrote:
I found the culprit of my bloated registry. There were variations of the same string repeated over an over. After deleting it, my registry is now 20MiB For the 20MiB registry, the improvement is 150ms -> 120ms (for load_init_registry_from_file only)
-- https://gitlab.winehq.org/wine/wine/-/merge_requests/10804#note_138654
participants (2)
-
Stephan Seitz -
Stephan Seitz (＠theHamsta)