8 ms·

Leveraging SIMD: Splitting CSV Files at 3Gb/S

89 points by __exit__ 5y ago

zwegner 5y ago
Pretty similar article from very recently: https://nullprogram.com/blog/2021/12/04/ https://nullprogram.com/blog/2021/12/04/ Discussion: https://news.ycombinator.com/item?id=29439403 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 that generally occur after a vector containing both quotes and newlines in this version (the "else" case on lines 34-40) would hamper the performance somewhat, since it would eat up twice as much L1 cache bandwidth. I'd suggest dealing with the masks using bitwise operations in a loop, and letting i stay divisible by 16. Or just use CLMUL :)
- davidm1729 5y ago
  Hi, I'm one of the authors of the post Thanks for pointing us to CLMUL, I'm not familiar with these kind of multiplications, but, converting the quote bitmask to a quoted bitmask would certainly make it faster. With this new bitmask, we could negate it and AND it with the newline mask, generating a mask of newlines that are not inside quotes. Getting the last newline then would be a simple CLZ of that mask. And there wouldn't be a need to resort to byte to byte processing. In our tests, going byte to byte for more iterations to keep the alignment when hitting the "else case" performed worse than making the unaligned loads, but as you say "just use CLMUL" (as all loads will be aligned) :D
  - jart 5y ago
    PMOVMSKB/BSF/POPCNT takes serious wizardry, but instructions like PCLMULLQLQDQ make you feel like Gandalf. It's defined: pair clmul(uint64_t a, uint64_t b) { uint64_t t, x = 0, y = 0; if (a && b) { if (bsr(a) < bsr(b)) t = a, a = b, b = t; /* optional */ for (t = 0; b; a <<= 1, b >>= 1) { if (b & 1) x ^= a, y ^= t; t = t << 1 | a >> 63; } } return (pair){x, y}; } There's a famous paper on how it can perform polynomial division at 40gbps. It's really cool that it has practical applications in things like CSV too. https://www.intel.com/content/dam/www/public/us/en/documents/white-papers/fast-crc-computation-generic-polynomials-pclmulqdq-paper.pdf https://www.intel.com/content/dam/www/public/us/en/documents...
  - zwegner 5y ago
    CLMUL in general is a bit weird to wrap your head around, but a CLMUL with -1 isn't too tricky: it's like a running 1-bit sum, or in other words, each bit in the result is the parity of all the bits up to that point in the multiplier. > In our tests, going byte to byte for more iterations to keep the alignment when hitting the "else case" performed worse than making the unaligned loads, but as you say "just use CLMUL" (as all loads will be aligned) :D I was talking about using bitwise operations with the quote/escape/newline masks already computed (like in the blog post I linked), rather than a byte-by-byte loop. But yeah, CLMUL is better anyways :)
  - gpderetta 5y ago
    CLMUL is quite interesting. I learned about it when going in depth on how multiplications help with hashing. A multiplication is in practice: - a sum over - a series (i.e. one for each bit set in the multiplier) - of shifts (where the shift amount is the index of that bit in the multiplier) The shifting and the combining are great for hashing as they "distribute" each bit around. CLMUL simply replaces the addition in step one with xor (which can also be thought as the single bit carryless addition).
- pclmulqdq 5y ago
  The carryless multiplication instructions are amazing and people should use them more often. They are just so poorly explained that they feel like magic.
- mattewong 5y ago
  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"
  - zwegner 5y ago
    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?
    - mattewong 5y ago
      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.
      - zwegner 5y ago
        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).
rwmj 5y ago
Nice, but I'm afraid real world CSVs are a lot more complicated than described so don't use this code in production.
- mschuster91 5y ago
  If you're doing user-supplied CSVs, definitely... but if you are ingesting CSVs from a known source with known format (<insert audible sigh here>) it can definitely make sense to use a high-speed optimized ingester. One might wonder if it might be worth the time to look into optimising the runtimes of various languages. I took a look, all operate on naive byte-by-byte scanning, and all sans PHP are written in the respective language which means any form of SIMD optimization is right off the table (okay, maybe something could be done in Java, but it seems incredibly complex, see https://www.morling.dev/blog/fizzbuzz-simd-style/ https://www.morling.dev/blog/fizzbuzz-simd-style/): - PHP isn't optimized anywhere, but at least it's C: https://github.com/php/php-src/blob/1c0e613cf1a24cdc159861e4406abfcee7bc1aee/ext/standard/file.c#L2051 https://github.com/php/php-src/blob/1c0e613cf1a24cdc159861e4... - Python's C implementation is the same: https://github.com/python/cpython/blob/main/Modules/_csv.c https://github.com/python/cpython/blob/main/Modules/_csv.c - Java doesn't have a "standard" way at all (https://www.baeldung.com/java-csv-file-array https://www.baeldung.com/java-csv-file-array), and OpenCSV seems the usual object-oriented hell (https://sourceforge.net/p/opencsv/source/ci/master/tree/src/main/java/com/opencsv/ https://sourceforge.net/p/opencsv/source/ci/master/tree/src/...). - Ruby's CSV is native Ruby: https://github.com/ruby/ruby/blob/bd65757f394255ceeb2c958e87f862139dd37e7b/lib/csv.rb https://github.com/ruby/ruby/blob/bd65757f394255ceeb2c958e87...
  - __s 5y ago
    Python's csv imports _csv for core functionality, which is C: https://github.com/python/cpython/blob/main/Modules/_csv.c https://github.com/python/cpython/blob/main/Modules/_csv.c
    - mschuster91 5y ago
      Thanks! Updated accordingly.
Tuna-Fish 5y ago
Why is the unit expression in topic messed up?
jagrsw 5y ago
Not sure how the author of this entry on HN managed to change original title from gigabytes per second to gigabits per siemens :)
- __exit__ 5y ago
  Autocorrector issues + fast fingers to click on submit without double checking. Sorry for that. Whoever fixed the title, thank you :D
  - CodesInChaos 5y ago
    > fixed the title It still shows as "3Gb/S" for me, instead of "3GB/s"
- Sebb767 5y ago
  Probably auto-capitalization gone wrong. Or some very new code ;)
  - MisterTea 5y ago
    Genetic code most likely.
- jeltz 5y ago
  Isn't it easier to write 3GbΩ instead of 3Gb/S?
- HPsquared 5y ago
  Staying with Physics, "Gb/S" is Gigabarns per Siemens. Some relation of electrical conductance with cross-sectional area. The barn is a unit of cross-sectional area, based on the Uranium nucleus (area 1 barn). Uranium is pretty large in atomic terms; the name is from the idiom "couldn't hit the broad side of a barn".
  - jagrsw 5y ago
    And since 1/S = 1Ω, it'd be Gigabarnohm.
liuliu 5y ago
Splitting CSV file into chunks and process them independently won't necessarily be wrong (although there are implementations out there that I won't name would, because they do guess). The trick however requires to scan twice: https://liuliu.me/eyes/loading-csv-file-at-the-speed-limit-of-the-nvme-storage/ https://liuliu.me/eyes/loading-csv-file-at-the-speed-limit-o... Nice article otherwise!
michaelg7x 5y ago
Presumably solving the same kind of delimiter-finding issues as Hyperscan? https://news.ycombinator.com/item?id=19270199 https://news.ycombinator.com/item?id=19270199
- michaelg7x 5y ago
  I'm sorry, I don't mean Hyperscan, I mean simdjson [0]. I think I got confused by my recollection of Lemire/Langdale. [0] https://github.com/simdjson/simdjson https://github.com/simdjson/simdjson
mattewong 5y ago
Stay 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
- mattewong 5y ago
  As promised: https://github.com/liquidaty/zsv https://github.com/liquidaty/zsv

89 points by __exit__ 5y ago

Pretty similar article from very recently: https://nullprogram.com/blog/2021/12/04/ https://nullprogram.com/blog/2021/12/04/ Discussion: https://news.ycombinator.com/item?id=29439403 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 that generally occur after a vector containing both quotes and newlines in this version (the "else" case on lines 34-40) would hamper the performance somewhat, since it would eat up twice as much L1 cache bandwidth. I'd suggest dealing with the masks using bitwise operations in a loop, and letting i stay divisible by 16. Or just use CLMUL :)

davidm1729 5y ago
Hi, I'm one of the authors of the post Thanks for pointing us to CLMUL, I'm not familiar with these kind of multiplications, but, converting the quote bitmask to a quoted bitmask would certainly make it faster. With this new bitmask, we could negate it and AND it with the newline mask, generating a mask of newlines that are not inside quotes. Getting the last newline then would be a simple CLZ of that mask. And there wouldn't be a need to resort to byte to byte processing. In our tests, going byte to byte for more iterations to keep the alignment when hitting the "else case" performed worse than making the unaligned loads, but as you say "just use CLMUL" (as all loads will be aligned) :D
- jart 5y ago
  PMOVMSKB/BSF/POPCNT takes serious wizardry, but instructions like PCLMULLQLQDQ make you feel like Gandalf. It's defined: pair clmul(uint64_t a, uint64_t b) { uint64_t t, x = 0, y = 0; if (a && b) { if (bsr(a) < bsr(b)) t = a, a = b, b = t; /* optional */ for (t = 0; b; a <<= 1, b >>= 1) { if (b & 1) x ^= a, y ^= t; t = t << 1 | a >> 63; } } return (pair){x, y}; } There's a famous paper on how it can perform polynomial division at 40gbps. It's really cool that it has practical applications in things like CSV too. https://www.intel.com/content/dam/www/public/us/en/documents/white-papers/fast-crc-computation-generic-polynomials-pclmulqdq-paper.pdf https://www.intel.com/content/dam/www/public/us/en/documents...
- zwegner 5y ago
  CLMUL in general is a bit weird to wrap your head around, but a CLMUL with -1 isn't too tricky: it's like a running 1-bit sum, or in other words, each bit in the result is the parity of all the bits up to that point in the multiplier. > In our tests, going byte to byte for more iterations to keep the alignment when hitting the "else case" performed worse than making the unaligned loads, but as you say "just use CLMUL" (as all loads will be aligned) :D I was talking about using bitwise operations with the quote/escape/newline masks already computed (like in the blog post I linked), rather than a byte-by-byte loop. But yeah, CLMUL is better anyways :)
