#1BRC - The First 80% of the Way

At the end of 2023, when everyone was busy with the holidays, Gunnar Morling got bored. So he came up with a fun little project to read one billion rows from a CSV file as fast as possible. Recognizing that performance challenges are best tackled by the community, he turned it into a competition. He wanted to see how fast Java code could become with the help of other Java nerds.^[1]

We don’t want to be as fast as the winning solution (which is about 9 seconds for a single thread, more later), we just want to end up with a fifth of the runtime. So we want to shave off 80% of the runtime.

You can find all the code at https://github.com/rschwietzke/1brc-the-first-80-meters. I will either link to the implementation or just mention the class by name.

Just to detour quickly. The original 1BRC uses single Java files and always runs them several times. To make measurements easier and also allow for better learning in regards to Java JIT compilation, I wrote a small framework for executing each solution including measurement, warming, and checksumming, not to forget batch execution.

The baseline is the original solution by Gunnar Morling. As you will see, we have a plain stream implementation that uses features Java provides, such as collecting and grouping. I leave the interpretation to you or just read about that in all of the other 1BRC articles out there.

The above code runs for a moment, but we don’t know yet where it might spend most of its time. We don’t want to guess what to optimize; we want to see. For that, we look into our toolbox and find the AsyncProfiler – perhaps the most versatile and powerful open-source profiler for Java.

With this command line, you can create this flamegraph and browse it yourself.

That is the last flamegraph we will see in this article. You can browse a lot more when you page through the Jfokus 2025 slides. For the rest of the article, we will go with a small table that shows us the most important parts and the percentage of time spent there.

About 80% of the total runtime goes into our own code, and split dominates that. Let’s start there. However, stream code is hard to tune because a lot of things are just magic done by the JDK and are not visible to us.

Our classic approach is just an unrolled stream operation and the collect and groupBy is done manually. Let’s look at the flamegraph data. DO is our DigitalOcean Intel Server and HE is our AMD 8-core at Hetzner.

So, we gained speed by getting rid of the stream code. That was easy.

Things moved a little, but the overall distribution is nearly the same. Our manual merge is slower and we will learn later why, and then use that knowledge to fix it.

Split consumes the majority of our time, so let’s get rid of that first. Split is a very powerful method that normally uses regular expressions to split a string. When you look at the JDK code of split, you can see that it tries to be smart. It features a fastpath when the split char is a single char and not a regex. The JIT (Just-In-Time) compiler might or might not be able to "constant fold" it (calculating the value once and reusing it). Even when this is folded, it still leaves us with a call to a larger method that creates objects and might not be inlined (where the compiler copies the method’s code into the caller to avoid the overhead of a method jump).

That is impressive. Almost no effort and we gained more than 20%. It is interesting to see that AMD and Intel are not getting the same speedup. We will see that pattern again and again.

Our split disappeared into indexOf and substring.

When you check the Double::parseDouble code in the JDK, you find code that is more than 200 lines long and covers almost all possible edge cases. But we don’t have edge cases here. We know that our input is always a valid double with one decimal place, so let’s use that knowledge to our advantage.

I had some code available that I used in another project, so I used that here. The code is already prepared to cover the next steps as well.

We gained a lot on the Intel CPU. For the AMD CPU, we got it 10 seconds faster.

If you look at our current code, you can easily see that we create a new String only to pass it to the Double::parseDouble method. Since it’s only being read, we don’t actually need that instance at all.

So, let’s continue by parsing the double inline, based on the position of the semicolon in the original data set without splitting it for real.

That was simple and very effective.

In case you have worked with old computers before, something like 486 or even the first Pentiums, you know that double is extra work and slower than int. We also know that our double here is something like XX.X, so we can easily deal with all numbers as int and only fix that up at the end when we print out the data.

Our new double parsing is actually only int parsing now and we silently drop the decimal information. Essentially, we postpone working with doubles until we print the result data.

We did not gain that much—just a little bit. You have to keep one thing in mind: a modern CPU still has more execution units for integer operations than for double-precision operations. Modern CPUs run instructions in parallel, so we’re enabling them to utilize more execution units where possible. Do we really profit from that? It’s hard to tell.

When we look at our flamegraph data, we can also not really draw any conclusions. A modern CPU does not execute one command at a time, but many. If they cannot do that, they become slow.

At the moment, we utilize a lambda expression to merge the data. Because we plan some more optimizations later, we might have to change that.

Wow, that is unexpected. We are slower now. But why? This is not obvious but easily explained.

