If you think a bug might affect users in the 57 release, please set the correct tracking and status flags for Release Management.

Can we re-order elements in read-mostly JS HashTables to minimize probes?

NEW
Unassigned

Status

()

Core
JavaScript Engine
6 years ago
3 years ago

People

(Reporter: Justin Lebar (not reading bugmail), Unassigned)

Tracking

Firefox Tracking Flags

(Not tracked)

Details

(Reporter)

Description

6 years ago
Splitting off from bug 729940 comment 68:

I've noticed in running V8 that the compartment->initialShapes hashtable is by far the hottest JS HashTable in Gecko.  I've further noticed that its |stats.steps| value varies by a factor of 3 between the min and max I've observed, even as the hashtable's other stats stay constant.

What I think is happening is that a hot shape is getting stuck behind a cold shape (or maybe even a remove()'d entry) in the hashtable.  Once this happens, we're stuck with it until we rehash.

But what we could do instead is, on successful lookup, move the looked up entry forward in the logical hash chain, so the next time we look it up, we'll take one fewer step.  This might end up being a net loss, particularly if two hot entries lie on the same logical chain, but it could be a net win.

I'm a total JS engine newb, so let me know if this is a dumb idea...
(Reporter)

Comment 1

6 years ago
This really messes up:

 * const correctness
 * that you can hold a pointer into the hashtable between calls to lookup()

so we probably wouldn't want to enable it for all hashtables.
(Reporter)

Comment 2

6 years ago
An alternative would be to place a small one-way set associative cache in front of the hashtable.  This should be easy, but it's hard to say if it would be as fast as re-ordering the elements.  Probably depends on the usage pattern...

Comment 3

6 years ago
For the most part, we try not to spend significant time doing VM things like hash-table lookups.  (For V8, I'm suspecting closure and call object creation; those should be jitted (thereby avoiding the hash table lookup) soonish.)  What % of total time in V8 is spent doing hash table lookups in initialShapes?

Another thing to play with is bumping sMaxAlphaFrac to decrease the load on hash tables.  (This is currently a HashTable-wide constant, but it could be made per-table.)  The general idea of lookup reordering elements doesn't sound awful, but it is extra complexity (and a slight slow-down when the optimization doesn't apply) so I'd like to know it was really necessary.
(Reporter)

Comment 4

6 years ago
> Another thing to play with is bumping sMaxAlphaFrac to decrease the load on hash tables.

I tried this without much success.  It may have reduced the worst-case number of steps (hard to say without running the benchmark many times), but I still saw high variance between runs.

> What % of total time in V8 is spent doing hash table lookups in initialShapes?

I'm building for this now, but as background: Changing the hash functions in InitialShapeEntry and StackBaseShape got me a 1.5% slowdown on Dromaeo jslib across multiple platforms (and a V8 slowdown, I believe, although I'm not 100% confident in the methodology Talos is using).  This is despite the fact that the new hash function has fewer collisions than the old one (bug 729940 comment 60).

The only way I can think to explain this is:

1) The hash function is hot code, and the new one runs slower (perf says the hashfn code is not hot, bug 729940 comment 66), or

2) The hashtable lookup is hot and somehow made slower by the different hash codes.

My current guess is that somehow the new hash codes tickle the hashtable into hitting its worse-case collision behavior.  I'd be kind of surprised if this were true, though, since the regression appears on multiple platforms.
(Reporter)

Comment 5

6 years ago
> What % of total time in V8 is spent doing hash table lookups in initialShapes?

If I annotate lookup with MOZ_NEVER_INLINE, I see three lookup's in the profile:

0.43%  js::detail::HashTable<js::ReadBarriered<js::types::TypeObject> const, js::HashSet<js::ReadBarriered<js::types::TypeObject>, js::types::TypeObjectEntry, js::SystemAllocPolicy>::SetOps, js::SystemAllocPolicy>::lookup(JSObject* const&, unsigned int, unsigned int) const

0.13%  js::detail::HashTable<js::Shape* const, js::HashSet<js::Shape*, js::ShapeHasher, js::SystemAllocPolicy>::SetOps, js::SystemAllocPolicy>::lookup(js::StackShape const&, unsigned int, unsigned int) const

