63890 - GetPrimaryFrame could still be faster, and more space efficient

Status: RESOLVED FIXED

(Core :: Layout, defect, P3)

Description

[buster]

Even after I check in my fix for bug 56432, GetPrimaryFrame() will still need
some work.

1. Part of the reason we scrounge around in the frame tree is because we don't
pre-seed the primary frame map for inline frames or text frames.  This is
because we don't want to unnecessarily bloat the primary frame map in cases
where we never ask for the primary frame (such as caret placement or selection.)
 I think this is too extreme a position.  It would be nice to seed the primary
frame map with the first n inline and text frames, in a classic speed/size
tradeoff.
We should examine what it would take to add the code to do this. It's probably a
counter on nsCSSFrameConstructor; a little logic in the 2 places where inline
and text frames explicitly turn off notification to the primary frame map; and
maybe a pref to tell us the cut-off for notification to the primary frame map
for inline and text frames.  That way, the normal desktop browser could default
to some reasonable number (maybe 100?), while memory-constrained systems could
set the bar lower, even to 0 (where we are today.)

2. We need to add a lookup into the undisplay map to skip searches if we already
know the content has no frame.  A lookup in a hashtable map is much, much faster
than walking around in the frame tree, even with the new hint mechanism.
nsCSSFrameConstructor calls SetUndisplayedContent() for every content node that
has display: none.
Today, the undisplay map doesn't quite support what we need to make use of this.
We need to see if we can add a method to make a search for aContent
very fast in the embedded hash table.
This would almost completely remove the lookup penalty for things undisplayed
content like <SCRIPT> and comments in very large documents.

3. the frame manager should be a memory pressure listener, and should clear it's
primary frame map when requested.  the primary frame map is purely a cache, so
we should be able to dump it in low memory situations.

Comment 1

[buster]

it would be nice to get some data for the ideas I've suggested in this bug, to
see which if any of them should be implemented.

cc-ing some people who might care enough to help get some data, suggest ways
that data could be collected, suggest priorities, etc.

Comment 2

[Hixie (not reading bugmail)]

cc'ing relevant mozilla.org drivers and MathML module owner. See above.

Comment 3

[Judson Valeski]

comments to Buster's points.
1. yup, mem vs. speed tradeoff. If you wind up w/ this "object cache" it should
be a nsIObserver listening to the MEMORY_PRESSURE topics so it can clear itself
when memory becomes constrained.
2. the indexing idea sounds great, though maybe overkill. How's the tree
searched? I don't know how big the tree is, but maybe we could apply a faster
algorithm there (or is adding the index, basically the faster aglo :-))?
3. :-)

Comment 4

[buster]

the portion of this that should be moz0.9 is the memory pressure listener (3).
The rest of it is optional, nice to have.  (2) is more important than (1).

Comment 5

[buster]

making the pres shell a memory pressure listener is easy enough.  Make it an
observer, and add a FlushMemory Call to the frame manager as well. But one trick
is to be sure when you tell the frame manager to dump memory, you should not
delete mPrimaryFrameMap because you need to always have a handle on at least one
frame, the root.  So, you should:
get the primary frame for the root
clear mPrimaryFrameMap
re-insert the root primary frame

Comment 6

[rbs]

*** Bug 70292 has been marked as a duplicate of this bug. ***

Comment 7

[Mike Pinkerton (not reading bugmail)]

i'll put in my vote (and hyatt's) that this doesn't need to be a tree. It should 
just be a hash table.

Just as a side note, GPFF is about 15% of window activation time (brining a 
window to the fg).

Comment 8

[Chris Waterson]

pink, re 15% of activation time. Is this because of time spent navigating the 
DST? Or is time spent searching for frames that were never put into the GPFF map 
in the first place?

Comment 9

[karnaze (gone)]

Moving to mozilla1.0

Comment 10

[rbs]

Interesting. A posting of Troy which shows that he first tried the hashtable 
before moving on to the DST.
=====================

      Subject: Checkin (layout) - pres shell
         Date: 16 Jul 99 03:34:37 GMT
         From: [e-mail] (Troy Chevalier)
 Organization: Netscape Communications
           To: raptor-cvs <[e-mail]>
   Newsgroups: netscape.public.mozilla.layout.checkins

I changed the pres shell to use a digital search tree instead of the
hash table for the primary frame map. This should cut down on the amount
of memory that's needed, especially in the case where there are a lot of
entries in the primary frame map.

Troy

Comment 11

[Brendan Eich [:brendan]]

Troy was no doubt comparing to nsHashtable, which is a malloc pig (see bug
72722).  Sfraser proposed PATRICIA as a more space-efficient d.s. than the DST,
and shaver was going to investigate those vs. raw pldhash.

/be

Comment 12

[Tom Mraz]

Not platform specific.

Comment 13

[Kevin McCluskey (gone)]

Build reassigning Buster's bugs to Marc.

Comment 14

[Markus Hübner]

Reassigning as attinasi won't work on this bug in the next time

Comment 15

[karnaze (gone)]

Buster has not been on the project for over a year. Reassigning back to default 
layout placeholder.

Comment 16

[Boris Zbarsky [:bzbarsky]]

So... Is GPFF still showing up in profiles?  Are any of the ideas in this bug
still relevant?

Comment 17

[Robert O'Callahan (:roc) (email my personal email if necessary)]

I think we should just leave this open until the issue is proved one way or the
other.

Comment 18

[Boris Zbarsky [:bzbarsky]]

This is fixed; nsIContent now has an nsIFrame* member.