Re: Conditional branch in tree builder based on DOM state

On Fri, Jan 2, 2009 at 2:09 PM, Jonas Sicking <jonas@sicking.cc> wrote:
> On Thu, Dec 25, 2008 at 11:59 AM, Ian Hickson <ian@hixie.ch> wrote:
>> On Tue, 9 Dec 2008, Henri Sivonen wrote:
>>>
>>> We had a meeting about moving parsing off the main thread in Gecko. The
>>> idea is to make the tree builder output a sequence of tree mutations on
>>> a dedicated thread and to actuate the mutations on the main thread.
>>>
>>> It is then a problem if the sequence of mutations is conditional on
>>> information read synchronously from the DOM. There is one place in the
>>> HTML5 parsing algorithm where this problem arises and cannot be remedied
>>> by deferring the conditional check itself to the mutation actuation
>>> time: step 7.5. of the adoption agency algorithm. The changes to the
>>> internal state of the tree builder depend on whether a node has
>>> children.
>>>
>>> The problem would go away if instead of checking whether the node has
>>> children in the DOM, there were a 'has children' flag on the tree
>>> builder stack tracking whether the node has *parser-inserted* children.
>>>
>>> The spec change suggestion, therefore, is making step 7.5. of the AAA
>>> read "If node has any *parser-inserted* children, perform a shallow
>>> clone of node——".
>>
>> I'm vaguely convinced that this wouldn't introduce the possibility of
>> crashers in weird cases with hostile scripts, but as I was looking at this
>> a second concern came up.
>>
>> While what you describe would make your particular implementation strategy
>> easier, it would in fact complicate implementations that support script
>> and operate on the DOM directly (i.e. all script-aware implementations
>> today).
>>
>> Instead, I recommend passing along an _assertion_ along with the
>> mutations, along the lines of "these elements have children" and "these
>> elements don't have children", which the main thread can quickly check. If
>> the assertions turn out to be false, which will only happen in rare caes,
>> then the thread can synchronise with the main thread, getting itself
>> updated on what nodes have children, and then try again from that point.
>
> I agree that this would complicate a parser implementation that
> doesn't do speculative parsing while blocked for <script>s. However
> the extra complication is very small compared to the complication
> added to speculative parsers. Additionally, it does simplify the
> interface between the parser and the DOM since with this and the other
> change that has been proposed there is no need to read data back from
> the DOM. This interface simplification is likely about the same as
> adding an extra flag to each node in the tag stack.
>
> Also, any competitive browser is going to have to do speculative
> parsing. The performance gains from doing so is so substantial that
> not doing it is not really an option. So while you'd have slightly
> simpler HTML parsing in consumers other than browsers, you will make
> all browsers more complex. The alternative for browsers is likely to
> not use a real tokenizer when doing speculative parsing which means
> wasting CPU cycles. Also, something that isn't a browser is likely to
> not run scripts, so such a parser could optimize to use the algorithm
> in the current spec if it really is an advantage (see above regarding
> complexities of feeding data back from the DOM).
>
> Finally, using the algorithm that Henri is suggesting will yield
> somewhat more logical results IMHO. Currently if you are modifying the
> DOM as it is being loaded you can have race conditions where the
> resulting DOM depends on when you make a seemingly unrelated DOM
> mutation. If you insert your content before the parser reads from the
> DOM you get one result, if you do it after you get another.

Ugh, about an hour after sending the above I realized that I was
totally off the deep end. This request wasn't made to allow for better
speculative parsing, but rather to allow for off-the-main-thread
parsing. So just ignore my previous response as none of it was
correct.

So, starting over :)

I agree that it does make the parser slightly more complex. You have
to keep a stack of pairs (node + has-child-flag) rather than just a
stack of nodes. And anytime you insert a child into a node you have to
set a boolean flag. Finally you have to change where you read the
does-this-node-have-children to instead of calling into the DOM, check
the value in the node stack.

Of these only the first two actually seem to introduce complexity. And
in neither case this extra complexity seems very big.

The upshot of making this change it that it allows performant
off-the-main-thread parsing. Without making this change you have to
introduce the ability to rewind parsing to any point where you are
making guesses regarding if a node has children or not. Doing this
book-keeping is going to cost both performance and large amounts of
code complexity.

It's hard to gauge at this point in time how popular off-main-thread
parsing will be. Current trend in CPU engineering seems to be to add
more cores which means that any time you are able to thread your
application you'll see significant gains. We're not at that point yet
and optimizing for single-core is currently a better strategy, but it
seems like this will change.

If we do end up in a world with multicore being standard I suspect
most browsers will want to thread as much as possible and putting the
parser on a separate thread is an obvious target for threading.

In any case, I think restricting to single threaded parsing is a
significant loss, one that should not be taken lightly. So far none of
the arguments against the ability has not been convincing to me.

Also, the following comment from my original mail still applies:

> Finally, using the algorithm that Henri is suggesting will yield
> somewhat more logical results IMHO. Currently if you are modifying the
> DOM as it is being loaded you can have race conditions where the
> resulting DOM depends on when you make a seemingly unrelated DOM
> mutation. If you insert your content before the parser reads from the
> DOM you get one result, if you do it after you get another.

/ Jonas

Received on Saturday, 3 January 2009 01:56:21 UTC