0.01%  js::detail::HashTable<js::gc::Chunk* const, js::HashSet<js::gc::Chunk*, js::GCChunkHasher, js::SystemAllocPolicy>::SetOps, js::SystemAllocPolicy>::lookup(js::gc::Chunk* const&, unsigned int, unsigned int) const
(Reporter)

Comment 6

6 years ago
I pushed a one-element cache to try for grins.  It definitely reduces the number of |steps| in  The Big Hashtable (by a factor of 20 or so), although the data in comment 5 suggests this shouldn't be a big deal.

[1] https://tbpl.mozilla.org/?tree=Try&rev=8582586cc05b

Comment 7

6 years ago
Try run for 8582586cc05b is complete.
Detailed breakdown of the results available here:
	https://tbpl.mozilla.org/?tree=Try&rev=8582586cc05b
Results (out of 210 total builds):
    exception: 3
    success: 180
    warnings: 22
    failure: 5
Builds (or logs if builds failed) available at:
http://ftp.mozilla.org/pub/mozilla.org/firefox/try-builds/jlebar@mozilla.com-8582586cc05b

Comment 8

6 years ago
Try run for 8582586cc05b is complete.
Detailed breakdown of the results available here:
	https://tbpl.mozilla.org/?tree=Try&rev=8582586cc05b
Results (out of 220 total builds):
    exception: 3
    success: 190
    warnings: 22
    failure: 5
Builds (or logs if builds failed) available at:
http://ftp.mozilla.org/pub/mozilla.org/firefox/try-builds/jlebar@mozilla.com-8582586cc05b
(Reporter)

Comment 9

6 years ago
> Try run for 8582586cc05b is complete.

Yeah, that didn't seem to help at all.
(Reporter)

Comment 10

6 years ago
> If I annotate lookup with MOZ_NEVER_INLINE, I see three lookup's in the profile:

It could be that the hashtable lookup is a greater percentage of one of the benchmark sections than the others.  If that section is weighted more heavily in the overall score (V8 uses a harmonic mean), that could inflate the importance of the hash lookup.
(Reporter)

Comment 11

6 years ago
Hashtable lookup percentages broken down by v8 sub-benchmark.  The TypeObject hashtable is particularly hot in RayTrace, but aside from that, it looks like there's little to be gained here.

Richards: None

DeltaBlue:

  0.36% HashTable<ReadBarriered<TypeObject>>::lookup
  0.30% HashTable<Shape*>::lookup
  0.04% HashTable<gc::Chunk*>::lookup

Crypto:

  0.03% HashTable<Shape*>::lookup
  0.02% HashTable<HashMapEntry<void*, RootInfo>>::lookup
  0.01% HashTable<ReadBarriered<TypeObject>>::lookup

RayTrace:

  1.67% HashTable<ReadBarriered<TypeObject>>::lookup

Earley-Boyer:

  0.27% HashTable<Shape*>::lookup
  0.18% HashTable<ReadBarriered<TypeObject>>::lookup

RegExp:

  0.19% HashTable<Shape*>::lookup
  0.04% HashTable<ReadBarriered<TypeObject>>::lookup
  0.03% HashTable<gc::Chunk*>::lookup
  0.01% HashTable<HashMapEntry<void*, RootInfo>>::lookup

Splay:

  0.18% HashTable<ReadBarriered<TypeObject>>::lookup
  0.03% HashTable<gc::Chunk*>::lookup
(Reporter)

Comment 12

6 years ago
> RayTrace:
>   1.67% HashTable<ReadBarriered<TypeObject>>::lookup

This 1.67% comes 90% from callstack

  JSObject::getNewType
  js_CreateThisForFunctionWithProto
  js::mjit::stubs::CreateThis

and 10% from callstack

  js_CreateThisForFunctionWithProto
  js::mjit::stubs::CreateThis.

Is this path what you said in comment 3 will be jit'ed soon?

Comment 13

6 years ago
Nope.  I thought CreateThis was (usually) inlined.  There seem to be a few things that turn off the inlining (non-singleton ctor, prototype, bad type info).  Brian: is this that goofy constructor pattern in raytrace?
CreateThis is currently inlined only for monomorphic sites, e.g. the object being created always has the same prototype, initial shape, etc.  That won't hold for the raytrace constructor pattern (will get fixed sometime down the road).
(Assignee)

Updated

3 years ago
Assignee: general → nobody
You need to log in before you can comment on or make changes to this bug.