647367 - rm jshash.h and remaining uses

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Luke Wagner [:luke]]

Almost all uses of the bucket-based hash table have been removed save 3.  We could numHashTableImplementations-- if these last 3 were finished off.

Comment 1

[Luke Wagner [:luke]]

Whoa, JSAtomList and JSHashTable are rather intertwined.  That one is non-trivial.

Comment 2

[Chris Leary [:cdleary] (not checking bugmail)]

(In reply to comment #1)
> Whoa, JSAtomList and JSHashTable are rather intertwined.  That one is
> non-trivial.

No kidding! The JSAtomList starts off as a linked list of JSHashEntry (which is effectively just a generic linked list node). Once the list hits critical mass the JSAtomList table-ifies with explicitly managed stable ordering of the entries during the transition.

JSAtomList's implementation manages the hash table's guts to be a multimap with special properties: a lookup that hits causes a node to be moved to the front of the hash chain; hoisted definition nodes are added at the end of the hash chain; any number of shadowed definitions can coexist in a single hash bucket.

I'm mulling over a few solutions.

Comment 3

[Luke Wagner [:luke]]

Wow.  Well, if you are going break an abstraction, might as well break the hell out of it!

Comment 4

[Chris Leary [:cdleary] (not checking bugmail)]

billm's taking care of the scripFilenameTable use in bug 661903 and jorendorff is self-hosting sharp var support in bug 486643. There's one more minor usage in traceviz that follows the same form as the script filename table. When billm's patch lands we can generalize a CStringHasher.

Now we wait.

Comment 5

[Chris Leary [:cdleary] (not checking bugmail)]

Attachment: WIP: rm jshash.h

Decided to see if I could remove jshash in the engine. Only took about an hour. JS binary goes down by ~20K. However, there are still some uses in jsd! That's for another day.

Comment 6

[Nicholas Nethercote [inactive]]

Attachment: Sequester jshash.{h,cpp} in js/jsd/.

The removal of sharps made this a lot easier.

Although js/src/ barely uses jshash.{h,cpp}, js/jsd/ still does.  So I just
moved those files into js/jsd/.  (I'm not sure if that'll show up in
Bugzilla's nicely-formatted patch viewers.)  I figure this is a win because
I have a notion that js/jsd/ is headed for the scrap-heap -- is that right?
And even if it's not, this greatly reduces the visibility of those files.

A few things from those moved files were used in js/src/ and
js/xpconnect/src/.  Here's what I did with them:

- I replaced JSHashNumber with js::HashNumber;  they're both typedefs of
  uint32_t.

- I moved JS_HashString, which has a single use, into jsstr.{h,cpp}.

- I inlined the single use of JS_GOLDEN_RATIO.

- And I removed ATOM_HASH because it is dead code.

Comment 7

[Luke Wagner [:luke]]

Comment on attachment 643259 [details] [diff] [review]
Sequester jshash.{h,cpp} in js/jsd/.

Review of attachment 643259 [details] [diff] [review]:
-----------------------------------------------------------------

Sweet!  I agree with your reasoning on it to jsd.

::: js/src/jsatom.h
@@ +100,5 @@
>  #endif
> +
> +    static const js::HashNumber goldenRatio = 0x9E3779B9U;
> +
> +    return n * goldenRatio;

Even better, I think you could replace the body with:

  return HashGeneric((void *)JSID_BITS(id));

from mozilla/HashFunctions.h.  (This (void *) wouldn't be necessary if you added a AddToHash(uint32_t hash, uint64_t value) overload to HashFunctions.h.)

::: js/src/jsstr.h
@@ +18,5 @@
>  #include "vm/Unicode.h"
>  
> +/* General-purpose C string hash function. */
> +extern JS_PUBLIC_API(js::HashNumber)
> +JS_HashString(const void *key);

I think you kept this around for the 1 use in ScriptFilenameHasher.  For that, you could use HashString in mozilla/HashFunctions.h instead.  With that change, I think you could kill JS_HashString and make it a non-public extern in jsd.

Comment 8

[Nicholas Nethercote [inactive]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/61d052e202c8

Comment 9

[Ryan VanderMeulen [:RyanVM]]

http://mozillamemes.tumblr.com/post/21637966463/yes-i-have-a-condition-that-forces-me-to-insert

Sorry, but this caused Windows bustage, so I had to back it out.
https://hg.mozilla.org/integration/mozilla-inbound/rev/2fcb28092c13

https://tbpl.mozilla.org/php/getParsedLog.php?id=13654674&tree=Mozilla-Inbound

e:/builds/moz2_slave/m-in-w32/build/js/jsd/jshash.cpp(68) : error C2491: 'JS_NewHashTable' : definition of dllimport function not allowed

e:/builds/moz2_slave/m-in-w32/build/js/jsd/jshash.cpp(106) : error C2491: 'JS_HashTableDestroy' : definition of dllimport function not allowed

e:/builds/moz2_slave/m-in-w32/build/js/jsd/jshash.cpp(138) : error C2491: 'JS_HashTableRawLookup' : definition of dllimport function not allowed

e:/builds/moz2_slave/m-in-w32/build/js/jsd/jshash.cpp(218) : error C2491: 'JS_HashTableRawAdd' : definition of dllimport function not allowed

e:/builds/moz2_slave/m-in-w32/build/js/jsd/jshash.cpp(248) : error C2491: 'JS_HashTableAdd' : definition of dllimport function not allowed

e:/builds/moz2_slave/m-in-w32/build/js/jsd/jshash.cpp(270) : error C2491: 'JS_HashTableRawRemove' : definition of dllimport function not allowed

e:/builds/moz2_slave/m-in-w32/build/js/jsd/jshash.cpp(288) : error C2491: 'JS_HashTableRemove' : definition of dllimport function not allowed

e:/builds/moz2_slave/m-in-w32/build/js/jsd/jshash.cpp(304) : error C2491: 'JS_HashTableLookup' : definition of dllimport function not allowed

e:/builds/moz2_slave/m-in-w32/build/js/jsd/jshash.cpp(323) : error C2491: 'JS_HashTableEnumerateEntries' : definition of dllimport function not allowed

e:/builds/moz2_slave/m-in-w32/build/js/jsd/jshash.cpp(418) : error C2491: 'JS_HashTableDump' : definition of dllimport function not allowed

e:/builds/moz2_slave/m-in-w32/build/js/jsd/jshash.cpp(430) : error C2491: 'JS_HashString' : definition of dllimport function not allowed

e:/builds/moz2_slave/m-in-w32/build/js/jsd/jshash.cpp(442) : error C2491: 'JS_CompareValues' : definition of dllimport function not allowed

Comment 10

[Nicholas Nethercote [inactive]]

Second attempt:

https://hg.mozilla.org/integration/mozilla-inbound/rev/3c589e94b3e0

Comment 11

[Ed Morley [:emorley]]

https://hg.mozilla.org/mozilla-central/rev/3c589e94b3e0

Comment 12

[Luke Wagner [:luke]]

\o/