Closed Bug 743107 Opened 12 years ago Closed 12 years ago

OrderedHashTable

Categories

(Core :: JavaScript Engine, defect)

Product:
Core
Component:
JavaScript Engine
Version:
Other Branch
Type:
defect
Priority:
Not set
Severity:
normal

Tracking

()

Status:
RESOLVED FIXED
Milestone:
mozilla17

People

(Reporter: jorendorff, Assigned: jorendorff)

References

Details

Attachments

(1 file, 3 obsolete files)

v4
40.72 KB, patch
luke
: review+
Details | Diff | Splinter Review
Attached patch v1 (obsolete) — — Splinter Review 
Yay deterministic hash tables!

This patch makes Map and Set use an OrderedHashTable for storage. It relies on the Map/Set tests (jit-test/tests/collections) for test coverage; please let me know if there's a kind of test that should be added to that suite.

There is a line in here that says
  //e->value = Value(); // wtf GCC
I would like to uncomment that, but I don't understand the error message it gives me when I do. (For Map and Set, it turns out that line doesn't really matter.)

The next step will be to expose Ranges as JS iterators (bug 725909).

The benchmarking I did on this kind of hash table implementation is:
  https://wiki.mozilla.org/User:Jorend/Deterministic_hash_tables
Attachment #612766 - Flags: review?(luke)
Note to myself: the comment on OrderedHashTable::get should explain that the pointer it returns is valid until the next call that changes the count, so the next put() or remove() that actually adds or removes an entry.
Review ping. This is ready to go.
Target Milestone: --- → mozilla14
Version: Other Branch → 15 Branch
Target Milestone: mozilla14 → ---
Version: 15 Branch → Other Branch
I'm terribly sorry for the delay.  This deserves no small amount of time to review and I've been trying to finish off bug 659577 (which blocks IM release).  Nearing the end, but probably not done for a week or so.  Feel free to re-assign review.
Thanks for the note. I think you're the right person for it and it can wait.

If you'd *rather* someone else do it, please feel free to reassign to any passing person who's more enthusiastic about reviewing template patches. :)
Comment on attachment 612766 [details] [diff] [review]
v1

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

A new hash table is a lot to digest, so I'll post this chunk of comments so we can discuss.

Overall, I like how clean and simple the code is, certainly makes reviewing easier!

First thought (already suggested on irc): js::HashMap (HT) and js::OrderedHashMap (OHM) have similar-but-slightly-different functions when going from the result of the hash function to the table index.  Perhaps we could factor out a PrepareHash function (into jsutil.h if not mfbt) that maps (hash-function-result, table-size) -> bucket-index and has a big beefy comment explaining (and encapsulating) the golden ratio funny business.

One overall question is: is this table basically "the table used for Map and not much else" or do we expect to use it more as the need arises.  I'd prefer the later, but it does imply that we should do some more work to make the two hash tables more similar to prevent minimize surprise and mental overhead from having two in the codebase.  A few specific cases are commented below.

Another question:
The performance discussion on the wiki (which I need to reread more slowly) shows OHM faster than HM, which is useful information.  IIUC, OHM adds this boost by having less collisions than HM (the low-level ops seem the same with slight favor to HM for avoiding the indirection on direct hit).  There seem to be two things giving HM more collisions than OHM:
 1. open-addressing has relatively more collisions than bucketing for the same fill ratio (b/c collisions beget more collisions in open-addressing)
 2. the OHM impl has a lower fill ratio than HM
This naturally makes me want to see a more apples-to-apples comparison where OHM and HM have the same fill ratio (open-adressing will still have more collisions due to (1), of course).  Now, since open-addressing stores the elements inline, this would disproportionately increase memory consumption when sizeof(T) is big, but of course, we could use different ratios for different sizeof(T).  That is for a different bug: my main goal here is to know: for small sizeof(T), when HM has the same fill ratio as OHM, how do they compare?

::: js/public/OrderedHashTable.h
@@ +17,5 @@
> +//     are effect-free and consistent); the hashing is a pure performance
> +//     optimization.
> +//
> +//   - Range objects over Ordered tables remain valid even when entries are
> +//     added or removed or the table is resized.

That sounds like it could be useful, but I don't see any uses yet.  Is the goal to handle removing-while-enumerating?  For that specific case, what's wrong with the Range.removeFront strategy used by HashTable?  Admittedly, Range.removeFront is less general, but it allows an element to be removed without re-looking it up.

