9 ms·

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

499 points by nalgeon 3y ago

avinassh 3y ago
> 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. I am curious, can it be made even faster than this?
- makotech221 3y ago
  Dunno about Go, but most c# solutions are around 2s and under https://hotforknowledge.com/2024/01/13/1brc-in-dotnet-among-fastest-on-linux-my-optimization-journey/#results https://hotforknowledge.com/2024/01/13/1brc-in-dotnet-among-...
  - junto 3y ago
    Wow that’s pretty damn fast. C# has made some improvements in the past years or they have some other advantages?
    - pjmlp 3y ago
      Yes to both. .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.
    - Anon4Now 3y ago
      Stephen Toub wrote a book-length blog post about all the performance improvements made in .NET 8 [1]. Add the option to compile to native. [1] https://devblogs.microsoft.com/dotnet/performance-improvements-in-net-8/ https://devblogs.microsoft.com/dotnet/performance-improvemen...
      - pjmlp 3y ago
        His blogs posts go back all the way to .NET 5, for those curious to some deep dive on performance improvements done on each release.
    - to11mtm 3y ago
      Yeah. 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.
- krallja 3y ago
  There's a layer of pointer indirection when using slices in Go, you may be able to eke out some time by moving to arrays on the stack.
- pram 3y ago
  From looking at the final code it’s probably the performance of copy() as the biggest hurdle.
- scotty79 3y ago
  Instead of hash table I'd try sort of "eager" trie inside stack allocated memory. So I can find the slot for the stats of given station after parsing minimal number of characters that differentiate this station from others.
jonahx 3y ago
Nice post. Interesting that the fastest Java beats the fastest Go, though they are close: AY fastest Go version 2.90s 36.2 TW fastest Java version 0.953s 110 I would have expected Go to win. That JVM works pretty good...
- dsff3f3f3f 3y ago
  The Java version does additional optimizations that his Go version doesn't do and he mentions that at the end of the post. The Java version is really optimized and is an interesting read.
  - avinassh 3y ago
    > The Java version is really optimized and is an interesting read. is there any similar blog post on the Java optimisations?
    - dsff3f3f3f 3y ago
      Not that I know of. I just looked at the code and the commit history but a more in depth article would certainly be interesting.
    - o11c 3y ago
      https://news.ycombinator.com/item?id=39467885 https://news.ycombinator.com/item?id=39467885 but it looks like there have been improvements since.
    - cempaka 3y ago
      Cliff Click did a walkthrough of his solution on YouTube: https://youtu.be/NJNIbgV6j-Y?si=Wj97f-Imw5nfIzF7 https://youtu.be/NJNIbgV6j-Y?si=Wj97f-Imw5nfIzF7
    - lucianbr 3y ago
      https://questdb.io/blog/billion-row-challenge-step-by-step/ https://questdb.io/blog/billion-row-challenge-step-by-step/
  - 3y ago
tonymet 3y ago
i saw the custom hashtable, but why was Map slow?
- sethammons 3y ago
  I believe it is because he did not pre allocate the map, so as it grew, it reallocated multiple times. Just a guess.
  - tonymet 3y ago
    I double checked and he mentioned a couple other points. One was incrementally hashing the keys to reduce double read. The other was about storing pointers for the value structs more efficiently. I encourage implementing maps and other DS btw, i was just curious
    - canucker2016 3y ago
      The authour has already converted the code to using a pointer to value struct for storing in the standard go hash table in Solution 2. 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.
bbkane 3y ago
I found this super interesting - especially as all the data I've written code to manipulate has been small enough that I haven't needed to optimize my code, so I've never had to think in this direction. 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".
- latchkey 3y ago
  I hate to "me too", but you also nailed that analysis.
  - yau8edq12i 3y ago
    [flagged]
- timetopay 3y ago
  A few months ago, I had to quickly bang out a script to output about 20 million lines of text, each the output of a hash function. My naive solution took more than a few minutes - simple optimizations such as writing every 10k lines cut the time significantly. Threading would have helped quite a bit as well.
- jasonwatkinspdx 3y ago
  It also underscores just how insane raw disk bandwidth is on modern ssds. Most software is not designed around a world where you have gigabytes a second of sequential scan on a laptop.
  - walth 3y ago
    I believe this test is run several times and the data set fits in page cache.
    - deleted 3y ago
      [deleted]
