Boris Zbarsky [:bzbarsky] Reporter
	Description • 14 years ago

This should be doable, if we make sure that selector matching never changes DOM state.

	Boris Zbarsky [:bzbarsky] Reporter
	Comment 1 • 14 years ago

Of course right now it _does_ change DOM state: the various slow selector flags.  We'd need to figure out how to handle that.

	Boris Zbarsky [:bzbarsky] Reporter
	Comment 2 • 13 years ago

The other data structure whose updates are interleaves with selector matching is the ruletree.  We need to fix that too.

	Chris Jones [:cjones] inactive; ni?/f?/r? if you need me
	Comment 4 • 13 years ago

Notes on pastebin'd WIP

 - Is there a wide variation in the cost of FindRulesFor()?  That is, is it way more expensive for some nodes that others.

 - What's the cost of ResolveStyleFor()/ResolveStyleForNonElement() compared to FindRulesFor(), usually?

You could cut down on a lot of possibly unnecessary synchronization overhead here by dividing the node list among threads before dispatching the tasks to them.  Similarly, you could eliminate a lot of contention by having each thread keep its own table of results.

If there's a huge variation in FindRulesFor(), it might be better to dynamically schedule the tasks among threads by having them steal nodes off a list as here.

If ResolveStyleFor()/ResolveStyleForNonElement() is expensive (and main-thread only?), it might make sense to have the main thread doing this in parallel to workers running FindRulesFor().  In that case, it would be better for the workers to post tasks to a shared data structure that the main thread steals work from.

Stylistic notes

 - Instead of the PR* synchronization stuff, use the mozilla:: wrappers in xpcom/glue (Mutex, CondVar).  They have useful checking

 - Use MutexAutoLock instead of explicit Lock/Unlock.  It's much less error prone.

 - Your WIP is "spinning" on a shared counter and doing a non-atomic load (technically).  If we're going to fork threads for style-matching here and then destroy them, then it would be better to Join() all the forked threads.  If the idea is to keep them around, then the primitive we want here is a barrier; we should land bug 486442 with fast pthreads+windows impls soon, if so.

Sorry I couldn't spot the bug in the WIP.  I'd recommend setting up a VM to run valgrind.

Let me know if you have any more questions.

	Boris Zbarsky [:bzbarsky] Reporter
	Comment 5 • 13 years ago

> - Is there a wide variation in the cost of FindRulesFor()?

There can be, yes.  Certainly it's trivial to write testcases where this is the case...  What happens in practice on web pages is a good question.

> - What's the cost of ResolveStyleFor()/ResolveStyleForNonElement() compared to
> FindRulesFor(), usually?

It varies, but generally the non-FindRulesFor parts are cheaper than FindRulesFor.  Sometimes much cheaper.

Having the main thread doing ResolveStyleFor (which for now is indeed main-thread-only) in parallel with worker threads doing the rule matching is a pretty interesting idea.  I like it, but I'm ok with trying it as a followup too.

Keeping the matching thread around seems fine to me.  Is there any drawback to doing that?

	Chris Jones [:cjones] inactive; ni?/f?/r? if you need me
	Comment 6 • 13 years ago

(In reply to comment #5)
> Keeping the matching thread around seems fine to me.  Is there any drawback
> to doing that?

Well, thread*s* eventually, right?  Nothing subtle, just standard memory vs. complexity tradeoff.  If the pool would be per process, and matching doesn't require much stack space (so the threads don't need much allocated), then I don't see any reason to bother with expiring threads.

	Boris Zbarsky [:bzbarsky] Reporter
	Comment 7 • 13 years ago

Pool would be per process, yes.  We'd need to measure matching stack space, but I suspect it won't be too bad (in particular, we avoid recursive algorithms in matching already).

	:Ms2ger (he/him; ⌚ UTC+1/+2)
	Comment 10 • 13 years ago

Comment on attachment 546175 [details] [diff] [review]
Part 1: Separate rule matching from tree building

>--- a/content/base/src/nsGenericElement.h
>+++ b/content/base/src/nsGenericElement.h
>+class nsRuleWalker;

This doesn't seem really necessary

>--- a/layout/style/nsCSSRuleProcessor.cpp
>+++ b/layout/style/nsCSSRuleProcessor.cpp
>-    if (!next || SelectorMatchesTree(data->mElement, next,
>+    return (!next || SelectorMatchesTree(data->mElement, next,
>                                      data->mTreeMatchContext,

Indentation is off.

>--- a/layout/style/nsStyleSet.h
>+++ b/layout/style/nsStyleSet.h
>+  already_AddRefed<nsStyleContext>
>+  
>+  ResolveStyleFor(ElementRuleProcessorData* aData,
>+                  nsStyleContext* aParentContext,
>+                  TreeMatchContext& aTreeMatchContext);

New line *before* already_AddRefed<nsStyleContext>?

And maybe file a followup to move WalkContentStyleRules from nsIContent to Element?

	:Ms2ger (he/him; ⌚ UTC+1/+2)
	Comment 11 • 13 years ago

Comment on attachment 546176 [details] [diff] [review]
Part 2: Add a function to nsCSSFrameConstructor to resolve styles in parallel

>--- a/layout/base/nsCSSFrameConstructor.cpp
>+++ b/layout/base/nsCSSFrameConstructor.cpp
>+  for (nsIContent* child = aStartChild;
>+        child != aEndChild;
>+        child = child->GetNextSibling()) {
>+

Indentation; also below.

>+    // XXX the GetContent() != aContent check is needed due to bug 135040.

No aContent in sight.

>+    // Remove it once that's fixed.  

Trailing spaces.

>+  
>+  /*for (nsIContent* child = aFirstNewContent;
>+       child;
>+       child = child->GetNextSibling()) {
>+    AddFrameConstructionItems(state, child, PR_FALSE, parentFrame, items);
>+  }*/

I'm assuming you're removing this code.

	David Zbarsky (:dzbarsky)
	Comment 17 • 13 years ago

Avoid copying arrays

	Boris Zbarsky [:bzbarsky] Reporter
	Comment 18 • 13 years ago

So one obvious issue with part 1: nsHTMLBodyElement::WalkContentStyleRules is writing to mContentStyleRule.

In fact, WalkContentStyleRules is not const.  It needs to be, right?

For the preshint level, can we assert that we either got css rules or non-CSS ones but not both?  Is that even an invariant that holds?  If we get both, we don't know how to sort them against each other with this patch, right?

The code duplication in FileRules/FileRules2 and ConstructRuleTree bothers me, but maybe there's really no better way....

	David Zbarsky (:dzbarsky)
	Comment 19 • 13 years ago

The changes we talked about on IRC

	David Zbarsky (:dzbarsky)
	Comment 25 • 13 years ago

Change a little due to part 0.

	Boris Zbarsky [:bzbarsky] Reporter
	Comment 29 • 12 years ago

So one thing I definitely recall being a problem with the above patches and that I've meant to put in here for a while...  They were calling into the animation/transition manager from off-thread, during selector matching, iirc.  Those parts needed to move to ruletree construction instead.

	Chris Jones [:cjones] inactive; ni?/f?/r? if you need me
	Comment 30 • 12 years ago

(We need this kind of work to take better advantage of multicore phones.)

	Chris Jones [:cjones] inactive; ni?/f?/r? if you need me
	Comment 31 • 12 years ago

For the b2g use case, we'll need this for multicore devices, but those are a bit off in the future so for now important technical issue.

Things are totally different on higher-end HW though! :)

	Boris Zbarsky [:bzbarsky] Reporter
	Comment 32 • 6 years ago

Done by stylo.