Hi everyone,
I've been discussing this idea with a few people in person over the past
week, and nobody told me it was completely insane. ;) So I thought I'd
send this idea around.
By now many people have heard of WebKit's CSS JIT. It's a surprisingly
small amount of code. One of the issues that they cite in their blog
post [1] is compilation time: the compilation has to be very fast in
order to avoid nullifying the gains. With that in mind, I had an idea:
what if the "AST" that the CSS parser generated was actually machine code?
The AST for the CSS grammar is extremely small: 176 lines of Rust for
the whole thing [2], and the selector grammar is just a fraction of
that. This is because selectors describe a very simple language, even
with all the extensions that have been added over the years. So one
could write a simple template-emitting compiler that takes CSS selectors
and writes a small template of machine code. (This is in fact the
approach that WebKit uses.) For example, I could imagine that the JIT
code for the selector ".foo #a" might look like (assuming that "#a" has
already been matched in the ID hash):
; assume that node is in ebx
l1: mov ebx,[ebx+offsetof(parentNode)]
test ebx,ebx
jz nomatch
mov edx,[ebx+offsetof(class)]
xor ecx,ecx
l2: cmp [edx+ecx*4],"foo"
je match
inc ecx
cmp ecx,[ebx+offsetof(classcount)]
jne l2
jmp l1
This is just 29 bytes of code when assembled. This is likely larger than
the equivalent `nsRuleNode`, but `nsRuleNode` instances are not a large
amount of the heap in my cursory glances at `about:memory`.
The major question is: If you don't have an AST, then how do you
implement the CSSOM and style debugging? Here's the trick: Since CSS
selectors are so simple compared to, say, the output of a JS JIT, it
should be possible to *disassemble* the code by simply pattern-matching.
Since the compiler is nothing more than a very simple template processor
(and it has to be, for speed reasons) it should be possible to reverse
the output and go from JIT code back to the CSS selectors. This would be
done by performing some very simple analysis (not full disassembly) on
the machine code. For instance, on the above selector, it might do:
; start with `#a` from the rule hash
l1: mov ebx,[ebx+offsetof(parentNode)]
test ebx,ebx
jz nomatch
; found a test for parentNode, so we must be a descendant or
; child selector (depending on whether we see a backwards jump)
mov edx,[ebx+offsetof(class)]
xor ecx,ecx
l2: cmp [edx+ecx*4],"foo"
je match
inc ecx
cmp ecx,[ebx+offsetof(classcount)]
jne l2
; found a test for the "foo" class
jmp l1
; found a backwards jump, so we know we're a descendant selector
; result: `.foo #a`
So you wouldn't need a full disassembler, just a simple pattern matcher.
Note that one doesn't have to JIT everything: for more complex tests
such as "attribute contains substring", we can just call out to
functions implemented in Rust in the JIT code. The disassembler can just
pattern match on those function addresses and arguments. This also
increases the maintainability of this approach in the presence of new
stuff that the CSS working groups add to the spec: we can implement all
new features as functions at first, and only JIT them if they become
widely used.
Thoughts?
Patrick
[1]: https://www.webkit.org/blog/3271/webkit-css-selector-jit-compiler/
[2]: https://github.com/mozilla-servo/rust-cssparser/blob/master/ast.rs
_______________________________________________
dev-servo mailing list
dev-servo@lists.mozilla.org
https://lists.mozilla.org/listinfo/dev-servo
