Making It FAST - 1 Billion Row Challenge in Go 

Hey Prime, this was one of the best programming videos I've ever seen. I really want to see you tackle some of these problems, and venture into that "unsafe" zone of Go that I'm so scared of.

Your comment on the Apple silica is literally why I bought my first max after years of fighting. It’s performant efficiency. My ability to be off charger for wayyyy longer under load. I got to test drive a x1 Lenovo and it last 1.75 hours under decently heavy load while my M1 Pro was about 7hrs. It’s something I’ve been annoyed at intel for a while at just pushing inefficient power to get more and more diminishing clock gains. Performant battery life is one of the best innovations of the last couple decade imo along with SSD storage.

Great article, loved the scientific approach of handling the challenge!

I love both this challenge and this article. It's an excellent example of the way I would expect optimization to work in industry, albeit in a more approachable format. Step 1 is make it work, then start to analyze and optimize approachable bottle necks iteratively until you hit your goal. What the article skips over briefly is the extra reading and deep diving you would need to do to go into what things seem like ACTUAL potential time saves if you aren't familiar w/ optimizations like this from the outset. Would LOVE to see something like this done for a website or other UI. (Make it work, then making the response time under 1/4 of a second, or whatever other goal you would have. That case is more of finding unexpected bottle necks and cutting them out)

The record in java is 1.4 seconds, prescinding of the garbage collector, using multithreading with 8 cores, and using the Vector API

My first stab would be to memory map the file. Split the data into number of hardware threads available, have each thread process it's chunk and create its own hash of sum, min, max, count, etc. Then join the threads and tabulate the final results. This way each thread is independent and there is no locking on anything. Not sure how it would perform in go or any other language, but that's the basic approach I would start with.

Really great article! Followed her on Twitter.

Kudos to the Java community - all jokes about the language and the jvm aside - for launching a challenge that inspired extensive collaboration and interesting articles even outside their own "domain". Credit where credit is due. Applause.

You need to use monoids -- Haskell Fanboy I'd think IO would be the first thing to tackle -- find fastest way to read huge file without doing anything and then find the fastest way process each chunk, then fastest way to reduce the chunks.

This was awesome to see the process that the developer went through. Good job. But, it amazes me that Java's JVM is so powerful that it can do this in 1.8 seconds without a native binary and 1.5 seconds with GraalVM.

I would read 1k lines per thread and base the hash on the bucket index (bucket-1000-0, bucket-1000-1..., bucket-2000-0, bucket-2000-1...)

