501398 - TM: internalize FrameInfo structures

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[David Anderson [:dvander] - inactive, e-mail if emergency]

Two FrameInfo objects that have identical contents should always get the same pointer. This is so recursion can efficiently guard on the upwards frame having the same pc and typemap at runtime.

Comment 1

[Brendan Eich [:brendan]]

Please tell me you will get rid of the bogus callee member!

/be

Comment 2

[David Anderson [:dvander] - inactive, e-mail if emergency]

Attachment: proof of concept

Getting this out of my patch queue. I don't like this very much so other approaches welcome, I just needed something quick to build recursion off.

Luke was interested in having a prettier templatized hash table that could inline keys into node allocations.

Brendan: going to keep FrameInfo as-is for now, can do this in a follow-up bug.

Comment 3

[David Anderson [:dvander] - inactive, e-mail if emergency]

Attachment: patch

Latest version.

Comment 4

[Brendan Eich [:brendan]]

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

JSDHashTable is the way to go if you want a Set.

/be

Comment 5

[Andreas Gal :gal]

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

>+
>+    /* Internalize FrameInfo pointers. */
>+    JSHashTable             *frameCache;
> };

Is Luke's hash table ready yet?


>+        traceMonitor->tempAlloc->alloc(sizeof(FrameInfo) + stackSlots * sizeof(JSTraceType));
>+    JSTraceType* typemap = fi->get_typemap();

Mister random indentation wants his tab back.


>     // The typemap just before the callee is called.
>     JSTraceType* get_typemap() { return (JSTraceType*) (this+1); }
>+    const JSTraceType* get_typemap() const { return (JSTraceType*) (this+1); }

Whats this? 2 versions of get_typemap()?

Comment 6

[David Anderson [:dvander] - inactive, e-mail if emergency]

Luke's hash table won't be landing for a while - not in time for recursion at least :(

Indentation isn't random - it's what the original code did to avoid overflowing the line (see above cast).

I forget why the const get_typemap() was added. Might be part of another patch. Will remove.

Comment 7

[David Anderson [:dvander] - inactive, e-mail if emergency]

Attachment: dhash version

Comment 8

[Brendan Eich [:brendan]]

Comment on attachment 402919 [details] [diff] [review]
dhash version


>+++ b/js/src/jstracer.cpp
>@@ -2562,6 +2562,9 @@ oom:
>     return false;
> }
> 
>+static JSDHashTable*
>+CreateFrameCache();
>+

Add inline DestroyFrameCache helper to match?

> void
> JSTraceMonitor::flush()
> {
>@@ -2583,6 +2586,10 @@ JSTraceMonitor::flush()
>             js_FragProfiling_FragFinalizer(f->head, this);
>     )
> 
>+    if (frameCache)
>+        JS_DHashTableDestroy(frameCache);

Avoids asymmetry here?

>+struct JSDHashFrameInfoEntry {
>+    JSDHashEntryHdr hdr;
>+    FrameInfo *fi;

Better to inherit:

struct JSDHashFrameInfoEntry : public JSDHashEntryHdr
{
    FrameInfo *fi;
};

>+    const FrameInfo* fi1 = (FrameInfo*)((JSDHashFrameInfoEntry*)entry)->fi;

You don't need to cast away const. You definitely don't need the (FrameInfo*) cast.

>+    const FrameInfo* fi2 = (const FrameInfo*)key;
>+    if ((r = memcmp(fi1, fi2, sizeof(FrameInfo))) != 0)

r is not used again after being set here, and it's against style to nest assignment in an if (as opposed to a loop) condition.

>+        return 0;
>+    r = memcmp(fi1->get_typemap(), fi2->get_typemap(), fi1->callerHeight * sizeof(JSTraceType));
>+    return r == 0;

Lose r, it's single-use throughout.

>+}
>+
>+static JSDHashNumber
>+HashFrameInfo(JSDHashTable *table, const void *key)
>+{
>+    FrameInfo* fi = (FrameInfo*)key;
>+    JSHashNumber hash = 5381;
>+    const char *data = (const char*)fi;
>+    size_t len = sizeof(FrameInfo) + fi->callerHeight;
>+    for (size_t i = 0; i < len; i++)
>+        hash = ((hash << 5) + hash) + data[i]; // hash*33 + c

Can we do better than byte-wise hashing? Do we care? Profiler data welcome, just asking. FrameInfo was originally word-y so you could do fewer loads and ^.

Murmur-hash or rotate/xor simpler hashes we use are more winning than +, which tends to mix poorly by just letting carries fly off the left end.

>-    JSTraceType* typemap = reinterpret_cast<JSTraceType *>(fi + 1);
>+        traceMonitor->tempAlloc->alloc(sizeof(FrameInfo) + stackSlots * sizeof(JSTraceType));
>+    JSTraceType* typemap = (JSTraceType*)(fi + 1);

Heh, down with verbose and ugly reinterpret_cast! ;-)

