Closed Bug 506410 Opened 15 years ago Closed 14 years ago

bring template lovin' to hash tables

Categories

(Core :: JavaScript Engine, defect)

Product:
Core
Component:
JavaScript Engine
Platform:
x86
Linux
Type:
defect
Priority:
Not set
Severity:
normal

Tracking

()

Status:
RESOLVED DUPLICATE of bug 515812

People

(Reporter: luke, Assigned: luke)

Details

Attachments

(1 file, 4 obsolete files)

v.5, stable, shrinks, no pools
32.78 KB, patch
Details | Diff | Splinter Review 
A C++-style templated hash table has the potential to improve upon jshash.h/jsdhash.h in the following ways
 - use RAII to automatically release memory
 - allow arbitrary types for keys and values instead of void *.  this avoids dynamic allocation when the key/value isn't word-sized.
 - support value semantics for non-POD key/value types so that key/value constructors/destructors get called at the right times
 - allocate the first N elements inline (for a template parameter N) so that no dynamic allocation occurs when size < N
 - improve performance by making hashing/key-compare static parameters (hence inlined) instead of dynamic pointer-to-function calls
 - improve performance through ordinary inlining of template methods
 - avoid JSHashTable's malloc-per-entry and JSDHashTable's one-big-buffer by using a fixed-size pool that grows.  thus, entries can be stable and we still have log2(size) malloc calls.
