899834 - Use a better hash function for the atoms table

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Nicholas Nethercote [inactive]]

Attachment: Cachegrind data for Unreal

Large Emscripten-generated asm.js files contain *many* identifiers.  Even 
though Emscripten uses 1 and 2 char identifiers -- which get statically 
pre-atomized -- as much as possible, identifier atomization still dominates.

I've attached function-level Cachegrind output for calling the shell's parse() function on the Unreal demo, which is 55 MB of code.  If you sum up all the functions relating to atomization, it's almost a quarter of the instructions executed.

And it turns out that using a better hash function for the atoms table helps a lot.

Comment 1

[Nicholas Nethercote [inactive]]

Attachment: Use a better hash function for the atoms table.

Instruction count improvements:

- Unreal:    1.178x
- Parsemark: 0.999x
- Sunspider: 0.997x

The time improvement for Unreal is about 1.15x, and there's negligible time
change for Sunspider and Parsemark.

So it's a slight pessimization for non-huge, non-Emscripten code.  I guess the
more expensive hash function doesn't pay for itself until the atoms table gets
to a certain size.  Seems like a decent trade-off to me, though.

Comment 2

[Luke Wagner [:luke]]

Another interesting experiment would be to mess with the load factor of the hash table.  You can change this via the sMaxAlphaFrac constant.  The open-addressing scheme we use suffers disproportionally more from collisions than a bucket-based scheme and I've been wondering for a while if we should play with this.  Of course, it'll waste more memory, so if this did end up helping we could make it a parameter instead of a constant.

Comment 3

[Nicholas Nethercote [inactive]]

I tried changing the max load factor to 0.5 (changing sMaxAlphaFrac *and* sInvMaxAlpha).  Instruction count improvements (including the hash function patch):

- Unreal:    1.208x
- Parsemark: 1.009x
- Sunspider: 0.997x

So a bit better for Unreal and Parsemark, but my gut says it's not worth the extra memory.

Comment 4

[Luke Wagner [:luke]]

Thanks for trying!

Comment 5

[Marty Rosenberg [:mjrosenb]]

Just tried this patch on my chromebook and parsing the unreal code:
before: 9.18user 1.68system 0:11.12elapsed 97%CPU (0avgtext+0avgdata 1016784maxresident)k
after: 7.48user 1.83system 0:09.44elapsed 98%CPU (0avgtext+0avgdata 1016780maxresident)k
which is a 22.7% improvement. Will try to figure outmemory issues, then re-run and also give numbers for a pandaboard.

I haven't tried running this with cachegrind yet.

Comment 6

[Nicholas Nethercote [inactive]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/bad4a1691369

Comment 7

[Ed Morley [:emorley]]

https://hg.mozilla.org/mozilla-central/rev/bad4a1691369

Comment 8

[Matt Brubeck (:mbrubeck)]

It looks like this patch may have caused a regression in the Dromaeo CSS benchmark:
https://groups.google.com/d/topic/mozilla.dev.tree-management/DsP-bRn0CfM/discussion

Comment 9

[Nicholas Nethercote [inactive]]

Backout:
https://hg.mozilla.org/integration/mozilla-inbound/rev/badfeeb91254

Comment 10

[Nicholas Nethercote [inactive]]

Mercurial gave me "bad" as the start of both revision ids... this bug is clearly cursed.

Comment 11

[Matt Brubeck (:mbrubeck)]

The backout didn't have a noticeable effect on any benchmarks, so I think I was wrong about the regression in comment 8, and this patch can re-land.  Sorry!

Comment 12

[Nicholas Nethercote [inactive]]

> The backout didn't have a noticeable effect on any benchmarks, so I think I
> was wrong about the regression in comment 8, and this patch can re-land. 
> Sorry!

Thanks for the prompt follow-up!  Re-landed:
https://hg.mozilla.org/integration/mozilla-inbound/rev/e106a8c9ac8c

Comment 13

[Ed Morley [:emorley]]

https://hg.mozilla.org/mozilla-central/rev/e106a8c9ac8c

Comment 14

[Nicholas Nethercote [inactive]]

It was too good to be true.  Instead of using parse(), I change my measurement methodology to just run the UDKGame-Browser-Shipping.js until it craps out (which is enough for asm.js parsing to finish).  That takes about 4x longer than just calling parse(), but the instruction count reduction from the better hash function is reduced to a mere 1.002x :(

In better news, I now have Cachegrind results for the entire asm.js compilation phase, which I've filed in bug 901407.