Perhaps, instead of using a map, we could construct an array . I don't know how fast the hash function for maps is in Go, but perhaps it's worth trying the following. Convert three bytes from each name into 15 bits. Three-byte combination is unique for 10.000 names. We can, for example, take first three bytes ( If the characters in the string (name) are not all from ASCII, we should take the 4th, 8th and 12th byte, with len check first) Then, by using fast bit-operations, from each byte extract bits at 5 characteristic positions to three contiguous bit-chunks. This gives an unsigned number < 32.768 which is the index of an array element, a sub array consisting of min, max and avg. Sort using radix sort with the radix of 5 bits (the order should remain alphabetical, if I'm not wrong). The array will be two-thirds empty, though, but this is a rather small array, so it doesn't matter. Actually, not sure about preserving the alphabetical order if characters are not all from ASCII, but in that case we can still use the same procedure, bu store also the name as a string in the array element, and then sort by runes also using radix sort.. The first and last out of three stages of the radix sort can be done in parallel.

I recently adapted Go and absolutely loving it as my personal primary backend language and got away from JS/TS for everything. I still use NodeJS those for current job but Go gives me a minimal syntax vibe of Python, modern C++ like characteristics with speed and concurrency.

Array vs struct in that usage is the same, but you'd probably want to use a struct so you can try padding it out to cache line size and align the entire thing on cache line

Relevant info for those who say "Java can do it in 1.5 seconds" beware that the java tests ran on RAMDISK of this machine: "dedicated server (32 core AMD EPYC™ 7502P (Zen2), 128 GB RAM). Programs are run from a RAM disk (i.o. the IO overhead for loading the file from disk is not relevant), using 8 cores of the machine." It is not a bad article, but as a hiperf-nerd I find it also fascinating how the guys thinking process is: Like calculating sum/min/max instead of storing the file in memory first is so annoying he does not do at first try even without thinking (I saw this surprised prime too). Also mmap-ing the whole thing should work better (even with ramdisk I feel) plus doing threads the way the guy does here seems very wasteful. I literally think that a simd-style parallelism wins over threads here very bigly. But if one really wants to use threads I imagine it should be more like somehow doing big chunks of the file I/O separately - like starting from line X (by literally doing A, B, C, D threads or even 8 threads that read only parts of the file - but HUGE parts). This means to have 4-8 min-max-count-sum values for each thread for each processed block (that can still happen with simd) and then after all of them finished (for which you not need any inter-thread communication and can do it fully lock-free) you just mix together that result. I think on that heavy EPYC server on a ramdisk, with well set up I/O in C should be done in milliseconds or 10-100 of milliseconds at most to be honest. On "real" machines it should be bottlenecked by I/O performance of your hardware.

would love to see you solving the challenge iteratively

I'd probably do a boss worker model on a chunk of the lines, for each thread return a map of the thread local minimum/maximum/avg/count. On return you can then combine. There's no need for input state to be sync'd. Also as I'm watching more of this, IDK if an array vs struct would be that much different. Struct should be packed similarly to the array in this use case. You could probably even get away with using a tuple too. An easy way to validate this would be to look at the IR for go for this program.

Gonna be honest, it hurt to immediately realize that map access was going to be a problem late game, and then learn at the end that they weren't going to do anything with it. This BRC thing is a really fun challenge!

Too complicated. Just use Python for loops.

People probably pointed it out, but the rounding is indeed ceiling as you figured out. Negative numbers, however, need to be rounded in the same direction, so there's some level of complexity to that. You can't /10*10 the integer like some people thought unless goland has a different opinion than most other programming languages. I couldn't find the specifics for goland, but integer division should point to 0, so negative numbers wouldn't be right.

<a href="#" class="seekto" data-time="547">9:07</a> I'd personally have all routines process chunky reads from file, and return maps to merge using the coordinator routine (main), so that way i won't have to do any mutexes. Might cause a bottleneck on the merge part, but the row processing would be fast enough in threads but might be similar to mutex waits. Actually, i kinda wanna write both and find out now.

I would love if this became a mini-series on yt from your streams on your main channel or on one of your secondary channels. This would be immensely helpful to noobs like me on Go and just programming in general ❤

Seal of approval

Channels IIRC have mutexes internally. What I'd do: take a hash of the name, take a modulo, use it to locate the target goroutine in a finite list. Each goroutine is associated with a preallocated slice + start/end indexes (implement the queue manually, a lock-free circular buffer). That would avoid synchrosization costs. Enqueue while you read. Reading can be parallelized too (if it's not an HDD). Calculate on the fly without storing in intermediary data structures.

<a href="#" class="seekto" data-time="250">4:10</a> the apple encoders are very efficient BUT they're much much worse in quality at low bitrates (streaming bitrates). Currently the best quality h.264, h.265 and Av1 goes to Intel, then Nvidia, AMD and dead last Apple. To give you a reference Apples h.265 is about as good as Intel's h.264 at the same bitrate, so ~2x worse than Intel.

<a href="#" class="seekto" data-time="463">7:43</a>: "I always reduce my loads when I can ... damn!" this is what i am here for, every single fkin day!

i got python down to 3.3 seconds on a 16gb m2 macbook pro. i don't think i can get below 1 second like the java bros without resorting to rewriting it for compiling. vanilla single threaded python using csv module to iterate it a row at a time took a little over ten minutes, so there's a lot of improvement to be had from that starting point 😆

made great sence in the process of solving the 1BRC. Bravo

Now I want to see people do this in all sorts of languages and see just what comes of it. I also want to try this myself in Go and if I was still well versed in Python which I've given up for Go, maybe I'd try that and suffer.

A fun exercise, even though I'd probably not go as far as to write my own string to int parser