Does everyone agree or is this a minor style war?

/be

Comment 9

[Luke Wagner [:luke]]

(In reply to comment #8)
> >-    JSTraceType* typemap = reinterpret_cast<JSTraceType *>(fi + 1);
> >+        traceMonitor->tempAlloc->alloc(sizeof(FrameInfo) + stackSlots * sizeof(JSTraceType));
> >+    JSTraceType* typemap = (JSTraceType*)(fi + 1);
> 
> Heh, down with verbose and ugly reinterpret_cast! ;-)
> 
> Does everyone agree or is this a minor style war?

In general, I like to use reinterpret_cast as a way to yell "hey, look what I'm doing; its not normal!", but only sparingly, because, if used all over, it gets ignored like the boy who cried wolf.  (Here, yelling doesn't seem necessary -- the alloc-size computation is noisy enough -- so I agree your comment.)

Comment 10

[Jeff Walden [:Waldo]]

Is reinterpret_cast necessary, or would a static_cast<> be sufficient?  void*->JSTraceType* shouldn't go across type hierarchies.

Wasn't the very point of *_cast to be verbose and ugly?  I find it more readable, gives me more to hang my mind on than parentheses and a name I have to distinguish as a type (especially for something ghastly like this).

Comment 11

[Brendan Eich [:brendan]]

(In reply to comment #10)
> Wasn't the very point of *_cast to be verbose and ugly?

Intended or not, verbose and ugly they are, so some people don't use 'em.

/be

Comment 12

[David Anderson [:dvander] - inactive, e-mail if emergency]

Attachment: dhash v2

> Lose r, it's single-use throughout.

This was old code from when I envisioned returning a >, =, or < value. Thanks.

> Can we do better than byte-wise hashing? Do we care?

I don't think we care, it's a recording cost that only occurs when entering interpreted functions. There was no perf change switching off the old FrameInfo code.

> Heh, down with verbose and ugly reinterpret_cast! ;-)

I just go with the local style rules :) I only removed it by accident. I think it's ugly for good reasons. In this case it's not necessary, but perhaps warranted since we're _not_ casting from void*. Really I prefer to not have code like this at all, it's hard to tell what's going on and easy to make mistakes.

Comment 13

[Brendan Eich [:brendan]]

Comment on attachment 403321 [details] [diff] [review]
dhash v2

>+static JSDHashTable*
>+CreateFrameCache();
>+
>+static void
>+DestroyFrameCache(JSDHashTable *table);

Wondering whether it's worth pulling up the code and inlining stuff into a FrameCache class? Faster, cleaner, easier to use Luke's forthcoming templatized dhash stuff, etc.

>@@ -2588,6 +2594,10 @@ JSTraceMonitor::flush()
>             js_FragProfiling_FragFinalizer(f->head, this);
>     )
> 
>+    if (frameCache)
>+        DestroyFrameCache(frameCache);
>+    CreateFrameCache();

Return value is dropped on the floor here.

