1BRC in Go

[AlexanderYastrebov]

Completes in ~20s on my machine, see https://github.com/AlexanderYastrebov/1brc/tree/go-implementation/src/main/go

~$ go version
go version go1.21.4 linux/amd64
~$ uname -r
4.15.0-213-generic
~$ cat /proc/cpuinfo | grep 'model name' | sort -u
model name	: Intel(R) Core(TM) i5-8350U CPU @ 1.70GHz
~$ cat /proc/meminfo | grep MemTotal
MemTotal:       16301440 kB
~$ lsblk -o NAME,MODEL | grep nvme0n1
nvme0n1                 SAMSUNG MZVLW256HEHP-000L7              
├─nvme0n1p1             
├─nvme0n1p2             
└─nvme0n1p3             
  └─nvme0n1p3_crypt

Note that I use encrypted disk.

The results vary greatly on different platforms, see discussion below.

[AlexanderYastrebov]

Uses memory-maped file and a goroutine per cpu.

The dirty trick is to use 8-byte hash of id as a key assuming there are no collisions 🙈

[AlexanderYastrebov]

Its also easier to work with a mmapped byte slice than with a reader/scanner

[AlexanderYastrebov]

Posted hardware details

[sharpobject]

@narqo it looks like two of these sources are about databases, which cannot use mmap for data integrity reasons, and the third is concerned with latency caused by the major page faults, not with overall execution time. The cost of all syscalls is very large because of Spectre mitigations and similar.

[narqo]

it looks like two of these sources are about databases, which cannot use mmap for data integrity reasons

The original paper from 1 outlines several problems of mmap: transactional safety, I/O stalls, error handling AND performance issues (for "larger-than-memory DBMS workloads on high-bandwidth disks").

It might be interesting to see if opening a file with direct IO (O_DIRECT flag on Linux) would make a noticeable difference, comparing to the mmap. But, at the moment, I don't have a Linux box (with both fast drive and enough memory) to play with the tests.

[jkroepke]

Not sure. Any ranked top 5 java solution here is using mmap. If O_DIRECT would be faster, it would be used in ranked submissions.

[corlinp]

Thanks for starting this. I have some experience writing this type of program in Go so I couldn't help myself: https://gist.github.com/corlinp/176a97c58099bca36bcd5679e68f9708

On my M3 Pro Macbook, my solution is quite a bit faster than the Go solutions from warpstreamlabs or AlexanderYastrebov, and twice as fast as the current fastest Java implementation. Please give it a spin!

Here's a snippet of the those results:

Script	                                Time (s)
calculate_average_corlinp.sh	           5.092  (Go)
calculate_average_warpspeedlabs.sh         8.183  (Go)
calculate_average_ddimtirov.sh            10.183
calculate_average_ebarlas.sh	          11.625
calculate_average_royvanrijn.sh	          11.970
calculate_average_AlexanderYastrebov.sh	  14.114  (Go)
calculate_average_filiphr.sh	          15.038

While memory-mapped files are great for random concurrent reads, I took the serial approach, but with minimal logic in the read so we're not blocking IO to parse individual bytes. Instead, chunks get passed off to another worker to align the lines and another set of concurrent workers to do the parsing. It's still CPU-bound on my Mac, so there are probably some further optimizations to be made, especially in using something faster than Go's built-in maps.

[neon-sunset]

Now also add C# to the mix :)

[jkroepke]

https://gist.github.com/corlinp/176a97c58099bca36bcd5679e68f9708#file-1brc_corlinp-go-L178

What is the 44 here?

[corlinp]

@jkroepke Good question - I originally had the city name in a [44]byte because the longest city name is 44 characters. Then I simplified it to 64 but this must've been left over. It doesn't make much difference if that's 44 or 64.

[jkroepke]

Ah, should it 100 then? README says, station name can have a max length of 100 bytes.

[corlinp]

I didn't read that closely :) yes it should probably be 100!

[jkroepke]

Here is my final solution:

https://github.com/jkroepke/1brc-go/tree/main/go

While I initially start with mmap.Open and bufio.Scanner, I was in an area approx 25sec.

Then I take note of @AlexanderYastrebov by using bytes.IndexByte instead bufio.Scanner, directly using the mmap syscall and using maphash as unsafe alternative to string as map key.

The key difference between @AlexanderYastrebov and my solution is may using more fixed-sized array rather than maps over all. It has the downside that number of worker needs to be pre-defined.

Both solutions are living between 5.6 and 6.2 seconds on a MacBook Pro 2019 (Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz) with 12 logical cores and 32GB RAM.

59.42s user 4.62s system 1100% cpu 5.816 total

[jkroepke]

@bluntelk That for '\n' (EOL), but for ';' comes after the station name with an unknown length

