Investigate O(N^2) performance in bug 374037




11 years ago
8 months ago


(Reporter: bz, Unassigned)



Windows XP
Dependency tree / graph

Firefox Tracking Flags

(Not tracked)



(4 attachments, 2 obsolete attachments)

See bug 374037 comment 0.  The 10K times are 4 times as big as the 5K times.
Blocks: 374037
Created attachment 264569 [details]
Profile of the "create 5K rectangles" part of the testcase


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.
Depends on: 233463, 380475
Created attachment 264579 [details]
Profile of the "create 5K text elements" part of the testcase

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.

Comment 6

11 years ago
(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.  :(
OS: Linux → Windows XP

Comment 8

11 years ago 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.
Assignee: general → nobody
QA Contact: ian → general
Created attachment 8848811 [details]
SVG for test
Created attachment 8848812 [details]
Test - append a query string to specify the number of elements; e.g. ?5000 for 5000 elements
Created attachment 8848813 [details]
Test - append &count=5000 to the URL for 5000 elements, etc.
Attachment #8848812 - Attachment is obsolete: true
Created attachment 8848814 [details]
Test - append &count=5000 to the URL for 5000 elements, etc.
Attachment #8848813 - Attachment is obsolete: true
Seems O(N) nowadays.
Last Resolved: 8 months ago
Resolution: --- → WORKSFORME
You need to log in before you can comment on or make changes to this bug.