avoid the need for getKey callback in pldhash/jsdhash

RESOLVED FIXED

Status

()

RESOLVED FIXED
12 years ago
12 years ago

People

(Reporter: dbaron, Assigned: dbaron)

Tracking

Trunk
Points:
---
Dependency tree / graph
Bug Flags:
in-testsuite -

Firefox Tracking Flags

(Not tracked)

Details

(Whiteboard: [patch])

Attachments

(5 attachments, 2 obsolete attachments)

pldhash/jsdhash requires a getKey callback to get the key from an entry.  This is painful for some callers (such as one I was trying to write) whose key can't fit within a void*, but can be stored in the value in a compressed way that prevents it from being represented in memory as the key structure.  (For example, I wanted a key for nsRuleNode composed of a pointer plus 4 additional bits, stored in nsRuleNode in the high bits of other values.)

I realized that pldhash/jsdhash doesn't need the getKey callback at all.  It's only using it because ChangeTable calls SearchTable.  However, we know that this particular call to SearchTable will never find a matching entry, since we're adding an entry that's already in the table.  So it actually doesn't need the key.

The patch I'm about to attach changes the implementation of pldhash/jsdhash so that it never uses the getKey callback.  It seems to work fine at first glance.  I decided to make a copy of SearchTable and hard-code the invariants of ChangeTable as a caller since adding an extra parameter would have created a lot of extra (and confusing) branches.

What I'm not sure is what the binary compatibility issues related to pldhash being part of the XPCOM glue are.  Can we change the signature of its data structures?  Do we know that we'll never get the old version that some binary component linking in the glue carries with it, and that that component will never get our new version?
Created attachment 259308 [details] [diff] [review]
patch to stop using the getKey callback
Probably FindFreeEntry is a better name than FindFirstFree.
Whiteboard: [patch]
This supersedes bug 216172 -- good thinking, dbaron!

I don't know what if any binary compatibility constraint we have, but one idea is to leave getKey there in the ops struct and just not call it. I'll review next.

/be
Blocks: 216172
Comment on attachment 259308 [details] [diff] [review]
patch to stop using the getKey callback

FindFreeEntry is a better name.

Don't use NS_ASSERTION (how can that work in js/src?), use JS_ASSERT and let the sed script rename it for pldhash.

/be
Good to see this keep getKey in the ops struct. We can remove it in moz2, and make further fixes in another bug. We might want to abstract the keyHash storage and collision flagging, as I believe Google's double hashtable code does, and allow aggressively space-optimizing implementations to squeeze entries down below the two word minimum of today's jsdhash design.

I'll WONTFIX the other bug.

/be

Comment 6

12 years ago
There are no binary compatibility issues (might be more of a problem on stable branches). Remove old entries at will.
Created attachment 259337 [details] [diff] [review]
patch to stop using the getKey callback

Here's a patch with the new name, and perhaps a slightly improved comment.

I'm certainly happy with removing the getKey callback from the ops struct; it should more than make up for the codesize change here.  But I'd rather land this part first and make sure it doesn't break anything before doing that.

Note that this patch is doubled; you're seeing the NS_ASSERTION in the pldhash.c half.
Attachment #259308 - Attachment is obsolete: true
Attachment #259337 - Flags: review?(brendan)
Created attachment 259361 [details] [diff] [review]
patch to stop using the getKey callback

Toss in one more tweak:  move the common chunk of code that's right before the double-hashing loop and again at the end of it to be at the beginning of the loop, in both SearchTable (where it differed slightly, but can be fixed by initializing firstRemoved to null before the loop and using the second version) and in FindFreeEntry (where it was identical).
Attachment #259337 - Attachment is obsolete: true
Attachment #259361 - Flags: review?(brendan)
Attachment #259337 - Flags: review?(brendan)
Comment on attachment 259337 [details] [diff] [review]
patch to stop using the getKey callback

r=me, thanks.

/be
Attachment #259337 - Flags: review+
Attachment #259361 - Flags: review?(brendan)
Attachment #259337 - Attachment is obsolete: false
Created attachment 259466 [details] [diff] [review]
loop cleanup in comment 8

This patch is the loop cleanup described in comment 8 as its own patch, now that attachment 259337 [details] [diff] [review] landed.  Note that in the first change, diff decided to show the larger moved hunk rather than the smaller one, but it's just reversing the order of the two pieces within that loop.
Attachment #259361 - Attachment is obsolete: true
Attachment #259466 - Flags: review?(brendan)
Created attachment 259468 [details] [diff] [review]
remove getKey from PLDHashTableOps/JSDHashTableOps

This patch removes the getKey method from PLDHashTableOps and
JSDHashTableOps.

This patch is basically code removal, but it does have some other
changes of interest:
 * The comment change in jsdhash.h and pldhash.h.
 * The ops in nsCSSRuleProcessor, where I was crossing virtual functions
   and need the getKey callback.  I made a pseudo-derived-class of
   PLDHashTableOps and kept the getKey callbacks on the tables where I
   need them (using them from the matchEntry callback), although I gave
   the callback a signature that was more useful to me.  (This also 
   fixes my XXX comment there about the bad constness in the getKey
   callback.)
 * I simplified what's stored in the entries in nsStaticNameTable; it
   was storing an extra word in the entries because of the need to
   implement getKey.
 * I added an XXX comment that we should do something similar to
   simplify nsAtomTable.  I should file a followup bug on that.
 * I converted a few callers to use PL_DHashGetStubOps:
   nsContentSupportMap and nsJavaXPCOMBindingUtils because they made 
   their own copies of the stub ops.

I plan to trim the nsTHashtable API and nsDoubleHashtable APIs in
followup patches.  This patch only removes their implementation of the
getKey callback without removing the parts of their APIs used to
implement it.
Attachment #259468 - Flags: review?(benjamin)
Created attachment 259469 [details] [diff] [review]
remove GetKeyPointer from nsTHashtable key implementations

This patch removes the GetKeyPointer method from nsTHashtable key templates.  It was made unused (except for one caller in nsFontMetricsOS2.h that I fixed ...not that that code is even built anymore) by attachment 259468 [details] [diff] [review].
Attachment #259469 - Flags: review?(benjamin)
Created attachment 259470 [details] [diff] [review]
remove GetKey from nsDoubleHashtable key types

This removes GetKey from nsDoubleHashtable's key types.  This code was also made unused by attachment 259468 [details] [diff] [review].
Attachment #259470 - Flags: review?(benjamin)
Comment on attachment 259466 [details] [diff] [review]
loop cleanup in comment 8

>         if (ENTRY_IS_REMOVED(entry)) {

JS/NS_UNLIKELY() around the condition. Need plify_jsdhash.sed addition to s/JS_UNLIKELY/NS_UNLIKELY/g.

/be
Attachment #259466 - Flags: review?(brendan) → review+

Updated

12 years ago
Attachment #259468 - Flags: review?(benjamin) → review+

Updated

12 years ago
Attachment #259469 - Flags: review?(benjamin) → review+

Updated

12 years ago
Attachment #259470 - Flags: review?(benjamin) → review+
Final 4 patches checked in.  Filed bug 375551 as followup on nsAtomTable.
Status: NEW → RESOLVED
Last Resolved: 12 years ago
Resolution: --- → FIXED

Updated

12 years ago
Flags: in-testsuite-
You need to log in before you can comment on or make changes to this bug.