1BRC in Rust #57
Replies: 18 comments 43 replies
-
|
I had the same idea! Runs in |
Beta Was this translation helpful? Give feedback.
-
|
Interesting, for me it takes |
Beta Was this translation helpful? Give feedback.
-
|
Looking better at my |
Beta Was this translation helpful? Give feedback.
-
|
I'm probably just going to implement a |
Beta Was this translation helpful? Give feedback.
-
|
not sure if it is feasible to run on CI, with iai? name: benchmark
on:
push:
branches:
- main
pull_request:
permissions:
contents: read
env:
CARGO_TERM_COLOR: always
RUSTFLAGS: -Dwarnings
# setup sccache for Rust; see https://github.com/Mozilla-Actions/sccache-action
SCCACHE_GHA_ENABLED: "true"
RUSTC_WRAPPER: "sccache"
jobs:
iai:
runs-on: ubuntu-latest
steps:
- uses: actions/checkout@v4
- uses: mozilla-actions/[email protected]
- uses: dtolnay/rust-toolchain@stable
- run: sudo apt-get -y install valgrind
- run: cargo bench --bench benchmark_by_cachegrind |
Beta Was this translation helpful? Give feedback.
-
|
@coriolinus |
Beta Was this translation helpful? Give feedback.
-
|
@Lucretiel's version slightly modified, it runs under 10s => https://github.com/mtb0x1/1brc. I am pretty sure that we can speed it up by using custom hasher with Fxhashmap (make assumption about keys "city names", instead of comparing every bytes. check 2 firsts and 2 lasts or something similar) |
Beta Was this translation helpful? Give feedback.
-
|
I gave it a go, too. https://github.com/thebracket/one_billion_rows My biggest speedups came from using memmap2, chunking slices on a newline boundary, forward-only parsing (to keep each core's cache happy) and using one ahash map per thread - returning vectors for merging. Keying the hashmap on the slice of name bytes rather than a string of some sort helped a LOT. |
Beta Was this translation helpful? Give feedback.
-
|
Interesting! I've been testing with the With With the naieve program: If I can find the reference file, I'll download it. My suspicion is that I generated the values file slightly differently from the original - and then built my parser around that mistake. |
Beta Was this translation helpful? Give feedback.
-
|
Found the issue! My measurements generator is adding a space: Whereas the original data lacks the space after the semicolon: That should be an easy fix. |
Beta Was this translation helpful? Give feedback.
-
|
Ok, I corrected the measurement creator and And I get the same results on both of my test programs. Still clocking around 3.2 seconds. (The last push also includes some stuff I did before; reworking it to run in |
Beta Was this translation helpful? Give feedback.
-
|
Corrected another minor issue. I was printing out |
Beta Was this translation helpful? Give feedback.
-
|
And it keeps getting better! Replaced the native |
Beta Was this translation helpful? Give feedback.
-
|
Not yet (I actually generated my own input file) - that'll be tomorrow, ran
out of time for today.
…On Thu, Jan 4, 2024, 6:48 PM Corlin Palmer ***@***.***> wrote:
Did you check to see that your output was identical to the output of the
reference on the same file? If so, you might have the fastest solution
around!
—
Reply to this email directly, view it on GitHub
<#57 (reply in thread)>,
or unsubscribe
<https://github.com/notifications/unsubscribe-auth/ADRU4365VBHFF3OVT3LQO4TYM5EXJAVCNFSM6AAAAABBL4UL32VHI2DSMVQWIX3LMV43SRDJONRXK43TNFXW4Q3PNVWWK3TUHM4DAMJYGQ4DA>
.
You are receiving this because you commented.Message ID:
***@***.***>
|
Beta Was this translation helpful? Give feedback.
-
|
Nice work! Would you be so kind to measure the runtime of my C implementation here: https://github.com/dannyvankooten/1brc? Your solution runs in about 9s on my machine so I’m lacking some hardware. :( |
Beta Was this translation helpful? Give feedback.
-
|
Here you go: |
Beta Was this translation helpful? Give feedback.
-
|
Running it a few more times (to ensure its in the disk cache): |
Beta Was this translation helpful? Give feedback.
-
|
Awesome, thank you! And wow, that cache difference is huge on your machine. EDIT: Scratch that. It's just that my cache was pretty much always full because of running it all the time. Calling |
Beta Was this translation helpful? Give feedback.
-
|
You can run your solution with https://crates.io/crates/hyperfine to get a consistent result |
Beta Was this translation helpful? Give feedback.
-
|
~3.5s on M1 MAX Macbook Pro Strategy
Treat the first eight bytes of the name as a hash key into a fixed size 10k item hash table. Resolve collisions by finding the next unoccupied slot. Parse temperatures as Split input based on core count and run it with a thread per core. |
Beta Was this translation helpful? Give feedback.
-
|
Reduced it to 3.24s on the Macbook by switching from |
Beta Was this translation helpful? Give feedback.
-
|
With some SIMD it's now ~2.5s on the Macbook |
Beta Was this translation helpful? Give feedback.
-
|
Hi guys, https://github.com/gabrieledarrigo/1brc I'm learning the Rust basics, so my implementation is very naive (and quite OO) and uses a single thread. ~200s on a i7-3930K @3.20Ghx, with 64 GB of DD3 on Windows, running the binary on WSL. If a kind soul would like to review my code I'll be grateful forever! |
Beta Was this translation helpful? Give feedback.
-
|
Looks good! I didn't know about |
Beta Was this translation helpful? Give feedback.
-
|
I had a quick look and there are two things that stand out to me: Needless allocationYou always allocate a Error handlingThe error handling is a bit unidomatic. Read the error handling chapter in the Rust Book and refactor based on that. Consider using |
Beta Was this translation helpful? Give feedback.
-
|
@joaoeinride OK, and what can I use instead? @k0nserv Thank you for your suggestions 😊 Thank you so much guys, very appreciated 🙏 ❤️ |
Beta Was this translation helpful? Give feedback.
-
You can use https://doc.rust-lang.org/std/io/trait.BufRead.html#method.read_line, but make sure to |
Beta Was this translation helpful? Give feedback.
-
|
Hi, my attempt at the problem https://github.com/Namit-Nayan/one_billion_row |
Beta Was this translation helpful? Give feedback.
-
|
Hi, Here you can find my attempt: https://github.com/arthurlm/one-brc-rs I have explain in details my code and how I achieve this. I am also very curious of this program performances on any other computer. |
Beta Was this translation helpful? Give feedback.
-
|
I tried on my 32GB M2 Max, got a segmentation fault... But I'm in class so I haven't looked into it, but I'm willing to take a closer look if you're curious. |
Beta Was this translation helpful? Give feedback.
-
|
It is true I have used a lot of Here few things you may try:
I am really interested by your feedback, so feel free to ask any more question if needed. |
Beta Was this translation helpful? Give feedback.
-
|
I opened up an issue on the repo with a screenshot of the error. |
Beta Was this translation helpful? Give feedback.
-
|
Running on a Ryzen 7 5800X 8-Core & 32GB of RAM, I got: # Cold Cache (likely due to the SATA drive)
Inside main total duration: 26.360960134s
Elapsed: 0:26.74
# Warm Cache
Inside main total duration: 1.644969495s
Elapsed: 0:01.98 |
Beta Was this translation helpful? Give feedback.
-
|
Certainly late to the party, but here is my attempt none the less: https://github.com/GeistInDerSH/1brc |
Beta Was this translation helpful? Give feedback.
-
|
I figured there may be some collision, but adding the following to the // ...
.entry(hash) // The source code for this function does the collision handling
.and_modify(|data: &mut Data<'a>| {
if data.name != station { // Added for debugging
let data_name = std::str::from_utf8(data.name).unwrap();
let station = std::str::from_utf8(station).unwrap();
eprintln!("Names do not match!!! {} vs {}", data_name, station);
}
data.add_value(value)
})
// ...
// Same was true for the other and_modify, skipping for brevityDiffing some of the other results with my own shows that mine is indeed incorrect, but only for a single key. If the collision was an error, I'd think it would impact more than just that key. |
Beta Was this translation helpful? Give feedback.
-
|
Your last change fixed the error that I posted. The point is that even if there's no collision, the code still needs to check if the station names are the same, and if not get another key. How does this check that you added for debugging impact your time? |
Beta Was this translation helpful? Give feedback.
-
|
And if the code has to consider a possible collision, then the code below would not work anymore, because two local maps ( // We have to send any data we have that has not already been sent
if let Ok(mut shared_map) = entries.lock() {
for (station, data) in local_values.into_iter() {
shared_map
.entry(station)
.and_modify(|map_data| map_data.add_data(&data))
.or_insert(data);
}
} |
Beta Was this translation helpful? Give feedback.
-
|
I've updated all |
Beta Was this translation helpful? Give feedback.
-
|
The code can be further improved by removing the unnecessary allocation in or_insert(Data::new(value)). The or_insert function will always create the Data object whether the entry is found or not. local_values
.entry(station)
.and_modify(|data: &mut Data| data.add_value(value))
.or_insert(Data::new(value));To fix it, the code should be local_values
.entry(station)
.and_modify(|data: &mut Data| data.add_value(value))
.or_insert_with(|| Data::new(value)); |
Beta Was this translation helpful? Give feedback.
-
|
Never wrote any rust code in my life before this challenge. I broke the rules about not using external dependencies on this but anyway here's my code https://github.com/ANKerD/1brc It runs on about 15s on a Macbook air M1 8GB. I used an external heap allocator (mimalloc), FxHashpMap for faster HashMap access, itertools to iterate over the sorted keys, and used Profile-Guided Optimization for general 10~20% faster execution times. |
Beta Was this translation helpful? Give feedback.
-
|
A concise solution using rayon: Runs in 27s on ryzen 7 3800x. No optimizations were done other than adding The one-liner in main is just: fs::read_to_string("measurements.txt")?
.par_lines()
.flat_map(parse_line)
.fold(Stations::default, Stations::insert_line)
.reduce(Stations::default, Stations::merge)
.print(); |
Beta Was this translation helpful? Give feedback.
-
|
Did some optimizations and made a new version without rayon, still quite simple IMHO, now down to ~1.22s on ryzen 9 5950x: Memory mapping, ditching rayon for a custom thread scheduler with chunking, using hashbrown HashMap, custom float parser, some simd, and removing unnecessary allocations helped make this possible. |
Beta Was this translation helpful? Give feedback.
-
|
~50s on Ryzen 7 3700U 8 core 2.3 GH With using Mmap and thread pool. Implementation: I am open to your support and development ideas, please comment. |
Beta Was this translation helpful? Give feedback.
-
|
Hi! let thread_count = std::thread::available_parallelism().unwrap().into(); // Note: Likely 8 on a R7 3700U
// ...
for i in 0..thread_count { // Note: Only reading the first 8 1048576 byte chunks of the file
let mmap_arc_clone = mmap_arc.clone(); // Clone the Arc, not the Mmap
let results_clone = results.clone();
let start = i * CHUNK_SIZE;
let mut end = start + CHUNK_SIZE;
if end > file_len {
end = file_len;
}
// ... |
Beta Was this translation helpful? Give feedback.
-
|
Omg how I make this mistake :( I was incredibly surprised how it works so fast, I should have understood. Now I fix issue it is now run under 1 minute =~ 50 sn on my machine Thanks for response |
Beta Was this translation helpful? Give feedback.
-
|
Can someone be nice enough to review my code. I am using pure |
Beta Was this translation helpful? Give feedback.
-
|
Update: Optimized float parsing and unchecked UTF8 str usage little bit more, it now completes the task in I'm able to parse measurements.txt correctly in I used libc, cityhash64 and Rust std. Feel free to test/roast my code: https://github.com/SuperioOne/1brc |
Beta Was this translation helpful? Give feedback.
-
|
Here's my attempt using only the Not many seems to mention the this: my SSD which is noted to have 3,500MB/s Seq. Read by the manufacturer would theoretically allow me to read the 14 GB file in ~4s, so attaining sub 1s is kind of a lost hope for now :') |
Beta Was this translation helpful? Give feedback.
-
|
Now runs in 2.3s 🚀, without any dependency nor unsafe calls 🙌. I've improved my code (hash function and table) and mapped the file in memory by moving it in a tmpfs partition to bypass the SSD speed limitations. |
Beta Was this translation helpful? Give feedback.
-
|
Down to 1.08s after using SIMD (through the experimental |
Beta Was this translation helpful? Give feedback.
-
|
I know I'm late to the game but here is my rusty solution: https://github.com/Cobinja/onebrc NOTE: Don't run this on 16GB machines, it reads the whole 13.8 GB to RAM. |
Beta Was this translation helpful? Give feedback.
-
|
Brought it down to ~8.3 seconds |
Beta Was this translation helpful? Give feedback.
-
|
Down to 7.8 seconds after dropping caches, 6.0 seconds with caches |
Beta Was this translation helpful? Give feedback.
-
|
Well this is my go at it. |
Beta Was this translation helpful? Give feedback.
-
|
@sehnryr |
Beta Was this translation helpful? Give feedback.
and others
-
Nothing too exciting - mmap whole file, split it into slices (one per core), collect partial results and merge.
Code is here: https://github.com/tumdum/1brc/blob/main/src/main.rs
Runs in ~15.5s on a m2pro
Beta Was this translation helpful? Give feedback.
All reactions