Another comment on the current Range design: Range moves to the next element if you remove it's current 'front' element.  This initially seems smarter and more friendly but the problem is that it produces a subtle bug when you write:

  for (Range r = ohm.all(); !r.empty(); r.popFront())
    ohm.remove(r.front().key);

Having such a subtle difference between HashMap and OrderedHashMap seems really bad.

@@ +21,5 @@
> +//     added or removed or the table is resized.
> +//
> +//   - The API is a little different, so it's not a drop-in replacement.
> +//     In particular, the hash policy is a little different.
> +//     Also, the Ordered templates lack the Ptr and AddPtr types.

It seems like Ptr could be added w/o too much trouble in the current design, but maybe I'm missing an angle.  The benefits as I see them:
 1. it avoids re-lookup in various situations
 2. it is more consistent with HashTable requiring less total interface knowledge for SM devs
 3. remove(Element) and put(Element) methods can be added as simple helpers

@@ +39,5 @@
> +
> +// detail::OrderedHashTable is the underlying data structure used to implement both
> +// OrderedHashMap and OrderedHashSet. Programs should use one of those two
> +// templates rather than OrderedHashTable.
> +//

A random nit: I noticed that sometimes multi-line comments have this trailing // and sometimes not.  Is this an established style?  If it's not established, I'd prefer we didn't have trailing //.  If it is established, it would be good to identity when and put that in the style wiki and send a group mail.

@@ +173,5 @@
> +        }
> +
> +        *foundp = true;
> +        liveCount--;
> +        Ops::makeEmpty(&e->element);

This is probably a pre-optimization, so feel free to ignore (or maybe add a comment), but a common use of hash tables I've seen/written is LIFO insert/remove.  For that case, can avoid rehashing every N push/pop pairs by noticing that e == &data[dataLength - 1] which allows us to simply destroy the element, decrement dataLength, etc.  I guess since this is a table for web content we can't exactly just measure :)

@@ +295,5 @@
> +    // the fill factor times sizeof(Data) is close to but <= a power of 2.
> +    // This fixed fill factor was chosen to make the size of the data
> +    // array, in bytes, close to a power of two when sizeof(T) is 16.
> +    //
> +    static double fillFactor() { return 8.0 / 3.0; }

Instead of picking a just-so constant which is tuned for a particular sizeof(T), could we instead:
 1. pick a simple fill factor (say, just 2)
 2. have dataCapacity = RoundUpPow2(fillFactor * (hashTableMask + 1)) / sizeof(T)
?

@@ +299,5 @@
> +    static double fillFactor() { return 8.0 / 3.0; }
> +
> +    // The minimum permitted value of (liveCount / dataLength).
> +    // If that ratio drops below this value, we shrink the table.
> +    static double minVectorFill() { return 0.25; }

minDataFill?

@@ +346,5 @@
> +        Data **newHashTable = static_cast<Data **>(alloc.malloc_((newMask + 1) * sizeof(Data *)));
> +        if (!newHashTable)
> +            return false;
> +        for (uint32_t i = 0; i <= newMask; i++)
> +            newHashTable[i] = 0;

s/0/NULL/

@@ +415,5 @@
> +    OrderedHashMap(AllocPolicy ap = AllocPolicy()) : impl(ap) {}
> +    bool init()                                     { return impl.init(); }
> +    uint32_t count() const                          { return impl.count(); }
> +    bool has(const Key &key) const                  { return impl.has(key); }
> +    Range all()                                     { Range r(impl.all()); return r; }

If Range === Impl::Range, why not 'return impl.all()' ?

::: js/src/builtin/MapObject.h
@@ +65,5 @@
>          typedef HashableValue Lookup;
>          static HashNumber hash(const Lookup &v) { return v.hash(); }
>          static bool match(const HashableValue &k, const Lookup &l) { return k.equals(l); }
> +        static bool isEmpty(const HashableValue &v) { return v.value.isMagic(JS_ARRAY_HOLE); }
> +        static void makeEmpty(HashableValue *vp) { vp->value = MagicValue(JS_ARRAY_HOLE); }

Could you add a new JSWhyMagic enumerator instead of reusing JS_ARRAY_HOLE?
I am working on this patch. It has bitrotted a little. I will reply to everything eventually, but to start with:

(In reply to Luke Wagner [:luke] from comment #5)
> One overall question is: is this table basically "the table used for Map and
> not much else" or do we expect to use it more as the need arises.  I'd
> prefer the later, but it does imply that we should do some more work to make
> the two hash tables more similar to prevent minimize surprise and mental
> overhead from having two in the codebase.  A few specific cases are
> commented below.

I think I should just go ahead and do this stuff -- particularly providing Ptr and AddPtr doesn't seem like it'd be too hard.

> know: for small sizeof(T), when HM has the same fill ratio as OHM, how do
> they compare?

We chatted about this today on IRC. I mentioned that fill ratios are naturally different numbers for open-addressing tables (must be <=.8 for reasonable perf) vs. chaining hash tables (must be >=2). But that is a quibble.

The real reason I haven't already done the comparison you're interested in is just that all the table sizes basically have to be powers of 2 (in order to use the OpenTable and CloseTable implementations without making something fancier). If you add a constraint "both tables use the same amount of memory on average" then ISTM the problem becomes overconstrained.

But! There might be a way to adjust only the CloseTable's data table size to be non-power-of-2. I'll look at it if you like -- I'd really rather spend this time on other stuff though.

> ::: js/public/OrderedHashTable.h
> @@ +17,5 @@
> > +//     are effect-free and consistent); the hashing is a pure performance
> > +//     optimization.
> > +//
> > +//   - Range objects over Ordered tables remain valid even when entries are
> > +//     added or removed or the table is resized.
> 
> That sounds like it could be useful, but I don't see any uses yet.  Is the
> goal to handle removing-while-enumerating?  For that specific case, what's
> wrong with the Range.removeFront strategy used by HashTable?  Admittedly,
> Range.removeFront is less general, but it allows an element to be removed
> without re-looking it up.

Iterators will be exposed to script.

> Another comment on the current Range design: Range moves to the next element
> if you remove it's current 'front' element.  This initially seems smarter
> and more friendly but the problem is that it produces a subtle bug when you
> write:
> 
>   for (Range r = ohm.all(); !r.empty(); r.popFront())
>     ohm.remove(r.front().key);
> 
> Having such a subtle difference between HashMap and OrderedHashMap seems
> really bad.

I agree and I think this is a bug in my implementation. Needs a test.

More later.
(In reply to Jason Orendorff [:jorendorff] from comment #6)
> > That sounds like it could be useful, but I don't see any uses yet.  Is the
> > goal to handle removing-while-enumerating?  For that specific case, what's
> > wrong with the Range.removeFront strategy used by HashTable?  Admittedly,
> > Range.removeFront is less general, but it allows an element to be removed
> > without re-looking it up.
> 
> Iterators will be exposed to script.

Ahh, so the OHM::Range instance will live in the GC-thing?  Then I can definitely see why this is necessary.  OTOH, it does make OHM more specific to Map/Set, which suggests making OHM specific and local to builtins/MapObject, as you were saying on irc.  If you do that, I still think it makes sense to factor out a little of the hashing number theory/magic so that it can be reused by all our hash tables.
Attachment #612766 - Flags: review?(luke)
Attached patch WIP 2 (obsolete) — — Splinter Review 
This fixes most of the review comments but not all. Posting this because I posted a patch in bug 725909 that depends on this one.
Assignee: general → jorendorff
Attachment #612766 - Attachment is obsolete: true
Attached patch v3 (obsolete) — — Splinter Review 
> First thought (already suggested on irc): js::HashMap (HT) and
> js::OrderedHashMap (OHM) have similar-but-slightly-different functions
> when going from the result of the hash function to the table index.
> Perhaps we could factor out a PrepareHash function (into jsutil.h if
> not mfbt) that maps (hash-function-result, table-size) -> bucket-index
> and has a big beefy comment explaining (and encapsulating) the golden
> ratio funny business.

Done.

> One overall question is: is this table basically "the table used for
> Map and not much else" or do we expect to use it more as the need
> arises.  I'd prefer the later, but it does imply that we should do
> some more work to make the two hash tables more similar to prevent
> minimize surprise and mental overhead from having two in the codebase.
> A few specific cases are commented below.

Moved to js/src/builtin/OrderedHashTable.h.

We can polish it to match the HashTable API if it ever finds another
user outside js/src.

> ::: js/public/OrderedHashTable.h
> @@ +17,5 @@
> > +//     are effect-free and consistent); the hashing is a pure performance
> > +//     optimization.
> > +//
> > +//   - Range objects over Ordered tables remain valid even when entries are
> > +//     added or removed or the table is resized.
> 
> That sounds like it could be useful, but I don't see any uses yet.  Is
> the goal to handle removing-while-enumerating?  For that specific
> case, what's wrong with the Range.removeFront strategy used by
> HashTable?  Admittedly, Range.removeFront is less general, but it
> allows an element to be removed without re-looking it up.

Yes, it's to handle the Iterator .next() case.

> Another comment on the current Range design: Range moves to the next
> element if you remove it's current 'front' element.  This initially
> seems smarter and more friendly but the problem is that it produces a
> subtle bug when you write:
> 
>   for (Range r = ohm.all(); !r.empty(); r.popFront())
>     ohm.remove(r.front().key);
> 
> Having such a subtle difference between HashMap and OrderedHashMap
> seems really bad.

I ended up keeping this subtle difference, since it's the simplest way
to implement Map and Set iterators (bug 725909). I can go into more
detail on this if you like. It's complicated and probably not a terribly
valuable thing to understand.

I added comments warning about the subtle difference and showing the
workaround.

> > +//   - The API is a little different, so it's not a drop-in replacement.
> > +//     In particular, the hash policy is a little different.
> > +//     Also, the Ordered templates lack the Ptr and AddPtr types.
> 
> It seems like Ptr could be added w/o too much trouble [...]

Totally agree. If we ever make it public, we'll fill out the API.

> A random nit: I noticed that sometimes multi-line comments have this
> trailing // and sometimes not.  Is this an established style?  If it's
> not established, I'd prefer we didn't have trailing //.  If it is
> established, it would be good to identity when and put that in the
> style wiki and send a group mail.

I removed all the extra //'s and converted longer documentation-y
comments to /**/.

> @@ +173,5 @@
> > +        }
> > +
> > +        *foundp = true;
> > +        liveCount--;
> > +        Ops::makeEmpty(&e->element);
> 
> This is probably a pre-optimization, so feel free to ignore (or maybe
> add a comment), but a common use of hash tables I've seen/written is
> LIFO insert/remove.  For that case, can avoid rehashing every N
> push/pop pairs by noticing that e == &data[dataLength - 1] which
> allows us to simply destroy the element, decrement dataLength, etc.  I
> guess since this is a table for web content we can't exactly just
> measure :)

Commented. This made me want to spend a bunch more time on this patch :)
but let's do it later.

> > +    static double minVectorFill() { return 0.25; }
> 
> minDataFill?

Changed.

> > +            newHashTable[i] = 0;
> s/0/NULL/

Done.

> > +    Range all()                                     { Range r(impl.all()); return r; }
> If Range === Impl::Range, why not 'return impl.all()' ?

Done.

> > +        static bool isEmpty(const HashableValue &v) { return v.value.isMagic(JS_ARRAY_HOLE); }
> > +        static void makeEmpty(HashableValue *vp) { vp->value = MagicValue(JS_ARRAY_HOLE); }
> Could you add a new JSWhyMagic enumerator instead of reusing JS_ARRAY_HOLE?

Done.
Attachment #634231 - Attachment is obsolete: true
Attachment #634461 - Flags: review?(luke)
That leaves two comments, both regarding performance. This:

> This naturally makes me want to see a more apples-to-apples comparison
> where OHM and HM have the same fill ratio (open-adressing will still
> have more collisions due to (1), of course).

And this:

> > +    // This fixed fill factor was chosen to make the size of the data
> > +    // array, in bytes, close to a power of two when sizeof(T) is 16.
> > +    static double fillFactor() { return 8.0 / 3.0; }
> 
> Instead of picking a just-so constant which is tuned for a particular sizeof(T), could we instead:
>  1. pick a simple fill factor (say, just 2)
>  2. have dataCapacity = RoundUpPow2(fillFactor * (hashTableMask + 1)) / sizeof(T)
> ?

I think the specific suggestion here goes too far: it would mean that
given the speed on 64-bit platforms, it'd be hard to guess the speed on
32-bit, because the fill factor would be tuned almost exclusively for
efficient use of memory.

It should be tuned for speed first, then to conserve memory.

Anyway--I think this comment calls for the same action as the first one:
try varying fillFactor() and see what happens. Mac has malloc_size() so
I can actually find out how much memory is being wasted.

I hope the review can proceed in parallel. Ping me if not.
Comment on attachment 634461 [details] [diff] [review]
v3

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

Looking good, almost done: a few nits, tweaks, and one non-trivial request.

> Moved to js/src/builtin/OrderedHashTable.h.
> 
> We can polish it to match the HashTable API if it ever finds another
> user outside js/src.

