On Saturday 2013-02-09 12:34 +0100, David Bruant wrote: > Le 08/02/2013 18:41, Simon Sapin a Γ©crit : > >For context, see other threads about my new CSS parser. > > > >Servo is made to "parallel all the things", right? > Some algorithms are very hard to parallelize. Parsers would be a > very good example, because they often look like "read a bit, change > the state, read a bit, change the state" and how what is read is > interpreted depends on the current state.
For some languages (e.g., HTML, and possibly also CSS) parsing could be relatively parallizable by splitting up the input into chunks and parsing each chunk by speculating on a likely state at the start of the chunk, having slight overlap between chunks, and throwing out results if the state was still wrong at the end of the overlap (e.g., if something was in a large comment, or if there are really substantially different states that persist for long segments). I remember the http://parlab.eecs.berkeley.edu/ folks talking about doing something like this, I think with HTML, though I don't recall if it was only for tokenization or more deeply into parsing. -David -- π L. David Baron http://dbaron.org/ π π’ Mozilla http://www.mozilla.org/ π _______________________________________________ dev-servo mailing list dev-servo@lists.mozilla.org https://lists.mozilla.org/listinfo/dev-servo
