Use binary-search in LocaleToScriptMapping
Created attachment 426363 [details] Patch
Comment on attachment 426363 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=426363&action=review Great idea! > Source/WebCore/ChangeLog:10 > + This patch removes HashMaps in LocaleToScriptMapping, and binary-search onto the constant data arrays. > + These maps are not frequently used. Keys of the maps can be encoded into uint32_t or uint64_t so that > + comparison becomes super cheap and we can initialize this array at compile-time. I’ve long wanted to make a re-usable binary search constant data array class. Glad you are doing this here; there seem to be many other places using hash tables that could do this sort of thing instead. > Source/WebCore/platform/text/LocaleToScriptMapping.cpp:41 > +using ScriptName = uint32_t; I’d like to see this use a bit more template machinery so we can do this for 4 and 8 without writing two separate sets of functions. > Source/WebCore/platform/text/LocaleToScriptMapping.cpp:50 > + result |= (static_cast<ScriptName>(code) << ((4 - index - 1) * CHAR_BIT)); I think we can use 8 instead of CHAR_BIT; I don’t think CHAR_BIT helps readability or portability here. > Source/WebCore/platform/text/LocaleToScriptMapping.cpp:55 > +static Optional<ScriptName> tryParseScriptName(StringView string) Not 100% sure this needs "try" in its name. It is quite common throughout all kinds of WebKit code for functions named parse to have failure modes and use Optional to express that failure. > Source/WebCore/platform/text/LocaleToScriptMapping.cpp:64 > + result |= (static_cast<ScriptName>(toASCIILower(code)) << ((4 - index - 1) * CHAR_BIT)); I think we can use 8 instead of CHAR_BIT; I don’t think CHAR_BIT helps readability or portability here. Ideally we’d find a way to share code so we know the above is the same. > Source/WebCore/platform/text/LocaleToScriptMapping.cpp:199 > + auto* element = tryBinarySearch<ScriptNameCode>(scriptNameCodeList, WTF_ARRAY_LENGTH(scriptNameCodeList), name.value(), std::size should work and seems nicer to use than WTF_ARRAY_LENGTH > Source/WebCore/platform/text/LocaleToScriptMapping.cpp:455 > + auto* element = tryBinarySearch<LocaleScript>(localeScriptList, WTF_ARRAY_LENGTH(localeScriptList), localeName.value(), std::size should work and seems nicer to use than WTF_ARRAY_LENGTH Also would be nice to make another template like tryBinarySearch, maybe even an overload of it, that handles the sizing automatically. Seems like it should be able to deduce both the type and the size without an explicit template or function argument for either.
Created attachment 426364 [details] Patch
Since I already reviewed, I won’t set review+ on the new patch unless you tell me you aren’t going to make any more changes. Otherwise, I’ll wait for a newer patch that takes some of my suggestions and review again then.
More generally I think we can do this binary search pattern with ASCIILiteral in much the same way you are doing here with the fixed length packing into an integer. This is even more optimized, but something reusable could help encourage people not to use HashMap for fixed things like this.
Created attachment 426366 [details] Patch
Ah, the uploaded patch is simply adding static_assert based test :)
Comment on attachment 426363 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=426363&action=review Thanks >> Source/WebCore/platform/text/LocaleToScriptMapping.cpp:41 >> +using ScriptName = uint32_t; > > I’d like to see this use a bit more template machinery so we can do this for 4 and 8 without writing two separate sets of functions. Changed. >> Source/WebCore/platform/text/LocaleToScriptMapping.cpp:50 >> + result |= (static_cast<ScriptName>(code) << ((4 - index - 1) * CHAR_BIT)); > > I think we can use 8 instead of CHAR_BIT; I don’t think CHAR_BIT helps readability or portability here. Changed. >> Source/WebCore/platform/text/LocaleToScriptMapping.cpp:55 >> +static Optional<ScriptName> tryParseScriptName(StringView string) > > Not 100% sure this needs "try" in its name. It is quite common throughout all kinds of WebKit code for functions named parse to have failure modes and use Optional to express that failure. Changed it to paseScriptName. Instead, constexpr version is renamed to parseConstantScriptName. >> Source/WebCore/platform/text/LocaleToScriptMapping.cpp:64 >> + result |= (static_cast<ScriptName>(toASCIILower(code)) << ((4 - index - 1) * CHAR_BIT)); > > I think we can use 8 instead of CHAR_BIT; I don’t think CHAR_BIT helps readability or portability here. > > Ideally we’d find a way to share code so we know the above is the same. Changed it to 8. Unfortunately, currently we have separate function because of constexpr. >> Source/WebCore/platform/text/LocaleToScriptMapping.cpp:199 >> + auto* element = tryBinarySearch<ScriptNameCode>(scriptNameCodeList, WTF_ARRAY_LENGTH(scriptNameCodeList), name.value(), > > std::size should work and seems nicer to use than WTF_ARRAY_LENGTH Changed, std::size_ sounds nice. >> Source/WebCore/platform/text/LocaleToScriptMapping.cpp:455 >> + auto* element = tryBinarySearch<LocaleScript>(localeScriptList, WTF_ARRAY_LENGTH(localeScriptList), localeName.value(), > > std::size should work and seems nicer to use than WTF_ARRAY_LENGTH > > Also would be nice to make another template like tryBinarySearch, maybe even an overload of it, that handles the sizing automatically. Seems like it should be able to deduce both the type and the size without an explicit template or function argument for either. std::size sounds nice. For now, I'll leave tryBinarySearch refactoring for the future change.
Created attachment 426367 [details] Patch
Created attachment 426368 [details] Patch
Comment on attachment 426368 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=426368&action=review A few more ideas for refinements. > Source/WebCore/platform/text/LocaleToScriptMapping.cpp:45 > + ASSERT_UNDER_CONSTEXPR_CONTEXT(length <= sizeof(ResultType)); Since we’re doing assertions like this, how about asserting the terminator is the null character? > Source/WebCore/platform/text/LocaleToScriptMapping.cpp:48 > + uint8_t code = static_cast<uint8_t>(string[index]); Seems like we could have code be "ResultType" instead of uint8_t and avoid the static_cast on the next line of code. > Source/WebCore/platform/text/LocaleToScriptMapping.cpp:49 > + result |= (static_cast<ResultType>(code) << ((sizeof(ResultType) - index - 1) * 8)); I think this has one set of parentheses that aren’t needed for clarity or correctness, the outermost set. > Source/WebCore/platform/text/LocaleToScriptMapping.cpp:64 > + result |= (static_cast<ResultType>(toASCIILower(code)) << ((sizeof(ResultType) - index - 1) * 8)); I think this has one set of parentheses that aren’t needed for clarity or correctness, the outermost set. > Source/WebCore/platform/text/LocaleToScriptMapping.cpp:82 > + static constexpr ScriptNameCode scriptNameCodeList[] = { > + { parseConstantScriptCode<ScriptName>("arab"), USCRIPT_ARABIC }, I think we’re going to be able to make a fancier version of this where you don’t have to write the calls to parseConstantScriptCode because it’s all done by the constexpr constructor of an object. Even better, I think it can encapsulate the implementation detail of the "parsing into an integer" and just take a couple of function arguments, and also make it easier to correctly call the binary search function. Just refactoring! But should be more elegant. And maybe have a version where we store const char* rather than a fixed size item in the table but otherwise it’s similar, and uses the same template just with different arguments. Depending on what other places in WebKit need.
Comment on attachment 426368 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=426368&action=review >> Source/WebCore/platform/text/LocaleToScriptMapping.cpp:45 >> + ASSERT_UNDER_CONSTEXPR_CONTEXT(length <= sizeof(ResultType)); > > Since we’re doing assertions like this, how about asserting the terminator is the null character? Added. >> Source/WebCore/platform/text/LocaleToScriptMapping.cpp:48 >> + uint8_t code = static_cast<uint8_t>(string[index]); > > Seems like we could have code be "ResultType" instead of uint8_t and avoid the static_cast on the next line of code. I would like to first cast it from char to uint8_t to ensure that we are handling unsigned types, and avoid accidental sign-extension. >> Source/WebCore/platform/text/LocaleToScriptMapping.cpp:49 >> + result |= (static_cast<ResultType>(code) << ((sizeof(ResultType) - index - 1) * 8)); > > I think this has one set of parentheses that aren’t needed for clarity or correctness, the outermost set. Removed. >> Source/WebCore/platform/text/LocaleToScriptMapping.cpp:64 >> + result |= (static_cast<ResultType>(toASCIILower(code)) << ((sizeof(ResultType) - index - 1) * 8)); > > I think this has one set of parentheses that aren’t needed for clarity or correctness, the outermost set. Removed. >> Source/WebCore/platform/text/LocaleToScriptMapping.cpp:82 >> + { parseConstantScriptCode<ScriptName>("arab"), USCRIPT_ARABIC }, > > I think we’re going to be able to make a fancier version of this where you don’t have to write the calls to parseConstantScriptCode because it’s all done by the constexpr constructor of an object. Even better, I think it can encapsulate the implementation detail of the "parsing into an integer" and just take a couple of function arguments, and also make it easier to correctly call the binary search function. > > Just refactoring! But should be more elegant. > > And maybe have a version where we store const char* rather than a fixed size item in the table but otherwise it’s similar, and uses the same template just with different arguments. Depending on what other places in WebKit need. I've added PackedASCIILowerCodes<T> which encapsulate them.
Created attachment 426372 [details] Patch
Committed r276225 (236707@main): <https://commits.webkit.org/236707@main>
Comment on attachment 426368 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=426368&action=review >>> Source/WebCore/platform/text/LocaleToScriptMapping.cpp:48 >>> + uint8_t code = static_cast<uint8_t>(string[index]); >> >> Seems like we could have code be "ResultType" instead of uint8_t and avoid the static_cast on the next line of code. > > I would like to first cast it from char to uint8_t to ensure that we are handling unsigned types, and avoid accidental sign-extension. Yes, I agree. We would cast it with the static_cast as we are doing here and then have a local variable be of type ResultType which would achieve exactly what you were talking about.
rdar://76809872