Since this is highly specialized to Map/Set, could we stick it in MapObject.cpp?  I think that properly scopes it; it seems to me that the condition for polishing OHM isn't use outside js/src, it's use outside js/src/builtin/MapObject.cpp.

::: js/public/HashTable.h
@@ +9,5 @@
>  #define jshashtable_h_
>  
>  #include "TemplateLib.h"
>  #include "Utility.h"
> +#include "jsutil.h"

The goal is that the *only* INSTALLED_HEADERS will be in js/public so including js/src/jsutil.h from js/public/HashTable.h works against that goal.  Actually, my comment below suggests hoisting ScrambleHashCode into Utility.h so this #include can be removed as well.

@@ +26,5 @@
>  template <class T, class HashPolicy, class AllocPolicy>
>  class HashTable;
>  
> +template <class T, class Ops, class AllocPolicy>
> +class OrderedHashTable;

Rather than doing this just to share HashMapEntry, can you just create an OrderedHashMapEntry?  There isn't much reuse since the MoveRef and IsPodType hoopla isn't needed for OrderedHashMapEntry.

@@ +38,5 @@
> + * highly nonrandom, given the constraints that this must be deterministic and
> + * quick to compute.
> + */
> +inline HashNumber
> +ScrambleHashCode(HashNumber h)

Thanks, and great comment.  Could you put this in public/Utility.h?

::: js/src/builtin/MapObject.cpp
@@ +170,2 @@
>          }
> +        map->rekeyAll();

I think this is wrong wrt moving GC: HashableValue::mark doesn't update r.front().key in-place so rekeyAll won't see the new keys.  Also, rekeyAll isn't really the right name since it isn't rekeying; it is rehashing the keys which (once you've arranged to update them in-place) are in the wrong place.  This is another good reason to keep OHM local to MapObject.cpp: this is a rather dangerous API whereby the caller updates keys in-place (w/o going through the table's interface).

