Post · bonfire.cafe

@jonhoo@fosstodon.org · 2 days ago

I'm late to the party, but the One Billion Row Challenge (https://github.com/gunnarmorling/1brc) feels like an excellent way to dig into optimizing Rust code and learning somethings about assembly, SIMD, performance profiling, and just CPUs in general in the process, so let's take it on!

Come join me on Saturday at 11am UTC (https://everytimezone.com/s/70bf2c9d) over on https://youtube.com/live/g2EKNXKKGM4?feature=share, and we'll see what we can squeeze out of it 🏎️ This will likely be a long one 😅

Every Time Zone Converter

Easily find the exact time difference with the visual Time Zone Converter. Find meeting times for your contacts, locations and places around the world. Never warp your brain with time zone math again.

GitHub - gunnarmorling/1brc: 1️⃣🐝🏎️ The One Billion Row Challenge -- A fun exploration of how quickly 1B rows from a text file can be aggregated with Java

1️⃣🐝🏎️ The One Billion Row Challenge -- A fun exploration of how quickly 1B rows from a text file can be aggregated with Java - gunnarmorling/1brc

@jonhoo@fosstodon.org replied · 2 days ago

There are already several Rust implementations (https://github.com/gunnarmorling/1brc/discussions/57), this excellent write-up (https://curiouscoding.nl/posts/1brc/), and even an existing stream (https://www.youtube.com/watch?v=Q-0durxAB6s), but I'm hoping that walking through the process live will still be a good teaching exercise.

One Billion Row Challenge

Table of Contents External links The problem Initial solution: 105s First flamegraph Bytes instead of strings: 72s Manual parsing: 61s Inline hash keys: 50s Faster hash function: 41s A new flame graph Perf it is Something simple: allocating the right size: 41s memchr for scanning: 47s memchr crate: 29s get_unchecked: 28s Manual SIMD: 29s Profiling Revisiting the key function: 23s PtrHash perfect hash function: 17s Larger masks: 15s Reduce pattern matching: 14s Memory map: 12s Parallelization: 2.0s Branchless parsing: 1.7s Purging all branches: 1.67s Some more attempts Faster perfect hashing: 1.55s Bug time: Back up to 1.71s Temperatures less than 100: 1.62s Computing min as a max: 1.50 Intermezzo: Hyperthreading: 1.34s Not parsing negative numbers: 1.48s More efficient parsing: 1.44s Fixing undefined behaviour: back to 1.56s Lazily subtracting b'0': 1.52s Min/max without parsing: 1.55s Parsing using a single multiplication: doesn’t work Parsing using a single multiplication does work after all! 1.48s A side note: ASCII Skip parsing using PDEP: 1.42s Improved A further note Branchy min/max: 1.37s No counting: 1.34s Arbitrary long city names: 1.34 4 entries in parallel: 1.23s Mmap per thread Reordering some operations: 1.19s Reordering more: 1.11s Even more ILP: 1.05 Compliance 1, OK I’ll count: 1.06 TODO Postscript A youtube video on this post is here.

YouTube

Auf YouTube findest du die angesagtesten Videos und Tracks. Außerdem kannst du eigene Inhalte hochladen und mit Freunden oder gleich der ganzen Welt teilen.

Log in

bonfire.cafe

A space for Bonfire maintainers and contributors to communicate

bonfire.cafe: About · Code of conduct · Privacy · Users · Instances

Bonfire social · 1.0.0 no JS en

Automatic federation enabled