- gpderetta 5y ago
  CLMUL is quite interesting. I learned about it when going in depth on how multiplications help with hashing. A multiplication is in practice: - a sum over - a series (i.e. one for each bit set in the multiplier) - of shifts (where the shift amount is the index of that bit in the multiplier) The shifting and the combining are great for hashing as they "distribute" each bit around. CLMUL simply replaces the addition in step one with xor (which can also be thought as the single bit carryless addition).
pclmulqdq 5y ago
The carryless multiplication instructions are amazing and people should use them more often. They are just so poorly explained that they feel like magic.
mattewong 5y ago
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"
- zwegner 5y ago
  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?
  - mattewong 5y ago
    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.
    - zwegner 5y ago
      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).

rwmj 5y ago

Nice, but I'm afraid real world CSVs are a lot more complicated than described so don't use this code in production.

mschuster91 5y ago
If you're doing user-supplied CSVs, definitely... but if you are ingesting CSVs from a known source with known format (<insert audible sigh here>) it can definitely make sense to use a high-speed optimized ingester. One might wonder if it might be worth the time to look into optimising the runtimes of various languages. I took a look, all operate on naive byte-by-byte scanning, and all sans PHP are written in the respective language which means any form of SIMD optimization is right off the table (okay, maybe something could be done in Java, but it seems incredibly complex, see https://www.morling.dev/blog/fizzbuzz-simd-style/ https://www.morling.dev/blog/fizzbuzz-simd-style/): - PHP isn't optimized anywhere, but at least it's C: https://github.com/php/php-src/blob/1c0e613cf1a24cdc159861e4406abfcee7bc1aee/ext/standard/file.c#L2051 https://github.com/php/php-src/blob/1c0e613cf1a24cdc159861e4... - Python's C implementation is the same: https://github.com/python/cpython/blob/main/Modules/_csv.c https://github.com/python/cpython/blob/main/Modules/_csv.c - Java doesn't have a "standard" way at all (https://www.baeldung.com/java-csv-file-array https://www.baeldung.com/java-csv-file-array), and OpenCSV seems the usual object-oriented hell (https://sourceforge.net/p/opencsv/source/ci/master/tree/src/main/java/com/opencsv/ https://sourceforge.net/p/opencsv/source/ci/master/tree/src/...). - Ruby's CSV is native Ruby: https://github.com/ruby/ruby/blob/bd65757f394255ceeb2c958e87f862139dd37e7b/lib/csv.rb https://github.com/ruby/ruby/blob/bd65757f394255ceeb2c958e87...
- __s 5y ago
  Python's csv imports _csv for core functionality, which is C: https://github.com/python/cpython/blob/main/Modules/_csv.c https://github.com/python/cpython/blob/main/Modules/_csv.c
  - mschuster91 5y ago
    Thanks! Updated accordingly.

Tuna-Fish 5y ago

Why is the unit expression in topic messed up?

jagrsw 5y ago

Not sure how the author of this entry on HN managed to change original title from gigabytes per second to gigabits per siemens :)

__exit__ 5y ago
Autocorrector issues + fast fingers to click on submit without double checking. Sorry for that. Whoever fixed the title, thank you :D
- CodesInChaos 5y ago
  > fixed the title It still shows as "3Gb/S" for me, instead of "3GB/s"
Sebb767 5y ago
Probably auto-capitalization gone wrong. Or some very new code ;)
- MisterTea 5y ago
  Genetic code most likely.
jeltz 5y ago
Isn't it easier to write 3GbΩ instead of 3Gb/S?
HPsquared 5y ago
Staying with Physics, "Gb/S" is Gigabarns per Siemens. Some relation of electrical conductance with cross-sectional area. The barn is a unit of cross-sectional area, based on the Uranium nucleus (area 1 barn). Uranium is pretty large in atomic terms; the name is from the idiom "couldn't hit the broad side of a barn".
- jagrsw 5y ago
  And since 1/S = 1Ω, it'd be Gigabarnohm.

liuliu 5y ago

Splitting CSV file into chunks and process them independently won't necessarily be wrong (although there are implementations out there that I won't name would, because they do guess). The trick however requires to scan twice: https://liuliu.me/eyes/loading-csv-file-at-the-speed-limit-of-the-nvme-storage/ https://liuliu.me/eyes/loading-csv-file-at-the-speed-limit-o... Nice article otherwise!

michaelg7x 5y ago

Presumably solving the same kind of delimiter-finding issues as Hyperscan? https://news.ycombinator.com/item?id=19270199 https://news.ycombinator.com/item?id=19270199

michaelg7x 5y ago
I'm sorry, I don't mean Hyperscan, I mean simdjson [0]. I think I got confused by my recollection of Lemire/Langdale. [0] https://github.com/simdjson/simdjson https://github.com/simdjson/simdjson

mattewong 5y ago

Stay 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

mattewong 5y ago
As promised: https://github.com/liquidaty/zsv https://github.com/liquidaty/zsv