This is a perfect example of how text parsing is really inherently non-parallelizable. It's very rare that you can do anything useful with a buffer of text without knowing the precise state of the parse at the beginning of that buffer.
The kinds of patterns that would make parsing more parallelizable, like marking the beginning of a delimited region with its length, are human unfriendly so would never be part of an actual text format. Who would ever want to write this?
# Update "19" whenever string length changes.
x = {19}"String of length 19"
This is a perfect example of how text parsing is really inherently non-parallelizable. It's very rare that you can do anything useful with a buffer of text without knowing the precise state of the parse at the beginning of that buffer.
There are two mechanisms that are usually used to get around this:
(1) Perform a fast, sequential "skeleton parsing" pass before the main parse that scans just enough to find "split points" that are consumed by the parallel parser. This is what some of the parallel XML parsing work [1] did.
(2) Guess the state you're in based on some heuristics, and roll back on failure. This actually works surprisingly well in practice for many grammars, for example HTML [2].
(1) Perform a fast, sequential "skeleton parsing" pass before the main parse that scans just enough to find "split points" that are consumed by the parallel parser.
I'm not able to access the full text of this paper. But from the description I wouldn't really consider this "parallel parsing." For the "skeleton parser" to be correct, it must transition through a state machine that is exactly as complex as the real parser. I suspect (again, not being able to read the paper right now) that what makes the "skeleton parse" faster than the "real parse" is not the speed of the parser itself, but the speed of the "load" on the parser.
For the skeleton parse, the "load" on the parser is just finding split points (cheap). At the application level, the "load" on the parser in many cases is building a tree of some sort. The tree-building is often significantly more expensive than the parse itself because it usually involves a lot of dynamic memory allocation.
So yes, if you do a preliminary parse that chunks up the document, and then a second parse that has a heavier load on it like tree-building, the second parse can indeed be parallelized. But I wouldn't consider this parallelizing a parser, I would consider it parallelizing the tree-building. In raw terms you have probably spent more CPU on the actual parsing logic than in the single-threaded case.
I don't mean for this to be a semantic quibble. I'm really interested in parsing architectures that decouple the parser itself from its "load." Event-based parsers like SAX parsers do this. I'm interested specifically in the parser part itself, and the limits of how it can be optimized.
(2) Guess the state you're in based on some heuristics, and roll back on failure. This actually works surprisingly well in practice for many grammars, for example HTML [2].
Looks like an interesting paper, I'll have to dig more into that.
I've always wondered if parsing is still unparallelizable if you also allow backtracking. In other words, can you parse eagerly assuming that you're likely to be in a certain state, and then if you're proven wrong maybe you can retry?
The problem with this is that you can do worse than single-threaded (although not asymptotically speaking) in the worst case.
Consider what happens if you've got something along the lines of the following:
",",",",",",",",","
If every parser thread (but the first, the one parsing from the start, of course) picks the wrong parity (i.e. if they should start quoted or not) repeatedly, you end up throwing away all the work of every thread but the first. And meanwhile, your first thread has to do the additional work of figuring out when to invalidate the other threads.
This is unlikely to happen, but definitely possible.
It's vaguely similar to recursive descent parsing, with vaguely similar drawbacks too.
One other similar approach is to parse eagerly as you say, but with a higher-priority thread that goes through the thread from the start only keeping track of as much state as is necessary, checking / invalidating the other threads as necessary. For CSV I think the required info is only the parity of quotes, though I could be wrong.
And now that you're using a computer to do it you might as well use protobuf or bson or.... But then it's not a plain text format anymore and we're back to square one.
Comments
This is a perfect example of how text parsing is really inherently non-parallelizable. It's very rare that you can do anything useful with a buffer of text without knowing the precise state of the parse at the beginning of that buffer.
The kinds of patterns that would make parsing more parallelizable, like marking the beginning of a delimited region with its length, are human unfriendly so would never be part of an actual text format. Who would ever want to write this?
There are two mechanisms that are usually used to get around this:
(1) Perform a fast, sequential "skeleton parsing" pass before the main parse that scans just enough to find "split points" that are consumed by the parallel parser. This is what some of the parallel XML parsing work [1] did.
(2) Guess the state you're in based on some heuristics, and roll back on failure. This actually works surprisingly well in practice for many grammars, for example HTML [2].
[1]: http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=410047...
[2]: http://www.cs.wm.edu/~xshen/Publications/taco14.pdf
I'm not able to access the full text of this paper. But from the description I wouldn't really consider this "parallel parsing." For the "skeleton parser" to be correct, it must transition through a state machine that is exactly as complex as the real parser. I suspect (again, not being able to read the paper right now) that what makes the "skeleton parse" faster than the "real parse" is not the speed of the parser itself, but the speed of the "load" on the parser.
For the skeleton parse, the "load" on the parser is just finding split points (cheap). At the application level, the "load" on the parser in many cases is building a tree of some sort. The tree-building is often significantly more expensive than the parse itself because it usually involves a lot of dynamic memory allocation.
So yes, if you do a preliminary parse that chunks up the document, and then a second parse that has a heavier load on it like tree-building, the second parse can indeed be parallelized. But I wouldn't consider this parallelizing a parser, I would consider it parallelizing the tree-building. In raw terms you have probably spent more CPU on the actual parsing logic than in the single-threaded case.
I don't mean for this to be a semantic quibble. I'm really interested in parsing architectures that decouple the parser itself from its "load." Event-based parsers like SAX parsers do this. I'm interested specifically in the parser part itself, and the limits of how it can be optimized.
Looks like an interesting paper, I'll have to dig more into that.
I've always wondered if parsing is still unparallelizable if you also allow backtracking. In other words, can you parse eagerly assuming that you're likely to be in a certain state, and then if you're proven wrong maybe you can retry?
Yes, and that's exactly what a lot of things do.
The problem with this is that you can do worse than single-threaded (although not asymptotically speaking) in the worst case.
Consider what happens if you've got something along the lines of the following:
If every parser thread (but the first, the one parsing from the start, of course) picks the wrong parity (i.e. if they should start quoted or not) repeatedly, you end up throwing away all the work of every thread but the first. And meanwhile, your first thread has to do the additional work of figuring out when to invalidate the other threads.This is unlikely to happen, but definitely possible.
It's vaguely similar to recursive descent parsing, with vaguely similar drawbacks too.
One other similar approach is to parse eagerly as you say, but with a higher-priority thread that goes through the thread from the start only keeping track of as much state as is necessary, checking / invalidating the other threads as necessary. For CSV I think the required info is only the parity of quotes, though I could be wrong.
http://www.cse.chalmers.se/edu/year/2010/course/TDA341/Paper...
Also look at CYK parsing algorithm, it is highly parallelizable (it is based on matrix multiplication).
And that's why you let the computer do it for you.
And now that you're using a computer to do it you might as well use protobuf or bson or.... But then it's not a plain text format anymore and we're back to square one.