1098618 - Use a smaller initial IdSet size in jsiter.cpp:Snapshot()

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Nicholas Nethercote [inactive]]

jseward identified the following issue with Valgrind's DHAT tool: the IdSet in Snapshot() is given an initial length of 32, which results in a capacity of 64. But most of the time that's much bigger than necessary.

Here are the top 20 "count / capacity" frequencies when the table is destroyed.
This is from a run of http://gregor-wagner.com/tmp/mem50.

> (  1)   208975 (81.2%, 81.2%): len = 0 / 64
> (  2)    14135 ( 5.5%, 86.7%): len = 1 / 64
> (  3)     5940 ( 2.3%, 89.0%): len = 2 / 64
> (  4)     4730 ( 1.8%, 90.9%): len = 3 / 64
> (  5)     3483 ( 1.4%, 92.2%): len = 5 / 64
> (  6)     2742 ( 1.1%, 93.3%): len = 4 / 64
> (  7)     2262 ( 0.9%, 94.2%): len = 36 / 64
> (  8)     1937 ( 0.8%, 94.9%): len = 6 / 64
> (  9)     1912 ( 0.7%, 95.7%): len = 8 / 64
> ( 10)     1799 ( 0.7%, 96.4%): len = 7 / 64
> ( 11)      666 ( 0.3%, 96.6%): len = 35 / 64
> ( 12)      635 ( 0.2%, 96.9%): len = 9 / 64
> ( 13)      593 ( 0.2%, 97.1%): len = 10 / 64
> ( 14)      471 ( 0.2%, 97.3%): len = 12 / 64
> ( 15)      452 ( 0.2%, 97.5%): len = 16 / 64
> ( 16)      420 ( 0.2%, 97.6%): len = 78 / 128
> ( 17)      385 ( 0.1%, 97.8%): len = 21 / 64
> ( 18)      364 ( 0.1%, 97.9%): len = 15 / 64
> ( 19)      362 ( 0.1%, 98.1%): len = 97 / 256
> ( 20)      333 ( 0.1%, 98.2%): len = 14 / 64

90.9% of the time the length is <= 3, which requires a capacity of 4 (due to
the 0.75 max load factor in js::HashTable).

94.1% of the time the length is <= 6, which requires a capacity of 8.

Knowing that, I think an initial capacity of 4 is fine.

Comment 1

[Nicholas Nethercote [inactive]]

Attachment: Use a smaller initial IdSet size in jsiter.cpp:Snapshot()

The new histogram looks much nicer:

> (  1)   163131 (74.8%, 74.8%): len = 0 / 4
> (  2)    16573 ( 7.6%, 82.4%): len = 1 / 4
> (  3)     7435 ( 3.4%, 85.8%): len = 2 / 4
> (  4)     4800 ( 2.2%, 88.0%): len = 3 / 4
> (  5)     3404 ( 1.6%, 89.6%): len = 5 / 8
> (  6)     3012 ( 1.4%, 91.0%): len = 4 / 8
> (  7)     2724 ( 1.2%, 92.2%): len = 36 / 64
> (  8)     2204 ( 1.0%, 93.3%): len = 7 / 16
> (  9)     1970 ( 0.9%, 94.2%): len = 6 / 8
> ( 10)     1724 ( 0.8%, 94.9%): len = 8 / 16
> ( 11)     1249 ( 0.6%, 95.5%): len = 9 / 16
> ( 12)     1235 ( 0.6%, 96.1%): len = 10 / 16
> ( 13)      692 ( 0.3%, 96.4%): len = 35 / 64
> ( 14)      630 ( 0.3%, 96.7%): len = 16 / 32
> ( 15)      629 ( 0.3%, 97.0%): len = 12 / 16
> ( 16)      486 ( 0.2%, 97.2%): len = 37 / 64
> ( 17)      453 ( 0.2%, 97.4%): len = 97 / 256
> ( 18)      435 ( 0.2%, 97.6%): len = 15 / 32
> ( 19)      361 ( 0.2%, 97.8%): len = 14 / 32
> ( 20)      326 ( 0.1%, 97.9%): len = 11 / 16

You can't see it from this histogram, but I computed that cumulative
allocations are reduced by ~7x.

Comment 2

[Nicholas Nethercote [inactive]]

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

Comment 3

[Carsten Book [:Tomcat]]

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