The One Billion Row Challenge in Go: from 1m45s to 4s in nine solutions

I found this super interesting - especially as all the data I&#x27;ve written code to manipulate has been small enough that I haven&#x27;t needed to optimize my code, so I&#x27;ve never had to think in this direction.<p>I think my favorite part was the very first section, where he got baseline measurements with `cat`, `wc`, and friends. I wouldn&#x27;t have thought to do that and its such an easy way to get a perspective on what&#x27;s &quot;reasonable&quot;.

I was curious how long it would take with Polars (for scale), apparently 33s: <a href="https:&#x2F;&#x2F;github.com&#x2F;Butch78&#x2F;1BillionRowChallenge&#x2F;tree&#x2F;main">https:&#x2F;&#x2F;github.com&#x2F;Butch78&#x2F;1BillionRowChallenge&#x2F;tree&#x2F;main</a><p>I’m kind of interested in the opposite problem, what is the simplest solution using a well known library&#x2F;db that approaches the fastest hand optimized solution to this problem?

For anyone looking for more examples of 1BRC in Go, we had a friendly competition at work and collected the results here: <a href="https:&#x2F;&#x2F;github.com&#x2F;dhartunian&#x2F;1brcgo&#x2F;">https:&#x2F;&#x2F;github.com&#x2F;dhartunian&#x2F;1brcgo&#x2F;</a><p>In addition to the loop-unrolling and bit-twiddling tricks that also show up in the fastest Java and C++ versions, some Go-specific things I learned were:<p>- unsafe.Pointer can be used to read memory without bounds checks<p>- many functions in the bytes and bits packages in the standard library are written in assembly<p>- debug.SetGCPercent and SetMemoryLimit to turn off GC<p>- runtime.LockOSThread to lock a goroutine to a thread<p>- print is slightly faster than fmt.Printf (but writes to stderr)

&gt; I find this report confusing. Why does if items[hashIndex].key == nil show as taking 5.01s, but the call to bytes.Equal shows as only 390ms. Surely a slice lookup is much cheaper than a function call? If you are a Go performance expert and can help me interpret it, I’m all ears!<p>These two lines are both conditionals, so the time reported is sensitive to branch mispredictions. If the timings are not intuitive based on the complexity of the associated lines, then it may be explained by the data being not very predictable and the branch predictor having a bad time.

I love the nerdery around 1BRC. My axe to grind is that unless you do dangerous stuff DBs are just as fast, less complicated, and more resilient to data updates than application code [0]. Do more in the database!<p>0: <a href="https:&#x2F;&#x2F;geraldonit.com&#x2F;2024&#x2F;01&#x2F;31&#x2F;1-billion-row-challenge-in-sql-and-oracle-database&#x2F;" rel="nofollow">https:&#x2F;&#x2F;geraldonit.com&#x2F;2024&#x2F;01&#x2F;31&#x2F;1-billion-row-challenge-in...</a>

Back in 2010, I used PostgreSQL for a web app that queried 270 million rows of climate data from Environment Canada:<p><a href="https:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=10KEr3sEG80" rel="nofollow">https:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=10KEr3sEG80</a><p>I wanted to see how the temperature was changing over time for specific regions using a map-based interface. The following chart was particularly eye-opening:<p><a href="https:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=iEtvf9xzRB4&amp;t=164s" rel="nofollow">https:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=iEtvf9xzRB4&amp;t=164s</a><p>The software won a couple of awards and was heavily optimized to produce reports in under a minute. Kudos to the author for getting a parse time of a billion records down to mere seconds.

It&#x27;s worth noting that if you&#x27;re messing around with large text files from the CLI, awk, grep, etc will be an order-of-magnitude faster if you opt out of unicode parsing.<p>I&#x27;m pretty confident adding LC_ALL=C to the awk solution would get it easily under a minute.

I just want to go on record that given the simplistic (i.e fun) problem, a shell developer would have had the answer to a first, specific set of billion rows done while all the other language were still putting on their shoes.