::: js/src/builtin/OrderedHashTable.h
@@ +418,5 @@
> +    void rehashInPlace() {
> +        for (uint32_t i = 0; i <= hashTableMask; i++)
> +            hashTable[i] = NULL;
> +        Data *wp = data, *end = data + dataLength;
> +        for (Data *rp = data, *end = data + dataLength; rp != end; rp++) {

There is some creepy shadowing of 'end' going on here.  Perhaps you could you rename them to wEnd and rEnd?
Attachment #634461 - Flags: review?(luke)
Blocks: 769504
Attached patch v4 — — Splinter Review 
> Since this is highly specialized to Map/Set, could we stick it in
> MapObject.cpp?  I think that properly scopes it; it seems to me that the
> condition for polishing OHM isn't use outside js/src, it's use outside
> js/src/builtin/MapObject.cpp.

Moved.

I disagree about this code being highly specialized to Map/Set, and that the world is better off with this code hidden away where it can't be conveniently reused, and that ds/*.h is shiny enough that OrderedHashTable would be an embarrassment there, but whatever.

> The goal is that the *only* INSTALLED_HEADERS will be in js/public so
> including js/src/jsutil.h from js/public/HashTable.h works against
> that goal.  Actually, my comment below suggests hoisting
> ScrambleHashCode into Utility.h so this #include can be removed as
> well.

Fixed.

> @@ +26,5 @@
> >  template <class T, class HashPolicy, class AllocPolicy>
> >  class HashTable;
> >  
> > +template <class T, class Ops, class AllocPolicy>
> > +class OrderedHashTable;
> 
> Rather than doing this just to share HashMapEntry, can you just create
> an OrderedHashMapEntry?  There isn't much reuse since the MoveRef and
> IsPodType hoopla isn't needed for OrderedHashMapEntry.

Done. (The MoveRef stuff was necessary. I didn't bother with IsPodType.)

> > +inline HashNumber
> > +ScrambleHashCode(HashNumber h)
> 
> Thanks, and great comment.  Could you put this in public/Utility.h?

Moved.

I had to move JS_ROTATE_LEFT32 into Utility.h as well.

> >          }
> > +        map->rekeyAll();
> 
> I think this is wrong wrt moving GC: HashableValue::mark doesn't
> update r.front().key in-place so rekeyAll won't see the new keys.

Good catch, it was wrong. I rewrote this stuff a bit.

> This is another good reason to keep OHM local to MapObject.cpp: this
> is a rather dangerous API whereby the caller updates keys in-place
> (w/o going through the table's interface).

OK, I removed "rekeyAll()" and implemented marking using a
Range::addFront method, but it still left an ugly spot in the OHT::Range
API: there's a Range::addFrontWithSameHashCode method now. I'll remove
it in bug 769504.

> > +        Data *wp = data, *end = data + dataLength;
> > +        for (Data *rp = data, *end = data + dataLength; rp != end; rp++) {
> 
> There is some creepy shadowing of 'end' going on here.

Yep. Fixed by deleting the inner 'end' variable (it was just leftover code).
Attachment #634461 - Attachment is obsolete: true
Attachment #637928 - Flags: review?(luke)
Summary: OrderedHashTable.h → OrderedHashTable
(In reply to Jason Orendorff [:jorendorff] from comment #12)
> Moved.
> 
> I disagree about this code being highly specialized to Map/Set, and that the
> world is better off with this code hidden away where it can't be
> conveniently reused, and that ds/*.h is shiny enough that OrderedHashTable
> would be an embarrassment there, but whatever.

OHT wouldn't be an embarrassment; it's written really well.  However, if there is actually going to be a reuse outside MapObject, I think there would be two reasons:
 1. it was faster
 2. the caller needed the ordering property

If (1) was the reason, we should re-evaluate the open-addressing scheme (or static load factor, or make the load-factor depend on sizeof(Elem), or make it a dynamic value...) until either HashMap/Set was good enough or we had an argument for a "size-optimized hash table" vs. "space-optimized hash table" or *something* intentional.  Waiting until we have such a use case will be good b/c hopefully it'll give us something good to measure.

If (2) was the reason, then we should go ahead with ds/OrderedHashTable (or public/OrderedHashTable) and strive to make the two interfaces as compatible as possible except when there is a good reason (like STL does).  Most of the interface similarity is I think easy work, but the sticky point is the subtle removeFront behavioral difference which stems from the fact that OHM::Range supports mutation during iteration which itself stems from the use in MapObject.  Thus, if we were going to share OHM, I'd want to see if we couldn't make OHM::Range a dumb Range w/ the same semantics as HM::Range and then somehow build the smart Range that MapObject needs on top of it.  In theory this is possible since MapObject knows where all the mutation occurs.  This would also avoid penalizing OHM::Range performance when the smart-ness wasn't necessary.

Both of these take time and, atm, there is no good reason because there is no second use.  Putting OHM in MapObject.cpp is just a "read barrier" of sorts in that it will force us to address these questions if we find a second use case.  Without this, I fear we'd grow uses w/o asking these questions and then be left in a situation analogous to the old stdint situation: no clear guidance on which to use when/where.  If my fear is unfounded (no reuses) then it doesn't really matter and it's nicer that OHM is in MapObject b/c all the code is local.

I don't think I'm making a "better is better" mistake here because nothing is being blocked (I'll finish the review promptly), no effort is being unnecessarily expended.  I realize you've already agreed (thanks!), I'm just trying to explain my reasoning a bit better than I have been able to on irc.
Comment on attachment 637928 [details] [diff] [review]
v4

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

Thanks again for addressing all the comments.

::: js/src/builtin/MapObject.cpp
@@ +155,5 @@
> +     */
> +    bool put(const T &element) {
> +        HashNumber h = prepareHash(Ops::getKey(element));
> +        Data *e = lookup(Ops::getKey(element), h);
> +        if (e) {

Could you do "if (Data *e = ...)" and re-declare 'e' below?

@@ +385,5 @@
> +                while (*ep != &entry)
> +                    ep = &(*ep)->chain;
> +                *ep = entry.chain;
> +
> +                // Add it to the new hash chain.

Could you put a comment here about preserving the descending-memory-order invariant?  Perhaps also mention that code doesn't depend on it atm.

@@ +603,5 @@
> +    const Entry *get(const Key &key) const          { return impl.get(key); }
> +    Entry *get(const Key &key)                      { return impl.get(key); }
> +    bool put(const Key &key, const Value &value)    { return impl.put(Entry(key, value)); }
> +    bool remove(const Key &key, bool *foundp)       { return impl.remove(key, foundp); }
> +    void rekeyAll()                                 { return impl.rekeyAll(); }

I think rekeyAll is dead now?
Attachment #637928 - Flags: review?(luke) → review+
(In reply to Luke Wagner [:luke] from comment #13)
> I don't think I'm making a "better is better" mistake here because nothing
> is being blocked (I'll finish the review promptly), no effort is being
> unnecessarily expended.  I realize you've already agreed (thanks!), I'm just
> trying to explain my reasoning a bit better than I have been able to on irc.

Thanks. I feel a lot better about it now that I'm pushing to try server, and I apologize for letting myself get grumpy over this.

Fixed your last three nits; the comment in OHT::put() looks like this:

                // Add it to the new hash chain. We could just insert it at the
                // beginning of the chain. Instead, we do a bit of work to
                // preserve the invariant that hash chains always go in reverse
                // insertion order (descending memory order). No code currently
                // depends on this invariant, so it's fine to kill it if
                // needed.
er, OHT::rekeyFront().
https://hg.mozilla.org/mozilla-central/rev/5f4c341d773a
Status: NEW → RESOLVED
Closed: 12 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla16
This bug, or something which was merged to mozilla-central in the same push, caused a permanent orange on Linux32 mochitest-chrome for builds without frame pointers (example log: <https://tbpl.mozilla.org/php/getParsedLog.php?id=13227357&tree=Profiling&full=1>).  This is important because framepointers are not enabled on Aurora, so this permaorange will appear there on the next uplift.  I backed out this patch as part of the rest of the js and xpconnect patches in the same merge push.  Please test this patch locally (and push to the try server if needed by taking out the --enable-profiling command from the Linux32 mozconfig) and reland when you make sure that it's not the cause behind the perma-orange.  I apologize in advance for the inconvenience in case this patch is not at fault.

Backout changeset:
https://hg.mozilla.org/mozilla-central/rev/a9aa3ca03627
Status: RESOLVED → REOPENED
Resolution: FIXED → ---
In order to test whether this patch is at fault, push it to try with --enable-profiling removed from browser/config/mozconfigs/linux32/nightly, and if you get a green Linux Moth run, you're good to go!

And in turn you can reproduce the crash on try with your patch, I'd suggest you keep the possibility of having hit a compiler bug in mind.  :-)
Also, note that these backouts indeed made the Linux32 Moth runs on the profiling branch green again, so we can be fairly certain that one of the backed out patches was at fault.
Depends on: 770954
Comment on attachment 637928 [details] [diff] [review]
v4

>+     * The particular value of shuffleBits is taken from the hex expansion of
>+     * the golden ratio, which starts 1.9E3779B9.... This value has been
>+     * cargo-culted around since the original jshash.h. I doubt there is
>+     * anything particularly magical about it, except:

No cargo cult. Hmph! Who has been deleting my comments citing chapter and verse?

Please read Knuth chapter 6, which I can't lay hands on at the moment. Multiplication by the fixed point reciprocal approximation of an irrational number is important. Knuth gives a lemma but leaves the proof as an exercise, IIRC. You can do it!

/be
(In reply to Brendan Eich [:brendan] from comment #22)
> Please read Knuth chapter 6, which I can't lay hands on at the moment.
> Multiplication by the fixed point reciprocal approximation of an irrational
> number is important. Knuth gives a lemma but leaves the proof as an
> exercise, IIRC. You can do it!

I'll have to reread 6.4 tonight.
The Golden Ratio is particularly good if keys are well-distributed (and ignoring collisions), because

$ bc
scale=20
2/(1+sqrt(5))                                                                               # 1: 1/phi = (phi - 1)
.61803398874989484820

4/(1+sqrt(5))                                                                               # 2
1.23606797749978969641
(4/(1+sqrt(5)) - 1) / (2/(1+sqrt(5)))                                            # fraction splits lower interval by
.38196601125010515179                                                         # 1 - 1/phi conjugate

6/(1+sqrt(5))                                                                              # 3
1.85410196624968454461
(6/(1+sqrt(5)) - ((1+sqrt(5))/2)) / (1 - (2/(1+sqrt(5))))               # fraction splits upper interval by
.61803398874989484819                                                         # 1/phi

8/(1+sqrt(5))                                                                              # 4
2.47213595499957939282
(8/(1+sqrt(5)) - 2 - (4/(1+sqrt(5)) - 1)) / (2/(1+sqrt(5)))           # fraction splits upper-of-lower by
.38196601125010515179                                                        # conjugate

and so on.

This is from my aging memory, but it's in Knuth 6.4 (my copy grew legs) for those who care to look.

/be
Argh, why did I trust that textbox to use fixed-width?


$ bc
scale=20
2/(1+sqrt(5))                                               # 1: 1/phi = (phi - 1)
.61803398874989484820

4/(1+sqrt(5))                                               # 2
1.23606797749978969641
(4/(1+sqrt(5)) - 1) / (2/(1+sqrt(5)))                       # fraction splits lower interval by
.38196601125010515179                                       # 1 - 1/phi conjugate

6/(1+sqrt(5))                                               # 3
1.85410196624968454461
(6/(1+sqrt(5)) - ((1+sqrt(5))/2)) / (1 - (2/(1+sqrt(5))))   # fraction splits upper interval by
.61803398874989484819                                       # 1/phi

8/(1+sqrt(5))                                               # 4
2.47213595499957939282
(8/(1+sqrt(5)) - 2 - (4/(1+sqrt(5)) - 1)) / (2/(1+sqrt(5))) # fraction splits upper-of-lower by
.38196601125010515179                                       # conjugate

/be
Blocks: 775896
This comment is still present in jshash.cpp:

> /*
>  * Multiplicative hash, from Knuth 6.4.
>  */
> #define BUCKET_HEAD(ht, keyHash)                                            \
>     (&(ht)->buckets[((keyHash) * JS_GOLDEN_RATIO) >> (ht)->shift])

The subsequent hash tables jsdhash.cpp and HashTable.h implement the same sort of thing but lack the comment.

As always Knuth is an enlightening read.

My comment needs to be rewritten and more importantly OrderedHashTable needs code changes. The right shift here, dependent on the table size, is important, and OHT doesn't have it. Filed bug 775896 for that.

In cases where the input hash codes are integers in sequence, like 907, 908, 909, 910, ... the magic constant 1/φ spreads the entries across hash buckets about as uniformly as possible (more uniformly than a uniform random distribution would do!).  If the input hash codes are multiples of 24, say, then 1/24φ would be ideal.

Spreading the points as evenly as possible probably is not ideal in practice, since it minimizes collisions at the cost of guaranteeing worst-case memory locality. An opportunity for further optimization down the road.
(In reply to Jason Orendorff [:jorendorff] from comment #26)
> In cases where the input hash codes are integers in sequence, like 907, 908,
> 909, 910, ... the magic constant 1/φ spreads the entries across hash buckets
> about as uniformly as possible (more uniformly than a uniform random
> distribution would do!).

(However note that if we really expected that to be the common case, we would skip all the multiplying and bit-shifting and just use the low bits. This case can happen but it's probably not especially important. What's important is mixing the bits of the input hash code so that no likely set of input hash codes produces pathologically bad collisions.)
New comments in my local copy of this patch:

>/*
> * Given a raw hash code, h, return a number that can be used to select a hash
> * bucket.
> *
> * This function aims to produce as uniform an output distribution as possible,
> * especially in the most significant (leftmost) bits, even though the input
> * distribution may be highly nonrandom, given the constraints that this must
> * be deterministic and quick to compute.
> *
> * Since the leftmost bits of the result are best, the hash bucket index is
> * computed by doing ScrambleHashCode(h) / (2^32/N) or the equivalent
> * right-shift, not ScrambleHashCode(h) % N or the equivalent bit-mask.
> *
> * FIXME: OrderedHashTable uses a bit-mask; see bug 775896.
> */
>inline HashNumber
>ScrambleHashCode(HashNumber h)
>{
>    /*
>     * Simply returning h would not cause any hash tables to produce wrong
>     * answers. But it can produce pathologically bad performance: The caller
>     * right-shifts the result, keeping only the highest bits. The high bits of
>     * hash codes are very often completely entropy-free. (So are the lowest
>     * bits.)
>     *
>     * So we use Fibonacci hashing, as described in Knuth, The Art of Computer
>     * Programming, 6.4. This mixes all the bits of the input hash code h.
>     * 
>     * The value of goldenRatio is taken from the hex
>     * expansion of the golden ratio, which starts 1.9E3779B9....
>     * This value is especially good if values with consecutive hash codes
>     * are stored in a hash table; see Knuth for details.
>     */
>    static const HashNumber goldenRatio = 0x9E3779B9U;
>    return h * goldenRatio;
>}
https://hg.mozilla.org/mozilla-central/rev/e4fc754010f9
Status: REOPENED → RESOLVED
Closed: 12 years ago → 12 years ago
Resolution: --- → FIXED
Target Milestone: mozilla16 → mozilla17
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Creator:
Created:
Updated:
Size: