Closed Bug 984241 Opened 8 years ago Closed 8 years ago

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

Categories

(Core :: CSS Parsing and Computation, defect)

defect
Not set
normal

Tracking

()

RESOLVED FIXED
mozilla31

People

(Reporter: dholbert, Assigned: SimonSapin)

References

Details

Attachments

(1 file, 1 obsolete file)

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.
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.
Assignee: nobody → simon.sapin
Status: NEW → ASSIGNED
Attachment #8392104 - Flags: review?(dholbert)
Blocks: 981752
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!
Attachment #8392104 - Flags: review?(dholbert) → review+
Attached patch Patch v2Splinter Review
Attachment #8392104 - Attachment is obsolete: true
Attachment #8392688 - Flags: review+
https://hg.mozilla.org/mozilla-central/rev/6cad68e31490
Status: ASSIGNED → RESOLVED
Closed: 8 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla31
You need to log in before you can comment on or make changes to this bug.