Bug 224727 – Use binary-search in LocaleToScriptMapping

• Component: New Bugs
• Status: RESOLVED FIXED

[Yusuke Suzuki]

Use binary-search in LocaleToScriptMapping

[Yusuke Suzuki]

Created attachment 426363 [details]
Patch

[Darin Adler]

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.

[Yusuke Suzuki]

Created attachment 426364 [details]
Patch

[Darin Adler]

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.

[Darin Adler]

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.

[Yusuke Suzuki]

Created attachment 426366 [details]
Patch

[Yusuke Suzuki]

Ah, the uploaded patch is simply adding static_assert based test :)

[Yusuke Suzuki]

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.

[Yusuke Suzuki]

Created attachment 426367 [details]
Patch

[Yusuke Suzuki]

Created attachment 426368 [details]
Patch

[Darin Adler]

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.

[Yusuke Suzuki]

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.

[Yusuke Suzuki]

Created attachment 426372 [details]
Patch

[Yusuke Suzuki]

Committed r276225 (236707@main): <https://commits.webkit.org/236707@main>

[Darin Adler]

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.

[Ryan Haddad]

rdar://76809872