Last Comment Bug 645491 - Very-very slow mark files on Filesonic.com with a large number of directories. To 5-10 seconds on one file.
: Very-very slow mark files on Filesonic.com with a large number of directories...
Status: VERIFIED FIXED
:
Product: Core
Classification: Components
Component: CSS Parsing and Computation (show other bugs)
: unspecified
: x86 Windows XP
: -- normal with 1 vote (vote)
: mozilla6
Assigned To: Boris Zbarsky [:bz] (Out June 25-July 6)
:
Mentors:
http://www.filesonic.com/filesystem/b...
Depends on:
Blocks:
  Show dependency treegraph
 
Reported: 2011-03-27 06:30 PDT by pumay
Modified: 2011-07-20 07:13 PDT (History)
5 users (show)
bzbarsky: in‑testsuite+
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
part 1. Rename ClassSelector to AtomSelector. going to use this same data structure for id selectors too, so the old name doesn't make sense any more. (6.37 KB, patch)
2011-03-27 22:56 PDT, Boris Zbarsky [:bz] (Out June 25-July 6)
dbaron: review+
Details | Diff | Review
Part 2; the actual speedup (5.61 KB, patch)
2011-03-27 22:57 PDT, Boris Zbarsky [:bz] (Out June 25-July 6)
no flags Details | Diff | Review
merged to tip (5.63 KB, patch)
2011-04-03 07:26 PDT, Boris Zbarsky [:bz] (Out June 25-July 6)
dbaron: review+
Details | Diff | Review
With the comment 12 and comment 14 issues fixed (7.16 KB, patch)
2011-04-12 01:30 PDT, Boris Zbarsky [:bz] (Out June 25-July 6)
no flags Details | Diff | Review

Description pumay 2011-03-27 06:30:12 PDT
User-Agent:       Mozilla/5.0 (Windows NT 5.1; rv:2.0) Gecko/20100101 Firefox/4.0
Build Identifier: Mozilla/5.0 (Windows NT 5.1; rv:2.0) Gecko/20100101 Firefox/4.0

Very-very slow mark files with a large number of folders. To 5-10 seconds on one file. Browser does not respond to even a few seconds.
On Google Chrome like done very quickl, less than 1 second.
Test account on Filesonic.com :
Login: firefox4test
Password: test

Reproducible: Always

Steps to Reproduce:
1. Go to account Files Manager http://www.filesonic.com/filesystem/browse
2. Select file (files), when many folders on account.
3. Mark very-very slowly, to 5-10 seconds on one file. Browser does not respond to even a few seconds.
Actual Results:  
Mark very-very slowly, to 5-10 seconds on one file. 

Expected Results:  
Mark files quickly, to 0-1 seconds on the file.
Comment 1 Boris Zbarsky [:bz] (Out June 25-July 6) 2011-03-27 12:00:06 PDT
Not a security bug.

Is there any way to reproduce this without having a filesonic account?  If not, are you willing to email me login information I can use to reproduce?
Comment 2 Boris Zbarsky [:bz] (Out June 25-July 6) 2011-03-27 21:54:44 PDT
Reporter sent me test login information.  Then I realized that it's actually present in comment 0, just scrunched up against the other parts.

The short of it is that each click seems to trigger a script that sets and removes attributes.  For each removal/addition we end up doing a HasAttributeDependentStyle check, of course; this is what takes almost all the time.

Chrome makes this fast by just implementing CSS selector matching wrong, which allows it to take a number of shortcuts when computing the impact of attribute changes on style.  See http://weblogs.mozillazine.org/bz/archives/020267.html

That said, I wonder why this is really taking so much time... unless the page is changing thousands of attribute and has tons of poorly-written selectors, this shouldn't take that long.
Comment 3 Boris Zbarsky [:bz] (Out June 25-July 6) 2011-03-27 21:55:18 PDT
Oh, and this is clearly reproducible.
Comment 4 Boris Zbarsky [:bz] (Out June 25-July 6) 2011-03-27 22:19:05 PDT
OK, so all the attribute changes seem to be changes to the "id" attribute of <li> elements.  Of course if you change the id attribute any id selectors around have to be rematched against the node, and I bet there are tons of them here (in fact, there are 6477 or so in the stylesheets this page uses).  As far as I can tell, the page is doing this to every single <li> element, so we end up with about 26000 selector-matching operations per <li> element.  Half the time is spent in SelectorMatches itself, half is self time in HasAttributeDependentStyle.