JensRantil 3y ago
Second article I'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. I submitted a github issue on this for the other implementation I looked at here[1]. [1] https://github.com/shraddhaag/1brc/issues/2 https://github.com/shraddhaag/1brc/issues/2
- pillusmany 3y ago
  He already uses custom parsing. 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.
  - treyd 3y ago
    If you're clever about how you initially take apart the input you can just do a single memory load at a computed offset.
    - praptak 3y ago
      I don't see how you can make computing the offset faster than just parsing the number.
      - PeterisP 3y ago
        You could have a much simpler parsing than ordinary parsing if you know/assume that you definitely have a valid number from -99.99 to 99.99. 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.
m3kw9 3y ago
I’d just pay my way to 4s by upgrading hw
- JohnBooty 3y ago
  You can't just throw hardware at this one to get to 4s. At least not in 2024. 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!
  - lmeyerov 3y ago
    The nice thing about a GPU soln (ex: python dataframes in cudf, just a few loc) is these generally come down to your IO bandwidth, like a single 2GB/s SSD to a 16-32 GB/s PCIe to 1-2 GPUs running crazy fast. And then buy more cheap SSDs to chain together before buying more/better GPUs :)
    - JohnBooty 3y ago
      I guess it depends on what we mean by "throwing hardware at it." 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.
      - lmeyerov 3y ago
        Indeed! 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 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
nicois 3y ago
It would be interesting to know how effective Profile Guided Optimisation is here.
- neonsunset 3y ago
  It is only mildly effective because how anemic Go compiler is. And even then it's extremely limited. If you want to see actual good implementations - look into what OpenJDK HotSpot and .NET JIT compilers do with runtime profiling and recompilation (.NET calls it Dynamic PGO).
- benhoyt 3y ago
  Unfortunately it doesn't seem to help at all, I think mainly because (at present) Go's PGO basically inlines hot functions, and the important code here is all in one big function.
neonsunset 3y ago
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.
- donor20 3y ago
  But isn’t the Java version unrolling loops? This seems like some effort on the Java side.
  - dsff3f3f3f 3y ago
    The fast Java version is using all the same optimizations as this Go version and then some. It's significantly more complicated.
- Mawr 3y ago
  That you put Rust among those languages says it all. Do some basic research.
  - neonsunset 3y ago
    Oh, and what the basic research you speak of constitutes? Surely you looked at ASM emitted by compilers for these languages and HPC-adjacent APIs each of them offers? No? Then let me tell you - Go is pretty much consigned to having to use its special flavour of non-portable bespoke hand-written ASM which is the only way to access SIMD instructions necessary to achieve optimal hardware utilization in the benchmark. This takes a lot of effort and skill, so, as you may have noticed, if you can't do it, Go simply cannot come close to better options you can see on the benchmark chart. 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.
nottorp 3y ago
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. 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.
- cangeroo 3y ago
  Regarding Java, It probably could be done with arrays and object reuse (arenas). But it's slightly less ergonomic. And the ecosystem isn't designed for it, so you'd have to implement your own memory-efficient parser.
  - nottorp 3y ago
    Yep, but it wasn't a critical feature and we were in a rush, so the feature was killed instead. > 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.
    - syspec 3y ago
      Sounds like a skill issue
- pjmlp 3y ago
  Depends on which Java implementation is used. 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.
- masklinn 3y ago
  Depends what you call “naive”, but the “idiomatic Java solution” from last week’s post (https://questdb.io/blog/billion-row-challenge-step-by-step/ https://questdb.io/blog/billion-row-challenge-step-by-step/) clocked in at 71 seconds, or 1:11. And just running it on graal was down to 66. “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.
thangalin 3y ago
Back in 2010, I used PostgreSQL for a web app that queried 270 million rows of climate data from Environment Canada: https://www.youtube.com/watch?v=10KEr3sEG80 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 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.
- heavenlyblue 3y ago
  [flagged]
faizshah 3y ago
I was curious how long it would take with Polars (for scale), apparently 33s: https://github.com/Butch78/1BillionRowChallenge/tree/main https://github.com/Butch78/1BillionRowChallenge/tree/main 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?
- sharno 3y ago
  That’s the question worth asking imo. I was wondering how fast is the idiomatic Java solution
  - lucianbr 3y ago
    71 seconds https://questdb.io/blog/billion-row-challenge-step-by-step/ https://questdb.io/blog/billion-row-challenge-step-by-step/
    - kaba0 3y ago
      Is that the same hardware? Otherwise it doesn’t say much.
  - KingOfCoders 3y ago
    Java is often slightly faster than Go, has similar (perhaps, older, better optimized Map) constructs, perhaps better GC (older, more optimized), though I don't think the GC is a challenge, has slower startup times - so I'd say roughly the same as the idiomatic Go version?
    - kaba0 3y ago
      Java’s GC is just incomparably better, literally every research on the topic is written for Java. Though that’s true that without value types, Java does rely slightly more on it.
      - geodel 3y ago
michae2 3y ago
For anyone looking for more examples of 1BRC in Go, we had a friendly competition at work and collected the results here: https://github.com/dhartunian/1brcgo/ https://github.com/dhartunian/1brcgo/ 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)
- benhoyt 3y ago
  Oh, I'd missed those solutions, thanks. You guys got way more hard core than I did -- nice work! Looking forward to reading the code for those solutions this week. Update: for reference, Jason Chu's solution (https://github.com/dhartunian/1brcgo/blob/494eabd6ea958cc193648fe34859ac53d86c8743/jason.go https://github.com/dhartunian/1brcgo/blob/494eabd6ea958cc193...) seems to be the fastest on my machine, and runs in about 1.3s!
  - michae2 3y ago
    I think we all ended up using unsafe, though there were some solutions without mmap. It would have been interesting if we had adhered to the same constraints you did!
  - markoman 3y ago
    Could you say why you find using memory-mapped files to be a portability issue? Thanks.
    - benhoyt 3y ago
      Well, I guess it's more that the standard library doesn't have a cross-platform way to access them, not that memory-mapped files themselves can't be done on (say) Windows. It looks like there's a fairly popular 3rd party package that supports at least Linux, macOS, and Windows: https://github.com/edsrzf/mmap-go https://github.com/edsrzf/mmap-go
fizx 3y ago
It's worth noting that if you'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. I'm pretty confident adding LC_ALL=C to the awk solution would get it easily under a minute.
- benhoyt 3y ago
  It's a good point, but I believe because of the "-b" option (characters as bytes), using LC_ALL=C doesn't make a difference.
1vuio0pswjnm7 3y ago
How about kdb+ or shakti
deleted 3y ago
[deleted]
afiodorov 3y ago
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's a bad assumption when dealing with a lot of data.
- masklinn 3y ago
  This is not a general solution, it’s a specific problem with a specific data shape, and processes specifically 1 billion rows on a 32GB machine.
  - pletnes 3y ago
    And this is why file io is not the bottleneck - all the data is in RAM/disk cache.
- Alifatisk 3y ago
  > A lot of the solutions assume we have enough ram to keep the stats per station 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.
  - afiodorov 3y ago
    What I am saying is that the solutions presented assume we have N stations which are way less than 1_000_000_000. 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!
    - blackoil 3y ago
blue_pants 3y ago
There's a nodejs version which takes 23s https://github.com/1brc/nodejs https://github.com/1brc/nodejs
- Alifatisk 3y ago
  How come node performed this good? Any specific reason?
  - saagarjha 3y ago
    https://github.com/1brc/nodejs/tree/main/src/main/nodejs/Edgar-P-yan https://github.com/1brc/nodejs/tree/main/src/main/nodejs/Edg... has a few
twophotocollage 3y ago
[flagged]
satvikpendem 3y ago
Nice. I wonder how Rust would fare, given that it has no garbage collector.
- tjpnz 3y ago
  You can disable GC for Golang but don't think it will improve on 4s.
- n8henrie 3y ago
  There are a few rust solutions in the "Show and Tell" linked above, for example this fairly readable one at 15.5s: https://github.com/gunnarmorling/1brc/discussions/57 https://github.com/gunnarmorling/1brc/discussions/57 A comment above referencing Python "polars" actually has rust polars, std, and SIMD solutions as well (SIMD was fasted, but less readable for a hobbyist like me). EDIT: https://github.com/Butch78/1BillionRowChallenge/tree/main https://github.com/Butch78/1BillionRowChallenge/tree/main
camgunz 3y ago
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! 0: https://geraldonit.com/2024/01/31/1-billion-row-challenge-in-sql-and-oracle-database/ https://geraldonit.com/2024/01/31/1-billion-row-challenge-in...
- riku_iki 3y ago
  actually that guy can now be sued, per TOS it is illegal to publish benchmarks for Oracle DB.
  - Rexxar 3y ago
    I'm not sure this part of the TOS is valid in many jurisdictions. But there is a better reason to not publish benchmarks: they do not deserve free advertisement. We should just collectively forget they exist and use other tools.
    - riku_iki 3y ago
      which corp is considered to be good now days?..
      - christophilus 3y ago
        Umbrella Corp.
- giantrobot 3y ago
  I agree with doing more in the database, you're closer to the data (disk/disk cache/L2 cache) than the application code is. At the same time I get really nervous around doing work in the database because you have to be really disciplined that the in-database code (functions, views, etc) match the code in source control. Also that your testing/QA database contains all the same code and enough test data to actually exercise the performance bounds of that code. 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.
sireat 3y ago
Those super optimized solutions are fun to read about. 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.
michalsustr 3y ago
> the fastest, heavily-optimised Java solution runs in just under a second on my machine 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?
- gozzoo 3y ago
  most of the file remains in the OS disk cache after the first run
- whyever 3y ago
  My guess: If you run the benchmark several times, the OS will cache the file in RAM.
- dietr1ch 3y ago
  Benchmarking this gets tricky once you realize that the file might be entirely cached if the computer has enough RAM.
  - deleted 3y ago
    [deleted]
  - klyrs 3y ago
    Hah, we use different computers. I was thinking, this might be tricky if you aren't careful to keep the file entirely cached in RAM.
- chii 3y ago
  that might be a sustained single threaded read performance. What if the method of access was concurrent from different parts of the file, and was operating system cached?
- mainde 3y ago
  I think this bit in the baseline section applies to the Java one too >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.
fullstackchris 3y ago
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?
WesolyKubeczek 3y ago
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.
hoten 3y ago
> 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! 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.
- benhoyt 3y ago
  Yeah, someone emailed me privately after they'd dug into this. They mentioned that "items[hashIndex]" was a significant source of cache misses. They used "perf record -e cache-misses" and found it was the largest source of cache misses. They also found (by digging into the assembly) that the "bytes.Equal" line has some sort of source-line attribution issue.
worldwidelies 3y ago
I’d like to see a 1 trillion row challenge.
- tbragin 3y ago
  One exists https://blog.coiled.io/blog/1trc.html https://blog.coiled.io/blog/1trc.html
  - genewitch 3y ago
    five minutes! with some silliness groupby("name").agg(the math stuff). So their testbed (coiled, a cluster manager?) is meant to do exactly what the challenge requires. and it was data out of S3. 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.
deleted 3y ago
[deleted]
deleted 3y ago
[deleted]
Alifatisk 3y ago
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.
- gunnarmorling 3y ago
  There's the "Show & Tell", where folks have shared implementations in many different languages: https://github.com/gunnarmorling/1brc/discussions/categories/show-and-tell https://github.com/gunnarmorling/1brc/discussions/categories....
- ayewo 3y ago
  You could also view attempts in other languages at https://github.com/1brc https://github.com/1brc
  - mik09 3y ago
    c dominates every other language again...https://github.com/dannyvankooten/1brc#submitting https://github.com/dannyvankooten/1brc#submitting
    - Alifatisk 3y ago
      The C implementation runs in ~1.7 seconds, but so does Swift [1]. The Dart [2] implementation achieved 1.17 seconds, but the record now looks to be ~0.57 seconds [3]. 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#discussion-6045429 https://github.com/gunnarmorling/1brc/discussions/251#discus... 2. https://github.com/gunnarmorling/1brc/discussions/241#discussioncomment-8067373 https://github.com/gunnarmorling/1brc/discussions/241#discus... 3. https://github.com/gunnarmorling/1brc/discussions/710 https://github.com/gunnarmorling/1brc/discussions/710
verytrivial 3y ago
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.
Beltalowda 3y ago
How did you generate the timings on: https://benhoyt.com/images/go-1brc-profile-r9-source.png https://benhoyt.com/images/go-1brc-profile-r9-source.png ?
- benhoyt 3y ago
  Using Go's profiling tool with its "source" view: I used "go tool pprof -http=: cpu.prof", where cpu.prof was generated by "go-1brc -cpuprofile=cpu.prof -revision=9 measurements.txt".
  - Beltalowda 3y ago
    Cheers; I've always difficulty mapping those pprof graphs to actual concrete code and I never managed to get anything more useful out of it. 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 stdout
CyanLite2 3y ago
Meanwhile the C# (.net) implementation is 4x faster.
mohamedattahri 3y ago
There’s something cool about the fact that parallel code in Go is still idiomatic Go.
llmblockchain 3y ago
One "trick" 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).

499 points by nalgeon 3y ago

> 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. I am curious, can it be made even faster than this?

makotech221 3y ago
Dunno about Go, but most c# solutions are around 2s and under https://hotforknowledge.com/2024/01/13/1brc-in-dotnet-among-fastest-on-linux-my-optimization-journey/#results https://hotforknowledge.com/2024/01/13/1brc-in-dotnet-among-...
- junto 3y ago
  Wow that’s pretty damn fast. C# has made some improvements in the past years or they have some other advantages?
  - pjmlp 3y ago
    Yes to both. .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.
  - Anon4Now 3y ago
    Stephen Toub wrote a book-length blog post about all the performance improvements made in .NET 8 [1]. Add the option to compile to native. [1] https://devblogs.microsoft.com/dotnet/performance-improvements-in-net-8/ https://devblogs.microsoft.com/dotnet/performance-improvemen...
    - pjmlp 3y ago
      His blogs posts go back all the way to .NET 5, for those curious to some deep dive on performance improvements done on each release.
  - to11mtm 3y ago
    Yeah. 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.
krallja 3y ago
There's a layer of pointer indirection when using slices in Go, you may be able to eke out some time by moving to arrays on the stack.
pram 3y ago
From looking at the final code it’s probably the performance of copy() as the biggest hurdle.
scotty79 3y ago
Instead of hash table I'd try sort of "eager" trie inside stack allocated memory. So I can find the slot for the stats of given station after parsing minimal number of characters that differentiate this station from others.

jonahx 3y ago

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

dsff3f3f3f 3y ago
The Java version does additional optimizations that his Go version doesn't do and he mentions that at the end of the post. The Java version is really optimized and is an interesting read.
- avinassh 3y ago
  > The Java version is really optimized and is an interesting read. is there any similar blog post on the Java optimisations?
  - dsff3f3f3f 3y ago
    Not that I know of. I just looked at the code and the commit history but a more in depth article would certainly be interesting.
  - o11c 3y ago
    https://news.ycombinator.com/item?id=39467885 https://news.ycombinator.com/item?id=39467885 but it looks like there have been improvements since.
  - cempaka 3y ago
    Cliff Click did a walkthrough of his solution on YouTube: https://youtu.be/NJNIbgV6j-Y?si=Wj97f-Imw5nfIzF7 https://youtu.be/NJNIbgV6j-Y?si=Wj97f-Imw5nfIzF7
  - lucianbr 3y ago
    https://questdb.io/blog/billion-row-challenge-step-by-step/ https://questdb.io/blog/billion-row-challenge-step-by-step/
- 3y ago

tonymet 3y ago

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

sethammons 3y ago
I believe it is because he did not pre allocate the map, so as it grew, it reallocated multiple times. Just a guess.
- tonymet 3y ago
  I double checked and he mentioned a couple other points. One was incrementally hashing the keys to reduce double read. The other was about storing pointers for the value structs more efficiently. I encourage implementing maps and other DS btw, i was just curious
  - canucker2016 3y ago
    The authour has already converted the code to using a pointer to value struct for storing in the standard go hash table in Solution 2. 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.

bbkane 3y ago

I found this super interesting - especially as all the data I've written code to manipulate has been small enough that I haven't needed to optimize my code, so I've never had to think in this direction. 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".

latchkey 3y ago
I hate to "me too", but you also nailed that analysis.
- yau8edq12i 3y ago
  [flagged]
timetopay 3y ago
A few months ago, I had to quickly bang out a script to output about 20 million lines of text, each the output of a hash function. My naive solution took more than a few minutes - simple optimizations such as writing every 10k lines cut the time significantly. Threading would have helped quite a bit as well.
jasonwatkinspdx 3y ago
It also underscores just how insane raw disk bandwidth is on modern ssds. Most software is not designed around a world where you have gigabytes a second of sequential scan on a laptop.
- walth 3y ago
  I believe this test is run several times and the data set fits in page cache.
  - deleted 3y ago
    [deleted]

JensRantil 3y ago

Second article I'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. I submitted a github issue on this for the other implementation I looked at here[1]. [1] https://github.com/shraddhaag/1brc/issues/2 https://github.com/shraddhaag/1brc/issues/2

pillusmany 3y ago
He already uses custom parsing. 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.
- treyd 3y ago
  If you're clever about how you initially take apart the input you can just do a single memory load at a computed offset.
  - praptak 3y ago
    I don't see how you can make computing the offset faster than just parsing the number.
    - PeterisP 3y ago
      You could have a much simpler parsing than ordinary parsing if you know/assume that you definitely have a valid number from -99.99 to 99.99. 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.

m3kw9 3y ago

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

JohnBooty 3y ago
You can't just throw hardware at this one to get to 4s. At least not in 2024. 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!
- lmeyerov 3y ago
  The nice thing about a GPU soln (ex: python dataframes in cudf, just a few loc) is these generally come down to your IO bandwidth, like a single 2GB/s SSD to a 16-32 GB/s PCIe to 1-2 GPUs running crazy fast. And then buy more cheap SSDs to chain together before buying more/better GPUs :)
  - JohnBooty 3y ago
    I guess it depends on what we mean by "throwing hardware at it." 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.
    - lmeyerov 3y ago
      Indeed! 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 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

