562809 - js::HashTable::init(n) should guarantee success of next 'n' add()s

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[[e-mail]]

http://mxr.mozilla.org/mozilla-central/source/js/src/jshashtable.h#290

Currently it rounds 'n' up to the nearest power of 2, and sizes the hash thusly. But when add()ing an element, alpha gets involved, which may result in an appropriately-presized hash being expanded.

It would be nice if init() took alpha into account, such that those 'n' add()s could be guaranteed.

Comment 1

[Brendan Eich [:brendan]]

I was wrong on IRC, this is the same as JS_DHashTableInit. The parameter name is capacity, so rounding up to power of two is the right thing given the meaning of the parameter. Callers use JS_DHASH_DEFAULT_CAPACITY(n) where n is the number of initial entries.

Looking back, this seems silly to foist off on all callers. I may have been thinking that Init would be called with a guess at capacity rather than an exact (or simpler better guess at) number of initial or near-term entries. Anyway, if jshashtable.h takes the more usable route, please document the difference.

We should try to retire jsdhash/pldhash at some point, in favor of jshashtable. I remember Luke worrying about template bloat, but let's find out how bad of a problem that is.

/be

Comment 2

[[e-mail]]

Attachment: patch

Uses a statically defined sInvMaxAlpha. I went with a << 7 shift, rather than 8, to keep it fitting in a uint8. (Which is useful so that the max table size of 2^24 is still achievable.)

Comment 3

[Luke Wagner [:luke]]

Comment on attachment 443691 [details] [diff] [review]
patch

Looks good, thanks!

>+        /* Correct for sMaxAlphaFrac such that the table will not resize
>+           when adding 'length' entries. */

Nit: SM does:

 /*
  * comments
  */

Comment 4

[[e-mail]]

Comment on attachment 443691 [details] [diff] [review]
patch

http://hg.mozilla.org/tracemonkey/rev/2cc1ad9809b2

Comment 5

[Robert Sayre]

http://hg.mozilla.org/mozilla-central/rev/2cc1ad9809b2