216172 - extend jsdhash/pldhash to allow complex key types

Status: RESOLVED FIXED

(Core :: JavaScript Engine, enhancement, P5)

Description

[Benjamin Smedberg]

I need to write a hashtable with a complex key-type (for an extension to the
static component loader, no bug yet):

struct keyPair {
  nsIFile* file;
  nsACString& string;
};

To make a long story short, a complex key type like this is very difficult to
write with the current pldhash API, because the key is a reference when passed
in, but a concrete class in the actual hashtable entry. I have found that I can
solve this problem by changing the "GetKey" hashtableop into a "MatchEntries"
op, without measurably affecting codesize or speed.

Comment 1

[Benjamin Smedberg]

Attachment: Complete patch to jsdhash/pldhash

This is a complete patch... i can break it down into smaller pieces for review,
if that would be helpful.

Comment 2

[Benjamin Smedberg]

Comment on attachment 129804 [details] [diff] [review]
Complete patch to jsdhash/pldhash

I know brendan/dougt should review this... I hope I don't need to get MOA from
every place I've touched?

Comment 3

[Brendan Eich [:brendan]]

This certainly affects performance, both code size and runtime, of SearchTable
and other parts of the *dhash.c code.  Before writing a big patch that I'm
unlikely to approve, please say more than "To make a long story short, a complex
key type like this is very difficult to write ...."  Tell the long story.

/be

Comment 4

[Benjamin Smedberg]

There are two use-cases I've encountered:

1)
alecf's atom-table currently has a char* key. However, there are frequently
non-flat ACStrings being passed into the API, that must be flattened, which is a
performance hit (see bug 109129). I would like to make the "void* key" a
nsACString*, but the actual key entry must still be a char*. There is no simple
way to implement nsACString* GetKey() because I can't allocate a temporary
object. Using a matchEntries callback avoids the problem entirely.

2)
I need a hash entry keyed on a nsIFile/ACstring pair. I can't just concatenate a
filepath, because on mac nsIFile doesn't guarantee unique string paths. So I
want my "void* key" to be:

typedef struct*
{
  nsIFile* aFile;
  nsAString& aString;
} filestringpointertype;

The entry class looks so:

struct nsFileStringEntry : public PLDHashEntryHdr
{
  nsCOMPtr<nsIFile> aFile;
  nsSharableCString  aString; /* or char *, it might end up in an arena */
  /* data members */
};

Again, implementing "GetKey" on this class requires a temporary.

codesize:
On linux, gcc 3.2, this patch increases the codesize of libmozjs.so by 88 bytes:
libmozjs.so
        Total:          +88 (+121/-33)
        Code:           +88 (+121/-33)
        Data:            +0 (+0/+0)
                +88 (+121/-33)  T (CODE)
                        +88 (+121/-33)  UNDEF:libmozjs.so:T
                                +42     resolving_MatchEntries
                                +38     SearchTable
                                +26     JS_DHashMatchEntriesStub
                                +15     JS_DHashTableOperate
                                -11     resolving_GetKey
                                -11     JS_DHashGetKeyStub
                                -11     ChangeTable

performance stats from the JS shell forthcoming. I don't have a quiet enough
machine to make TS/TP/TXUL tests practical.

Comment 5

[Benjamin Smedberg]

Attachment: other method of implementing SearchTable

to allay concerns about  ?: inside a loop, this method calls SearchTable in a
different manner, using a function pointer.

Comment 6

[Brendan Eich [:brendan]]

Attachment: add optional freeKey op and spares for binary compatibility

This is what I'd rather see used by the few hard cases that need a different
internal or stored key type from external (passed to *_DHashTableOperate) key
type.  In addition to the {js/src/js,xpcom/ds/pl}dhash.[ch] files, I changed
two js/src/*.c files' JSDHashTableOps initializers to avoid warnings.

Benjamin, if you are ok with this approach, please supply the big patch that
depends on this one, the one that changes all other *dhash.h clients similarly.
Or tell me to do it! ;-)

/be

Comment 7

[Benjamin Smedberg]

brendan: I was dreaming about this last night ;-(  You metnioned using a static
"temporary" object for the "getKey" stub, and I think that will work for both of
my cases. The following should be documented:

1) "getKey" is only called during a "non-const" JS_DHashTableOperate or
JS_DHashTableEnumerate

2) the result of "getKey" is used before "getKey" is called again

So really, I no longer need a patch to jsdhash, except for documentation. If you
are still interested in the patch you posted, I have one concern: it adds a
restriction that the void* key be non-null.

Comment 8

[Benjamin Smedberg]

discussed, WONTFIX

Comment 9

[Brendan Eich [:brendan]]

Or maybe WORKSFORME?  I'm not a bugzilla best-resolution-for-RESOLVED guru.

/be

Comment 10

[Phil Schwartau]

Marking Verified -

Comment 11

[Brendan Eich [:brendan]]

dbaron and bryner expressed interest in something like the patch for this bug,
so I've cc'd bryner.

To answer bsmedberg's comment 7, there are already two comments describing
getKey in jsdhash.h.  I'll beef up the second of these to talk about how getKey
is not called again until the last call's return value has been used and is no
longer needed.  I'll do that *unless* someone makes a new case for the patch in
this bug, though, to avoid CVS churn.

The point about disallowing (void*)0 return from getKey is well-taken.  Perhaps
I should just ignore potential OOM errors from getKey in the non-null freeKey case.

/be

Comment 12

[Brendan Eich [:brendan]]

mine.

/be

Comment 13

[Brendan Eich [:brendan]]

Dbaron removed the need for this bug when he patched bug 374906.

/be