The particular id removal in question seems to be handling inside sizzle stuff in the jquery-min that the site loads.  The relevant script bit is:

        t.querySelectorAll &&
        function () {
            var g = k,
                i = t.createElement("div");
            i.innerHTML = "<p class='TEST'></p>";
            if (!(i.querySelectorAll && i.querySelectorAll(".TEST").length === 0)) {
                k = function (m, p, q, u) {
                    p = p || t;
                    m = m.replace(/\=\s*([^'"\]]*)\s*\]/g, "='$1']");
                    if (!u && !k.isXML(p)) if (p.nodeType === 9) try {
                        return C(p.querySelectorAll(m), q)
                    } catch (y) {} else if (p.nodeType === 1 && p.nodeName.toLowerCase() !== "object") {
                        var F = p.getAttribute("id"),
                            M = F || "__sizzle__";
                        F || p.setAttribute("id", M);
                        try {
                            return C(p.querySelectorAll("#" + M + " " + m), q)
                        } catch (N) {} finally {
                            F || p.removeAttribute("id")
                        }
                    }
                    return g(m, p, q, u)
                };
                for (var n in g) k[n] = g[n];
                i = null
            }
        }();

I don't understand that code.  It sounds like it makes sure that if you have a properly working querySelectorAll then k is set to some function that does .... something.  In particular, this seems to be the main thing it does:

  p.setAttribute("id", M);
  try {
    return C(p.querySelectorAll("#" + M + " " + m), q);
  } finally {
    p.removeAttribute("id");
  }

But this should be exactly the same as doing this:

  return p.querySelectorAll(m, q);

so why the heck does it need to munge the id?  John, do you have any idea what this sizzle stuff is doing?

Oh, and this is all happening inside things that seem to be looking for "#folderTree li:has(li.active)" or something.  Hard to tell from the minified jquery, exactly, since all the functions are anonymous and none of the line numbers are useful...
Comment 5 Boris Zbarsky [:bz] (Out June 25-July 6) 2011-03-27 22:22:58 PDT
David, we _might_ be able to optimize this a bit for the special case of adding/removing attributes, though handling :not correctly would still be a pain...

Another option is to special-case things like all id and class selectors not followed by + or ~ and just default to restyling self or something in those situations.

And yet another option is to store the id selectors in the rule processor in a hashtable instead of an array, so we don't have to enumerate them all...
Comment 6 Boris Zbarsky [:bz] (Out June 25-July 6) 2011-03-27 22:24:42 PDT
In other words, handle ids more like we handle classes.  It's silly, because most sites don't do this sort of thing, but...
Comment 7 Boris Zbarsky [:bz] (Out June 25-July 6) 2011-03-27 22:56:26 PDT
Created attachment 522307 [details] [diff] [review]
part 1.  Rename ClassSelector to AtomSelector.   going to use this same data structure for id selectors too, so the old name doesn't make sense any more.
Comment 8 Boris Zbarsky [:bz] (Out June 25-July 6) 2011-03-27 22:57:54 PDT
Created attachment 522308 [details] [diff] [review]
Part 2; the actual speedup

This will conflict with the RuleProcessorData removal, but I can merge that as needed.
Comment 9 Boris Zbarsky [:bz] (Out June 25-July 6) 2011-03-27 23:03:57 PDT
Oh, with these patches, the site is just as fast as in Chrome and Opera, which is to say painfully slow.  But I'm not going to worry about why they feel the need to change ids on every single item in the list twice if someone checks one of the checkboxes.  If they care about the user experience, they'll sit down and debug it themselves.
Comment 10 Boris Zbarsky [:bz] (Out June 25-July 6) 2011-04-03 07:26:03 PDT
Created attachment 523876 [details] [diff] [review]
merged to tip
Comment 11 David Baron :dbaron: ⌚️UTC-7 (review requests must explain patch) 2011-04-11 15:21:18 PDT
Comment on attachment 522307 [details] [diff] [review]
part 1.  Rename ClassSelector to AtomSelector.   going to use this same data structure for id selectors too, so the old name doesn't make sense any more.

r=dbaron
Comment 12 David Baron :dbaron: ⌚️UTC-7 (review requests must explain patch) 2011-04-11 15:31:32 PDT
Comment on attachment 523876 [details] [diff] [review]
merged to tip

>+    PL_DHashTableInit(&mIdSelectors, &AtomSelector_CSOps.ops,
>+                      nsnull, sizeof(AtomSelectorEntry), 16);
>     PL_DHashTableInit(&mClassSelectors,
>                       aQuirksMode ? &AtomSelector_CIOps.ops :
>                                     &AtomSelector_CSOps.ops,
>                       nsnull, sizeof(AtomSelectorEntry), 16);

Judging from SelectorMatches, you need the same ?: expression with which we initialize the ops for mClassSelectors.

Please fix and add a test.

r=dbaron with that
Comment 13 Boris Zbarsky [:bz] (Out June 25-July 6) 2011-04-11 15:38:32 PDT
> Judging from SelectorMatches, you need the same ?: expression

Hmm.  Good catch; I forgot we did case-insensitive ID matches.  I'll fix.
Comment 14 Boris Zbarsky [:bz] (Out June 25-July 6) 2011-04-12 00:43:51 PDT
While writing that test I noticed that this part:

    } else {
      aCascade->mPossiblyNegatedIDSelectors.AppendElement(aSelectorInTopLevel);
    }

is pretty suboptimal.  It should be:

    } else if (negation->mIDList) {
      aCascade->mPossiblyNegatedIDSelectors.AppendElement(aSelectorInTopLevel);
    }
Comment 15 Boris Zbarsky [:bz] (Out June 25-July 6) 2011-04-12 01:30:01 PDT
Created attachment 525330 [details] [diff] [review]
With the comment 12 and comment 14 issues fixed

I did verify that after making the change from comment 14 we failed the test when using only CSOps.
Comment 16 Boris Zbarsky [:bz] (Out June 25-July 6) 2011-04-12 20:48:43 PDT
Pushed to mozilla-central:

  http://hg.mozilla.org/mozilla-central/rev/33f862ff50a0
  http://hg.mozilla.org/mozilla-central/rev/a2280498677f
Comment 17 Simona B [:simonab] 2011-07-20 07:12:53 PDT
Mozilla/5.0 (Windows NT 5.1; rv:6.0) Gecko/20100101 Firefox/6.0

Verified issue with FF6.0b2 using the STR from Comment 0 on Windows XP.

Setting resolution to VERIFIED FIXED.

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