Though there is no standard definition of CSV, de facto processing it properly requires recognizing quotes, and also escapes of literal quotes using double quoting:
this, "is, like, CSV", "with three so-called ""fields"""
Note that unquoted leading and trailing whitespace, and whitespace around the commas, is deleted, too.
(See CSV page in the Wikipedia)
A GPU-accelerated string split could be useful but it's not quite "parsing CSV".
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.
unquoted leading and trailing whitespace, and whitespace around the commas, is deleted, too. (See CSV page in the Wikipedia)
I'm not sure why you referenced the Wikipedia page -- it indicates that according to RFC 4180, (a) "spaces outside quotes in a field are not allowed", and (b) "Spaces are considered part of a field and should not be ignored."
Maybe you're referring to the comment that CSV parsers should "be liberal in what you accept from others"...?
(a) "spaces outside quotes in a field are not allowed", and (b) "Spaces are considered part of a field and should not be ignored."
Note that it's clear that (b) refers only to spaces inside quotes, because spaces outside quotes are not allowed.
Maybe you're referring to the comment that CSV parsers should "be liberal in what you accept from others"...?
I actually don't believe in that principle. If there is a spec that everyone agrees upon, violations should be accurately and loudly diagnosed and rejected.
Both preparation of the data format and processing of that data format should be conservative. Being liberal in what is accepted has unintended negative consequences.
Be that as it may, there is no universal CSV spec, though. RFC 4180 is just someone's opinion on what CSV should be. CSV is something that has been widely implemented in numerous programs over numerous decades, in different ways.
My main point holds that if you split the string on commas and do nothing else, then one of the aspects you're neglecting to handle is the treatment of unquoted whitespace outside of a field.
I actually don't believe in that principle. If there is a spec that everyone agrees upon, violations should be accurately and loudly diagnosed and rejected.
Both preparation of the data format and processing of that data format should be conservative. Being liberal in what is accepted has unintended negative consequences.
I agree on principle. But when Marie in accounting opens the CSV that Bob from customer X sent her, if software A opens it and software B screams "error!!!", she's going to use the one that "works". And that means B's vendor will make their tool liberal of what they accept too.
Similarly for websites, that's why browsers fixes what they see rather than not showing what you are asking it to show.
Does it lead to a worse state of things for clear format, with more errors in the wild and no actual reference to base yourself on ? Yes. But it is still what end users want.
I don't need to reproduce an entire detailed CSV spec here to make the point.
There is a danger in being too detailed because there is no universal spec anyway. For many users, CSV is whatever the most recent version or two of Microsoft Excel accept, as confirmed by trial-and-error reverse engineering.
Comments
Though there is no standard definition of CSV, de facto processing it properly requires recognizing quotes, and also escapes of literal quotes using double quoting:
Note that unquoted leading and trailing whitespace, and whitespace around the commas, is deleted, too.(See CSV page in the Wikipedia)
A GPU-accelerated string split could be useful but it's not quite "parsing CSV".
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.
I'm not sure why you referenced the Wikipedia page -- it indicates that according to RFC 4180, (a) "spaces outside quotes in a field are not allowed", and (b) "Spaces are considered part of a field and should not be ignored."
Maybe you're referring to the comment that CSV parsers should "be liberal in what you accept from others"...?
http://en.wikipedia.org/wiki/Comma-separated_values#Basic_ru...
Note that it's clear that (b) refers only to spaces inside quotes, because spaces outside quotes are not allowed.
I actually don't believe in that principle. If there is a spec that everyone agrees upon, violations should be accurately and loudly diagnosed and rejected.
Both preparation of the data format and processing of that data format should be conservative. Being liberal in what is accepted has unintended negative consequences.
Be that as it may, there is no universal CSV spec, though. RFC 4180 is just someone's opinion on what CSV should be. CSV is something that has been widely implemented in numerous programs over numerous decades, in different ways.
My main point holds that if you split the string on commas and do nothing else, then one of the aspects you're neglecting to handle is the treatment of unquoted whitespace outside of a field.
I agree on principle. But when Marie in accounting opens the CSV that Bob from customer X sent her, if software A opens it and software B screams "error!!!", she's going to use the one that "works". And that means B's vendor will make their tool liberal of what they accept too.
Similarly for websites, that's why browsers fixes what they see rather than not showing what you are asking it to show.
Does it lead to a worse state of things for clear format, with more errors in the wild and no actual reference to base yourself on ? Yes. But it is still what end users want.
You forgot with fields with line-breaks, with non printrable characters and so on.
I don't need to reproduce an entire detailed CSV spec here to make the point.
There is a danger in being too detailed because there is no universal spec anyway. For many users, CSV is whatever the most recent version or two of Microsoft Excel accept, as confirmed by trial-and-error reverse engineering.