984241 - Optimize parsing of "grid-template-areas" to avoid O(n^2) performance

Status: RESOLVED FIXED

(Core :: CSS Parsing and Computation, defect)

Description

[Daniel Holbert [:dholbert] (PTO until 2/24)]

While reviewing bug 981752 patch 2a, I noticed that the current code there will have bad performance on large values.

This is currently implemented as a n^2 algorithm which will get nasty if there are a large numbers of different tokens, e.g.
>      grid-template-areas: "a b c d e"
>                           "f g h i j"
>                           "k l m n o" [...]
since for each new token, we (currently) compare it to all of the ones we've seen before, if I understand correctly.

The code in question is here:
> 7091   for (column = 1; scanner.Next(token); column++) {
[...]
> 7116       // Check if this is the continuation of an existing named area:
> 7117       for (uint32_t i = 0, end = aNamedAreas.Length(); i < end; i++) {
> 7118         if (aNamedAreas[i].mName == token.mName) {
> 7119           currentArea = &aNamedAreas[i];
> 7120           if (currentArea->mColumnStart != column || currentArea->mRowEnd != aRow) {
> 7121             // Existing named area, but not forming a rectangle
> 7122             return false;
> 7123           }
> 7124           // Next row of an existing named area
> 7125           currentArea->mRowEnd++;
> 7126           break;
> 7127         }
> 7128       }
http://mxr.mozilla.org/mozilla-central/source/layout/style/nsCSSParser.cpp?rev=71014b91b6c6&mark=7091-7091,7117-7128#7091

We could speed this up by adding a layer of indirection - perhaps a hash-map or a tree-map, mapping the cell-names to numeric indices within aNamedAreas.

Then, when we find a token, we'd look it up in our map instead of walking through the array.

(And for each new named area we discover, we'd update this map with an index in the aNamedAreas array.)

I think we'd only need this map to last for the duration of parsing, and then we could discard it.

Comment 1

[Simon Sapin (:SimonSapin)]

Attachment: grid-template-areas-hashtable.patch

This patch uses a hash table as suggested, and also includes some more refactoring of grid-template-areas parsing that was previously Patch 2a of bug 981752.

Comment 2

[Daniel Holbert [:dholbert] (PTO until 2/24)]

Comment on attachment 8392104 [details] [diff] [review]
grid-template-areas-hashtable.patch

>+++ b/layout/style/nsCSSParser.cpp
>+      uint32_t index;
>+      if (aAreaIndices.Get(token.mName, &index)) {
>+        currentArea = &aAreas.mNamedAreas[index];

Assert that index is less than the array-length, before you index in.

>-  aColumns = column;
>+  if (row == 1) {
>+    aAreas.mNColumns = column;
>+  } else if (aAreas.mNColumns != column) {
>+    return false;
>+  }
>   return true;

Please add a comment explaining what's going on in this chunk.

>+  nsCSSValueGridTemplateAreas& areas = value.SetGridTemplateAreas();
>+  nsDataHashtable<nsStringHashKey, uint32_t> areaIndices;

Somewhere, we should have a brief comment explaining the purpose (and temporariness) of areaIndices -- either here, or in some documentation for ParseGridTemplateAreasLine().

e.g. // Lookup table |areas|, to help us parse faster/ (mapping area names
     // to their index within |areas|):

>+  for (;;) {
>     if (!GetToken(true)) {
>-      return false;
>+      break;
>     }
>     if (eCSSToken_String != mToken.mType) {
>       UngetToken();  // In case it's opening a block or function.

Per our conversation just now, maybe clarify this comment to make it clear that blocks / functions are invalid in this context?

>diff --git a/layout/style/nsCSSValue.h b/layout/style/nsCSSValue.h
>+  // Parsed value
>+  nsTArray<nsCSSGridNamedArea> mNamedAreas;
>+
>+  // Original <string> values. Length gives the number of rows,
>+  // content makes serialization easier.
>+  nsTArray<nsString> mTemplates;
>+
>+  // How many columns grid-template-areas contributes to the explicit grid.
>+  // http://dev.w3.org/csswg/css-grid/#explicit-grid
>+  uint32_t mNColumns;
>+
>+
>+  // How many rows grid-template-areas contributes to the explicit grid.

Nit: collapse the double-blank-line there to a single blank line.

>   nsCSSValueGridTemplateAreas(const nsCSSValueGridTemplateAreas& aOther)
>   {
>+    *this = aOther;
[...]
>+  void operator=(const nsCSSValueGridTemplateAreas& aOther)
>+  {
>+    mNamedAreas = aOther.mNamedAreas;
>+    mTemplates = aOther.mTemplates;
>+    mNColumns = aOther.mNColumns;
>+  }

Per IRC, I'm pretty sure you don't need these functions at all, since they're equivalent to the versions that the compiler will generate for you.

>-  SetGridTemplateAreas(*aRuleData->ValueForGridTemplateAreas(),
>-                       pos->mGridTemplateAreas, parentPos->mGridTemplateAreas,
>-                       canStoreInRuleTree);
>+  const nsCSSValue& gridTemplateAreas = *aRuleData->ValueForGridTemplateAreas();
>+  switch (gridTemplateAreas.GetUnit()) {

Per IRL conversation, I'd marginally prefer that this stays factored into a helper-function, so that it's easier to read SetPositionData and step through it in a debugger quickly.

r=me with the above. Thanks!

Comment 3

[Simon Sapin (:SimonSapin)]

Attachment: Patch v2

Comment 4

[Simon Sapin (:SimonSapin)]

Patch v2 https://tbpl.mozilla.org/?tree=Try&rev=7ae20e592d63

Comment 5

[Daniel Holbert [:dholbert] (PTO until 2/24)]

Landed: http://hg.mozilla.org/integration/mozilla-inbound/rev/6cad68e31490

Comment 6

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

https://hg.mozilla.org/mozilla-central/rev/6cad68e31490