shraddhaag/1brc

Solution to One Billion Rows Challenge in Golang.

Hi, I'm Shraddha! 👋

A backend engineer working with distributed systems. I currently work at Hasura, designing, building and maintaining the APIs that power the company's Cloud product. I also write and speak occasionally about the work I am doing.

I am focused on writing software that isn’t a pain in the ass for the next person who works with it or rather less crudely put, is well tested, documented and observable. I believe user empathy is an important consideration while designing APIs. I try to stay away from premature optimisation and consider writing documentation as important as development.

I mainly work with Golang these days, briefly explored Rust and have Python experience.

shraddhaag.dev is my home on the internet. You can reach out to me on mail [email protected] or on Twitter!

Challenges

Since late last year, I have discovered the joy of solving coding challenges with a strong community presense.

• aoc - Solution to Advent of Code 2023 in Golang.
• 1brc - My take on the One Billion Rows Challenge.

If you know about more challenges that I should try, please write to me!

Write

I believe writing cements understanding and boosts clarity. Some of my select posts:

• One Billion Rows Challenge in Golang - The Primeagen walked through the post on his livestream!
• Improving Teuthology Scheduling: GSoC 2020 with Ceph Foundation.

You can find all my posts here.

Talks

• How we are Building Hasura Cloud with Hasura (Part II).
• Giving back to the Community - Experience with GSoC and Outreachy.

You can find a complete list here.

1brc's Issues

`customStringToIntParser` can likely be faster using a lookup table

I had a look at https://github.com/shraddhaag/1brc/blob/8513d5e70a1bfabbf46ab86a9cb6558bc9805154/main.go#L240C6-L240C29. Given that the temperatures are always within [-99.9, 99.9] and you know that it always has a tenth of accuracy, you can build up a string -> int lookup table on startup of your application. The lookup table will hold 1999 items. That way, parsing will be looking up the string in the lookup table. My gut feeling is this will be faster.

Caveat: I have not looked at the raw data file, nor have a ran the program.

unit tests are not passing go 1.22 amd

the unit tests didn't pass for me on go 1.22amd. They are all failing heres the first two:

--- FAIL: TestMain (0.22s)
    --- FAIL: TestMain/test_cases\measurements-1 (0.02s)
       billionlinechallenge\main_test.go:18: 
            	Error Trace:	billionlinechallenge/main_test.go:18
            	Error:      	Not equal: 
            	            	expected: "{Kunming=19.8/19.8/19.8}\r\n"
            	            	actual  : "{Kunming=0.0/0.0/0.0}\n"
            	            	
            	            	Diff:
            	            	--- Expected
            	            	+++ Actual
            	            	@@ -1,2 +1,2 @@
            	            	-{Kunming=19.8/19.8/19.8}
            	            	+{Kunming=0.0/0.0/0.0}
            	            	 
            	Test:       	TestMain/test_cases\measurements-1
    --- FAIL: TestMain/test_cases\measurements-10 (0.01s)
       billionlinechallenge\main_test.go:18: 
            	Error Trace:	billionlinechallenge/main_test.go:18
            	Error:      	Not equal: 
            	            	expected: "{Adelaide=15.0/15.0/15.0, Cabo San Lucas=14.9/14.9/14.9, Dodoma=22.2/22.2/22.2, Halifax=12.9/12.9/12.9, Karachi=15.4/15.4/15.4, Pittsburgh=9.7/9.7/9.7, Ségou=25.7/25.7/25.7, Tauranga=38.2/38.2/38.2, Xi'an=24.2/24.2/24.2, Zagreb=12.2/12.2/12.2}\r\n"
            	            	actual  : "{Adelaide=0.0/0.0/0.0, Cabo San Lucas=0.0/0.0/0.0, Dodoma=0.0/0.0/0.0, Halifax=0.0/0.0/0.0, Karachi=0.0/0.0/0.0, Pittsburgh=84.5/84.5/84.5, Ségou=0.0/0.0/0.0, Tauranga=0.0/0.0/0.0, Xi'an=0.0/0.0/0.0, Zagreb=0.0/0.0/0.0}\n"
            	            	
            	            	Diff:
            	            	--- Expected
            	            	+++ Actual
            	            	@@ -1,2 +1,2 @@
            	            	-{Adelaide=15.0/15.0/15.0, Cabo San Lucas=14.9/14.9/14.9, Dodoma=22.2/22.2/22.2, Halifax=12.9/12.9/12.9, Karachi=15.4/15.4/15.4, Pittsburgh=9.7/9.7/9.7, Ségou=25.7/25.7/25.7, Tauranga=38.2/38.2/38.2, Xi'an=24.2/24.2/24.2, Zagreb=12.2/12.2/12.2}
            	            	+{Adelaide=0.0/0.0/0.0, Cabo San Lucas=0.0/0.0/0.0, Dodoma=0.0/0.0/0.0, Halifax=0.0/0.0/0.0, Karachi=0.0/0.0/0.0, Pittsburgh=84.5/84.5/84.5, Ségou=0.0/0.0/0.0, Tauranga=0.0/0.0/0.0, Xi'an=0.0/0.0/0.0, Zagreb=0.0/0.0/0.0}
            	            	 

How to run the program for the input size 1 billion

@shraddhaag Can you please help in running the program I'm trying to run go run main.go and also tried passing input file name it is not working can you please mention the commands.. Thank You..

Document/link how to get hold of data in the README

It took a while to find where to get the data from: https://github.com/gunnarmorling/1brc?tab=readme-ov-file#running-the-challenge

Speed up `processReadChunk` by alternating bytes.IndexByte calls

I would not be surprised if you could speed up https://github.com/shraddhaag/1brc/blob/8513d5e70a1bfabbf46ab86a9cb6558bc9805154/main.go#L187C6-L187C22 by alternating calling bytes.IndexByte(buf[lastTokenEnd:], ';'), followed by bytes.IndexByte(buf[lastTokenEnd:], '\n'). bytes.IndexByte function is highly optimized for fast searching in a byte slice. Since it is the inner loop it can have a big impact.

You could probably also skip the looking at the first 1 byte for station name and temperature (since it's at least one character). From my experience not inspecting bytes can be a very efficient way of speeding up parsing.

Also, I would convert from []byte to string only when I need to to avoid any kind of unicode handling.

Further read optimization

Hi, first of all thank you for sharing your code!

I was quite impressed by the reading speed, and I think that I found a way to make this part a bit faster:

1brc/main.go

Lines 131 to 155 in 8513d5e

	// spawn a goroutine to read file in chunks and send it to the chunk channel for further processing
	go func() {
	buf := make([]byte, chunkSize)
	leftover := make([]byte, 0, chunkSize)
	for {
	readTotal, err := file.Read(buf)
	if err != nil {
	if errors.Is(err, io.EOF) {
	break
	}
	panic(err)
	}
	buf = buf[:readTotal]
	toSend := make([]byte, readTotal)
	copy(toSend, buf)
	lastNewLineIndex := bytes.LastIndex(buf, []byte{'\n'})
	toSend = append(leftover, buf[:lastNewLineIndex+1]...)
	leftover = make([]byte, len(buf[lastNewLineIndex+1:]))
	copy(leftover, buf[lastNewLineIndex+1:])
	chunkStream <- toSend

Currently each loop calls 2 times make([]byte) and copy. This could be reduced to 1, by storing the leftover as a length, instead of a byte slice:

		buf := make([]byte, chunkSize)
		leftover := 0
		for {
			n, err := file.Read(buf[leftover:]) // append to the leftover
			if err != nil {
				if errors.Is(err, io.EOF) {
					break
				}
				panic(err)
			}
			toSend := buf[:leftover+n]

			lastNewLineIndex := bytes.LastIndexByte(toSend, '\n')

			buf = make([]byte, chunkSize) // prepare a new buffer for next read
			leftover = copy(buf, toSend[lastNewLineIndex+1:])

			chunkStream <- toSend[:lastNewLineIndex+1]
		}

On a sample file, this code is about 10% faster than the current version