Over the past 8 months I have returned again and again to my CSV parser, attempting to make it as fast as possible. In this article I will talk about all of the various rabbit-holes I went down, and a few I ended up emerging from, in an attempt to claim the title of the fastest CSV parser in Rust. I will also talk a bit about methods I used to benchmark, and some helpful tips for others who are attempting to write really fast Rust code.

Background

Rust already has a few mature CSV parsers. The canonical choice is the csv crate, which is what you should probably be using, as it has serde support and is well tested. There is also simd-csv, which is significantly faster, and very well rounded. I would heartily recommend it. There is also my crate: csimdv, which is largely an experiment to see how fast CSV parsing can be made.

Results(!!)

I'm going to start off by summarizing some of the results of this long experiment, which has culminated in a CSV parser that is up to 19-47% faster than simd-csv and over 2.48-3.6 faster than csv. The test files are a variety of sizes (513kb to 349mb), with a variety of average field sizes.

Benchmarks were ran on an Apple M1 Max CPU with 64gb of RAM. Benchmarks here and results for Intel CPUs here. Each benchmark file was ran for 50 seconds after 3 second warmup.

The Basics

The core of my parser's approach is relentless focus on optimizing SIMD performance. However, that leaves an important assumption unclarified: how, exactly, do you vectorize CSV parsing?

A CSV file is composed of four things: commas, quotes, newlines, and the actual data. A parser must determine

1. the boundaries of each field (by finding the commas).
2. the boundaries of each row (by finding the newlines)
3. whether a comma or newline is a real comma or newline, or an imposter, inside of a quoted field

That last part is the trickiest! Non-SIMD CSV parsers get around that by maintaining a small state machine that essentially does the following:

• if we find a quote, we are now inside quotes
• if we are inside quotes, ignore newlines and commas
• if we find another quote, we are now outside quotes, and can stop ignoring the newlines and commas

This leads to very poor performance for a variety of reasons, but the most important is branch prediction. This state machine inevitably manifests as a series of if-statements that wreak havoc on branch prediction accuracy, leading to pipeline flushing, and misery. The most elegant way around this is...

The Humble pclmulqdq

The pclmulqdq instruction (or pmull on lesser instruction sets (my animosity will be explained later)), allows us a very convenient and fast way to calculate the prefix xor of a series of bits. This trick is explained much better elsewhere, but in essence allows the parser to, in a few instructions, mask out the newlines and delimiters that are inside of quotes. It is also used, though I do not know if it was invented by, the authors of the famous simdjson library. This allows us to throw out the state machine, and bring in a more ergonomic, and dare I say, beautiful method of parsing:

1. figure out where the quotes, newlines, and delimiters are in chunks
2. mask out delimiters and newlines that are inside quotes inside that chunk
3. use the masked out delimiters and newlines to continue to parse

The primary benefit is that it allows us to parse in chunks, which makes SIMD the natural choice for accelerating. It is also the main difference between my crate and simd-csv, which also uses SIMD, but does not use the prefix xor trick, instead using the memchr crate for accelerated "seeking" which more quickly transitions between states in the state machine, but is still saddled by the branch mis-prediction.

Now, you may ask "what about escaped quotes?", which leads me to a simple example:

a,b,c,d,"e"",""",g
010101010000100010 <- delimiters
000000001011011100 <- quotes
000000001101101000 <- prefix xor
010101010000000010 <- masked delimiters

Because escaped quotes are two quotes in a row, this registers as in-quotes->out-of-quotes in two characters, meaning the delimiter nested in between is still masked out.

Comparison Of Comparison Methods

The next interesting part, that I likely spent the most time on, is how to actually do the comparison between in SIMD. On good ISAs, this is as easy as you would expect. Use _mm512_cmpeq_epi8_mask 4 times to extract the positions of commas, quotes, and newline/return characters.

On aarch64, the most basic method would look like this:

let comma_splat = vdupq_n_u8(',' as u8);
let quote_splat = vdupq_n_u8('"' as u8);
let newline_splat = vdupq_n_u8('\n' as u8);
let return_splat = vdupq_n_u8('\r' as u8);
let comma_equal = uint8x16x4_t(
    vceqq_u8(chunk.0, comma_splat),
    vceqq_u8(chunk.1, comma_splat),
    vceqq_u8(chunk.2, comma_splat),
    vceqq_u8(chunk.3, comma_splat),
);
let quote_equal = uint8x16x4_t(
    vceqq_u8(chunk.0, quote_splat),
    vceqq_u8(chunk.1, quote_splat),
    vceqq_u8(chunk.2, quote_splat),
    vceqq_u8(chunk.3, quote_splat),
);
let newline_equal = uint8x16x4_t(
    vorrq_u8(vceqq_u8(chunk.0, newline_splat), vceqq_u8(chunk.0, return_splat)),
    vorrq_u8(vceqq_u8(chunk.1, newline_splat), vceqq_u8(chunk.1, return_splat)),
    vorrq_u8(vceqq_u8(chunk.2, newline_splat), vceqq_u8(chunk.2, return_splat)),
    vorrq_u8(vceqq_u8(chunk.3, newline_splat), vceqq_u8(chunk.3, return_splat)),
);

