Branchfree

Yeah, I see how the quoting complications make CLMUL pretty hard to use (or just useless). I have a few ideas about how to deal with the quoting/escaping, and if I get some free time in the near future I'll try and code something up.

I've also pinged Geoff and Daniel on Twitter, linking your library: https://mobile.twitter.com/zwegner/status/1473400733525544973 ...maybe they'll have some ideas. (Geoff has mentioned that he had done some initial work on a simdcsv)

I'll also drop some more links that you might've already seen, but could be useful otherwise.
For removing double quotes, rather than memmove, you could use the "pack left" operation on vectors. There's a handful of ways to do this pre-AVX-512-VBMI2 (where the magical vcompressb instruction was added), like in these SO questions:

https://stackoverflow.com/questions/36932240/avx2-what-is-the-most-efficient-way-to-pack-left-based-on-a-mask

https://stackoverflow.com/questions/45506309/efficient-sse-shuffle-mask-generation-for-left-packing-byte-elements

And for keeping the main lexer structure that ZSV uses now, but using a small DFA to maintain the lexer state, this other trick from Geoff might work: https://branchfree.org/2018/05/25/say-hello-to-my-little-friend-sheng-a-small-but-fast-deterministic-finite-automaton/

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/

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).

PMOVMSKB is a great instruction, and 3c understates how cheap it is - if you have a throughput problem (rather than a latency problem) it's even more efficient relative to the ARM equivalent.

I have a blog post about coping strategies for working around the absence of PMOVMSKB on NEON:

https://branchfree.org/2019/04/01/fitting-my-head-through-the-arm-holes-or-two-sequences-to-substitute-for-the-missing-pmovmskb-instruction-on-arm-neon/

We used these techniques in simdjson (which I presume still uses them; the code has changed considerably since I built this): https://github.com/simdjson/simdjson

The best techniques for mitigating the absence of PMOVMSKB require that you use LD4, which results in interleaved inputs. This can sometimes make things easier, sometimes harder for your underlying lexing algorithm - sadly, it's not a 1:1 transformation of the original x86 code.

*avoid branches

The blog post I mentioned:

Paper: Parsing Gigabytes of JSON per Second
https://branchfree.org/2019/02/25/paper-parsing-gigabytes-of-json-per-second/

Another related post from Lemire:

Ridiculously fast unicode (UTF-8) validation
https://lemire.me/blog/2020/10/20/ridiculously-fast-unicode-utf-8-validation/

Those algorithms are fast. But to put them in perspective. A single x86 CPU can write 64B per cycle. At 5GHz, the theorical maximum bandwidth is 320 GBps. IIRC, the read bandwidth is twice that.

There are others botlenecks, and is very hard to write code that writes at every cycle.

A interesting consequence, is that the theorical maximum bandwidth is logarithmical to the number of cycles. Again, talking about branchless streaming application.

I found the following article about the topic really good: https://branchfree.org/2019/04/01/fitting-my-head-through-the-arm-holes-or-two-sequences-to-substitute-for-the-missing-pmovmskb-instruction-on-arm-neon/

In my experience using a 512 wide movemask (to uint64_t) is the fastest on both x86 and arm64.

With rvv you don't really what to go from a vector mask to a general purpose non vector register, because the vector length may vary. But I found it really useful that vector masks are always packed into v0. So even with LMUL=8, you can just to a vmseq, switch to LMUL=1 and use vfirst & vmsif & vmandn to iterate through all indices. (Alternatively vfirst & vmsof & vmclr would also work, I'm not sure which one would be faster)

Nope. That still supports backreferences, and resolving backreferences is an NP-complete problem.[1] And I don't see anything in that paper that addresses that. Note that there may be some versions of the problem that maybe aren't NP-complete[2], but again, not addressed by that paper.

Besides, that paper was published 12 years ago. Where is the productionized version of it? Or are you suggesting the the OP go spend a few years writing a regex eninge? :-) Doesn't seem like a particularly practical suggestion.

[1] - https://perl.plover.com/NPC/NPC-3SAT.html

[2] - https://branchfree.org/2019/04/04/question-is-matching-fixed-regexes-with-back-references-in-p/