Nice post. Interesting that the fastest Java beats the fastest Go, though they are close:<p><pre><code> AY fastest Go version 2.90s 36.2 TW fastest Java version 0.953s 110 </code></pre> I would have expected Go to win. That JVM works pretty good...

&gt; the fastest, heavily-optimised Java solution runs in just under a second on my machine<p>I don’t understand how this is possible. The file in question has 13GB, while the fastest commonly available SSDs are 12400 MB&#x2F;s. Am I missing something?

I love the author’s step-by-step approach as very often it so happens that a hyper-optimized solution may be overfitted to the exact dataset it’s operating on. In each step, the tradeoffs are being explained: what we gain, but also what we lose by stripping the functionality away.

Second article I&#x27;m reading on implementing this in Go. Since the temperatures are in the range [-99.9, 99.9] with a tenth of precision (~2k values), I am surprised why no one has implemented a parsing of the numbers using a prepopulated lookup table. Should probably speed things up.<p>I submitted a github issue on this for the other implementation I looked at here[1].<p>[1] <a href="https:&#x2F;&#x2F;github.com&#x2F;shraddhaag&#x2F;1brc&#x2F;issues&#x2F;2">https:&#x2F;&#x2F;github.com&#x2F;shraddhaag&#x2F;1brc&#x2F;issues&#x2F;2</a>

I have a feeling that a naive implementation in Java would be a lot worse than a naive implementation in Go so optimizing matters more there.<p>Had to parse csvs in Java on a very memory constrained system once... we ended up cutting out a feature because it wasn&#x27;t worth it.

&gt; I’m in the same ballpark as Alexander Yastrebov’s Go version. His solution looks similar to mine: break the file into chunks, use a custom hash table (he even uses FNV hashing), and parse temperatures as integers. However, he uses memory-mapped files, which I’d ruled out for portability reasons – I’m guessing that’s why his is a bit faster.<p>I am curious, can it be made even faster than this?

Ia there a collection on all the languages that have attempted this challenge? I know comparing and competing languages is somewhat useless but it is still interesting to me.

There&#x27;s a nodejs version which takes 23s<p><a href="https:&#x2F;&#x2F;github.com&#x2F;1brc&#x2F;nodejs">https:&#x2F;&#x2F;github.com&#x2F;1brc&#x2F;nodejs</a>

Those super optimized solutions are fun to read about.<p>However, in real life I would never assume a millions rows of text all have all valid data in a specific format, much less a billion rows.<p>Thus a slower but more robust solution would be more realistic.

I’d like to see a 1 trillion row challenge.

My first instinct would be to spin up a local Postgres and keep station data there. A lot of the solutions assume we have enough ram to keep the stats per station, however that&#x27;s a bad assumption when dealing with a lot of data.

How did you generate the timings on: <a href="https:&#x2F;&#x2F;benhoyt.com&#x2F;images&#x2F;go-1brc-profile-r9-source.png" rel="nofollow">https:&#x2F;&#x2F;benhoyt.com&#x2F;images&#x2F;go-1brc-profile-r9-source.png</a> ?

It would be interesting to know how effective Profile Guided Optimisation is here.

One &quot;trick&quot; not tried in the article that I have used is to gzip the data (so you have a .csv.gz) and stream that instead of the raw file. I find it reduces a large amount of the disk read (as you have 6-10x less to read).

There’s something cool about the fact that parallel code in Go is still idiomatic Go.

Meanwhile the C# (.net) implementation is 4x faster.

performance is great but i would imagine the paralellized version requires a significantly higher minimum amount of RAM than the non paralellized ways... he claims that each more perfomant solution is less compute cost than the one before it, but in the case of paralellization its just the same amount of compute in just a shorter amount of time, right?

Nice. I wonder how Rust would fare, given that it has no garbage collector.

How about kdb+ or shakti

i saw the custom hashtable, but why was Map slow?

I’d just pay my way to 4s by upgrading hw

The effort and long time it took Go to get to something that 3-6x times slower than other, better languages should be an important reminder to everyone assuming it belongs to the same weight class as Rust, C# or Java.