Goroutines are coroutines, only in go. Coroutines are a fancy way of saying threads, except they are managed.

I wonder one more optimization... Have a lookup table/hashmap for all temps? If you have a hash map of [strings][float] for example allTemps["-99.9"][-99.9], no parsing and a straight hash lookup... Should be much faster then parsing anything...? Assuming the data is value for the temp values should be perfect to get some perf :)

This is another case where go isn't really any faster than java-- although it does have better memory consumption-- and you give up so much power from being able to use other JVM languages like Scala and Clojure, not to mention all the third-party library support.

My current computer only has 8 gigs of RAM, so i guess i'd have to use some cloud VM or something to really test this, but it does sound fun. I'd love to try this in Go and Zig. I wonder how much the differences in SIMD instructions between intel and arm would impact the results.

"Creating a new array might seem easier" true, but then you need to understand when and why sync.Pool is so much faster. Not at the end of the video yet, but my guess is a sync.Pool of pre-warmed goroutines is going to play a big part in a truly performant solution.

always bamboozeled by all the technical shit that goes on in this channel as im super new to coding but this one i swear i understood. great article

In java, I never used scanner. I only used file reader and processed data manually. I always found it to be quicker, and as a sanity check I had to know what the data being read was and how to handle reading it

Makes it even more insane that the fastest Java solution is <a href="#" class="seekto" data-time="1">00:01</a>.535 seconds with GraalVM(Compiling to native), and <a href="#" class="seekto" data-time="1">00:01</a>.880 seconds on any JVM.

I used to process credit card operations dumped by banks and used some of the optimizations showed here but learned a couple more from this vid 💪

<a href="#" class="seekto" data-time="326">5:26</a> You're not a General AI. You're Captain AI. 😎

The Sam Bankman-Fried prison photo is adorable

I never tried to solve this myself, but my first thought was to MMAP the file and access the bytes like it was memory? Then don't need to think hard how to optimize reading file chunks into buffer. I don't know where this would end up though performance wise.

<a href="#" class="seekto" data-time="300">5:00</a> Challenge accepted 😜! After many humans solve the 1BRC wouldn’t one be able to train a model & then it would output decent code? Possibly something the humans didn’t think of? 🤔

I thought I was the only one doing the seal thing

Apple Silicon is significantly more energy efficient for basically every purpose. People can hate on Apple all they want, but the fact is that they are doing excellent work with their new ARM chips.

<a href="#" class="seekto" data-time="1066">17:46</a> wait a second, the rules states the rounding should be done in the output, not the input. Converting to int64 will cause a loss in precision and increase a lot the rounding error of the final mean value. Since all the values have only one fractional digit, why did the author not store this additional decimal value to do some fixed point arithmetic to reduce the rounding error?

WELCOME TO COSTO I LOVE YOU

“Seal” 😂 <a href="#" class="seekto" data-time="130">2:10</a>

Would have wanted to see you code this challenge in this video.

I am loving the Go content so much.

<a href="#" class="seekto" data-time="151">2:31</a> Hamburg Mentioned! RAAAAAH 🔥🔥🔥🔥🔥🔥 Es gibt kein schlechtes Wetter nur falsche Kleidung!!!

Amazing

noice way to learn optimization

“Kiss From A Billion Rows” - Ceil

<a href="#" class="seekto" data-time="1453">24:13</a> Yeah, I love that this optimization is not rocket science.

I’d have it output random values and just claim it was a hallucination if wrong.

I swear that no matter how long I'm in this profession I'm always going to read Go as the board game rather than the language. Somehow I thought this might be about a computer Go tournament on a 1 billion by 19 board.

Prime just invented the DynamoDB sharding model. It's not a surprise that switching to int was faster. I just am not sure how you get there quickly. Read left of dot, multiply by 10, add right of dot? 1 billion times? I don't know.

The real way to solve this problem is to fix the stupid file format. Register each station to an integer identifier, and each temperature to an integer value, and you can mmap the whole file and move slices to any number of threads with no communication. You could even put the whole record in 4 bytes easily, making it trivial to extract the temperature and accumulate the stats with SIMD or vector machines. There is a way to do the mmap split without fixing the format, but it's a bit messy.

