645491 - Very-very slow mark files on Filesonic.com with a large number of directories. To 5-10 seconds on one file.

Status: VERIFIED FIXED

(Core :: CSS Parsing and Computation, defect)

Description

[pumay]

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 [:bzbarsky]]

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 [:bzbarsky]]

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 [:bzbarsky]]

Oh, and this is clearly reproducible.

Comment 4

[Boris Zbarsky [:bzbarsky]]

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 [:bzbarsky]]

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 [:bzbarsky]]

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 [:bzbarsky]]

Attachment: 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 [:bzbarsky]]

Attachment: Part 2; the actual speedup

This will conflict with the RuleProcessorData removal, but I can merge that as needed.

Comment 9

[Boris Zbarsky [:bzbarsky]]

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 [:bzbarsky]]

Attachment: merged to tip

Comment 11

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

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-4, no longer working on Mozilla)]

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 [:bzbarsky]]

> 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 [:bzbarsky]]

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 [:bzbarsky]]

Attachment: 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 [:bzbarsky]]

Pushed to mozilla-central:

  http://hg.mozilla.org/mozilla-central/rev/33f862ff50a0
  http://hg.mozilla.org/mozilla-central/rev/a2280498677f

Comment 17

[Simona Badau, Desktop QA]

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.