Comment

Comment by BeeOnRope

You can probably get another "few x" faster still:

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

parent BeeOnRope 4 years ago

Discussion

Live from the official Hacker News API

A modern reader for Hacker News · SvelteKit + Skeleton