696233 - Consider having four separate hashtables with smaller entries in the nth-index cache

Status: RESOLVED FIXED

(Core :: CSS Parsing and Computation, defect, P2)

Description

[Boris Zbarsky [:bzbarsky]]

For querySelector this should give better cache locality (and is a slight performance improvement).  For normal selector matching it might too, esp. in the common case when only one of the four types of selectors applies to a given node.

Comment 1

[Boris Zbarsky [:bzbarsky]]

Attachment: Switch the nth-index cache to having a single hashtable per selector type (from end vs from start and of-type vs not-of-type). Gives somewhat better cache locality on some workloads and makes entry addition much cheaper because we no longer need to initi

Comment 2

[Olli Pettay [:smaug][[e-mail]]]

Comment on attachment 569646 [details] [diff] [review]
Switch the nth-index cache to having a single hashtable per selector type (from end vs from start and of-type vs not-of-type).  Gives somewhat better cache locality on some workloads and makes entry addition much cheaper because we no longer need to initi

> nsNthIndexCache::IndexDeterminedFromPreviousSibling(nsIContent* aSibling,
>                                                     Element* aChild,
>                                                     bool aIsOfType,
>                                                     bool aIsFromEnd,
>+                                                    const Cache &aCache,
Cache& aCache would be consistent with other parameters.

>+  // This node's index for this cache.
>+  // If -2, needs to be computed.
>+  // If -1, needs to be computed but known not to be 1.
>+  // If 0, the node is not at any index in its parent.
>+  typedef PRInt32 CacheEntry;

huh, this code is...interesting.

>+  /**
>+   * Returns true if aResult has been set to the correct value for aChild and
>+   * no more work needs to be done.  Returns false otherwise.
>+   */
Don't remove the comments you added in the other bug.

Comment 3

[Boris Zbarsky [:bzbarsky]]

> Cache& aCache would be consistent with other parameters.

Yeah, ok.  Fixed.  At some point I should just switch them all...

> huh, this code is...interesting.

dbaron gets the blame for that bit.  :)  Turns out, the "not 1" case is more common (e.g. used in our UA stylesheets).

> Don't remove the comments you added in the other bug.

Indeed.  The patch here predates those comments being added; the actual patch to push has them.

Thank you for the quick review!

Pushed: http://hg.mozilla.org/integration/mozilla-inbound/rev/28afade47ac2

Comment 4

[Marco Bonardo [:mak]]

https://hg.mozilla.org/mozilla-central/rev/28afade47ac2