When we get our data, we need the hashCode first and we retrieve the data from the calculated position. If the data is not there, we return null. For the later put, we do the same again. Our lambda expression was able to combine that; hence it was only one method call, and it only needed to calculate the hashCode once and access the backing data structure once. But we will get there again, I promise.

Before we try to restore the original speed again, we should look at our code and see if there is something more obvious we can tackle.

Our code, even though I have not shown that here, still uses immutable classes for storing the temperature data. That is a modern practice and perfect for concurrent code because it makes things less error-prone, but it is a silent performance killer. Nothing is free: not memory, not CPU cycles, and not memory bandwidth. Every time you create a new instance to update a value, the JVM must allocate memory and later clean it up via Garbage Collection. So, let’s mutate the Temperature instead.

We only create a new Temperatures instance if we have not seen the city before. If we have seen the city before, we just add the temperature to the existing instance.

That helped a lot. Let’s take a look at the current state of our code. I took the liberty of removing some of the data we have seen before to keep things compact.

Mutating data removes the merge and makes the put very rare, so we don’t even see that in our profiling data anymore. The get is not slower, it just sees more share of the overall runtime. Also our add is so fast and likely inlined that we cannot see it in the flamegraph.

When we removed the lambda expression, we got slower. So, let’s address that now. We use the default HashMap from the JDK, and that is a good and very versatile implementation. But we don’t need that versatility here. We also know, when looking at our profiling data, that there is something like getNode visible. If you check the HashMap, you will see that it stores key and value in a wrapper object, the node. We can do better.

Our map has backing arrays with wrapper objects that hold key and value. In addition, in case of collisions, we build a linked list with the wrapper objects.

A simplified Map implementation might look like that.

Our open map uses a backing array as well but stores key and value next to each other. Yes, this is less perfect in terms of code beauty. When we have collisions, we store the other data simply in the next position in the array. I used ObjObjMap as the starting point.

So, some gain for AMD CPUs, but not much for Intel.

Our current map has a drawback. It needs two slots and it needs a wrapper for the values. Why not combine that into a single entry? And so we get a set.

We can fit twice as many object references into a CPU cache line (a small, ultra-fast memory area inside the processor). Because we already have our wrapper in our hands, we don’t need to look up a second object either, which reduces memory access and speeds things up.

As part of this change, we also will remove the need for a separate put method and return to the concept we abandoned when removing the lambda expression. Call the method once and let it decide if this is a new entry or just an update. In addition, we also move the Temperatures handling into the Set class. Yes, I know: reuse, architecture, clean code, and so on. Sometimes you have to trade a bit of elegance for performance. It is no longer a generic Set, but we’re giving everything for performance, aren’t we?

Ok, we gained about 2%. Not much, but we are making progress.

Okay, we’ve addressed all the "cheap" optimizations. Now what? We have to deal with the I/O side of life. How can we make readLine faster?

Sit back, relax, and let’s dive in. Let’s have another look at our data and its constraints.

Our data is well-formatted and controlled by definition. Everything is valid UTF-8, and UTF-8 includes ASCII characters. These are the first 127 bytes (not chars).

Since all our numbers, semicolons, and newlines are ASCII, why bother converting everything to char when reading from disk (which stores just bytes)? Instead, let’s delay the conversion to char until we actually need a char. This is similar to our double-to-int approach: delay repeated actions that aren’t necessary for immediate processing.

We could use the ByteBuffer directly and read bytes from it, but repeatedly calling methods that check the range of the backing array introduces significant overhead. Instead, we will access the backing array directly to gain speed.

What a leap! Let’s check our profiling data. Because the code is so different now, we will limit the profiling to our last two measurements.

Our readLine contains a method call to read and that is 2.2% of the runtime. The rest is used for our data processing. Yes, it could have been extracted more neatly into its own method. Next time!

When we run our baseline code with EpsilonGC, we get about 3.2 GB of heap usage for 10 million lines. That sums up to a staggering 320 GB for 1 billion rows. That is memory churn at the end of the day. Request memory, clean it, use it, investigate if still in use, add it to the free list or move the content around when still in use. By the way, we are not really allocating and deallocating against the OS here, because the JVM does its own memory segment management (ask for a chunk of memory from the OS and own that as long as possible).

When we repeat that for our version 13, before we changed to byte reading, we see 1.04 GB memory used for 10 million lines. That is a total of 104 GB for 1 billion rows.

If we repeat that with our version 14 and byte reading, we will consume 3.7 MB for 1 billion rows. You read that right: less than 4 MB for 1 billion rows.

