Closed Bug 110911 Opened 23 years ago Closed 23 years ago

remove nsDST

Categories

(Core :: Layout, defect, P2)

Product:
Core
Component:
Layout
Type:
defect

Tracking

()

Status:
RESOLVED FIXED
Milestone:
mozilla0.9.7

People

(Reporter: dbaron, Assigned: dbaron)

Details

Attachments

(2 files, 2 obsolete files)

patch addressing brendan's comments
42.60 KB, patch
attinasi
: review+
Details | Diff | Splinter Review
hash instrumentation to test distribution of keyHash values
2.67 KB, patch
Details | Diff | Splinter Review 
I have a patch to remove nsDST, and replace its users with pldhash, which should
be faster and use less memory (particularly in the cases where the value already
stores the key).  I've yet to test that it actually improved things, though. 
(It would be possible to change AllocTable/FreeTable to use the pres shell's
arena, but I don't think the performance improvement would be significant and I
suspect it could lead to bloat if nothing else takes objects of the table sizes
off the free list.)
Attached patch patch (7) (obsolete) — — Splinter Review 
There were three maps converted from nsDST to pldhash:
 * PresShell::mSubShellMap - a nondescript key,value-style entry.
 * FrameManager::mPrimaryFrameMap - Similar to mPlaceholderMap below, but I
didn't make the same changes to the API, although they might be worth making. 
I did add an assertion, and discovered that nsImageMap was using the primary
frame map to map from content other than the frame's content to a frame.  It
didn't need to use the primary frame map since it was using the mapping from a
data structure already in the frame tree, so I just gave the Area structures a
pointer back to their image frame.
 * FrameManager::PropertyList::mFrameValueMap - standard key,value-style entry.
 It was nice to discover that nsDST.h and nsIFrameManager.h define a bunch of
constants to the same values so that they can pass nsDST parameter/return
values straight through, and I had to generate these return values / handle the
options myself for this conversion.

I also converted from a wrapped plhash:
 * FrameManager::mPlaceholderMap - since it can now use an entry with a value
that stores the key.  I changed the APIs for accessing this map to make it
clearer so they don't require the key (the out-of-flow frame) as a parameter,
since the value (the placeholder frame) has a pointer to it.
It's also worth noting that I added an NS_WARNING when somebody overwrites an
entry in the primary frame map.  A few callers do this -- I haven't investigated
yet, but it seems silly.  However, the old code handled it silently by overwriting.
Oh, and one other change (hidden in the midst of the nsIFrameManager API change
for placeholders).  I had to give the root frame an mContent -- it was
previously initialized with a null mContent.  This hasn't caused any noticable
problems (yet, anyway).  And I did check for leaks.
Attached patch patch fixing one-line perf hit (obsolete) — — Splinter Review 
This patch fixes a costly mistake in GetPrimaryFrameFor -- for the O(N^2) check
to compute the "hint", I looked the wrong content node in the hashtable,
causing the hint to always be absent.  That mistake demonstrated that the
O(N^2) optimization really is an optimization, though.

Numbers on jrgm's tests show no measurable change:
  without changes:
    1021/1028/549/2960
    1010/1017/558/2954
  with changes:
    1014/1019/550/2972
    1017/1022/561/2965
Attachment #58477 - Attachment is obsolete: true
And the patch should really also include the cvs-removal of nsDST.{h,cpp}.
Status: NEW → ASSIGNED
Priority: -- → P2
Target Milestone: --- → mozilla0.9.7
Comment on attachment 58506 [details] [diff] [review]
patch fixing one-line perf hit

If nearly all frame managers have primary frame and placeholder maps, then I
agree that these members should be PLDHashTables, not pointers to PLDHashTables
that are optionally allocated.	Dumb question: do most/all frame managers need
these maps?

If PL_DHashTableInit fails, reset .ops = nsnull so you don't Finish an
uninitialized or partially initialized table.  You don't check for Init failure
when initializing mPlaceholderMap -- best do that too, with the .ops = nsnull
drill on failure.

Has that NS_WARNING on redundant add fired yet?

r/sr=brendan@mozilla.org with the necessary changes.

/be
Attachment #58506 - Flags: superreview+
This checks for Init failure in all three places.  I left the hashtables as
members rather than changing to pointer members -- every frame manager will
have a primary frame map, every property list will have a frame-value map, and
I suspect most frame managers will have a placeholder map -- certainly all XUL
frame managers will (for popups), and many HTML ones will as well (for floats
or absolutely positioned elements).  Even if that's not completely true, it's a
small amount of memory and it's more consistent.
Attachment #58506 - Attachment is obsolete: true
Memory statistics for bringing up a browser window with my homepage in it (3
runs each) show no significant change:

without changes:

    Leaks: 1295074 bytes, 4276 allocations
    Maximum Heap Size: 8441199 bytes
    46483384 bytes were allocated in 331975 allocations.

    Leaks: 1295074 bytes, 4274 allocations
    Maximum Heap Size: 8410789 bytes
    46474335 bytes were allocated in 332250 allocations.

    Leaks: 1295074 bytes, 4278 allocations
    Maximum Heap Size: 8330643 bytes
    46420709 bytes were allocated in 331249 allocations.

with changes:

    Leaks: 1294994 bytes, 4270 allocations
    Maximum Heap Size: 8410878 bytes
    46498445 bytes were allocated in 332744 allocations.

    Leaks: 1294994 bytes, 4274 allocations
    Maximum Heap Size: 8330446 bytes
    46429490 bytes were allocated in 331626 allocations.

    Leaks: 1295004 bytes, 4270 allocations
    Maximum Heap Size: 8333774 bytes
    46610742 bytes were allocated in 332893 allocations.
From a private email exchange:

marc attinasi wrote:
> If there is no measurable difference in performance (speed) or memory
> usage, then why are we doing this? From the initial comment it looks
> like you were expecting a performance improvement at least.

dbaron replied:
* We don't need yet-another-data-structure if we don't get any benefit
from it.
* It should be faster in some cases -- probably on larger pages.  I
should try to find and measure those cases, I guess...

I agree with he first comment and remain interested in seeing some performance
benefits as aluded to in the second comment. Patch looks good too-  r=attinasi

Comment on attachment 60499 [details] [diff] [review]
patch addressing brendan's comments

r=attinasi
Attachment #60499 - Flags: review+
This patch also seems to fix the patch on the minimized testcase in bug 105619
-- I think DST node removal was failing in some way on that testcase.  I'm
really not too interested in debugging it further, though...
the checkin has caused bug 113810.
Fix checked in 2001-12-05 21:45 PDT.
Status: ASSIGNED → RESOLVED
Closed: 23 years ago
Resolution: --- → FIXED
This shows the distribution of hash1 is quite good, with few collisions:

Distribution of counts of "buckets" for first hash:
  0: 177992
  1: 70216
  2: 12143
  3: 1660
  4: 131
  5: 2
on a testcase with 100000 paragraphs.

The distribution of hash2 is not so good (although it's not all that bad -- the
largest group is 21 rather than 5), but that's far less important and perhaps
is even intended that way.
The secondary hash is a different beast: it must be relatively prime to the
table size, and it does not directly address the table -- rather, it gives a
"stride" by which the double hash probe steps around the table in a
modular-arithmetic fashion, starting at the primary hash if it collided with an
existing entry.  So, you might rather model collisions and measure the mean and
variance for "chain" length -- but see pldhash.c's PL_DHashTableDumpMeter.

/be
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Creator:
Created:
Updated:
Size: