#1 Billion Row Challenge

20 messages · Page 1 of 1 (latest)

swift arch
#

This challenge has been doing the rounds recently: https://www.morling.dev/blog/one-billion-row-challenge/

(the criteria is for submissions in Java, but no harm in attempting it in Go 😉 )

I just wanted to ask for feedback from more experienced engineers about how you would approach optimising this using Go.

I have a basic/naive approach that tries to minimise allocations, but really it's just reading straight through the file and keeping the data in a map synchronously.

What would be a good way to leverage concurrency to speed this up?

From my understanding

  • you could perhaps use fixed worker pool of goroutines that can process the data as it comes off the file?

i'm just struggling with the best way to approach the problem and getting tripped up on my own feet trying to create some crazy ad-hoc concurrency patterns 🥴

The One Billion Row Challenge

Update Jan 4: Wow, this thing really took off!
1BRC is discussed at a couple of places on the internet, including Hacker News, lobste.rs, and Reddit.

For folks to show-case non-Java solutions, there is a "Show & Tell" now, check that one out for 1BRC implementations in Rust, Go, C++, and others.
Some interesting related write-ups include 1BRC...

#

ps my current execution time is 90 secs as a baseline if people wanted to have a go 😄

oblique linden
#

If you want something os agnostic I think you could get something drive bottlenecked by using two goroutines, both doing the processing but alternating the reads (so it's single threaded compute but with parallel double buffered input)

swift arch
#

thanks for the feedback really appreciate it 🙌 honestly most of that went over my head, but I will endeavour to read up on it all tomorrow and hack something together 😄

oblique linden
#

Actually I did the math and it's not as trivial as I made it sound

#

The TL;DR is how much do you think it takes to process one row ?
I think it should cost 50ns~250ns with a very optimized piece of code.
If one line is roughly 15bytes that 15bytes / 50ns = 300MB/s

#

So my guess was a bit off

#

300MB/s would saturate small cheap ssds and hdds but it's not easy to be drive saturated

#

so goroutines could be usefull to run compute on multiple cores.
The interesting thing with this approach is that the switching costs are significant, in the same order of magnitude as the cost to process a line, so you would need to read let's say 1MiB chunks in each goroutine so you do less switching, however then it's not likely the words will be alligned with the 1MiB chunks

swift arch
#

however then it's not likely the words will be alligned with the 1MiB chunks

yes this is kinda what i'm bumping up against, how is the best way to chunk it up Thinkfused

...but also as well I am quite early into learning about the concurrency primitives so i am tending to tie myself up in knots by either creating a deadlock, or simply just bamboozling myself 😄

if i run the file thru my machine (2021 MacBook pro M1 16GB) and literally just call scanner.Bytes on each line, it takes ~25 seconds to spin thru the file

oblique linden
#

how big is the file ?

swift arch
#

13.8GB

oblique linden
#

that .552GB/s

#

it's pretty good tbh

swift arch
#

aha yep, but then I add my 'magic' and we're up to about 90 seconds (so 150mb/s) 😅

oblique linden
#

terrible for readability, but you could inline the logic you need

swift arch
#

...just realised i am calculating the mean on every iteration, i need to sleep 😄