Some particularities are hand-waved away here, but the gist is that we can combine the "\r" and "\n" characters, because both are considered newlines. For those familiar with simdjson, you may be asking: why not use tables? The table approach is more thoughtfully explained here, but it can be improved slightly. By using this helpful table that lists the instruction throughput and latency, you can see that using vqtbx3q for an extended 48 byte lookup table has lower throughput (.75 vs .25), but avoids the need to AND together the high and low nibbles, saving a significant amount of runtime. In the original simdjson paper, it does process high and low nibbles separately. However, this is only necessary because in JSON you need to classify chars in the range [32-125], which requires 3 separate tbx4 instructions combined, whereas in CSV you only need to classify characters in [10-48], which can be accomplished in a single tbx3 call.

Unfortunately, even the optimized table lookup approach is significantly slower than just vceqq + vorrq. I wasted a lot of time attempting to see if there was a way to make this faster, but it comes down to fundamental differences between JSON and CSVs. Unlike JSON, where there are 6 structural characters that need to be masked out (excluding quotes, because those are doing the masking), CSVs only have 3: '\r', '\n', and ','. For the parsing logic, that means that even if we collapse all of those into one class, removing 12 vceqq, 4 vorrq, replaced by 4 vqtbx3q and 4 vceqq, we still need to disambiguate them eventually:

let masked_delimiters = ...
while masked_delimiters != 0 {
    let pos = masked_delimiters.trailing_zeros() as usize;
    match chunk[pos] {
        '\r' | '\n' => {
            // do newline stuff
        }
        ',' => {
            // do comma stuff
        }
    }
    masked_delimiters &= masked_delimiters - 1;
}

vs. creating bitmasks separately for each of the structural characters:

let masked_commas = ...
let masked_newlines = ...
let first_newline = masked_newlines.trailing_zeros();
while masked_commas != 0 {
    let pos = masked_commas.trailing_zeros() as usize;
    if pos > first_newline {
        break;
    }
    masked_commas &= masked_commas - 1;
    // do comma stuff
}
if masked_newlines != 0 {
   // do newline stuff
}

Thus, while we save a significant number of SIMD instructions, we introduce a dependency chain in the hot loop. By inspecting the generated assembly using cargo asm, you can see that it is introducing a load-then-branch dependency:

// src/lib.rs:102
    match chunk[pos] {
b.ls LBB7_28
ldrb w9, [x27, x22]
cmp w9, #10
ccmp w9, #13, #4, ne
b.eq LBB7_18

At most, one could combine "\r" and "\n" characters into one class, leaving commas and quotes as separate bitmasks, but that just trades 4 vceqq instructions for 4 table lookups, which is still slightly slower (2-3%).

Movemask Emulation Hell

I said I would explain my animosity towards aarch64 earlier, but it is more of a gripe with Apple. Apple, in their infinite wisdom, still do not support SVE2. NEON has no equivalent of the PMOVMSKB instruction on x86 which creates bitmasks, unlike SVE which does support predicate registers. I spent a long time researching the different emulation approaches, the most common of which is explained here, but as long as the bytes are either 0xFF or 0x00, this approach is significantly faster:

let to_bitmask = |input: uint8x16x4_t| -> u64 {
    let t0 = vbslq_u8(bit_select_mask_1, input.0, input.1); // 01010101...
    let t1 = vbslq_u8(bit_select_mask_1, input.2, input.3); // 23232323...
    let combined = vbslq_u8(bit_select_mask_2, t0, t1); // 01230123...
    let sum = vshrn_n_s16::<4>(vreinterpretq_s16_u8(combined));
    return vget_lane_u64::<0>(vreinterpret_u64_s8(sum));
};

Optimizing I/O

Once I had sufficiently optimized my SIMD usage, the main bottleneck was I/O latency, which I originally tried to work around by creating a buffer struct that would handle reading data into memory and compacting when possible (using some tricks from ring buffers), I eventually found that just using memmap2 very handily solved all my I/O issues and gave me a nice 10% speed gain on top. Because I was attempting to benchmark against simd-csv, I designed my API around row-by-row consumption, which required both not keeping the entire file in memory (would defeat the purpose of a streaming parser) while also keeping the current line in memory no matter how large it was. It is likely possible to improve the speed slightly by dropping one of these requirements, but that is out of scope.

Using Apple Instruments for profiling

Obviously, the point of all the work above was to avoid branch mispredictions, but what about actually measuring it? People using Linux can use perfstat, but it's a bit more complex on Apple devices. First, you must open the Instruments app, and create a template that has the hardware counters you're interested in. For branch misprediction, I used a "CPU Counters" instrument with 100 * (BRANCH_COND_MISPRED_NONSPEC / INST_BRANCH_COND) in the "Events and Formulas" section. Then, you can simply run your benchmarks after installing this crate, like so:

RUSTFLAGS='-C target-cpu=native' cargo instruments -t "Branch Misprediction" --release --bench benchmarks --time-limit 600000 -- --bench --baseline master csimdv

And it will open up Instruments with your trace file once the benchmark ends. This was pretty useful for measuring exactly how much different changes to the non-SIMD code impacted performance.

Correctness

My parser has been tested against simd-csvs ZeroCopy (which similarly does not escape or validate the CSV) parser for all of the input files presented above, which include a combination of both \r\n and \n newlines, as well as a variety of quoting scenarios. This parser is not yet at the stage where it will handle the diverse range of malformed CSVs that exist.

Conclusion

No doubt my work on CSV parsing will result in vast sums of money wired in my direction from the likes of Big CSV, however I would like to emphatically state that I did not do this for monetary gain but purely for self aggrandizement.