nicois 3y ago

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

neonsunset 3y ago
It is only mildly effective because how anemic Go compiler is. And even then it's extremely limited. If you want to see actual good implementations - look into what OpenJDK HotSpot and .NET JIT compilers do with runtime profiling and recompilation (.NET calls it Dynamic PGO).
benhoyt 3y ago
Unfortunately it doesn't seem to help at all, I think mainly because (at present) Go's PGO basically inlines hot functions, and the important code here is all in one big function.

neonsunset 3y ago

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.

donor20 3y ago
But isn’t the Java version unrolling loops? This seems like some effort on the Java side.
- dsff3f3f3f 3y ago
  The fast Java version is using all the same optimizations as this Go version and then some. It's significantly more complicated.
Mawr 3y ago
That you put Rust among those languages says it all. Do some basic research.
- neonsunset 3y ago
  Oh, and what the basic research you speak of constitutes? Surely you looked at ASM emitted by compilers for these languages and HPC-adjacent APIs each of them offers? No? Then let me tell you - Go is pretty much consigned to having to use its special flavour of non-portable bespoke hand-written ASM which is the only way to access SIMD instructions necessary to achieve optimal hardware utilization in the benchmark. This takes a lot of effort and skill, so, as you may have noticed, if you can't do it, Go simply cannot come close to better options you can see on the benchmark chart. 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.

nottorp 3y ago

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. 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.

cangeroo 3y ago
Regarding Java, It probably could be done with arrays and object reuse (arenas). But it's slightly less ergonomic. And the ecosystem isn't designed for it, so you'd have to implement your own memory-efficient parser.
- nottorp 3y ago
  Yep, but it wasn't a critical feature and we were in a rush, so the feature was killed instead. > 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.
  - syspec 3y ago
    Sounds like a skill issue
pjmlp 3y ago
Depends on which Java implementation is used. 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.
masklinn 3y ago
Depends what you call “naive”, but the “idiomatic Java solution” from last week’s post (https://questdb.io/blog/billion-row-challenge-step-by-step/ https://questdb.io/blog/billion-row-challenge-step-by-step/) clocked in at 71 seconds, or 1:11. And just running it on graal was down to 66. “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.

thangalin 3y ago

Back in 2010, I used PostgreSQL for a web app that queried 270 million rows of climate data from Environment Canada: https://www.youtube.com/watch?v=10KEr3sEG80 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 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.

heavenlyblue 3y ago
[flagged]

faizshah 3y ago

I was curious how long it would take with Polars (for scale), apparently 33s: https://github.com/Butch78/1BillionRowChallenge/tree/main https://github.com/Butch78/1BillionRowChallenge/tree/main 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?

sharno 3y ago
That’s the question worth asking imo. I was wondering how fast is the idiomatic Java solution
- lucianbr 3y ago
  71 seconds https://questdb.io/blog/billion-row-challenge-step-by-step/ https://questdb.io/blog/billion-row-challenge-step-by-step/
  - kaba0 3y ago
    Is that the same hardware? Otherwise it doesn’t say much.
- KingOfCoders 3y ago
  Java is often slightly faster than Go, has similar (perhaps, older, better optimized Map) constructs, perhaps better GC (older, more optimized), though I don't think the GC is a challenge, has slower startup times - so I'd say roughly the same as the idiomatic Go version?
  - kaba0 3y ago
    Java’s GC is just incomparably better, literally every research on the topic is written for Java. Though that’s true that without value types, Java does rely slightly more on it.
    - geodel 3y ago

michae2 3y ago

For anyone looking for more examples of 1BRC in Go, we had a friendly competition at work and collected the results here: https://github.com/dhartunian/1brcgo/ https://github.com/dhartunian/1brcgo/ 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)

benhoyt 3y ago
Oh, I'd missed those solutions, thanks. You guys got way more hard core than I did -- nice work! Looking forward to reading the code for those solutions this week. Update: for reference, Jason Chu's solution (https://github.com/dhartunian/1brcgo/blob/494eabd6ea958cc193648fe34859ac53d86c8743/jason.go https://github.com/dhartunian/1brcgo/blob/494eabd6ea958cc193...) seems to be the fastest on my machine, and runs in about 1.3s!
- michae2 3y ago
  I think we all ended up using unsafe, though there were some solutions without mmap. It would have been interesting if we had adhered to the same constraints you did!
- markoman 3y ago
  Could you say why you find using memory-mapped files to be a portability issue? Thanks.
  - benhoyt 3y ago
    Well, I guess it's more that the standard library doesn't have a cross-platform way to access them, not that memory-mapped files themselves can't be done on (say) Windows. It looks like there's a fairly popular 3rd party package that supports at least Linux, macOS, and Windows: https://github.com/edsrzf/mmap-go https://github.com/edsrzf/mmap-go

fizx 3y ago

It's worth noting that if you'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. I'm pretty confident adding LC_ALL=C to the awk solution would get it easily under a minute.

benhoyt 3y ago
It's a good point, but I believe because of the "-b" option (characters as bytes), using LC_ALL=C doesn't make a difference.

1vuio0pswjnm7 3y ago

How about kdb+ or shakti

deleted 3y ago

[deleted]

afiodorov 3y ago

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's a bad assumption when dealing with a lot of data.

masklinn 3y ago
This is not a general solution, it’s a specific problem with a specific data shape, and processes specifically 1 billion rows on a 32GB machine.
- pletnes 3y ago
  And this is why file io is not the bottleneck - all the data is in RAM/disk cache.
Alifatisk 3y ago
> A lot of the solutions assume we have enough ram to keep the stats per station 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.
- afiodorov 3y ago
  What I am saying is that the solutions presented assume we have N stations which are way less than 1_000_000_000. 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!
  - blackoil 3y ago

blue_pants 3y ago

There's a nodejs version which takes 23s https://github.com/1brc/nodejs https://github.com/1brc/nodejs

Alifatisk 3y ago
How come node performed this good? Any specific reason?
- saagarjha 3y ago
  https://github.com/1brc/nodejs/tree/main/src/main/nodejs/Edgar-P-yan https://github.com/1brc/nodejs/tree/main/src/main/nodejs/Edg... has a few

twophotocollage 3y ago

[flagged]

satvikpendem 3y ago

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

tjpnz 3y ago
You can disable GC for Golang but don't think it will improve on 4s.
n8henrie 3y ago
There are a few rust solutions in the "Show and Tell" linked above, for example this fairly readable one at 15.5s: https://github.com/gunnarmorling/1brc/discussions/57 https://github.com/gunnarmorling/1brc/discussions/57 A comment above referencing Python "polars" actually has rust polars, std, and SIMD solutions as well (SIMD was fasted, but less readable for a hobbyist like me). EDIT: https://github.com/Butch78/1BillionRowChallenge/tree/main https://github.com/Butch78/1BillionRowChallenge/tree/main

camgunz 3y ago

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! 0: https://geraldonit.com/2024/01/31/1-billion-row-challenge-in-sql-and-oracle-database/ https://geraldonit.com/2024/01/31/1-billion-row-challenge-in...

riku_iki 3y ago
actually that guy can now be sued, per TOS it is illegal to publish benchmarks for Oracle DB.
- Rexxar 3y ago
  I'm not sure this part of the TOS is valid in many jurisdictions. But there is a better reason to not publish benchmarks: they do not deserve free advertisement. We should just collectively forget they exist and use other tools.
  - riku_iki 3y ago
    which corp is considered to be good now days?..
    - christophilus 3y ago
      Umbrella Corp.
giantrobot 3y ago
I agree with doing more in the database, you're closer to the data (disk/disk cache/L2 cache) than the application code is. At the same time I get really nervous around doing work in the database because you have to be really disciplined that the in-database code (functions, views, etc) match the code in source control. Also that your testing/QA database contains all the same code and enough test data to actually exercise the performance bounds of that code. 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.

sireat 3y ago

Those super optimized solutions are fun to read about. 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.

michalsustr 3y ago

> the fastest, heavily-optimised Java solution runs in just under a second on my machine 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?

gozzoo 3y ago
most of the file remains in the OS disk cache after the first run
whyever 3y ago
My guess: If you run the benchmark several times, the OS will cache the file in RAM.
dietr1ch 3y ago
Benchmarking this gets tricky once you realize that the file might be entirely cached if the computer has enough RAM.
- deleted 3y ago
  [deleted]
- klyrs 3y ago
  Hah, we use different computers. I was thinking, this might be tricky if you aren't careful to keep the file entirely cached in RAM.
chii 3y ago
that might be a sustained single threaded read performance. What if the method of access was concurrent from different parts of the file, and was operating system cached?
mainde 3y ago
I think this bit in the baseline section applies to the Java one too >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.

fullstackchris 3y ago

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?

WesolyKubeczek 3y ago

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.

hoten 3y ago

> 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! 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.

benhoyt 3y ago
Yeah, someone emailed me privately after they'd dug into this. They mentioned that "items[hashIndex]" was a significant source of cache misses. They used "perf record -e cache-misses" and found it was the largest source of cache misses. They also found (by digging into the assembly) that the "bytes.Equal" line has some sort of source-line attribution issue.

worldwidelies 3y ago

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

tbragin 3y ago
One exists https://blog.coiled.io/blog/1trc.html https://blog.coiled.io/blog/1trc.html
- genewitch 3y ago
  five minutes! with some silliness groupby("name").agg(the math stuff). So their testbed (coiled, a cluster manager?) is meant to do exactly what the challenge requires. and it was data out of S3. 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.

deleted 3y ago

[deleted]

deleted 3y ago

[deleted]

Alifatisk 3y ago

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.

gunnarmorling 3y ago
There's the "Show & Tell", where folks have shared implementations in many different languages: https://github.com/gunnarmorling/1brc/discussions/categories/show-and-tell https://github.com/gunnarmorling/1brc/discussions/categories....
ayewo 3y ago
You could also view attempts in other languages at https://github.com/1brc https://github.com/1brc
- mik09 3y ago
  c dominates every other language again...https://github.com/dannyvankooten/1brc#submitting https://github.com/dannyvankooten/1brc#submitting
  - Alifatisk 3y ago
    The C implementation runs in ~1.7 seconds, but so does Swift [1]. The Dart [2] implementation achieved 1.17 seconds, but the record now looks to be ~0.57 seconds [3]. 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#discussion-6045429 https://github.com/gunnarmorling/1brc/discussions/251#discus... 2. https://github.com/gunnarmorling/1brc/discussions/241#discussioncomment-8067373 https://github.com/gunnarmorling/1brc/discussions/241#discus... 3. https://github.com/gunnarmorling/1brc/discussions/710 https://github.com/gunnarmorling/1brc/discussions/710

verytrivial 3y ago

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.

Beltalowda 3y ago

How did you generate the timings on: https://benhoyt.com/images/go-1brc-profile-r9-source.png https://benhoyt.com/images/go-1brc-profile-r9-source.png ?

benhoyt 3y ago
Using Go's profiling tool with its "source" view: I used "go tool pprof -http=: cpu.prof", where cpu.prof was generated by "go-1brc -cpuprofile=cpu.prof -revision=9 measurements.txt".
- Beltalowda 3y ago
  Cheers; I've always difficulty mapping those pprof graphs to actual concrete code and I never managed to get anything more useful out of it. 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 stdout

CyanLite2 3y ago

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

mohamedattahri 3y ago

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

llmblockchain 3y ago

One "trick" 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).