Lovitz is spot on

I think trie was only for identifiers and inside we would've kept the same 4 values as in map.

Yes, Mistral is a thing.

Haha, so this is why this project was trending when I was looking around at golang projects.

Wonder why they specify float rounding for something that fits losslessly in 11 bits of signed integer.

Exactly my first thought ( for first take/ baseline) min and max! Storing map/ array takes space- one 1️⃣ bil ?? Hmm 🤔! Nope! Also split the rows and read. Aggregate all max/ min from split data. And then we improv… but for first take baseline brute force , that’s what I’d do! <a href="#" class="seekto" data-time="467">7:47</a> Number 3, classic producer/ consumer with the wait() and notify() !! Who’d have “ thunk” it? Lol 😂 <a href="#" class="seekto" data-time="777">12:57</a> nice 👍 Also wondering after processing, if he did a flush() of the buf channel / stream. Yeah I’d increase it to 1000 from 100..… <a href="#" class="seekto" data-time="1275">21:15</a> Now he’s talking my language- chunk read ( above) and min/ max.. lol 😂 yep 👍 agree 👍- simple incremental optimization- nothing broken. That’s how you’d want to introduce change in production also. Or you’d have 1 billion customers clamoring at your door 🚪!! <a href="#" class="seekto" data-time="1456">24:16</a> Except I’d have shot for min/ max in step1. But that’s just me! Lol 😂 GO is a lot like Java with the ReadBytes lol 😂.. Good 😊 article/ video ! Yay 😀! - Amy ( aside: TreeMap in Java is sorted by keys 🔑 - If the temp was the key per city… hmm 🤔 <a href="#" class="seekto" data-time="1761">29:21</a> )

<a href="#" class="seekto" data-time="314">5:14</a> dall-e lol

Is this some insanely fast lockless tree implementation competition disguised as a file parser kind of exercise?

All these conditions, no attempt to account for file cache on an iOS bound problem.

one question: isn't reading all the data from disk or even SSD taking already much more time then these little computations for each line? I mean everything has to go through the sata cable.

Java made it in 1.53sec using a 32core EPYC monster. M1 pro 10C/16G is nowhere near that beast :) So we can't even compare the results

I also thought of Batman Forever.

It's M3 now for work laptops

Vedal indeed mentioned

Should probably memory map the file and delegate file reading to the OS.

Oh hey, its the picture of SBF in prison

nothing linked in the description. Great!

@theprimeagen if you go full time content creation, your first project HAS to be automating turning off alerts while streaming.

Navy seal mentioned! xD

i ran into a problem just like this reading a financial dataset that was 9 gigs of data tldr i just chunked it

Just use AWK for this.

Unless I am trying to show a poorer baseline, my thought process was to aggregate them per key.

I think she resorted to threading way too early.

I’d use a for loop

I guess he could also pass pointers to channel instead of objects.

Search about "Rinha de backend" a more interesting challenge

Trie != Tree

I want to see somebody do this in browser JavaScript. Spawn background processes with service workers and such.

Start bringing back the obfuscation challenges...lol...

I had to pre-calculate distances between top 1000-ish cities on earth. I calculated this as 2-4 billion rows to be saved in sql. At first it looked like it was gonna take weeks running on a server. Then I put an sql table into memory instead of regular. Then it ran in less than like 2 hours with php.

You can do a map reduce on this right?

Oh black is back

Do the challenge I miss main channel content!

How would one go about creating a profile graph like that at <a href="#" class="seekto" data-time="941">15:41</a>? Edit: pprof

Pretate!

I guess in python you'd use something like pandas to read the file, but not sure

Three additional cores

if your runtime isnt completely dominated by loading/parsing, you've messed up.

<a href="#" class="seekto" data-time="2">00:02</a> Kek "First photo of Sam Bankman-Fried in jail"

where's the blue hair

Is the parsing time included? Because that would actually be kind of insane because even with a 3000 MB/s drive that's still roughly 5 seconds just for parsing.