697646 - Don't create tiny property tables

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Nicholas Nethercote [inactive]]

Attachment: patch

Small property tables are really common.  Here's a distribution of sizes
with Gmail and TechCrunch open, with the form:

  propTable: entryCount + removedCount / capacity

  ( 1)   2398 (11.8%, 11.8%): propTable: 1, 0 / 16
  ( 2)   2048 (10.1%, 21.9%): propTable: 3, 0 / 16
  ( 3)   1844 ( 9.1%, 31.0%): propTable: 2, 0 / 16
  ( 4)   1832 ( 9.0%, 40.0%): propTable: 0, 0 / 16
  ( 5)   1569 ( 7.7%, 47.8%): propTable: 4, 0 / 16
  ( 6)    964 ( 4.8%, 52.5%): propTable: 5, 0 / 16
  ( 7)    912 ( 4.5%, 57.0%): propTable: 6, 0 / 16
  ( 8)    835 ( 4.1%, 61.1%): propTable: 7, 0 / 16
  ( 9)    605 ( 3.0%, 64.1%): propTable: 8, 0 / 16
  (10)    521 ( 2.6%, 66.7%): propTable: 15, 0 / 32
  (11)    514 ( 2.5%, 69.2%): propTable: 9, 0 / 32
  (12)    430 ( 2.1%, 71.3%): propTable: 10, 0 / 32
  (13)    401 ( 2.0%, 73.3%): propTable: 12, 0 / 32
  (14)    337 ( 1.7%, 74.9%): propTable: 11, 0 / 32
  (15)    261 ( 1.3%, 76.2%): propTable: 14, 0 / 32
  (16)    251 ( 1.2%, 77.5%): propTable: 13, 0 / 32
  (17)    244 ( 1.2%, 78.7%): propTable: 21, 0 / 64
  (18)    232 ( 1.1%, 79.8%): propTable: 19, 0 / 64
  (19)    186 ( 0.9%, 80.7%): propTable: 16, 0 / 32
  (20)    184 ( 0.9%, 81.6%): propTable: 17, 0 / 64

Notice that very small hash tables dominate -- more
than 50% have 5 or fewer entries.  In bug 610070 I changed the heuristic for
the creation of non-dictionary mode property tables to be based on the
number of searches instead of the number of entries.  This was a huge space
win, but we can do even better by not doing it for very small tables as
well.  (I didn't do that in bug 610070 because getting the entry count is
O(n), but I now see that I can stop counting as soon as we exceed the small
threshold.)

The attached patch implements this, so that non-dictionary mode property
tables are only created when there are at least 7 entries.  This reduces the
number of property tables by almost 60%, saving 5 words per table on 32-bit.
And the total number of entries in property tables is reduced by about 20%
-- although most tables are small, big ones unsurprisingly account for more
of the entries.

I also measured SS and V8 times, it has negligible effect, might even be a
tiny win.  I chose 7 based on some Cachegrind profiling, it seemed to be the best value.

(The other thing to notice about the data above is that all the tables are
less than half full.  This is despite the fact that
PropertyTable::needsToGrow uses an alpha of 0.75.  The reason is that
PropertyTable::init always initializes tables as 1/4 to 1/2 full, and table
creation is vastly more common than table growth.  (Julian noticed this in
bug 610070 comment 11.)  And most property tables are for non-dictionary
mode shapes, and so they never grow.  Making tables fuller when created is
easy, but I end up with more collisions, so I'll leave further investigation
for a follow-up bug.)

Comment 1

[Boris Zbarsky [:bzbarsky]]

If the shape is not in dictionary mode, the table can't grow, right?  In that case, would it be worth using a magic value of numLinearSearches (e.g. set the high bit or something) to avoid the walk over the up to 7 entries on each search()?  Or do we figure the walk is cheap enough it's not worth it?

Comment 2

[Nicholas Nethercote [inactive]]

(In reply to Boris Zbarsky (:bz) from comment #1)
> If the shape is not in dictionary mode, the table can't grow, right?  In
> that case, would it be worth using a magic value of numLinearSearches (e.g.
> set the high bit or something) to avoid the walk over the up to 7 entries on
> each search()?  Or do we figure the walk is cheap enough it's not worth it?

We always check first if the shape already has a property table.  The patch doesn't have quite enough context to see that, but look at
http://mxr.mozilla.org/mozilla-central/source/js/src/jsscope.h#711

Does that answer your question?  I'm not certain I've understood what you're asking.

Comment 3

[Boris Zbarsky [:bzbarsky]]

I'm asking what happens for shapes which hit start->numLinearSearches == PropertyTable::MAX_LINEAR_SEARCHES but have PropertyTable::MIN_ENTRIES-1 as the count.  Seems like each search() on the will end up doing two linear walks over the (at most 6) ancestor shapes.  My question was whether trying to eliminate one of those walks is worth worrying about and if so whether it's doable....

Comment 4

[Nicholas Nethercote [inactive]]

Attachment: alternative patch, not used

(In reply to Boris Zbarsky (:bz) from comment #3)
> I'm asking what happens for shapes which hit start->numLinearSearches ==
> PropertyTable::MAX_LINEAR_SEARCHES but have PropertyTable::MIN_ENTRIES-1 as
> the count.  Seems like each search() on the will end up doing two linear
> walks over the (at most 6) ancestor shapes.  My question was whether trying
> to eliminate one of those walks is worth worrying about and if so whether
> it's doable....

It's possible, I wrote an alternative patch, but it was a bit more complex and gave marginally worse instruction counts on Sunspider and V8, so I'll stick with the first patch.  I've attached the alternative patch for posterity.

Comment 5

[Nicholas Nethercote [inactive]]

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

Comment 6

[Ed Morley [:emorley]]

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