Presumably solving the same kind of delimiter-finding issues as Hyperscan? https://news.ycombinator.com/item?id=19270199
I'm sorry, I don't mean Hyperscan, I mean simdjson [0]. I think I got confused by my recollection of Lemire/Langdale.
Leveraging SIMD: Splitting CSV Files at 3Gb/S
31–40 of 43 posts
Re: Leveraging SIMD: Splitting CSV Files at 3Gb/S
#32Stay tuned for a SIMD powered CSV parser library and standalone utility about to drop this weekend. Alpha, but test showing it to be faster than anything else we could get our hands on
Re: Leveraging SIMD: Splitting CSV Files at 3Gb/S
#33Pretty similar article from very recently: https://nullprogram.com/blog/2021/12/04/ Discussion: https://news.ycombinator.com/item?id=29439403 The article mentions in an addendum (and BeeOnRope also pointed it out in the HN thread) a nice CLMUL trick for dealing with quotes originally discovered by Geoff Langdale. That should work here for a nice speedup. But without the CLMUL trick, I'd guess that the unaligned loads…
Even with the CLMUL trick, CSV parsing does not play nice. It can be made to work for JSON parsing because you can make more assumptions. With CSV, it only works smoothly if you are willing to accept a subset of what most spreadsheet programs accept i.e. to assume your CSV is "well-formed". Considering for example that the following three cells:
AA"A,"AA""A","A"A"A
when opened in Excel will all give you the same value, using CLMUL to normalize will require many repeated additional SIMD operations-- probably at least 8 if not more. At some vector size it will be worth it, but not clear at 256. The irony is, if you are stuck with CSV input, then the fact that you couldn't get a better format/encoding also suggests that you can't assume your CSV is "well-formed"
Re: Leveraging SIMD: Splitting CSV Files at 3Gb/S
#34Pretty similar article from very recently: https://nullprogram.com/blog/2021/12/04/ Discussion: https://news.ycombinator.com/item?id=29439403 The article mentions in an addendum (and BeeOnRope also pointed it out in the HN thread) a nice CLMUL trick for dealing with quotes originally discovered by Geoff Langdale. That should work here for a nice speedup. But without the CLMUL trick, I'd guess that the unaligned loads…
Even with the CLMUL trick, CSV parsing does not play nice. It can be made to work for JSON parsing because you can make more assumptions. With CSV, it only works smoothly if you are willing to accept a subset of what most spreadsheet programs accept i.e. to assume your CSV is "well-formed". Considering for example that the following three cells: AA"A,"AA""A","A"A"A when opened in Excel will all give you the same valu…
Good points all around. Not sure what the OP's requirements are, but judging by their current code, CLMUL should do nicely (or they have a bug).
And also, thanks for that example. Clearly I don't know CSV well enough--are quotes in fields that don't start with a quote not special?
Re: Leveraging SIMD: Splitting CSV Files at 3Gb/S
#35Pretty similar article from very recently: https://nullprogram.com/blog/2021/12/04/ Discussion: https://news.ycombinator.com/item?id=29439403 The article mentions in an addendum (and BeeOnRope also pointed it out in the HN thread) a nice CLMUL trick for dealing with quotes originally discovered by Geoff Langdale. That should work here for a nice speedup. But without the CLMUL trick, I'd guess that the unaligned loads…
Even with the CLMUL trick, CSV parsing does not play nice. It can be made to work for JSON parsing because you can make more assumptions. With CSV, it only works smoothly if you are willing to accept a subset of what most spreadsheet programs accept i.e. to assume your CSV is "well-formed". Considering for example that the following three cells: AA"A,"AA""A","A"A"A when opened in Excel will all give you the same valu…
That's not what Python and Google Sheets do.
>>> list(csv.reader(['''AA"A,"AA""A","A"A"A'''], dialect='excel'))
[['AA"A', 'AA"A', 'AA"A']]
Re: Leveraging SIMD: Splitting CSV Files at 3Gb/S
#36Earlier quoted context omitted.
Even with the CLMUL trick, CSV parsing does not play nice. It can be made to work for JSON parsing because you can make more assumptions. With CSV, it only works smoothly if you are willing to accept a subset of what most spreadsheet programs accept i.e. to assume your CSV is "well-formed". Considering for example that the following three cells: AA"A,"AA""A","A"A"A when opened in Excel will all give you the same valu…
That's not what Python and Google Sheets do. >>> list(csv.reader(['''AA"A,"AA""A","A"A"A'''], dialect='excel')) [['AA"A', 'AA"A', 'AA"A']] Has the CSV format been standardized somewhere?
What I can tell you is that if you save a file with 'AA"A,"AA""A","A"A"A' (excluding the surrounding single-quotes) and then double-click to open in Excel, you get 3 cells with the exact same values. Furthermore, if you run `echo 'AA"A,"AA""A","A"A"A' | xsv select 1,2,3` you again get the same 3 values. For people working with CSV, it's far more likely that the user cares more about consistency with Excel than consistency with some python lib or with Google sheets-- neither of which are used much, compared to Excel, in the worlds where CSV tends to reside (at least in my experience)
Re: Leveraging SIMD: Splitting CSV Files at 3Gb/S
#37Earlier quoted context omitted.
Even with the CLMUL trick, CSV parsing does not play nice. It can be made to work for JSON parsing because you can make more assumptions. With CSV, it only works smoothly if you are willing to accept a subset of what most spreadsheet programs accept i.e. to assume your CSV is "well-formed". Considering for example that the following three cells: AA"A,"AA""A","A"A"A when opened in Excel will all give you the same valu…
Good points all around. Not sure what the OP's requirements are, but judging by their current code, CLMUL should do nicely (or they have a bug). And also, thanks for that example. Clearly I don't know CSV well enough--are quotes in fields that don't start with a quote not special?
If their data comes from a controlled bubble and they need not assume "real-world" data, then CLMUL might do nicely but best case it would likely only be a marginal improvement (and even then I would be willing to bet, not at anything less than 512 bit vector sizes). Best case, it still needs additional vector calls to support quoting. Obviously, if no quoting will be supported, it's even simpler, but then you also cannot support commas or newlines inside of cell values and are getting so far from "CSV" that you might as well just say you have pipe-delimited data which happens to use comma instead of pipe in which case you don't need CLMUL. If quoting needs to be supported, CLMUL will still require a number of repeated passes, shifts etc to deal with the various cases including an escaped first quote char, last quote char, non-first-or-last quote char and embedded commas/newlines.
Re: Leveraging SIMD: Splitting CSV Files at 3Gb/S
#38Stay tuned for a SIMD powered CSV parser library and standalone utility about to drop this weekend. Alpha, but test showing it to be faster than anything else we could get our hands on
As promised: https://github.com/liquidaty/zsv
Re: Leveraging SIMD: Splitting CSV Files at 3Gb/S
#39Earlier quoted context omitted.
Even with the CLMUL trick, CSV parsing does not play nice. It can be made to work for JSON parsing because you can make more assumptions. With CSV, it only works smoothly if you are willing to accept a subset of what most spreadsheet programs accept i.e. to assume your CSV is "well-formed". Considering for example that the following three cells: AA"A,"AA""A","A"A"A when opened in Excel will all give you the same valu…
That's not what Python and Google Sheets do. >>> list(csv.reader(['''AA"A,"AA""A","A"A"A'''], dialect='excel')) [['AA"A', 'AA"A', 'AA"A']] Has the CSV format been standardized somewhere?
Huh? your comment proves exactly what my prior post said, which is that you end up with 3 equal values that were each represented, in the input, in different ways. Looks like csv.reader + dialect=excel is doing exactly that.
Re: Leveraging SIMD: Splitting CSV Files at 3Gb/S
#40Earlier quoted context omitted.
Good points all around. Not sure what the OP's requirements are, but judging by their current code, CLMUL should do nicely (or they have a bug). And also, thanks for that example. Clearly I don't know CSV well enough--are quotes in fields that don't start with a quote not special?
If their data comes from a controlled bubble and they need not assume "real-world" data, then CLMUL might do nicely but best case it would likely only be a marginal improvement (and even then I would be willing to bet, not at anything less than 512 bit vector sizes). Best case, it still needs additional vector calls to support quoting. Obviously, if no quoting will be supported, it's even simpler, but then you also c…
Thread's getting a bit old, hope you see this :)
Referring to the OP, I'm not sure what exact dialect of csv they're using, but its quoting rules are nothing like Excel's: quotes are escaped with a separate character (possibly backslash), and quoted regions can start anywhere, not just the start of a field. This makes CLMUL much easier to apply, quite similarly to how it's used in simdjson. Finding escaped characters can be done branchlessly with a handful of scalar operations on the masks (this code is in simdjson too).
For proper Excel-style parsing, you're quite possibly right (and looking at ZSV, I trust that you've thought about this problem a lot more than me). I'm not certain that it can't all be done efficiently with very few branches, though, using mostly SIMD and some scalar operations on masks. CLMUL might not be useful here, since quotes are treated completely differently depending on whether the field started with a quote. Instead you'd have a first phase basically looking for a comma or newline followed by a quote, then looking for the next unescaped quote. Escaped quotes within quoted fields can be found with a similar sequence to simdjson's backslash support (and removed with something like vcompressb on newer AVX-512 chips).