For EOL, I'm exactly doing this: https://github.com/jkroepke/1brc-go/blob/debcbc13f6e54037b2d1744739e921534f5c2be3/go/main.go#L80-L89

[AlexanderYastrebov]

We don't need to look for \n at all since we know where it is after we parsed the metric value.

[AlexanderYastrebov]

Check out processChunk in https://github.com/AlexanderYastrebov/1brc/blob/go-implementation/src/main/go/calc.go

[jkroepke]

We don't need to look for \n at all since we know where it is after we parsed the metric value.

Before running the main loop, I running a smaller loop over first 5.000.000 bytes (I assume, I get all station names here) to setup an symbol table (station name -> zero-index uint64). Then I can use the the int value as key on the fixed size array for the results.

In this smaller loop, I have to look-up for '\n', since I skip the metric value there.

I have the feeling that using fixed length array perform better than maps.

[bluntelk]

nope, the ; delimiter only appears in one of 3 places, the decimal place is always second to last.
this means no need to do comparisons on every element of the string.

you could potentially also use a uint64 comparison against the last 8 bytes of the string to determine the position of the ; in fewer instructions

[skhaz]

Please try this https://blog.twitch.tv/en/2019/04/10/go-memory-ballast-how-i-learnt-to-stop-worrying-and-love-the-heap/

[jkroepke]

Turn of the GC might be the best option in this case.

[AlexanderYastrebov]

Created proof-of-concept of non-java submission #298

[elh]

My Go solution here https://github.com/elh/1brc-go. Opened as a submission via Docker if they end up allowing that #435. I had a lot of fun trying to minimize memory allocations to optimize the file scanning and then just added concurrency at the end. Did not spend a lot of time tuning it.

Similar performance characteristics to @corlinp 's solution on my Macbook M2 Pro. Both of our solutions run fast on my machine; others are slow.

It's a good performance lesson that everyone's solution seems to be the fastest on their machine 😅

Times measured on 2023 Apple M2 Pro Macbook with 10 cores and 16GB RAM.

• 140s - Naive implementation. Reading lines with Scanner.Text.
• 83s - Using Scanner.ReadSlice to reduce a massive string allocation.
• 54s - Using file.Read directly and avoided some bytes helper functions to iterate bytes in a single scan.
• 45s - Using a far larger buffer to reduce IO latency. Removed a redundant map lookup. Using unsafe.String to avoid additional string allocs.
• 35s - Implemented a custom, simplified replacement for strconv.ParseFloat.
  • Most of the time just goes into scanning byte slices. Biggest other bottleneck is map[string]*Stats lookups. Decently pleased with single threaded optimizations so now making it concurrent.
• 7s - Concurrently read and parse the file as byte index addressed chunks, then merge results in a single final goroutine. See tunable numParsers and parseChunkSize parameters.
• 5.5s - Select concurrency and read buffer size parameters for my machine using hyperfine parameter testing.

[phuanca]

@elh It seems that with each iteration, a digit from the buffer is being lost. Does what I'm saying make sense?

i = parseChunkSize + 1 (i++)

	go func() {
		for i := 0; i < int(info.Size()); i++ {
			chunkOffsetCh <- int64(i)
			i += parseChunkSize
		}
		close(chunkOffsetCh)
	}()

[elh]

@phuanca good catch! I'll change the for loop to only have the termination condition

The reason why this code has generally been working is because of how I handle chunk boundaries. However, if you were unlucky and a chunk coincided perfectly with a newline a byte would be skipped!

[khepin]

Just found out about this a couple days ago and was able to work on it a bit today.
The file I generated had 10k station names and each was between 3 and 15 chars long. This produces a file of roughly 16GB which seems to be what the original test was using. Using a length up to 100 chars made the file much much larger (55GB).

I'm running this on an M1 Pro Macbook (10 vCpus). And I ran 2 versions of the code one using the standard go maps, and one using https://github.com/dolthub/swiss . I tested a couple different map implementations and this is the one that performed the best.

test	time
go standard map	6.7s
Swiss Map	4.6s

General approach I took:

1. Memory Map the file into a giant []byte slice
2. Start a goroutine that sends [2]int [begin,end] arrays on a channel. Each slice is os.Getpagesize() large (remnant of reading the file in chunks instead of memory mapping, not sure of the impact)
3. Start runtime.NumCPU() worker coroutines
4. Each coroutine creates its own map[string]*AggregateMetric to aggregate its local results
5. Then pulls a [2]int off the chunks channel and starts working on that
6. The workers read directly from the giant []byte slice at various offsets. Well, they start from one place and then move sequentially from there until the end of their chunk.

Other than mmap, the only uncommon thing I'm using is unsafe.String to convert a station name to a string cheaply.

[khepin]

