The One Billion Row Challenge - Gunnar Morling

[giscus[bot]]

The One Billion Row Challenge - Gunnar Morling

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 in SQL with DuckDB by Robin Moffatt and 1 billion rows challenge in PostgreSQL and ClickHouse by Francesco Tisiot.

Thanks a lot for all the submissions, this is going way beyond what I’d have expected!
I am behind a bit with evalutions due to the sheer amount of entries, I will work through them bit by bit.
I have also made a few clarifications to the rules of the challenge; please make sure to read them before submitting any entries.

Let’s kick off 2024 true coder style—​I’m excited to announce the One Billion Row Challenge (1BRC), running from Jan 1 until Jan 31.

Your mission, should you decide to accept it, is deceptively simple:
write a Java program for retrieving temperature measurement values from a text file and calculating the min, mean, and max temperature per weather station.
There’s just one caveat: the file has 1,000,000,000 rows!

https://www.morling.dev/blog/one-billion-row-challenge/

[QwertGold]

Is the input data considered secret ? If so, it would have been nice if the project included a main-method that would generate a file with 1B rows, to test against.

[gunnarmorling]

Please see the README file of the challenge repo, there is a main class which does exactly that.

[QwertGold]

Thanks, got distracted by the leaderboard at the top ;)
Also, running Windows, I prefer gradle to .sh and mvn ;)

[bablupeddi2ax]

I understood the question but i am not getting any idea about how to do the task, although I have been using java for 1 year

[iajzenszmi]

/home/ian/1bnr-ajz.java
ian@ian-Latitude-E7440:~$ time java 1bnr-ajz.java
Station1=20.6/29.6/38.8
Station10=2.8/18.8/34.7
Station11=-8.6/5.3/35.6
Station12=-17.9/5.3/38.9
Station13=-12.1/13.3/33.4
Station14=-9.5/17.8/30.3
Station15=-16.8/8.5/36.7
Station16=-19.1/-10.3/-1.5
Station17=-17.0/6.6/39.4
Station18=-11.1/1.7/27.2
Station19=-12.3/12.0/34.2
Station2=-18.8/5.3/36.4
Station20=-18.5/8.7/29.2
Station3=-15.2/0.1/23.8
Station4=-10.8/10.4/21.3
Station5=-18.2/14.6/39.8
Station6=-16.5/4.8/21.2
Station7=-7.1/0.0/14.6
Station8=1.3/8.6/15.9
Station9=2.6/21.7/35.0

real 0m1.009s
user 0m2.605s
sys 0m0.135s
ian@ian-Latitude-E7440:$
ian@ian-Latitude-E7440:$ cat 1bnr-ajz.java
import java.io.;
import java.nio.file.;
import java.util.;
import java.util.concurrent.;
import java.util.stream.*;

public class TemperatureAggregator {
private static final String FILE_PATH = "temperature_data.txt";
private static final int THREAD_COUNT = Runtime.getRuntime().availableProcessors();

public static void main(String[] args) throws Exception {
    Map<String, DoubleSummaryStatistics> stationStats = processFile(FILE_PATH);
    printResults(stationStats);
}

private static Map<String, DoubleSummaryStatistics> processFile(String filePath) throws IOException {
    ExecutorService executor = Executors.newFixedThreadPool(THREAD_COUNT);
    ConcurrentHashMap<String, DoubleSummaryStatistics> concurrentStats = new ConcurrentHashMap<>();

    try (Stream<String> stream = Files.lines(Paths.get(filePath))) {
        List<Future<?>> futures = stream.map(line -> executor.submit(() -> processLine(line, concurrentStats)))
                                         .collect(Collectors.toList());

        for (Future<?> future : futures) {
            try {
                future.get();
            } catch (InterruptedException | ExecutionException e) {
                e.printStackTrace();
            }
        }
    }

    executor.shutdown();
    return new TreeMap<>(concurrentStats);
}

private static void processLine(String line, ConcurrentHashMap<String, DoubleSummaryStatistics> concurrentStats) {
    String[] parts = line.split(";");
    if (parts.length == 2) {
        String station = parts[0];
        double temp = Double.parseDouble(parts[1]);
        concurrentStats.computeIfAbsent(station, k -> new DoubleSummaryStatistics())
                       .accept(temp);
    }
}

private static void printResults(Map<String, DoubleSummaryStatistics> stationStats) {
    stationStats.forEach((station, stats) -> System.out.printf("%s=%.1f/%.1f/%.1f%n",
        station, stats.getMin(), stats.getAverage(), stats.getMax()));
}

}
The time for 1 billion records to run is 1000000000/100 * real or user or sys times as provided. The run time for billion records can be extrapolated from the time running 100 records.

[Bajahaw]

i am wondering if something like this will help:

List<Future<?>> futures = stream.map(line -> executor.submit(() -> {
// Inside physical thread, create virtual threads
for (int i = 0; i < 1_000_000; i++) {
Thread.ofVirtual().start(() -> processLine(line, concurrentStats));
}
})).collect(Collectors.toList());

[stevenjwest]

Hello Gunnar! Thanks for setting this interesting challenge! I fear I have found it too late to submit a serious entry. I have been looking into improving performance of Java code for past few months, have found the Vector API and run a few benchmarks. I had not read about SWAR before, so thanks for mentioning it.

I just wondered if you knew of any useful textbooks or blog posts that give a good overview of high-performance coding strategies, and ideally Java implementations?

I can see this useful blog post from last year you wrote, the only performance-related suggestion is to use GraalVM I think?

Thanks!

[Dunemaster]

The top of the leaderboard is filled entirely with GraalVM entries, which is expected, startup time is a decisive factor here. I think a separate challenge would also be interesting, comparing the performance on warmed-up Java Machines

[mrjink]

In this commit you renamed the "basic implementation", so the link from this post is now a 404.

[gunnarmorling]

Thx, good spot! Updated the link in the post.

[Dotika21]

I've tried to contact you countless times, i give up lol (give me an email)

[Ebrahim-Ramadan]

https://ebrahim-ramadan.vercel.app/blogs/GitLFS

[andrewmarx]

Just saw some videos about this. It made me think of processing short-read genetic data, which could be an interesting way to expand on this challenge. Basically, you can find FASTA files with hundreds of millions to billions of short genetic sequences. Each sequence is associated with 4 lines in the file (one for the sequence, one for metadata, one for quality scores, and one that often isn't used). So these files can easily be hundreds of GB in size, and typically are stored compressed to get them in the tens of GB size range. For a challenge, people would have to deal with loading the compressed data, decompressing it, checking quality scores to determine if a sequence should be kept or discarded, and then figuring out which sequences match each other. So there's a lot of string processing and opportunity for concurrency. The matching sequences is tricky because sequencers have a small amount of error leading to substitutions and insertions/deletions, and individual genetic variation can also cause this. Depending on the dataset there could also be barcode matching to add an additional level of grouping to the data (barcodes being used to identify sequences from different individuals that were pooled to together)

[jmletennier2]

Hello All, This can be done 8-10 minutes , and yes it uses C , (https://www.academia.edu/170188636/Associative_Memory_Systems_Technical_Technical_Overview) only it does not use Rows and columns..