Attached patch WIP v.1 (obsolete) — — Splinter Review 
There is some touch-up work left, but JSHashMap has been unit and "fuzz" tested, so it should be correct.
(In reply to comment #0)
> A C++-style templated hash table has the potential to improve upon
> jshash.h/jsdhash.h in the following ways
>  - use RAII to automatically release memory

Cool.

>  - allow arbitrary types for keys and values instead of void *.  this avoids
> dynamic allocation when the key/value isn't word-sized.

There is no dynamic allocation burden in jsdhash, you can use placement new on an arbitrary entry subtypes. See bug 72722.

>  - support value semantics for non-POD key/value types so that key/value
> constructors/destructors get called at the right times

Beats using C callbacks!

>  - allocate the first N elements inline (for a template parameter N) so that no
> dynamic allocation occurs when size < N

>  - avoid JSHashTable's malloc-per-entry and JSDHashTable's one-big-buffer by
> using a fixed-size pool that grows.  thus, entries can be stable and we still
> have log2(size) malloc calls.

jsdhash parameterized how the table grew but it did indeed not grow in place. But you can't guarantee in-place growth without a reservation scheme. ???

/be
For the comment 1 attachment, I did a perf test with the following basic algorithm (here with the new C++ std::unordered_map):

for (int i = 0; i < Outer; ++i) {
    std::unordered_map<int, int> hm;
    for (int j = 0; j < Inner; ++j)
        hm.insert(std::make_pair(j, j));
    for (int j = 0; j < Inner; ++j)
        if (hm.find(j) != hm.end())
            ++sum;  
    for (int j = 0; j < Inner; ++j)
        hm.erase(j);
    sum += hm.size();
}

where sum is live to prevent optimization.  Varying Inner and Outer:

Outer 100000, Inner 100
[unordered_map] 1.15929
[JSDHashTable] 2.3988
[JSHashTable] 1.48708
[JSHashMap] 0.260179

Outer 1000, Inner 10000
[unordered_map] 1.28528
[JSDHashTable] 3.28084
[JSHashTable] 1.67715
[JSHashMap] 0.571928

Outer 100, Inner 100000
[unordered_map] 1.51047
[JSDHashTable] 5.05725
[JSHashTable] 1.99628
[JSHashMap] 0.694431

Here, all hash tables are told on construction to reserve space for 128 entries.
Clearly, other/different tests are needed.
(In reply to comment #2)
> But you can't guarantee in-place growth without a reservation scheme. ???

Since random access isn't necessary for hash table elements, I just keep a linked list of increasingly-big blobs of storage.  The free list is woven through freed elements.
FWIW, we already have exactly this with nsTHashtable/nsBaseHashtable etc over pldhash, which is jsdhash by a different name.
(In reply to comment #5)
> FWIW, we already have exactly this with nsTHashtable/nsBaseHashtable etc over
> pldhash, which is jsdhash by a different name.

Not exactly.  If nsTHashtable is only a wrapper for pldhash, then it will achieve some of the type safety and ease-of-use goals, but fail on all the efficiency gains, viz., it will perform the same or worse than JSDHashTable.

Also, from a quick inspection of nsTHashtable, I see that it isn't able to avoid the callback style of enumeration.  JSHashMap allows you to write:

for (JSHashMap<...>::Range r = table.all(); !r.empty(); r.popFront())
  std::cout << r.front().value << '\n';

which is, IMHO, much easier to write and read.  Also faster.
Attached patch WIP v.2 (obsolete) — — Splinter Review 
Small tweaks and filled in documentation.

I made another benchmark, this one for the "raw" api, and saw roughly the same factor of speedup.
Attachment #390607 - Attachment is obsolete: true
With respect to the performance results reported in comment 3 and comment 7, I remembered one extra piece of logical work that JS{|D}HashTable is doing and JSHashMap is not: on erase, they are shrinking the hash table when it goes below a certain % load.

Since the hash table <Key,Value> pairs are pool allocated, it would not be efficient to implement shrinkage.  I think the reason to implement shrinkage at all is for the situation where you have a long-lived hash table (say JSContext::busyArrayTable) that gets really big once, then empties, and forever more the memory is pinned down.  To handle this problem, an efficient scheme would be to register the hash table in linked list, kept by the JSRuntime, and on GC (or other last-ditch memory reclamation attempt), go through the list and do the expensive shrinkage algorithm.  This could be handled by a special "long-lived container" allocation policy and extended to JSTempVector too.
Why is double hashing not being used? Arena allocation of chained entries will fragment badly under typical workloads.

/be
(In reply to comment #9)
> Why is double hashing not being used? Arena allocation of chained entries will
> fragment badly under typical workloads.

To recap our discussion for the benefit of the bug: pool allocation is very fast for growing (no copying the old allocation), fragmentation is addressed by the aforementioned demand-driven shrinking, and double-hashing is expensive for large sizeof(pair<Key,Value>).  Double-hashing would win for small <Key,Value>, so perhaps a separate similarly-templated data structure.
Attached patch v.3 (obsolete) — — Splinter Review 
To avoid some weird "shrink the table on magic event" logic, I just added the same underflow logic already in JSHashTable and JSDHashTable.

This patch also installs a first use of js::HashMap in, unsurprisingly, Array.toString.  Actually, all that is needed is a "set" (the value is not needed); if more situations like this pop up I can specialize HashMap to accept 'void' as the Value type and then avoid wasting storage.  As is, busyArrayTable is always minute, so no pressing need.

I will make a separate bug, in the style of bug 503952, to go around installing HashMap in more places.
Attachment #390892 - Attachment is obsolete: true
Attachment #396861 - Flags: review?(jwalden+bmo)
I am finding this hard to read, and although I want this hash table template in as soon as possible, it'll have to wait at least until tomorrow.

One preliminary question:

>+    cx->busyArrayTable = cx->create<JSBusyArrayTable>(cx);

I can't tell what `create` refers to. Is it something that is added to JSContext in some other patch?
Oops, yes, that relies on the patch in 511750 comment 21.  The comment explains how it factors out a common idiom.
Code style should change to the newly minted convention of not having a conventional prefix or suffix for member variables (or, I presume, globals or static members). I'm all for LeadingCaps for template parameters, but not for member variables as in Pool::MemberData::Buf. OK?

>+template <> struct DefaultHasher<const char *> {
>+    static uint32 hash(const char *key) {
>+        /* hash character strings like JS_DHashStringKey. */
>+        typedef const unsigned char uchar;
>+        uint32 h = 0;
>+        for (uchar *s = (uchar *)key; *s != '\0'; s++)
>+            h = JS_ROTATE_LEFT32(h, 4) ^ *s;
>+        return h;
>+    }
>+};

Can we drop this? The hash table will still compare strings for equality using operator==.

Each hash table gets its own pool. We do this so we can free a whole table very quickly without visiting all the elements (in the case that V's destructor doesn't do anything), right? The cost in terms of memory usage is, I think, proportional to the total count()*sizeof(Element) of all tables. It seems ok, and probably similar to the memory cost of open addressing.

What kind of code size hit can we expect per instantiation?

That we call consolidate() is necessary in order to give any memory back to the system, eh? All right then.

More to come.
Google hashtable tests or some such could be entertaining. Can we have head-to-head benchmark results, us (old) vs. us (new, this patch) vs. them?

/be
(In reply to comment #14)
> Code style should change to the newly minted convention of not having a
> conventional prefix or suffix for member variables (or, I presume, globals or
> static members). I'm all for LeadingCaps for template parameters, but not for
> member variables as in Pool::MemberData::Buf. OK?

Ok.  I'll batch up all these edits and submit a new patch after you make it through.

> >+template <> struct DefaultHasher<const char *> {
> >+    static uint32 hash(const char *key) {
> >+        /* hash character strings like JS_DHashStringKey. */
> >+        typedef const unsigned char uchar;
> >+        uint32 h = 0;
> >+        for (uchar *s = (uchar *)key; *s != '\0'; s++)
> >+            h = JS_ROTATE_LEFT32(h, 4) ^ *s;
> >+        return h;
> >+    }
> >+};
> 
> Can we drop this? The hash table will still compare strings for equality using
> operator==.

I think the issue isn't equality, but getting a good distribution.  However, even if all the const char*s are concentrated in a small area, the multiply-by-sGoldenRatio step after hashing should bring us back to good distribution.  Is that right / what you mean?

> Each hash table gets its own pool. We do this so we can free a whole table very
> quickly without visiting all the elements (in the case that V's destructor
> doesn't do anything), right?

Right.

> What kind of code size hit can we expect per instantiation?

I haven't measured, but I should.  I filed bug 512813 about building a tool that would measure these types of things.  I also heard there is already a "codesighs" tool.

> That we call consolidate() is necessary in order to give any memory back to the
> system, eh? All right then.

Yeah, otherwise if you have a long lived (held by context/runtime) hashtable (which I think is fairly common) that grows really big once, then that memory is forever claimed.

Thanks!
>+ * objects. Pool allocation is not contiguous and never reallocates, hence
>+ * pointers into the pool are stable.

This comment neglects consolidate(), which invalidates pointers.

>+    /*
>+     * lookup and add: analogous to the std::map operation. [...]
>+     */
>+    Value *operator[](const Key &k);

I would actually rather do without this, since the need to report OOM makes a mess of the std::map interface. It doesn't seem to be used yet.

>+/*
>+ * When sInlineBytes is zero, remove Buf member variable. The "Z" parameter
>+ * does nothing and is only included because C++ has strange rules
>+ * (14.7.3.17-18) regarding explicit specializations.
>+ */
>+template <class T, size_t N, class AP>
>+template <class X>
>+struct Pool<T,N,AP>::MemberData<0,X>
>+{
>[...]
>+};

I am a simple caveman, and your partial template specializing ways confuse and frighten me. I think you meant "X" instead of "Z".

>+class Pool : AllocPolicy

I would really appreciate it if you could make this AllocPolicy a member of the Pool instead of a private base class. It's hard enough to remember that a Pool isn't an AllocPolicy (in the "concept" sense) without it also actually being an AllocPolicy!

I for one will want more high-level helper functions on HashTable, but that can come later.

That's really it. There are some things that kind of subliminally worry me about this patch, but really only in a hand-wringing kind of way. (The API that Pool presents to HashTable seems idiosyncratic, as if they're not really two independent classes. I worry about the maintenance cost of this admittedly elite use of templates. The behavior on underflow strikes me as kind of weird. All stuff I can live with. I've reviewed scarier stuff.)

I'm ready to stamp an update with the fixes requested here and in comment 14.
(In reply to comment #16)
> (In reply to comment #14)
> > >+template <> struct DefaultHasher<const char *> {
> >
> > Can we drop this? The hash table will still compare strings for equality using
> > operator==.
> 
> I think the issue isn't equality, but getting a good distribution.  However,
> even if all the const char*s are concentrated in a small area, the
> multiply-by-sGoldenRatio step after hashing should bring us back to good
> distribution.  Is that right / what you mean?

Well -- I think it's unlikely that we'll get more hash collisions for const char * keys than for any other kind of key, yes -- but my real objections to this are (1) it's dead code at the moment; (2) you aren't gonna need it; (3) the semantics seem wrong, or at least anti-generic -- for example, hashing NULL would crash just for this one type of pointer. For another example, the same pointer could have different hash codes at different times, so it could end up being entered in the same hash table multiple places.
(In reply to comment #17)
> >+    /*
> >+     * lookup and add: analogous to the std::map operation. [...]
> >+     */
> >+    Value *operator[](const Key &k);
> 
> I would actually rather do without this, since the need to report OOM makes a
> mess of the std::map interface. It doesn't seem to be used yet.

There is only one, limited use of js::HashMap at the moment, so its not surprising that half this interface is unused. I intend to submit patches that, over time, replace JS_Hash* with js::HashMap. While usage is grosser, it does not mean that the use case for "lookup and add if not already present" disappears.

  Val *v = hm[k];
  if (!v)
    return false;

is still shorter than:

  HM::Pointer p = hm.lookup(k)
  if (!p) {
    if (!hm.addAfterMiss(k,v,p))
      return false;
  }
  Val &v = p->value;

> >+/*
> >+ * When sInlineBytes is zero, remove Buf member variable. The "Z" parameter
> >+ * does nothing and is only included because C++ has strange rules
> >+ * (14.7.3.17-18) regarding explicit specializations.
> >+ */
> >+template <class T, size_t N, class AP>
> >+template <class X>
> >+struct Pool<T,N,AP>::MemberData<0,X>
> >+{
> >[...]
> >+};
> 
> I am a simple caveman, and your partial template specializing ways confuse and
> frighten me.

Oh its quite odd to me too :). I had this without the additional X parameter, and the compiler didn't like that, so I filed a bug (http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40828), but it turns out to be an odd rule (bug?) in the C++ standard, so here we are.

> >+class Pool : AllocPolicy
> 
> I would really appreciate it if you could make this AllocPolicy a member of the
> Pool instead of a private base class. It's hard enough to remember that a Pool
> isn't an AllocPolicy (in the "concept" sense) without it also actually being an
> AllocPolicy!

I would prefer it to be a member as well, but if you do that, and AllocPolicy is empty, you get penalized a word because of some standard-based requirement to give member variables separate addresses (I assume).  Bases obviously don't have that requirement so they are optimized accordingly.

> I for one will want more high-level helper functions on HashTable, but that can
> come later.

Like js::Vector, I'm intentionally starting with a basic interface and letting it grow on an as-needed basis, so I'm happy to grow later as new uses present themselves.

> That's really it. There are some things that kind of subliminally worry me
> about this patch, but really only in a hand-wringing kind of way. (The API that
> Pool presents to HashTable seems idiosyncratic, as if they're not really two
> independent classes.

Very true.  But, of course, those idiosyncrasies are necessary for the algorithm to work at all.  I could have just rolled js::Pool into js::HashMap, but (1) in the past I've often found needs for a pool like this one, (2) while the interface is rather tailored to HashMap's needs, reasoning is O(n^2) wrt code size so I'd rather cut it.

> I worry about the maintenance cost of this admittedly
> elite use of templates.

On the Boost scale, this probably only ranks "moderate" ;-). But seriously, I only resort to these techniques for lack of a better way to achieve the same end result.

> The behavior on underflow strikes me as kind of weird.

Again, just copying JS_HashMap/JS_DHashMap to avoid pseudo-memory leaks for long-lived hash tables.

Thanks for wading through all this!  I'll get to work on all the feedback.
I thought of a few more comments.

>+    HashMap(const HashMap &);
>+    HashMap &operator=(const HashMap &);

These are public but I don't remember seeing definitions for them. Move them private and add a comment "These could be implemented with little trouble but we haven't needed them yet"?

HashMap::all() exposes the elements. Should the keys be const?

HashMap's Pool has an AllocPolicy in which cx is stored. Generally we pass in a cx parameter to avoid storing cx everywhere. Even with the extra word, HashMap is probably slimmer than JSHashTable, so again, not a big deal. But can we get rid of it?

"put" is a better name than "add". Java uses put(). add() sounds as though it might be only for adding new entries, not for changing the value of an existing entry. (At least this was my first impression -- and note that for addAfterLookup, this is actually the case!)
I meant addAfterMiss in comment 20, sorry.

(In reply to comment #19)
> (In reply to comment #17)
> > >+    /*
> > >+     * lookup and add: analogous to the std::map operation. [...]
> > >+     */
> > >+    Value *operator[](const Key &k);
> > 
> > I would actually rather do without this, since the need to report OOM makes a
> > mess of the std::map interface. It doesn't seem to be used yet.
> 
> There is only one, limited use of js::HashMap at the moment, so its not
> surprising that half this interface is unused. I intend to submit patches that,
> over time, replace JS_Hash* with js::HashMap. While usage is grosser, it does
> not mean that the use case for "lookup and add if not already present"
> disappears.
> 
>   Val *v = hm[k];
>   if (!v)
>     return false;
> 
> is still shorter than:
> 
>   HM::Pointer p = hm.lookup(k)
>   if (!p) {
>     if (!hm.addAfterMiss(k,v,p))
>       return false;
>   }
>   Val &v = p->value;

Maybe we can call that operation findOrAdd instead of [].
(In reply to comment #20)
> I thought of a few more comments.
> 
> >+    HashMap(const HashMap &);
> >+    HashMap &operator=(const HashMap &);
> 
> These are public but I don't remember seeing definitions for them. Move them
> private and add a comment "These could be implemented with little trouble but
> we haven't needed them yet"?

I originally had that, but putting these members private is the general idiom for "noncopyable".  Making them public says "use 'em, go for it", the ensuing linker error says "but someone needs to write it first".
 
> HashMap's Pool has an AllocPolicy in which cx is stored. Generally we pass in a
> cx parameter to avoid storing cx everywhere. Even with the extra word, HashMap
> is probably slimmer than JSHashTable, so again, not a big deal. But can we get
> rid of it?

The destructor already needs it to call cx->free().  The SystemAllocPolicy, which uses ::malloc and ::free doesn't store a cx.

> "put" is a better name than "add". Java uses put(). add() sounds as though it
> might be only for adding new entries, not for changing the value of an existing
> entry. (At least this was my first impression -- and note that for
> addAfterLookup, this is actually the case!)

I use add because this is what the previous hash tables named the operation and I wanted new HashMap users to know "this is the same logical operation".  OTOH, looking forward, "put" might be a better name.

> Maybe we can call that operation findOrAdd instead of [].

Sure. Though JS coders would not be likely to make the same mistake, I have been horrified to see:

m["foo"].x = 1;
m["foo"].y = 2;

because operator[] "looks fast", and a more descriptive name would prevent that.
Comment on attachment 396861 [details] [diff] [review]
v.3

(clearing the review bit here, per the last line of comment 19)
Attachment #396861 - Flags: review?(jwalden+bmo)
Attached patch v.4 (obsolete) — — Splinter Review 
With comments addressed.

I did a basic size test and, using lookup, add, remove, and the destructor, the cost is right around 1K per instantiation (-O3, measured by the Unix 'size' command).  This is per <K,V,N,H,AP> tuple.  There are some obvious ways to factor out common code without affecting perf, but they involve more complexity and, without a lot of instantiations in the code yet, it seems hard to measure the effectiveness of these changes.  Hence, I say we just keep "templated data structures" on the list of usual suspects for executable size and every time we want to shrink, we round 'em up and beat with the monomorphic stick.
Attachment #396861 - Attachment is obsolete: true
Attachment #399298 - Flags: review?(jorendorff)
Comment on attachment 399298 [details] [diff] [review]
v.4

OK, let's go.
Attachment #399298 - Flags: review?(jorendorff) → review+
Failed landing attempt this afternoon... looking more and more like a freak accident as it works fine on the try server and under valgrind...

BUT!  While thinking about hash tables, I realized that my change to resize on underflow breaks pointer the pointer stability property!  I'm not sure how that escaped my mind.  The solution I propose is to take out underflow checks and add an explicit "consolidate" member function that does the job.  That allows us to eliminate "leaks" in long-lived hash tables if need be.
(In reply to comment #26)
> Failed landing attempt this afternoon... looking more and more like a freak
> accident as it works fine on the try server and under valgrind...

That would be great news! (And shame on... everybody... for autoblaming GCC's template support.)

> BUT!  While thinking about hash tables, I realized that my change to resize on
> underflow breaks pointer the pointer stability property!

Oh, I'm sorry-- I noticed this but I didn't see any guarantee of pointer stability in the comments on HashMap, so I figured it was a known issue and had been settled in favor of auto-shrinking.

> The solution I propose is to take out underflow checks and
> add an explicit "consolidate" member function that does the job.  That allows
> us to eliminate "leaks" in long-lived hash tables if need be.

Yes, faster too, but I expect people will say auto-shrinking is more important than pointer stability. At least I'm not aware of any cases where we actually need pointer stability -- if we have any, it seems like they'll be easy to find since you'll be touching all the relevant lines.
One more random comment--

>+template <class T> struct DefaultHasher<T *> {
>+    static uint32 hash(const T *key) {
>+        /* hash pointers like JS_DHashVoidPtrKeyStub. */
>+        return (uint32)(unsigned long)key >> 2;

sGoldenRatio prevents this from being a terrible hash function (note that e.g. sizeof(JSObject) == 32 on 32-bitplatforms, so GC-heap JSObject pointers all end with the same 6 bits or something crazy like that).

But as long as sGoldenRatio is there, the bitshift is unnecessary, right?
(In reply to comment #27)
> > The solution I propose is to take out underflow checks and
> > add an explicit "consolidate" member function that does the job.  That allows
> > us to eliminate "leaks" in long-lived hash tables if need be.
> 
> Yes, faster too, but I expect people will say auto-shrinking is more important
> than pointer stability. At least I'm not aware of any cases where we actually
> need pointer stability -- if we have any, it seems like they'll be easy to find
> since you'll be touching all the relevant lines.

I think there are a few.  Also, now that I think about the open-addressing scheme more (and get over my distaste of the extra type-traits required for generic (Key,Value) types) it seems like one of the main reasons to use a chaining-based hash table, instead of open-addressing, is stability.  Otherwise, I keep having the reasons I thought open-addressing was necessarily slower quashed.
(In reply to comment #28)
> One more random comment--
> 
> >+template <class T> struct DefaultHasher<T *> {
> >+    static uint32 hash(const T *key) {
> >+        /* hash pointers like JS_DHashVoidPtrKeyStub. */
> >+        return (uint32)(unsigned long)key >> 2;
> 
> sGoldenRatio prevents this from being a terrible hash function (note that e.g.
> sizeof(JSObject) == 32 on 32-bitplatforms, so GC-heap JSObject pointers all end
> with the same 6 bits or something crazy like that).
> 
> But as long as sGoldenRatio is there, the bitshift is unnecessary, right?

Heh, I kept wondering the same thing.  I just assumed there was some wisdom-of-the-ages reason and was too lazy to ask.
we discussed on IRC that we shouldn't be changing algorithms in the bug. that can be later, but iirc there is good reason for that shift that I don't remember, and it's probably a low reward place to hunt.
For the benefit of the bug, Sayre summoned said wisdom of the ages to show why this shift is necessary: http://www.concentric.net/~Ttwang/tech/inthash.htm, with hints that this is probably in Knuth as well.
jsdhash.h's big comment talks about double hashing winning for small entry size and no entry address stability requirement. Otherwise chaining can win if either or both requirements apply.

JSAtoms are entries that must have stable addresses. They are also bigger than a couple of words, although they could be shrunk slightly.

The shift right by 2 is to clear what are usually low zero bits and get more of the non-zero bits into the multiplicand. For 0b => binary, X a binary digit,

PHI * 0bXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX00 is
PHI * 0b00XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX * 4 is
(PHI * 0b00XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX) << 2

which has two low zero bits. Jason's point about JSObject having 5 low zero bits is a good one, but fodder for another bug indeed.

/be
Of course multiplicative hash then picks the right bits. Only for a very large table might we get unwanted zeros. But more than zero-avoidance, we preserve more sums of products of those high-order X digits and PHI. Assuming the X digits and carries from lower sums have good entropy...

/be
(In reply to comment #34)
> Of course multiplicative hash then picks the right bits.

Sigh, still caffeinating after a late night -- "right" meaning best if not correct here. The leftmost log2(table size) bits, of course.

/be
So, go with dropping underflow-checking and making a separate "consolidate" member function?
Brendan and I talked about this "consolidate" API a bit more.  Punting consolidate to the hash table user doesn't really fix the problem, since for some users, there is no good time to break pointer stability (e.g. with the atom table).  Also, it makes the API more complex since long-lived hash tables now need to handle this resizing logic (when is the right time to consolidate?  hook into GC?  gross).

So, given that we want underflow-resize and pointer stability, pool allocation has to go.  Hence, like JS_HashTable, js::HashMap must do a cx->malloc per entry.  (Bummer.)  Also, in-place allocation becomes gross to do without a pool, so I stripped that out.  On the bright side, js::HashMap is a fair amount simpler.  (Apologies to jorendorff for having him read the template-delight version.)

Whereas the pool-allocated version is, as the results above show, 2-4x faster, the malloc-allocated version is only 10-30% faster.  However, I realized all my timing is in the standalone shell, hence I'm using glibc, not jemalloc.  I'll try to get those numbers and post later; in theory, they would show a greater speedup because inlining would matter more since malloc/free cost less.

        Attachment #399298 -
        Attachment is obsolete: true

    
    

    
  
Pool allocation of JSHashEntry substructs with no consolidation is done by JSAtomList code. It could use C++ lovin' a la this bug and jimb is giving it some in bug 515441.

So pooling to reduce malloc overhead and (more important with a good malloc) to guarantee free-everything-at-the-end-of-an-"episode" as is done with JSAtomLists when compiling, is a fine thing to add onto hashing with chaining, if you can stand to lose consolidation in order to keep entries from moving. But it shouldn't be mandatory.

I hope the Pool code can be factored accordingly. Maybe it becomes the upgrade to jsarena.h?

/be

    
    

    
  
(In reply to comment #39)

Hmm, that sounds like an interesting idea.  I'll need to look more at the precise algorithm used by the atom lists to know what HashMap's API should look like and how it can generalize to other uses, but that sounds like it could give the benefits of pool allocation while maintaining the stability and shrinking properties.  It'd be nice to go back to 2-4x faster :)

This whole trouble-with-chaining highlights the need for a templ-aided JS_DHashTable too (bug 515812).  I'm going to switch to bug 460904 for a bit, but I'll be back.

    
    

    
  
http://hg.mozilla.org/mozilla-central/rev/b866396faae4
Status: ASSIGNED → RESOLVED
Closed: 15 years ago
Resolution: --- → FIXED

    
    

    
  
j/k
Status: RESOLVED → REOPENED
Resolution: FIXED → ---

    
    

    
  
Since double-hashing does not have the malloc-per-entry vs. potential-pool-leak issue described above, I shifted attention to templating JS_DHashTable instead.  Since this bug already has a lot of comments related to chained hashing, I posted the patch on bug 515812 instead.

    
    

    
  
These bugs are all part of a search I made for js bugs that are getting lost in transit:

http://tinyurl.com/jsDeadEndBugs

They all have a review+'ed, non-obsoleted patch and are not marked fixed-in-tracemonkey or checkin-needed but have not seen any activity in 300 days. Some of these got lost simply because the assignee/patch provider never requested a checkin, or just because they were forgotten about.

    
  
Status: REOPENED → RESOLVED
Closed: 15 years ago → 14 years ago
Resolution: --- → DUPLICATE

          You need to log in
          before you can comment on or make changes to this bug.
        






  

    
  







  

    

      
Attachment

      

      
      
      
      
    

    

      

        

          

            
General

            

              Creator: 



            

            
Created: 

            
Updated: 

            
Size: