328305 - hashtables: iterator-like API for table enumeration

Status: RESOLVED WONTFIX

(Core :: JavaScript Engine, enhancement)

Description

[Igor Bukanov]

The current API for the hash tables enumeration, JS_DHashTableEnumerate and JS_HashTableEnumerateEntries, use callbacks to communicate the current entry under the enumeration. 

It would be nice to have an iterator alternative to API to replace the current code like:

JS_STATIC_DLL_CALLBACK(intN)
js_script_filename_marker(JSHashEntry *he, intN i, void *arg)
{
    ScriptFilenameEntry *sfe = (ScriptFilenameEntry *) he;

    sfe->mark = JS_TRUE;
    return HT_ENUMERATE_NEXT;
}

void
js_MarkScriptFilenames(JSRuntime *rt, uintN gcflags)
{
...

        JS_HashTableEnumerateEntries(rt->scriptFilenameTable,
                                     js_script_filename_marker,
                                     rt);
...
}


by a shorter and more easy to follow version:

void
js_MarkScriptFilenames(JSRuntime *rt, uintN gcflags)
{
    JSHashIter iter;
    ScriptFilenameEntry *sfe;
...
        js_HashIterStart(&iter, rt->scriptFilenameTable);
        while ((sfe = (ScriptFilenameEntry *)js_HashIterNext(&iter)))
            sfe->mark = JS_TRUE;
...
}

Comment 1

[Igor Bukanov]

Attachment: Implementation

Comment 2

[Igor Bukanov]

Attachment: Implementation + comments about usage

Comment 3

[Brendan Eich [:brendan]]

What is the code size effect?  Again there's a greater-good argument about using NSPR's plhash.[ch] (with macro-renaming) and XPCOM's pldhash.[ch] (which are the same as jsdhash.[ch] via plify_jsdhash.sed, note well -- so any patch here must include xpcom/ds/pldhash.[ch] changes too).  That would save relatively small but real footprint in Firefox.

/be

Comment 4

[Igor Bukanov]

(In reply to comment #3)
> What is the code size effect?

0: the size of optimized build of js shell did not change. The real story behind the patch is that it simplifies GC debugging as it no longer jumps between jsgc.c->jsd?hash.c->jsgc.c during marking/sweeping.

>  Again there's a greater-good argument about
> using NSPR's plhash.[ch] (with macro-renaming) and XPCOM's pldhash.[ch] (which
> are the same as jsdhash.[ch] via plify_jsdhash.sed, note well -- so any patch
> here must include xpcom/ds/pldhash.[ch] changes too).  That would save
> relatively small but real footprint in Firefox.

Does it mean that the patch should declare HashIter API public?

Comment 5

[Brendan Eich [:brendan]]

The thing is, if we want to use plhash instead of jshash, we will have to #ifdef, so we could leave the JSHashIter stuff outside that #ifdef, but then it would know all about internals over in plhash.[hc] in NSPR.  We don't share source via a hand-run sed script, even, so that could be a bad idea.  OTOH, this code is very stable and old.

Best path would be to get plhash to get a matching PLHashIter API.  Cc'ing wtc to get his thoughts.

The jsdhash/pldhash situation is much easier, you just need to sed each of your modified jsdhash.[ch] using plify_jsdhash.sed writing to xpcom/ds/pldhash.[ch].

/be

Comment 6

[Igor Bukanov]

Attachment: Update with xpcom/glue/pldhash.[ch] changes

Comment 7

[Igor Bukanov]

Regarding hash code sharing:

I looked at http://lxr.mozilla.org/seamonkey/ident?i=PL_NewDHashTable

AFAICS in all the cases one can replace PLDHashTable by nsTHashtable<T>. The latter is just a wrapper around very C-specific implementation. From the amount of code that went into the wrapper I suspect that pure C++ version would reduce the code by the same amount as savings from sharing between JS and XPCOM.

Moreover, the current implementation of D?HashTables waste memory in a few cases where it is used in JS code. 

For example, consider the cache of inflated strings where DHashTable is used to map JSString* into char* with byte-encoded characters. Since DHashTable does not know that the key hash is the key itself, it waste the memory to store the hash. In addition, since the inflated bytes are allocated on the heap, one can store JSString pointer there as well reducing the overhead of unoccupied hash cells. 
Similarly a specialized table can reduce the overhead of atom, root and lock hashes. But that removes most of the cases for D?HashTable and the rest does not all the functionality provided by the current implementation.

So why share something that is too generic to be efficient for most of its applications?

Comment 8

[Brendan Eich [:brendan]]

Igor: I am not proposing using nsTHashtable in SpiderMonkey -- for one thing, SpiderMonkey is still all-C, no-C++.  It has been for ~10 years, and now is not the time to change.

What I proposed in comment 3 was simply avoiding duplicating of jshash and jsdhash when identical-but-for-names versions of these .c files exist in NSPR and XPCOM.  I am not so concerned about jsdhash, as we share source still using that sed script, and the savings are not so great -- but with NSPR, we could share not only plhash.c, but also prdtoa.c and possibly other files that forked long ago from NSRP.  These are all C files, not C++.

JSDHashTable is general-purpose.  With some more macro madness, akin to poor-man's C++ templates, it could be made to avoid storing keyHash, but watch out for the free and removed sentinel-values, and the need for a collision bit.

/be

Comment 9

[Igor Bukanov]

I am not working on the bug right now.

Comment 10

[Luke Wagner [:luke]]

Replaced by js::HashMap/Set with Range iteration.