poor performance in GetPrimaryFrame is killing selection performance in large documents, and hurting performance elsewhere (need data to back this up.) GPF has a hash table mapping content->frame that stores all non-text-nodes as they are found. This helps somewhat. But Troy was reluctant to store text nodes because the size of the hash table would get very large. I propose we modify GPF to have 2 separate caches: 1) a node cache identical to the hash table we use today 2) a second MRU cache that holds only text nodes, and has a bounded size, whose size can be controlled by a pref (so platforms with different memory profiles can take advantage of available memory, etc.) Both caches should be memory-pressure API listeners, and clear the cache on low-memory requests. Comments welcome.

I can probably do this in a day, but I'm not sure what buster thinks the performance win would be.

moving to mozilla0.9

moving to mozilla0.9

The basic problem is there is an factorial algorithm lurking inside GetPrimaryFrame, when it's used as in selection, to linearly get the primary frame for a sequential series of content nodes (by far, the most interesting and common use case.) We do some frame tree pruning, but not nearly enough. The solution is to pass down hints about how we can prune the search tree further than we already do. We already have the hint in memory for the vast majority of cases. Almost always, when asking for a content node's primary frame, we've already asked for and cached that content node's previous sibling's primary frame. If we use that frame as the hint, then most the time we only have to walk the sibling list starting at the hint (not the beginning, as we do today.) Usually this reduces to a very quick traversal with a very small number of steps. I have a prototype that looks promising.

I've just attached the diffs for the important part of the performance work. If you apply the patch and recompile, you'll be using the new code. If you want to help verify that this code is correct, you can do 2 things: 1) run it. browser the web, select things, run the other applications, etc. 2) run it with validation turned on. to all.js, add pref("nglayout.debug.verifyFastFindFrame", true); This will completely negate your performance increase. But it will run the code the fast way, then re-run it the slow way to verify that we get the same answer both ways. It will raise an assertion if there is a mismatch. There are a small number of false-positives that I haven't quite factored out yet, all having to do with getting back a null frame for text content that contains only insignificant white space. I still need to add some comments, etc. But preliminary reviews would be great. I'll send out a note to reviewers@mozilla.org.

r=rods

Nits. - nsFrameManager.cpp doesn't need to include `windows.h' - Should the statistics gathering stuff be #ifdef'd? - Use #ifdef's to remove statistics output, not comments in nsFrameManager.cpp I'm still trying to grok what's going on here, will comment back as soon as I figure it out :-)

More nits... - In FrameManager::GetPrimaryFrameFor(), beware that nsIContent::IndexOf() does a linear scan through children. This may cause grief; e.g., on LXR pages where there is high fan-out. - In FrameManager::GetPrimaryFrameFor(), this code: + if (hint.mPrimaryFrameForPrevSibling) { + hintHits++; + styleSet->FindPrimaryFrameFor(presContext, this, aContent, aResult, &hint); + } + else { + styleSet->FindPrimaryFrameFor(presContext, this, aContent, aResult); + } will generate two complete call setup and teardowns in gcc. I realize that you just want to keep stats, but I'd suggest the more verbose: #ifdef NS_DEBUG if (hint.mPrimaryFrameForPrevSibling) ++hintHits; #endif styleSet->FindPrimaryFrameFor(presContext, this, aContent, aResult, hint.mPrimaryFrameForPrevSibling ? &hint : nsnull); so that the release build doesn't suffer. This generally looks real good, so if you could just address those nits, I'm happy!

kin suggested http://www.autsch.de/bitsteller/linux_penguin.html as a good test case.

fix checked in. please see bug 63890 for remaining work in this area.

Marking verified per last comments