See bug 374037 comment 0. The 10K times are 4 times as big as the 5K times.

Analysis: About 12% of total time is in nsFrameList::LastChild. That's basically bug 233463. This part is known to be O(N^2), with a small constant. About 20% of the time is spent on security checks (cross-document access and all that jazz). Frame construction in general (including the time taken by LastChild() above) is about 26% of total time.

I should note that over here Firefox 2 takes about 5 seconds to render that part of the testcase, while current trunk takes about 9 seconds. That's not quite as big a slowdown as the one seen in bug 374037, and matches up well with the time spent in frame construction. I've filed bug 380475 on a regression in the speed of the security checks.

On this testcase, for me, Firefox 2 takes about 4.6 seconds and trunk takes about 22. Profile analysis: 66% of the time is spent in frame construction. Of this time, most is spent in the pango font group code... which means I should reprofile once my opt build has the recent changes to that code in it (on Sunday). I'm not seeing any obvious O(N^2) algorithms here other than the LastChild() thing (which is 8% of total time). Of course if you discount the pango font group mess, I'm also not seeing the sort of slowdown reported. jwatt, tor, do you know what could be O(N^2) here?

OK, I profiled with the new build, and I see the same thing: almost 50% of total time on the testcase is spent under gfxPlatformGtk::CreateFontGroup, called by nsSVGGlyphFrame::DidSetStyleContext. It seems that on each call to this method we end up under gfxFontconfigUtils::ResolveFontName, which calls gfxFontconfigUtils::UpdateFontListInternal... which goes off into FontConfig land and we end up waiting on it for a while as it rereads stuff from disk (!). Oh, and we spend a bunch of time under gfxPangoFontGroup::FontCallback doing IndexOf() on string arrays. Not sure what's up there.

IndexOf() in gfxPangoFontGroup::FontCallback should be removed. see bug 366664.

(In reply to comment #2) Boris, FWIW I repeated my tests from bug 374037 comment 0 with the latest trunk and got more or less the same numbers as before, don't know why you see less of a slowdown unless the profile looks very different on a windows platform. As you say, my results are that pretty much the whole thing is N^2. Have you tried profiling the 10K case ?

I tried doing that for the text elements (by changing the "50" in the loop condition to "100"). Time for the testcase doubled, pretty much exactly.... So yes, it could be that something platform-specific is going on here. :(

....so ideally we need someone who can profile it on Windows XP. Maybe I could do it but I'm not instantly geared up for that. Running a few more specific tests I think we might be able to pin it down a little bit. Adding the SVG elements to a <g> that doesn't exist in the document shows no sign of non-linear behaviour until you get to really silly numbers Tight SVG SVG HTML Loop rectangle text DIV 5K .938 1.797 2.235 1.203 10K .954 3.188 3.891 2.297 20K .922 6.391 8.361 5.391 40K .937 13.033 26.129 17.300 But adding them to the document but using suspendRedraw() introduces non-linear behaviour right away Tight SVG SVG HTML Loop rectangle text DIV 5K .938 3.157 9.282 1.125 10K .938 10.861 29.253 2.094 20K .922 35.958 99.497 4.266 So would that point to frame creation rather than DOM or rendering ? Can't think why there'd be a platform-specific effect though unless it's something like memory allocation performance. I guess one would expect SVG to use more than HTML (?). Using the <g>, my firefox.exe process climbs quickly from an initial 25M or so, reaching about 70M at the point just before the <g> is added to the document and then rises to 105M in a few seconds until the image appears. Adding directly to the document and using suspendRedraw, the memory climbs much more slowly from the same starting level of 25M, reaching about 100M just before the call to "unsuspendRedraw". Then it climbs just a little bit to 105M and the image appears almost at once.

Seems O(N) nowadays.