Now that 2024R3 is out and supports Preemptive threading, I thought it might be fun to try our skill at the 1BRC (One Billion Row Challenge).
From the official 1BRC.Dev site
Your mission, should you choose to accept it, is to write a program that retrieves temperature measurement values from a text file and calculates the min, mean, and max temperature per weather station. There’s just one caveat: the file has 1,000,000,000 rows! That’s more than 10 GB of data!
The text file has a simple structure with one measurement value per row:
Hamburg;12.0 Bulawayo;8.9 Palembang;38.8 Hamburg;34.2 St. John's;15.2 Cracow;12.6 ... etc. ...The program should print out the min, mean, and max values per station, alphabetically ordered. The format that is expected varies slightly from language to language, but the following example shows the expected output for the first three stations:
Hamburg;12.0;23.1;34.2 Bulawayo;8.9;22.1;35.2 Palembang;38.8;39.9;41.0Oh, and this
input.txtis different for each submission since it’s generated on-demand. So no hard-coding the results!
Other Notes
- no plugins, libraries, or DLLs - let’s use pure Xojo code only
- if you use multiple CPU cores, limit of 8 cores
- Input value ranges are as follows:
- Station name: non null UTF-8 string of min length 1 character and max length 100 bytes (i.e. this could be 100 one-byte characters, or 50 two-byte characters, etc.)
- Temperature value: non null double between -99.9 (inclusive) and 99.9 (inclusive), always with one fractional digit
- There is a maximum of 10,000 unique station names (but note that the reference data only has 413 stations.)
Baseline
Here’s my Xojo project which can be a starting point:
- It’s a console app
- it’s purely single-threaded Xojo code
- if the input.txt data file is missing, it creates it. Note: It only creates 10 000 000 (10 Million) rows for now for practical reasons.
- it does a Baseline benchmark. This algorithm is how a normal person would solve the problem (using a TextInputStream, UTF8 Strings, Dictionaries, Arrays, String.ToDouble conversion, etc.)
- it then does several Optimized benchmarks and compares results
On my Core i9 Intel Mac here are my results:
----------------------------------------
Xojo 1BRC (One Billion Row Challenge)
Xojo1BRC version 1.0.0.0 macOS Intel x64
----------------------------------------
----------------------------------------
Baseline.CreateMeasurements
Creating Data File
----------------------------------------
Creating 10000000 measurements for 413 stations
Data file = input.txt
Write row 10000000 (100%)Created 10000000 rows in 239.7 seconds, rate = 41721 rows/second
----------------------------------------
Baseline.Process
Reading row 10000000
Processed 10000000 rows in 22.6 seconds, rate = 443388 rows/second
----------------------------------------
Optimization_md_1.Process
Reading row 10000000
Calculated 10000000 rows from 413 stations
Processed 10000000 rows in 17.9 seconds, rate = 560132 rows/second
Speedup : 1.3x faster than Baseline
----------------------------------------
Optimization_md_2.Process
Reading row 10000000
Calculated 10000000 rows from 413 stations
Processed 10000000 rows in 14.4 seconds, rate = 695441 rows/second
Speedup : 1.6x faster than Baseline
----------------------------------------
Optimization_md_3.Process
Reading row 10000000
Calculated 10000000 rows from 413 stations
Processed 10000000 rows in 10.2 seconds, rate = 978989 rows/second
Speedup : 2.2x faster than Baseline
----------------------------------------
Optimization_md_4.Process
Calculated 10000000 rows from 413 stations
Processed 10000000 rows in 5.2 seconds, rate = 1909900 rows/second
Speedup : 4.3x faster than Baseline
----------------------------------------
The baseline does about 400k rows per second, but as of my 4th optimization, I’m getting just under 2 million rows per second per CPU core.
How fast is that?
The winner of the original 1BRC (written in Java) gets about 80 million rows per second per CPU core.
So we have about 40x speedup left to go!
Here’s the baseline version of the project.
By request, the link to this version of the project has been removed. Please work back from the end of this conversation to get the latest version.
It includes a module named Optimization_yourname_1 which you can modify to test out your own optimizations.
