Or store the metadata immediately before the code, as GHC does for thunk entry code.
keegan ----- Original Message ----- From: "Niko Matsakis" <nmatsa...@mozilla.com> To: "Patrick Walton" <pcwal...@mozilla.com> Cc: dev-servo@lists.mozilla.org Sent: Monday, March 31, 2014 3:10:39 AM Subject: Re: [dev-servo] Crazy idea: CSS selector JITting at parse time Interesting thought. You could also use an embedding involving either coded no-ops at the start of each instruction and/or an unconditional jump over some meta-data. This would reduce coupling at the cost of somewhat more memory. Naturally you'd want to measure the effect on performance too, though I suspect it'd be minimal. Niko On Sat, Mar 29, 2014 at 05:23:02PM -0700, Patrick Walton wrote: > 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 _______________________________________________ dev-servo mailing list dev-servo@lists.mozilla.org https://lists.mozilla.org/listinfo/dev-servo _______________________________________________ dev-servo mailing list dev-servo@lists.mozilla.org https://lists.mozilla.org/listinfo/dev-servo
