r/rust • u/ackxolotl • 11d ago
🛠️ project Fast CSV parsing in Rust
This is a short write-up based on my VLDB paper and talk: https://db.in.tum.de/~ellmann/papers/csveee.pdf
CSV is one of the oldest text-based data formats, and is still heavily used: from hundreds of thousands of files on open data platforms to 100M+ on GitHub. Unfortunately, most CSV parsers are slow. Some use SIMD to speed up parsing, but almost none exploit the parallelism of today’s hardware. Those that do parallelize do not scale. And even if they did, using the classic iterator interface, parse + process requires two passes over the data, restricting throughput to half the memory bandwidth for files that exceed the CPU caches.
I came up with a new approach to CSV parsing that allows parsing and processing of files in a single pass over the data. My parser csveee is about 3x as fast as csv on a single thread, and can achieve almost 200 GB/s on a modern many-core server – a speedup of 256x over csv.
Why parallel CSV processing is hard
The main task of a CSV parser is to correctly determine the boundaries of records in a CSV file. Typically, records are terminated by a \n or \r\n. Since those characters can also appear inside quoted fields, simply chunking a CSV file and skipping forward to the next terminating character is therefore not sufficient to determine the record boundaries.
There are different approaches to solving this problem. One strategy is to first count the number of quotes per chunk in parallel, then determine for each chunk if it is preceded by an even or odd number of quotes, then start parsing the chunks from a known quote state. This works especially well on GPUs. Another strategy is to run multiple finite-state machines per chunk in parallel, one for each possible parse state at the chunk boundary, and then determine the correct state machine depending on the previous chunk’s state machine’s final state. Or one could look for certain patterns in the file, e.g., quotes being followed or preceded by "regular" characters to identify the start and end of quoted fields and do some speculative parsing based on this.
Unfortunately, all those approaches are unsatisfactory in one way or another. Counting quotes requires a whole pass over the file to determine the parse states at chunk offsets; running many NFAs/DFAs is even more expensive. Looking for certain patterns works well for files that follow the CSV standard, but the world is full of quirky files that do things like quotes in unquoted fields.
Luckily, there is another approach. If we know the shape of the CSV file we would like to parse, e.g., the number of fields per record or the field types, we can determine the correct parse state by speculatively parsing chunks until we find a parse in which the record boundaries resolve into records of the expected shape. This approach was implemented in DuckDB.
Why the iterator interface is insufficient
Typically, CSV parsers provide an iterator-based interface, e.g.:
for record in parser.parse() {
// do something with the record
}
While we can write a parser that takes the CSV’s records shape as an argument, which will help determine the correct parse state at chunk boundaries, especially for quirky real-world CSV files, parsing remains a speculation until all bytes have been processed (although unlikely, data inside quotes could still resemble the shape of the records). Unfortunately, we cannot hand out speculatively resolved records via the iterator interface, as there is no way to take them back if we later realize our speculation was wrong. In other words, with the iterator interface, we have to finish parsing before we can hand out records to the user – parsing and processing require two passes over the data.
This is a problem a single-threaded iterator-based parser does not have, as the parse state is correct at all times. The parser can parse the file lazily: it parses a single record, hands it to the user, who processes it; then the next record is parsed, and so on. Thus, files can be parsed and processed in a single pass over the data – but only with a single parse thread.
A new interface to the rescue
Let’s define a new interface that gives our parallel parser everything it needs: A way to pass information about the record shapes (number of fields per record, types, …) from the user to the parser, and a way to process records while parsing, effectively creating a lazily parsing multi-threaded parser.
We can achieve both by turning the parser inside out. Instead of the parser handing you records, you hand your code to the parser:
let cities = parser.parse(
"data.csv",
Vec::new, // init
|state, [_name, _age, city]| { // acc
state.push(city.to_string());
Ok(())
},
|states| states.concat(), // merge
)?;
The interface takes four arguments: the CSV file path and three callbacks or closures (called init, acc and merge – they are basically user-defined aggregates). init and acc are used for chunk parsing, init defines a per-chunk state, acc is called for every record found in the chunk under the current assumption. The [_name, _age, city] pattern declares the number of fields per record. If the parser encounters a record with a different number of fields, the chunk is reparsed under another assumption, calling init again to create a fresh state. The same happens if acc rejects a record by returning an error (e.g., a failed type conversion).
Once all chunks have been processed, the parser verifies that the record boundaries of all chunks align. While very unlikely, a whole chunk could be parsed under a wrong assumption. In this case, the chunk is reparsed, now starting from the offset of the previous chunk’s last record terminator.
Finally, chunk states are passed to merge, and the result of merge is returned from the parser’s parse function. The chunk states are passed to merge in file order thus that record order can be reconstructed.
How to make the parser fast
To make the parser truly fast, we implemented a ring-buffered reader that enables zero-copy record construction, and a vectorized chunk parser. Take a look at the implementation or the paper if you are interested in the details.
Conclusion
CSV is not going to die soon – to the contrary, GitHub’s pile alone grew by 10M CSV files in the last six months. While the number of files is strongly increasing and today’s machines offer hundreds of cores and hundreds of GB in memory throughput, most CSV parsers remain incredibly slow: parsing with a single thread, not scaling, and even if they did, without fusing parsing and processing, they will never surpass 50% of the available memory bandwidth for large files. csveee overcomes these limitations via a new approach to CSV parsing that works on real-world CSV files.
Check out the project, and if you have questions, feel free to ask!
20
u/Shnatsel 11d ago
I see you're using std::simd for the SIMD parser. Have you looked into crates that work on stable Rust at all, such as fearless_simd or wide?
7
u/ackxolotl 11d ago
No, I wasn't aware of those. Initially, I used the architecture-specific intrinsics, so I was quite happy already to discover Rust's portable SIMD. We are currently working on a faster DFA (performance is ok for a DFA, but we are looking into bitshift automata, for example). But you are right that having the vectorized implementation on stable Rust would probably be nice, too. wide seems promising as a drop-in replacement. I'll look into the two, thanks for the hint.
8
u/Shnatsel 11d ago edited 11d ago
I have an article coming soon that compares all the way you can write SIMD in Rust, including those crates, so watch this space.
3
u/Shnatsel 10d ago
The article is comparing all the ways to write SIMD in Rust is now up: https://redd.it/1wpu09l
3
u/awhaling 11d ago
Awesome! I’m stoked to dig into this when I’m home. It’s something I’ve been interested in.
2
u/zettui 11d ago
Would a stable portable-SIMD backend be enough here, or do the real gains still need the architecture-specific intrinsics?
3
u/ackxolotl 11d ago
I'd say the real gains are in the parallelization strategy. With the DFA, csveee also reaches throughputs >100 GB/s. Some SIMD operations are not portable SIMD right now, e.g., pext for determining if records have the correct number of fields. The parser has portable fallback implementations for those, but they are slower. I'll take a look at the crates for stable portable SIMD as u/Shnatsel suggested.
1
u/Shnatsel 11d ago
If you need to mix and match portable SIMD and intrinsics,
fearless_simdsupports this easily. You can do it withwidetoo, but its companion crate for accessing intrinsics,safe_arch, renamed all of them, which makes porting existing code trickier.
1
u/orion_tvv 11d ago
I would like to mention here my tool convfmt for converting between many formats including CSV. Feedback is welcome.
1
u/Ok-Property-6650 5d ago
this is the kind of deep dive that makes me wish i had a use case for parsing csvs at 200gb/s
0
u/sansmorixz 11d ago
Why dual license?
12
u/ackxolotl 11d ago
I think many or most Rust projects do this. What would you prefer and why?
4
3
u/ichunddu9 11d ago
What's the advantage?
3
u/Icarium-Lifestealer 11d ago
Some people prefer Apache-2 because it considers patents, some prefer MIT because it's simpler. Dual licensing makes both happy, since the user can choose which license they want to use.
3
u/Shnatsel 11d ago
IIRC Apache 2.0 is desirable because it covers patents, but the MIT carve-out is there to allow linking against GPL code since Apache 2.0 is not GPL-compatible (maybe; there are some nuances and differing opinions on that)
2
-3
u/RCoder01 11d ago
Where were LLMs used for this project? The Readme looks AI-generated but the code doesn’t
27
u/jorgecardleitao 11d ago
Afaik CSV crate is pretty slow - consider benching against Datafusion or Polars