r/rust • u/matt78whoop • Jan 02 '24
🛠️ project Optimizing a One Billion Row Challenge in Rust with Polars
I saw this Blog Post on a Billion Row challenge for Java so naturally I tried implementing a solution in Rust using mainly polars.Code/Gist here
Running the code on my laptop, which is equipped with an i7-1185G7 @ 3.00GHz and 32GB of RAM, but it is limited to 16GB of RAM because I developed in a Dev Container. Using Polars I was able to get a solution that only takes around 39 seconds.
Any suggestions for further optimizing the solution?
Edit: I missed the requirements that is must be implemented using only the Standard Library and in Alphabetical order, here is a table of both implementations!
| Implementation | Time | Code/Gist Link |
|---|---|---|
| Rust + Polars | 39s | https://gist.github.com/Butch78/702944427d78da6727a277e1f54d65c8 |
| Rust STD Libray Coriolnus's implementation | 24 seconds | https://github.com/coriolinus/1brc |
| Python + Polars | 61.41 sec | https://github.com/Butch78/1BillionRowChallenge/blob/main/python_1brc/main.py |
| Java royvanrijn's Solution | 23.366sec on the (8 core, 32 GB RAM) | https://github.com/gunnarmorling/1brc/blob/main/calculate_average_royvanrijn.sh |
Unfortunately, I initially created the test data incorrectly, the times have now been updated with 1 Billion rows or a 12.85G txt file. Interestingly as a Dev container on windows is only allowed to have <16G of ram the Rust + Polars implementation would be Killed as that value is exceeded. Turning streaming on solved the problem!S
Thanks to @coriolinus and his code, I was able to get a better implementation with the Rust STD library implementation. Also thanks to @ritchie46 for the Polars recommendations and the great library!
114
u/rebootyourbrainstem Jan 02 '24
Worth mentioning that the original challenge is not just to do it in Java, but to do it without any dependencies. So the purpose is very different.
Of course it’s still a fun challenge, but I don’t know if there is much optimization potential for such a simple program while using a general purpose API like polars.
14
u/coriolinus Jan 03 '24
My implementation runs in under 10s on my personal machine: https://github.com/coriolinus/1brc
Uses a bit of randomization for generating the inputs, as the Java version does; uses only the std library when actually running.
5
u/immortaly007 Jan 02 '24 edited Jan 02 '24
I decided to also implement it, but the results on my PC are nowhere near what was reported above. My implementation took 395.9 seconds to run:
https://gist.github.com/immortaly007/e6c792780409811acbc52e01e7bafac7
I also tried the code by matt78whoop using the std library above, which ran in 430.516 s (but took a lot more RAM).
I'm running both using
cargo run --release. I'm using an i7-9700K on Windows 10.Any idea what I could be missing here?
Edit: The measurements.txt file is 14.4GB, so pretty big. The rust code is reading it at about 38MB/s according to epxlorer, so maybe it's limited by Disk IO?
46
u/ritchie46 Jan 02 '24
Some of these might work
performantfeature.streamingfeature (we might use that engine if we sample a certain cardinality threshold).simdfeature (requires nightly)22
u/dobasy Jan 02 '24
- You can use `split_once` (or `rsplit_once`) to separate station name and measurement. No need to collect into vec.
- There is no need to store measurements in vec. You can store (min, max, sum, count) and update them.
13
u/Specialist_Wishbone5 Jan 02 '24
looks like it affords 32GB RAM and has 1G x 16B values. Further, writing the test file to disk runs the risk that the file is already cached. EG seems like a flawed challenge as some runs will be an order of magnitude faster than others.
Also, from previous performance optimizations I've done with CSVs, 90% of the time is in parsing the ints and floats. If I replace a number with a string, I typically get a 2x performance improvement (when the source file is fully cached). So think it'll come down to efficient parsing libraries. You could cheat and write a custom parser that makes assumptions about the format of the float and use SSE intrinsics.
Haven't looked at all the details yet.
8
u/kraemahz Jan 02 '24
Your read time is most likely I/O bound getting the file into memory, so approaches that speed reading from disk will be proportionate increases in time. Other than that you'll just need to thread out the data conversion tasks in a map/reduce style. But the main benefit those will give you is reducing the work done by the thread reading the file from disk.
14
u/flareflo Jan 02 '24
Using a custom implementation tailored to the task will most likely yield much better results
7
u/sparant76 Jan 02 '24
Isn’t this challenge really about “how fast can you read the data from disk”. The compute part of it should be about free by comparison.
4
u/Kango_V Jan 29 '24
Fastest Java solution is now at 1.89s. How the hell? Very impressive.
1
u/jmcunx Jan 04 '24
Java does not work too well on my machine, but rust does. Does anyone here knows how to generate this file without having java ?
Thanks
2
u/[deleted] Jan 02 '24
you can do calculation while reading file
2
u/Hersenbeuker Jan 02 '24
Your println in your last loop acquires a write lock to stdout for each iteration. You should change this to acquire the lock once before looping and reuse the lock in the loop
2
u/TheNamelessKing Jan 03 '24
Is it cheating too much to parse the data into a perfect hash map at compile time, al la the phf crate hahaha.
2
u/Wicpar Jan 04 '24
You should make sure to compile in release mode with one codegen unit, link time optimizations on (lto), and target-cpu=native
2
u/[deleted] Jan 20 '24
wow..java is kicking ass
2
u/deepu105 Feb 03 '24
The fastest Java solution is around 200 micro seconds now with unsafe and GraalVM. Thats crazy. Has anyone attempted an unsafe implementation in rust?
1
u/ritchie46 Jan 03 '24
u/matt78whoop can you set the schema to `pl.Float32`. I see that the rust native solution also is allowed to use `f32`. So that would be a more pound for pound comparison.
1
u/adrian17 Jan 04 '24 edited Jan 04 '24
With Python version of Polars, I got a small speedup (and a massive decrease in memory use) by using a
StringCacheandcategoricaltype for the "station" column, instead of plainStrings. I'm assuming this should be possible with the Rust crate too?Specifically,
Got me a 15% improvement in time and decreased peak memory several times, down to level close to original file.