>+HashFrameInfo(JSDHashTable *table, const void *key)
>+{
>+    FrameInfo* fi = (FrameInfo*)key;
>+    JSHashNumber hash = 5381;
>+    const char *data = (const char*)fi;
>+    size_t len = sizeof(FrameInfo) + fi->callerHeight;
>+    for (size_t i = 0; i < len; i++)
>+        hash = ((hash << 5) + hash) + data[i]; // hash*33 + c

Still seems like you are losing too many bits off the left end of hash. 32 bits is fewer than seven five-bit chunks. See JS_DHashStringKey, which you might steal from, losing the NUL-terminator loop.

/be

Comment 14

[David Anderson [:dvander] - inactive, e-mail if emergency]

Attachment: v3

Gah, stupid mistake. Anyway I like the idea of a class, so here's a new patch. I lifted code from the string hashing function as well.

Comment 15

[David Anderson [:dvander] - inactive, e-mail if emergency]

The unchecked return values in FrameInfoCache are for when we ever start caring about |new| OOM in jstracer and thus want separate ctor/init.

Comment 16

[Brendan Eich [:brendan]]

Comment on attachment 403339 [details] [diff] [review]
v3

>+class FrameInfoCache
>+{
>+    struct JSDHashFrameInfoEntry  : public JSDHashEntryHdr

I'd lose the JSDHash- prefix on JSDHashFrameInfoEntry -- you might evey use struct Entry as the name since it's inside FrameInfoCache and FrameInfoCache::Entry works.

>+    {
>+        FrameInfo *fi;
>+    };
>+
>+    static JSBool
>+    MatchFrameInfo(JSDHashTable *table, const JSDHashEntryHdr *entry, const void *key)
>+    {
>+        const FrameInfo* fi1 = ((const JSDHashFrameInfoEntry*)entry)->fi;

Just Entry shortens this line nicely!

>+        const FrameInfo* fi2 = (const FrameInfo*)key;
>+        if (memcmp(fi1, fi2, sizeof(FrameInfo)) != 0)
>+            return JS_FALSE;
>+        return memcmp(fi1->get_typemap(), fi2->get_typemap(),
>+                      fi1->callerHeight * sizeof(JSTraceType)) == 0;
>+    }
>+
>+    static JSDHashNumber
>+    HashFrameInfo(JSDHashTable *table, const void *key)
>+    {
>+        FrameInfo* fi = (FrameInfo*)key;
>+        size_t len = sizeof(FrameInfo) + fi->callerHeight;

Shouldn't you multiple fi->callerHeight * sizeof(JSTraceType), as above in MatchFrameInfo?

>+
>+        JSDHashNumber h = 0;
>+        const unsigned char *s = (const unsigned char*)fi;
>+        for (size_t i = 0; i < len; i++, s++)
>+            h = JS_ROTATE_LEFT32(h, 4) ^ *s;
>+        return h;
>+    }
>+
>+    static const JSDHashTableOps FrameCacheOps;
>+
>+    JSDHashTable *table;
>+  public:
>+    FrameInfoCache()
>+    {

Prevailing inline style wants { on the declarator line, not on its own line. This wins bigger later with the other methods.

>@@ -2588,6 +2683,7 @@ JSTraceMonitor::flush()
>             js_FragProfiling_FragFinalizer(f->head, this);
>     )
> 
>+    frameCache->reset();
>     dataAlloc->reset();
>     codeAlloc->reset();

Nice!

r=me with nits picked.

/be

Comment 17

[Brendan Eich [:brendan]]

One last nit: "internalize" is a bit odd given the already intern'ed nature of FrameInfo structs in trees. How about "memoize"?

/be

Comment 18

[David Anderson [:dvander] - inactive, e-mail if emergency]

Pushed with nits as:

http://hg.mozilla.org/tracemonkey/rev/911d01b21463

Comment 19

[David Anderson [:dvander] - inactive, e-mail if emergency]

Attachment: stupid bug

I backed this out as cset e3cbe5691b72 because it was crashing. I typo'd traceAlloc instead of dataAlloc despite Graydon warning me about the former being "rewound" on IRC.

Anyway, it's silly to pass in the allocator each time so I moved it to the ctor (see interdiff).

Comment 20

[David Anderson [:dvander] - inactive, e-mail if emergency]

Or not, since interdiff doesn't work.

Comment 21

[Brendan Eich [:brendan]]

Attachment: interdiff between hg raw diff of what landed and latest patch

Comment 22

[Brendan Eich [:brendan]]

Comment on attachment 403746 [details] [diff] [review]
stupid bug


>+    JSDHashTable *table;
>+    VMAllocator *allocator;
>+  public:
>+    FrameInfoCache(VMAllocator *allocator) : allocator(allocator) {

Nit: breathes better with a blank line before public: -- in general we do that before labels.

/be

Comment 23

[David Anderson [:dvander] - inactive, e-mail if emergency]

Pushed against, with nits, as cset http://hg.mozilla.org/tracemonkey/rev/89e665eb9944

Comment 24

[Brendan Eich [:brendan]]

Failed to suggest making FrameInfoCache : public JSDHashTable to save an indirect reference and separate allocation. But maybe it's better to pay those prices if we often don't have a JSDHashTable?

/be

Comment 25

[Brendan Eich [:brendan]]

Oh, but then we would want frameCache to be inline -- of type FrameInfoCache not FrameInfoCache*. So it's probably worth eliminating the indirection/allocation.

/be

Comment 26

[Robert Sayre]

http://hg.mozilla.org/mozilla-central/rev/89e665eb9944