Bug 236532 – look up InputTypeFactoryMap with an ASCII lowercase string instead of using a ASCIICaseInsensitiveHash

• Status: RESOLVED
• Resolution: FIXED
• Component: DOM

[Cameron McCormack (:heycam)]

InputType::create looks up the InputTypeFactoryMap based on the AtomString value of the <input type> attribute.  The HashMap uses an ASCIICaseInsensitiveHash, but the AtomStrings stored in the map are all ASCII lowercase to begin with.  This means that we spend time doing an ASCII case insensitive hash computation on the query string.  Most content already supplies an ASCII lowercase type value, so it's less work to ASCII lowercase the type value and then look up the HashMap using the regular hash for AtomStrings (i.e., pulling the hash out of AtomString).

Doing this is a 0.5% improvement on a couple of Speedometer 2 subtests, and a 0.1% improvement to the overall score.

[Cameron McCormack (:heycam)]

Created attachment 451754 [details]
Patch

[EWS]

Committed r289691 (247176@main): <https://commits.webkit.org/247176@main>

All reviewed patches have been landed. Closing bug and clearing flags on attachment 451754 [details].

[Radar WebKit Bug Importer]

<rdar://problem/88855498>

[Darin Adler]

Comment on attachment 451754 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=451754&action=review

> Source/WebCore/ChangeLog:3
> +        Look up InputTypeFactoryMap with an ASCII lowercase string instead of using a ASCIICaseInsensitiveHash

This seems like a great speedup, but if the cost is the hash computation there’s another approach we could have taken: We can change ASCIICaseInsensitiveHash::hash(StringImpl&) to check if there are any ASCII uppercase characters. If there are none, then it can use string.hash(). If we do this, it would optimize *all* uses of ASCIICaseInsensitiveHash that are typically used on already-lowercase strings. However, if the optimization here benefits from other savings as well, then perhaps my suggestion would not work as well as this did.

What do you think, Cameron?

[Cameron McCormack (:heycam)]

(In reply to Darin Adler from comment #4)
> This seems like a great speedup, but if the cost is the hash computation
> there’s another approach we could have taken: We can change
> ASCIICaseInsensitiveHash::hash(StringImpl&) to check if there are any ASCII
> uppercase characters. If there are none, then it can use string.hash(). If
> we do this, it would optimize *all* uses of ASCIICaseInsensitiveHash that
> are typically used on already-lowercase strings. However, if the
> optimization here benefits from other savings as well, then perhaps my
> suggestion would not work as well as this did.
> 
> What do you think, Cameron?

Nice idea, and I think it is worth trying that out.  In this particular case, I think it's still advantageous to move away from ASCIICaseInsensitiveHash, as it allows us to skip hashing the key upon insertion too (in createInputTypeFactoryMap).

Is it possible to configure HashMap in a way that hashing of keys on insertion is done differently from hashing of keys passed when looking up the map?

[Cameron McCormack (:heycam)]

Maybe we would only want to make your suggested ASCIICaseInsensitiveHash change if we were sure that all performance critical uses of ASCIICaseInsensitiveHash and AtomStrings tend to get called with already ASCII lowercase strings.

Or we could have a different hash trait type which means "compute an ASCII case insensitive hash but the string probably is already ASCII case insensitive".

[Darin Adler]

On reflection, I think I have a better idea. We should use SortedArrayMap instead of HashMap for InputType::create. Then there will be no hashing at all. I suspect it can match or exceed the speed of the HashMap; I believe the list is short enough that it will be a linear search, but maybe big enough for binary. Because this is not a dynamic data structure, but rather something that can be initialized at compile time, SortedArrayMap should be good.

I've learned to never doubt the speed one can get from hashing, so there is a slim chance that won't work, though!

(In reply to Cameron McCormack (:heycam) from comment #5)
> Nice idea, and I think it is worth trying that out.  In this particular
> case, I think it's still advantageous to move away from
> ASCIICaseInsensitiveHash, as it allows us to skip hashing the key upon
> insertion too (in createInputTypeFactoryMap).

Sorry, I don’t understand this.

As far as I can tell, neither the solution you implemented nor the ASCIICaseInsensitiveHash::hash solution I suggested will involve any extra hashing on insertion. In both cases, we detect that the String is already all lowercase, and use the hash stored in the String.

In the solution you implemented, we are relying on knowing that there are no ASCII uppercase characters in the string and so it uses String::hash.

In the solution I suggested, the hash table add function will call the ASCIICaseInsensitiveHash::hash function. That function will detect that the String lacks uppercase ASCII characters and then it will call String::hash.

It’s true that my suggestion incurs an "are there any uppercase ASCII letters" check on each string during insertion that yours did not, but no additional hashing.

> Is it possible to configure HashMap in a way that hashing of keys on
> insertion is done differently from hashing of keys passed when looking up
> the map?

I don’t think that’s needed here, but if we wanted to use it, the answer is yes.

HashMap provides HashTranslator versions of the functions find, contains, get, inlineGet, and add, and in all of these we can use a different type that hashes differently by providing HashTranslator traits.

This could be used to make a version of add that already knows there are no uppercase ASCII letters, and thus optimize the hash table building process. But that’s not an important optimization for a function that runs once, I don’t think.

If the speed of building the table matters at all, then my SortedArrayMap idea becomes even better, because the map is built at compile/load time, not at runtime.

[Darin Adler]

(In reply to Cameron McCormack (:heycam) from comment #6)
> Maybe we would only want to make your suggested ASCIICaseInsensitiveHash
> change if we were sure that all performance critical uses of
> ASCIICaseInsensitiveHash and AtomStrings tend to get called with already
> ASCII lowercase strings.
> 
> Or we could have a different hash trait type which means "compute an ASCII
> case insensitive hash but the string probably is already ASCII case
> insensitive".

I see your point.

If there are places where we use ASCIICaseInsensitiveHash, but the strings often have some uppercase ASCII letters in them, then the extra checking would be wasteful.

But since this check is quite inexpensive compared to the hash computation, I am guessing we wouldn’t need two differently tuned versions.

[Darin Adler]

One other thought: If this is so hot that all that hash computation is significant, maybe we also want to make a histogram and find out what values are actually used in practice and add special cases for the hottest most common values:

    if (string == "text")
        <do the thing and don't even bother with any fancy data structure>

Adding a case like this could speed things up further! All depends on this really being super-hot.

[Darin Adler]

I think I like SortedArrayMap best of the above ideas.

But also, we should probably think about the ASCIICaseInsensitiveHash optimization for the benefit of the other uses of it. I bet it will be a net win, maybe there are even other places where we can see a measurable speedup on some benchmark.