Closed
Bug 374906
Opened 17 years ago
Closed 17 years ago
avoid the need for getKey callback in pldhash/jsdhash
Categories
(Core :: XPCOM, defect)
Core
XPCOM
Tracking
()
RESOLVED
FIXED
People
(Reporter: dbaron, Assigned: dbaron)
References
Details
(Whiteboard: [patch])
Attachments
(5 files, 2 obsolete files)
7.18 KB,
patch
|
brendan
:
review+
|
Details | Diff | Splinter Review |
5.05 KB,
patch
|
brendan
:
review+
|
Details | Diff | Splinter Review |
58.72 KB,
patch
|
benjamin
:
review+
|
Details | Diff | Splinter Review |
11.95 KB,
patch
|
benjamin
:
review+
|
Details | Diff | Splinter Review |
3.14 KB,
patch
|
benjamin
:
review+
|
Details | Diff | Splinter Review |
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?
Assignee | ||
Comment 1•17 years ago
|
||
Assignee | ||
Comment 2•17 years ago
|
||
Probably FindFreeEntry is a better name than FindFirstFree.
Assignee | ||
Updated•17 years ago
|
Whiteboard: [patch]
Comment 3•17 years ago
|
||
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 4•17 years ago
|
||
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
Comment 5•17 years ago
|
||
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•17 years ago
|
||
There are no binary compatibility issues (might be more of a problem on stable branches). Remove old entries at will.
Assignee | ||
Comment 7•17 years ago
|
||
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)
Assignee | ||
Comment 8•17 years ago
|
||
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 9•17 years ago
|
||
Comment on attachment 259337 [details] [diff] [review] patch to stop using the getKey callback r=me, thanks. /be
Attachment #259337 -
Flags: review+
Assignee | ||
Updated•17 years ago
|
Attachment #259361 -
Flags: review?(brendan)
Assignee | ||
Updated•17 years ago
|
Attachment #259337 -
Attachment is obsolete: false
Assignee | ||
Comment 10•17 years ago
|
||
I landed attachment 259337 [details] [diff] [review] on the trunk.
Assignee | ||
Comment 11•17 years ago
|
||
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)
Assignee | ||
Comment 12•17 years ago
|
||
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)
Assignee | ||
Comment 13•17 years ago
|
||
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)
Assignee | ||
Comment 14•17 years ago
|
||
This removes GetKey from nsDoubleHashtable's key types. This code was also made unused by attachment 259468 [details] [diff] [review].
Assignee | ||
Updated•17 years ago
|
Attachment #259470 -
Flags: review?(benjamin)
Comment 15•17 years ago
|
||
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•17 years ago
|
Attachment #259468 -
Flags: review?(benjamin) → review+
Updated•17 years ago
|
Attachment #259469 -
Flags: review?(benjamin) → review+
Updated•17 years ago
|
Attachment #259470 -
Flags: review?(benjamin) → review+
Assignee | ||
Comment 16•17 years ago
|
||
Final 4 patches checked in. Filed bug 375551 as followup on nsAtomTable.
Status: NEW → RESOLVED
Closed: 17 years ago
Resolution: --- → FIXED
Updated•17 years ago
|
Flags: in-testsuite-
You need to log in
before you can comment on or make changes to this bug.
Description
•