This is a rather unexpected bonus: we are now effectively GC-less. We are using almost no memory, and the data will likely fit into the CPU cache. One important note: we still transfer 13 GB of data from the file into our program, but because this isn’t handled by the heap, it doesn’t involve constant allocation and garbage collection. While the CPU cache might see some "pollution" (where reading new data from disk pushes useful data out of the cache), the overall efficiency is massive.

We’ve made a huge leap, but we’re still not quite at our 80% reduction goal. While we’re very close on the Intel system, the AMD results are lagging slightly behind.

Let’s try some "cheaper" tuning first. Let’s revisit our number parsing.

There was still some juice to be squeezed out of this performance lemon. Eliminating the loop makes things easier for the CPU. While there are still several if-conditions, they keep the code readable. The CPU does not like to jump, so if-statements and loops always have a performance impact. The CPU tries to guess the likely branch and executes that code already in its pipeline (if possible). When the if-conditions turn out to be different, it throws away the temporary result and continues on the other branch. The fewer misses we have, the faster we will be because modern CPUs do not execute one command at a time, but many. If they cannot do that, they become slow.

Let’s look at our code more closely and start with this part that updates the total values for a city.

This code always compares the new value with the minimum and writes to memory even if the value hasn’t changed. It does the same for the maximum, even if the minimum was already updated. While Math.min and Math.max are likely efficient intrinsics, unnecessary writes are best avoided.

The following list shows one more improvement I haven’t explained in detail yet (BRC20_UseArrayNoBufferST): we refer to the direct reference of our backing array instead of asking the ByteBuffer for that array every time. Since it never changes, why ask for it repeatedly?

It is interesting to notice that the buffer trick speeds up Intel but not AMD, while min/max has a similar effect on both. Regardless, we are still not quite at our goal.

Let’s carefully check our code and also look at the latest list of hot methods. We can see that we spend a lot of time on the hashCode calculation. How to make that cheaper?

That is our current code.

The first loop looks for the semicolon, and then later we have essentially the same loop to calculate the hashCode. Why not do both in one go?

And we have liftoff! The Intel machine broke the 20% barrier (80% reduction), while the AMD machine is almost there.

To get the AMD CPU over the line, we will perform some minor tunings and fiddle around with ideas. We keep some, but will abandon others. At the end, we will finally see our code runs five times faster, as promised. No usage of Unsafe, no bit magic, no GraalVM. To limit the article length, I won’t discuss the other changes in detail.

If you want to see what changed, hop over to the repo and check it out. It also contains examples of what did not work. You can also see that I discovered a defect when comparing with another dataset: BRC58_UnnoticedCharSkipping. We already have a checksum in place; still, some errors only come up when the input looks different—strange, isn’t it?

There we go—tuned without turning the code into a complete disaster. It’s a bit "messy" perhaps, but still maintainable. Keep in mind that we’re relying on clean, well-formatted data. If we had to add checks for malformed data or varying lengths, the complexity (and performance) would look quite different.

For the fans of hard-core performance and low-level facts, let’s dive into the CPU and memory details. This is where "Mechanical Sympathy" – designing software that works in harmony with the underlying hardware – truly comes into play. These statistics are provided by the perf tool, courtesy of the Linux kernel.

We already have seen that CPUs are very much different, we can easily extend that warning to all types of machines.

Measuring performance in the cloud is often a trap because you are rarely alone on the hardware. Shared resources mean that small performance gains can be easily drowned out by "noisy neighbors" or unexpected fluctuations in CPU and memory bandwidth. Furthermore, features like burst capacity can lead to inconsistent results. To make matters worse, low-level profiling tools like perf often fail in virtualized environments, leaving you flying blind when trying to understand hardware effects.

The above listing shows a few runs on DigitalOcean Intel hardware. You can see how the runtimes fluctuate. The tuned version is slightly more stable, which might be partly due to JVM effects like the absence of GC (as we moved to a zero-allocation approach). However, for micro-optimizations, even these small fluctuations can be a significant hurdle.

The One Billion Row Challenge is a fantastic way to explore Java performance. By applying a systematic tuning approach, starting from a clean baseline and incrementally optimizing everything from stream usage to I/O and custom collection implementations, we achieved an 80% reduction in runtime using only standard Java features.

While Unsafe is not a standard feature in my view, and extreme bit magic is fully legal but makes the code difficult to understand for most people, those techniques fall under: only when truly needed, only by experts, and only with a ton of documentation.

These techniques aren’t just for coding competitions; they demonstrate how a deeper understanding of the JVM, memory management, and hardware characteristics can lead to big efficiency gains. Don’t forget: faster means fewer resources, and that translates directly into lower infrastructure costs.

Always remember to measure, profile, and optimize only where it truly matters!