Updated to pre-size the maps when using standard lib maps and now I get 4.8s with only standard lib calls.

[weirdgiraffe]

Wanted to drop my solution here as well https://github.com/weirdgiraffe/1brc/blob/master/main.go
My approach is a bit unique in this thread: I just read the file using normal Read and don't use Mmap, I use pool.Sync for storing pieces of memory, so I'm effectively doing the same thing that mmap does, but in the userspace =) Other than that the only thorough optimisation was to add custom float parsing function.

Based on this thread, only the solution from @elh (#67 (comment)) beats mine so far (I just tested locally on my mashine by just running go run ./main.go measurements.txt). But it uses not standard map which I can also try to use later.

Will try to polish up the solution to benchmark against others.

[khepin]

I get 1s more with your solution than with mine on the same file same machine after multiple runs. 3s more than my solution using SwissMap.

Have you tried without converting to float all the time? We know that every number will have exactly 1 decimal place, so instead of using floats, we can multiply every number by 10 and treat them as int for all the time spent reading.
When it comes time to display the results and compute the average, then we can convert those to float but that's a lot less conversions.

[weirdgiraffe]

now, it beats @elh =) key optimisation was to adjust the indexByte to specifically search for the end of line and skip initial 5 bytes: min city name, separator, and min length of temperature =)

[pbruton]

Just curious if any of the Go implementations used SIMD in their solutions? I noticed pretty much everyone getting faster times had to do it by busting out some SIMD, but I've looked at several solutions and haven't seen SIMD used in any of them. Would be interesting to see if it made a difference in Go.

https://github.com/stuartcarnie/go-simd

[weirdgiraffe]

You can take a look at the profile below, and figure out that arithmetics is not the bottleneck. So using SIMD instructions will limit the application to some specific CPU features, which may not be available on arm or other arch. This kind of optimization is a bit of an overkill while promising just insignificant improvement. Hope this answer was useful to you.

Two main bottlenecks are:

• Map access
• I/O

[Kanbenn]

Wow, this is a great challenge and very interesting solutions, I've learned a lot, thank you so much, guys! 🙏

I wonder, what storage would you choose for >1 Billion records with fast enough lookups? Especially for this type of data that changes so often while un-demanding in terms of being heavy relational, pretty much no JOINs needed, right? Would Postgres or SQLite be good enough to insert it quickly with fast enough Selects? Or should we consider things like ClickHouse or on-disk-Redis or maybe ObjectBox for that? Please share your thoughts?

[Goldabj]

I've been using this challenge as a way to learn go over the past few days. With my limited go experience, I've seem to hit a wall.

I have my submission here. On my M1 macbook pro with 16GB of memory, it runs in ~39s. I can get it a few seconds faster if I play around with some parameters (numWorkers and chunkSizes). I'm trying to make it a goal to get <20s. However, I'm stuck.

I came across another submission from this blog post . I've copied over the submission to my repo (otherSubmission.go) and it runs in ~19s. I was looking over their solution and it appears very similar to mine in apprach. The only difference is that they use os.Read to read the file sequentially, and my submission uses MMap. Plus a few other minor differences. Overall, both approaches look to be about the same. However, theirs runs in about half the time. I can't find anything that stands out to why there would be such a large difference in runtime.

I've been trying to use the profile and execution traces to figure out why. Below are my flameGraphs and execution traces

Below are the otherSubmission profile and execution traces:

The first thing that stands out to my are the # of GC collections. My submission seems to be running GC much more frequently - 100,000 incremental sweeps, 32,000 background sweeps, and around 1000 stop the world GCs. The heap only grows to 180MB at its peak, and typically stays around 72MB. In the otherSubmission, incremental GC only runs 6 times, and stop the work is ~30 times. Their heap grows much larger (up to 3.5GB), and GC happens less frequently.

Also, looking at the flame graphs, it looks like there is much more time being spent on managing the stack systemstack, runtime.morestack, and runtime.mcall. I think this may be due to more scheduler overhead due to the frequent GCs (waiting for routines to get to a stopping point, running GC, then re-scheduling threads to start again).

I believe the time discrepancy is mostly due to GC overhead and go scheduler overhead. Although, I'm not sure why.

Could anyone help a newbie figure out where I'm going wrong? Also could share any tools or tricks that could help me figure this out?

[bluntelk]

some optimisation tips, Channels are expensive, only read things once, manage your memory, pointers are more expensive than you think (Golang has to type check them) so keep as much as you can on the stack.

The way I tackled it was to fire up N workers and tell them to work between X and Y bytes of the file.
once they where done they fed the results back to the main process and combined them. (with 16 processes it's 16 items put onto the channel). No fancy mmap for me, just plain os.Read

on my machine (7900X, 32GiB RAM, fast SSD) I had it around 1-2s with this method