4 ms·

You can probably get another "few x" faster still: https://branchfree.org/2019/03/06/code-fragment-finding-quote-pairs-with-carry-less-multiply-pclmulqdq/ http

You can probably get another "few x" faster still: https://branchfree.org/2019/03/06/code-fragment-finding-quote-pairs-with-carry-less-multiply-pclmulqdq/ https://branchfree.org/2019/03/06/code-fragment-finding-quot... Based on a cursory scan this is the same problem so Geoff's trick should be directly applicable. The ideas are quite similar: using bit manipulation to detect the in and out regions. Geoff's trick does the "smearing" of the bits in a single SIMD "carryless multiply", plus some supporting stuff. It is constant time for an input word: there is no dependence on the number of bits. So it could be many times faster for inputs with very dense quotes. For an actual implementation, you'd want to handle the case where you don't have any quotes at all or where they are very sparse, which is common to a lot of CSV with a fast path that bails out when it sees a quote (possibly to be be resumed later if there is again a quote-free run).

henrydark 5y ago
Langdale also has a state machine simd idea that can be used for the full csv transition table: https://branchfree.org/2018/05/25/say-hello-to-my-little-friend-sheng-a-small-but-fast-deterministic-finite-automaton/ https://branchfree.org/2018/05/25/say-hello-to-my-little-fri... I implemented this at some point (the "noisy" version, in Langdale's words) and got a csv tokenizer that spent about 1.5 cycles per byte.
glangdale 5y ago
I started to build "simdcsv" - based on similar principles to "simdjson", but succumbed to lassitude. There's still a fork kicking around. Doing the CSV version of the quote convention is actually wildly easier than the JSON version, as you can just treat a record like "foo""bar",hi,1,"hatstand,teakettle" as having 'left the quotes and rentered the quotes" at the double-quote spot when you're busy looking for ','. This isn't, of course, much help for normalization, but for the bit where you're hoping to simply find which ',' characters are separators, it's fine to pretend that there's a gap in your "quoted stuff bitfield" that happens at the "" in "foo""bar", as of course that gap isn't going to land on a ',' anyhow. So it's much cheaper than doing a tedious shenanigan to handle some crafty user who has hit you with 100 \ characters in a row (as opposed to 99 or 101), a la JSON. IMO the cost of doing the CLMUL all the time vs taking a conditional to handle the 'I have no quotes today' case is pretty low. It makes for shorter and more easily understood (in performance terms) code. I wasn't allowed to take this to extremes in simdjson - we did handle the "common case" for UTF-8 validation (although I wonder if that's a very culturally determined notion of "common case").

henrydark 5y ago

Langdale also has a state machine simd idea that can be used for the full csv transition table: https://branchfree.org/2018/05/25/say-hello-to-my-little-friend-sheng-a-small-but-fast-deterministic-finite-automaton/ https://branchfree.org/2018/05/25/say-hello-to-my-little-fri... I implemented this at some point (the "noisy" version, in Langdale's words) and got a csv tokenizer that spent about 1.5 cycles per byte.

glangdale 5y ago

I started to build "simdcsv" - based on similar principles to "simdjson", but succumbed to lassitude. There's still a fork kicking around. Doing the CSV version of the quote convention is actually wildly easier than the JSON version, as you can just treat a record like "foo""bar",hi,1,"hatstand,teakettle" as having 'left the quotes and rentered the quotes" at the double-quote spot when you're busy looking for ','. This isn't, of course, much help for normalization, but for the bit where you're hoping to simply find which ',' characters are separators, it's fine to pretend that there's a gap in your "quoted stuff bitfield" that happens at the "" in "foo""bar", as of course that gap isn't going to land on a ',' anyhow. So it's much cheaper than doing a tedious shenanigan to handle some crafty user who has hit you with 100 \ characters in a row (as opposed to 99 or 101), a la JSON. IMO the cost of doing the CLMUL all the time vs taking a conditional to handle the 'I have no quotes today' case is pretty low. It makes for shorter and more easily understood (in performance terms) code. I wasn't allowed to take this to extremes in simdjson - we did handle the "common case" for UTF-8 validation (although I wonder if that's a very culturally determined notion of "common case").