The One Billion Row Challenge in Go: from 1m45s to 4s in nine solutions
benhoyt.com
benhoyt.com
I think my favorite part was the very first section, where he got baseline measurements with `cat`, `wc`, and friends. I wouldn't have thought to do that and its such an easy way to get a perspective on what's "reasonable".
I’m kind of interested in the opposite problem, what is the simplest solution using a well known library/db that approaches the fastest hand optimized solution to this problem?
Java is also more mature, which means you are entering a massive package-bloat setup that has evolved over the years to work for everyones wild and varied needs. By the time you have your database, cache, http/other handlers, tests, fixtures, metrics, logging, tracing, etc... setup you're looking at a scary pile of dependencies spanning thousands of classes that would make even NPM jealous.
https://github.com/gunnarmorling/1brc?tab=readme-ov-file#run...
The Python version:
https://github.com/gunnarmorling/1brc/blob/main/src/main/pyt...
It seems they are not running against the full dataset:
> Moving on to the 100 million file to see if size makes a difference.
ggplot2::autoplot(reorderMicrobenchmarkResults(bench1e8))
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:
- unsafe.Pointer can be used to read memory without bounds checks
- many functions in the bytes and bits packages in the standard library are written in assembly
- debug.SetGCPercent and SetMemoryLimit to turn off GC
- runtime.LockOSThread to lock a goroutine to a thread
- print is slightly faster than fmt.Printf (but writes to stderr)
Update: for reference, Jason Chu's solution (https://github.com/dhartunian/1brcgo/blob/494eabd6ea958cc193...) seems to be the fastest on my machine, and runs in about 1.3s!
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.
0: https://geraldonit.com/2024/01/31/1-billion-row-challenge-in...
With application code I can easily step through it in a debugger and verify the deployed code matches what's in the repo. It's more difficult to do in the database because it requires more organizational discipline.
[0]: getdbt.com
https://www.youtube.com/watch?v=10KEr3sEG80
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:
https://www.youtube.com/watch?v=iEtvf9xzRB4&t=164s
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.
I'm pretty confident adding LC_ALL=C to the awk solution would get it easily under a minute.
AY fastest Go version 2.90s 36.2
TW fastest Java version 0.953s 110
is there any similar blog post on the Java optimisations?
See https://hotforknowledge.com/2024/01/13/1brc-in-dotnet-among-...
Are you sure?
But yes, "I expected Go to win..." is exactly the core of the problem here. Same as with e.g. Swift, which people expect to perform on the level of Rust, when it is even slower than Go. The intuition caused by common misconceptions just does not correspond to reality sadly.
The Java and Go versions use different optimisations. There’s nothing stopping either language from using the same optimisations as the other. It just wasn’t something their respective authors cared to try in their respective exercises.
...
> This puts much greater burden on the programmer to match the performance while staying with Go.
Your second statement contradicts your first. You're not stopped from using SIMD in Go. There are in fact several 3rd party libraries out there to use SIMD. It's just not part of the standard library. So you can still use SIMD in Go without writing Go's dialect of assembly.
It's also worth noting that SIMD isn't even due to drop into std in C++ until C++26. At the moment you either have to use experimental or a 3rd party library.
You're also missing the point of these examples. Nobody writing these exercises are trying to claim that all languages are equal. And they certainly not trying to write idiomatic code either. They're just fun little exercises demonstrating the degree of optimisations one can go through. You wouldn't want to write code like those in the examples in all but a the tiniest of scenarios.
It's silly the amount of people over-analysing this, what is essentially just a game, and then arguing its "proof" about their biases towards different programming languages.
Source for that?
Go's advantage has always been that it is good enough at a lot of things.
JVM has had decades of experience at optimally translating bytecode to machine code and can take advantage of SIMD, AVX etc when needed. Most hand-written C code is far from optimal.
Modern JVMs, not only have the JIT being able to use actual production data, they are able to cache PGO data between execution runs, and reach an optimimal set of heuristics throughout execution time.
And on Android, those PGO files are even shared between devices via Play Store.
In particular, with JIT, you are able to initialize certain readonly data once, and then, on recompilation to a more optimized version, bake such data as JIT constants right into emitted machine code. This is not possible with AOT. Same applies for all kinds of in-runtime profiling/analysis and recompilation to incorporate a collected profile according to this exact run of an application. JIT also offers the ability to load modules dynamically in the form of bytecode without having to have a strict machine-level ABI, only the bytecode one, which allows for efficient generics that cross modules, as well as cross-module function inlining. And last but not least - there is no need to pick the least common denominator in supported hardware features as the code can be compiled to use the latest features provided by hardware like AVX512.
On the other hand, pure AOT means a frozen world which allows the compiler to know exact types and paths the code can take, performing exact devirtualization and much more aggressive preinitialization on code that accepts constant data. It also means bigger leeway in the time the compiler can spend on optimizing code. Historically, GCC and LLVM have been more advanced than their JIT counterparts because of different tradeoffs more favouring to absolute performance of the emitted code as well as simply higher amount of man hours invested in developing them (e.g. .NET punches above it's weight class despite being worked on by a smaller team vs OpenJDK or LLVM).
GCC & clang, in comparison, often produce assembly which I'd consider optimal, or close to it, for vectorizable loops, and are noticably better than OpenJDK for scalar code.
[1]: it's a bit messy to use but: https://github.com/dzaima/grr#java-jit
You might mean it's impractical? Or that it happens to not be true in the general case?
In go you've got your standard libraries, these are generally quicker than the Java equivalent simply because they do less in the lifecycle of the operation.
This lets Java do funky stuff like enabling full jvm/code tracing just by adding a jar file at runtime. But it does come with a performance penalty.
On the down side, there are quite a few features of the Java language and the JVM, which often make programs slow. Like a lot of details of the object model, lack of value classes, JIT compiling which takes time on startup etc. Also, a lot of Java libraries are pretty heavy weight.
Go is quite different here. It is statically compiled, which allows for fast program startup and the language model makes it quite easy to rather naively write programs which perform reasonally fast. The down side is, that the compiler is static and not so heavily optimizing as other static compilers for fast compilation speed. However recently the ability was added to use profiling data for optimizing the compilation.
I have never found this to be true.
There are a few programs (Talend, MySQL workshop) written in Java that I sometimes have to use, and I avoid them as much as I can, because they are slow, bloated, and eat lots of memory.
Java new operator is faster than malloc, because Java allocates all memory needed from the OS before starting the program. And malloc is extremely slow. C++ new operator uses malloc so it is also slow.
Stack allocation in a C program is hundreds of times faster than using new in Java.
And that's for one feature, there are many other features like C++ compile-time calculations in templates that simply have no Java equivalent.
Synthetic benchmarks aside, I think as far as average (spring boots of the world) code goes, Go beats Java almost every time, often in less lines than the usual pom.xml
Also, what even does the last line mean? Go in general is significantly more verbose than Java.
The more interesting comparison anyway is performance of the straightforward, idiomatic code, since that's what we all write 99% of the time.
Here's the key insight from the article: "Processing the input file in parallel provides a huge win over r1, taking the time from 1 minute 45 seconds to 24.3 seconds. For comparison, the previous “optimised non-parallel” version, solution 7, took 25.8 seconds. So for this case, parallelisation is a bit faster than optimisation – and quite a bit simpler."
$ time ./t
Hello, world
real 0m0.003sIt is Java entry because language used is Java but finally compiled artifact is far far away from typical compiled Java artifact.
I don’t understand how this is possible. The file in question has 13GB, while the fastest commonly available SSDs are 12400 MB/s. Am I missing something?
What if the method of access was concurrent from different parts of the file, and was operating system cached?
>Note that that’s a best-of-five measurement, so I’m allowing the file to be cached. Who knows whether Linux will allow all 13GB to be kept in disk cache, though presumably it does, because the first time it took closer to 6 seconds.
I submitted a github issue on this for the other implementation I looked at here[1].
How do you search in the lookup table? If you are thinking of a hash map it will be slower than the few operations of his custom parser.
For example, you could find whether it starts with a '-' and where the delimiter is to know the length of the number string representation (that's the "simpler parsing" part), and then don't do any work at all to decode the number, simply use these 1-5 bytes of that string (without sign and separator) directly as an index into a very large very sparse memory region in which all the valid values are pre-populated with the proper result.
You'd need to allocate 4 or 8 terabytes of virtual memory address space for that lookup table, but you'll touch only a tiny fraction of the memory pages, so it doesn't require an unacceptable amount of physical memory.
0: https://github.com/k0nserv/brc/blob/main/src/main.rs#L279
00.1
-10.3
0.1 (with an ending space)
The idea would be, you have a tree of all values of 0.0 to 99.9 and then just use the bytes to iterate the tree (e.g. in an array) to come up with the int value of e.g. 45.5
Had to parse csvs in Java on a very memory constrained system once... we ended up cutting out a feature because it wasn't worth it.
> Depends on which Java implementation is used.
... if you have a choice. It was a port of AOSP, so we didn't. In any case it wasn't the jvm's fault, the device just had very little ram.
People keep forgetting Java is like C and C++, plenty of implementations to choose from, each with its own approach to JIT, AOT, GC and escape analysis.
“Very memory constrained” would be a massive factor here, 1BRC is not really constrained (let alone very much so), it has 1 billion rows on a 32GB machine.
Anyway, it's just a fun memory now.
~~Using LLVM isn’t a magic solution to perform better than something relying on the JVM.~~
Here is a source: https://sites.google.com/view/energy-efficiency-languages
I am curious, can it be made even faster than this?
.NET team has been doubling down on performance improvements, people forget CLR also has features to support C like languages (hence Managed C++ and C++/CLI), and many of those capabilities are now surfaced into C# as well.
[1] https://devblogs.microsoft.com/dotnet/performance-improvemen...
A few highlights, as can be seen in some of the blog posts mentioned by other replies:
- 'Span<T>' to represent chunks of either managed OR unmanaged memory without using unsafe pointers throughout [0][1]
- Not relevant to this task necessarily, but a lot of machinery has been added to allow reuse of objects for tasks like queuing thread pool work, or waiting for an asynchronous result.
- Lots of intrinsics helpers for SIMD workloads, and increased usage of such intrinsics in internal parsers/etc.
- Generally improving a lot of the internal IO to take advantage of other improvements in the runtime.
- PGO (Performance Guided Optimization) on the JIT side, essentially helps with things like better devirt [2] and other improvements.
- AOT compilation, if that's your thing, (I do believe the fastest C# 1BRC submissions use this)
[0] - To be clear, unsafe can still be faster, however for most cases Span is fine and gives you a little more runtime safety.
[1] - You can also grab a Span<T> of a primitive (i.e. int, char) within a method, so long as you don't blow up stack, this is very nice when you need a small buffer for parsing but don't want to thrash the GC or deal with volatile or locks on some sort of pool.
[2] - Devirt historically was a problem in 'call heavy' .NET apps when Interfaces are used, before PGO there was more than one library I worked on where we intentionally used abstract base classes rather than interfaces due to the need to squeeze as much out as we could.
But I believe looking at this like I do is wrong because they all run on different machines with different performances.
1. https://github.com/gunnarmorling/1brc/discussions/251#discus...
2. https://github.com/gunnarmorling/1brc/discussions/241#discus...
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.
Thus a slower but more robust solution would be more realistic.
one thing that i caught there was that parquet serves the same purpose as CSV but for much bigger datasets and now i want to learn more about it.
I’ll give this example in Ruby but you’ll get the point, what you are mentioning is an issue if you chose to use File.read(), because it opens the file and reads its content into the ram. But this can be solved if you use File.readlines() because it streams each row instead which uses much less ram.
Worst case scenario for RAM would be if each line contained a unique station. In this case we'd have to allocate 1_000_000_000 * sizeof(stats) in RAM to contain the result of the computation.
So most of the solutions assume sufficient RAM ahead of reading the file.
In the first solution:
type stats struct { min, max, sum float64 count int64 }
would take up 32GB for the stats alone for all 1E9 stations, and that's ignoring space needed for each station's name!
Also, even for this, original problem statement sets maximum to 10,000 different station names.
I struggle a lot with this toy problem. Without constraints too trivial to pay attention to; then no one seems to agree on potential real-world constraints (stdlib only? no mmaps?).
If we have to solve just this problem as is, shouldn't we be timing simple solutions using various frameworks (polars, pandas, spark, bigquery[^1], go, awk) to compare various frameworks? Once you have the answer, why would you try to get the same answer again but in 4 seconds the second time round?
Comparing frameworks would at least indicate if a data practitioner should upskill and pick up yet another data framework.
[^1]: https://medium.com/@shuvro_25220/the-one-billion-rows-challe...
This is the biggest take-away from this post to be honest; had no idea it could do anything like that. Sometimes it's the little things...
You can get something similar with the CLI using:
go tool pprof -weblist='mypkgname' cpu.out # Generate HTML and open
go tool pprof -list='mypkgname' cpu.out # Generate text to stdoutEDIT: https://github.com/Butch78/1BillionRowChallenge/tree/main
I encourage implementing maps and other DS btw, i was just curious
Solution 7 contains the code and description for the custom hash table.
I can see where interleaving/inlining the hash generation of the station name/key with the search for the separator reduces the number of scans of bytes from 2-3x to just 1x.
The second point in Solution 7 was the use of the byte slice to the underlying buffer when the station name is found in the buffer instead of creating a new string. This saves a memory allocation.
The author's naive single-threaded Go solution took 1m45s on an "amd64 laptop with fast SSD drive and 32GB of RAM."
So, you'd need something 25x faster than his setup in terms of single-threaded performance. Let us know when you've upgraded your hardware to the equivalent of a 75ghz AMD processor with memory and SSD bandwidth to match!
GPUs aren't magic. You still need to come up with a parallelizable algorithm.
The TL;DR is that the fastest solutions are basically map/reduce with a bunch of microoptimizations for parsing each line.
But before you do that, you need to divide up the work. You can't just give each core `file_size_bytes/core_count` chunks of the file because those chunks won't align with the line breaks. So, you need to be clever about that part somehow.
Once you've done that, you have a nice map/reduce that should scale linearly up to at least 20 or 30 cores. So in that sense, you can "throw hardware at it."
Whether or not any of that is a good fit for GPU acceleration, I don't know.
You should try the challenge. It's trickier than you think but surprisingly fun.
You may enjoy this talk where I do just that... end-to-end on GPUs, and < 100loc Python: https://www.youtube.com/watch?v=8ZMzsTbfImU
Your intuition about mapping to kernels is good. Basically all SQL, Polars, DuckDB, Pandas, etc operators are pretty directly mappable to optimized GPU operators nowadays. This includes GPU-accelerated CSV/parquet parsing. This was theoretically true starting maybe 10 years ago, and implemented in practice about 3-5 years ago. These systems allow escape hatches via numbajit etc to do custom kernels, but it's better to stay in pure sql/pandas/etc subsets, which are already mapped and to more careful kernels.
To get a feel for times, I like to think about 2 classes: constant overheads and throughput
Constant overhead:
- JIT'ing. By using pure SQL/pandas/etc, you can avoid most CUDA JIT costs
- GPU context creation etc: Similar, after starting and initial memory pool is allocated, it gets reused
- Instruction passing: The pandas API is 'eager', so "df1() + df2()" may have a lot of back-and-forth of instructions between CPU<>GPU even if the data doesn't move. Dask & Polars introduce lazy semantics that allow fusion, but GPU implementations haven't leveraged that yet AFAICT.
Bandwith limits:
- SSD is the biggest killer. Even "Expensive" SSDs are still < 10GB/s, so you need to chain a bunch to get 100B/s ingest
- CPU pathways throttle things down again (latency+bandwidth): GDS/GDN lets you skip them
- PCIe cards are surprisingly fast nowadays. With PCIe5+, the bottleneck is getting pushed quickly back to the storage, and probably easier to buy more PCIe+GPU pairs than need individual to go faster for most workloads
- Once things hit the GPU, things are fast :)
4s is a LOT of time wrt what even commodity GPU hardware can do, so benchmarks showing software failing to saturate it is fascinating to diagnose
I also apologize. As you can probably tell, I lumped you in with all the folks who were being super glib about easy hardware gains!
There aren't any generally-available CPUs that are substantially faster today than were available ten years ago. Maybe double the speed per core, triple at best.
After that, throwing more cores at it also rapidly runs out of steam because parallel code has its own overheads. Any shared state instantly kills performance, no matter the language. Very clever tricks have to be used to get decent scaling past 64 hardware threads (32 cores), and going past 256 is surprisingly difficult. You start having to worry about NUMA, IRQ steering, and core pinning. Bandwidth gets to be an issue, even to L3 and L4 cache, let alone out to main memory.
This notion that you can just "dial up" hardware performance to infinity as a fix for any amount of developer laziness needs to die.
And yet, this is something that can be trivially done in C#, C++ and Rust (albeit C# has the best UX with crossplat SIMD API introduced in .NET 7, with C++ close second with its own take on this being in preview). Java OTOH manages to be in the same category by having extremely advanced JIT that allows it to have comparable codegen quality even though it lacks comparable SIMD API for now (Panama vectors are problematic currently), so benchmarks implementations using it are forced to do SWAR.
My main gripe is of course an extremely common misconception about Go's speed which it just does not have the moment you write anything sufficiently advanced or want to express a particular problem in a terser way than writing thousands of open coded loops.