One Billion Row Challenge - Part Two: C++ Baseline

In part one, we defined the challenge. In this part, we're going to implement a C++ baseline, and then we'll optimize its performance in future articles.

October 5, 20267 min readSwitch Case

In “One Billion Row Challenge - Part One: DuckDB”, I defined the 1BRC criteria and solved the challenge with SQL and DuckDB. Let’s continue our journey, this time by implementing a C++ baseline. I’m going to write the simplest and most understandable code that I can write to solve the problem, and I will optimize it in future articles. You can find this article’s code in the SwitchCaseLab GitHub repository.

Reading the file#

The easiest way to read a file in C++ is to use std::ifstream. It provides a high-level, object-oriented API for reading files from disk. I’m going to write code that allocates a large block of memory and then reads the whole file into the buffer. To make it easier to understand, I’m going to use std::vector as a memory-managed buffer and its resize method to allocate the memory.

#include <filesystem>
#include <fstream>
#include <iostream>
#include <vector>
 
using namespace std;
 
static void ReadWholeFile(const string& filePath, vector<char>& buffer)
{
    const auto size = filesystem::file_size(filePath);
    buffer.resize(size);
    ifstream file(filePath, ios::in | ios::binary);
    uintmax_t position = 0;
    while (position < size)
    {
        file.read(buffer.data() + position, min(4096ull, size - position));
        position += file.gcount();
    }
}

Snippet 1.Read the file size and resize the buffer

First, I use std::filesystem::file_size to get the file size, then I resize the buffer to match it. The code reads the file in 4 KiB chunks because read has OS-specific limits on how many bytes it can read per call, so I use a safe chunk size for each invocation.

#include <filesystem>
#include <fstream>
#include <iostream>
#include <vector>
 
using namespace std;
 
static void ReadWholeFile(const string& filePath, vector<char>& buffer)
{
    ...
}
 
int main()
{
    vector<char> buffer;
    ReadWholeFile(R"(C:\OBC.csv)", buffer);
    return 0;
}

Snippet 2.Read the file into the buffer.

On my machine, reading the whole file into the buffer takes 14 seconds. You can find my machine’s specs in Appendix A.

Extract column values#

After reading the file into the buffer, we need to extract the station names and temperature values, then calculate the min, max, and mean for each station. You can see the data layout in Figure 1.

Rock Hill;-54.3
Propriá;-26.0
Pianoro;48.6
Ciudad Altamirano;50.5
Hirokawa;21.7
Ivaiporã;-32.5

Figure 1.File content structure.

Each line starts with the station name and ends with \n, and the two columns are separated by a semicolon. To parse a line, I take everything from the start of the line up to the semicolon as the name, and everything from the semicolon up to the end of the line as the temperature.

#include <filesystem>
#include <fstream>
#include <iostream>
#include <vector>
 
using namespace std;
 
static void ReadWholeFile(const string& filePath, vector<char>& buffer)
{
    ...
}
 
static optional<tuple<string_view, string_view>> ParseNextLine(const vector<char>& buffer, int64_t& position)
{
    if (position < 0)
        throw runtime_error("Position can't be negative");
    if (buffer.size() <= position)
        return {};
    if (buffer[position] == '\n')
        return {};
 
    const auto scPos = find(buffer.begin() + position, buffer.end(), ';');
    if (scPos == buffer.end())
        throw runtime_error("Semicolon position not found");
    auto name = string_view(buffer.data() + position, (scPos - buffer.begin()) - position);
    position = (scPos - buffer.begin()) + 1;
 
    const auto tempPos = find(buffer.begin() + position, buffer.end(), '\n');
    if (tempPos == buffer.end())
        throw runtime_error("Temperature position not found");
    auto temp = string_view(buffer.data() + position , (tempPos - buffer.begin()) - position);
    position = (tempPos - buffer.begin()) + 1;
 
    return tuple{name, temp};
}
 
int main()
{
    vector<char> buffer;
    ReadWholeFile(R"(C:\OBC.csv)", buffer);
    int64_t position = 0;
    while (const auto lineOpt = ParseNextLine(buffer, position))
    {
    }
    return 0;
}

Snippet 3.Parsing lines.

The ParseNextLine function shows how I parse a line. Its result is an optional because the file ends with an empty line, which marks the end of the content. An empty result therefore means the code has reached the end of the file.

Parse a floating-point number as an integer#

As we discussed in “One Billion Row Challenge - Part One: DuckDB”, we can’t just convert temperatures to floating-point numbers and accumulate them. We have to convert them to integers and use integer accumulation to prevent float drift.

Since every temperature has exactly one decimal place, we can multiply it by 10 and cast the result to an integer.

#include <filesystem>
#include <fstream>
#include <iostream>
#include <vector>
 
using namespace std;
 
static void ReadWholeFile(const string& filePath, vector<char>& buffer)
{
    ...
}
 
static optional<tuple<string_view, string_view>> ParseNextLine(const vector<char>& buffer, int64_t& position)
{
    ...
}
 
static int64_t ParseTemperature(const string_view temperature)
{
    char *dummy = nullptr;
    return static_cast<int64_t>(std::strtod(temperature.data(), &dummy) * 10);
}
 
int main()
{
    vector<char> buffer;
    ReadWholeFile(R"(C:\OBC.csv)", buffer);
    int64_t position = 0;
    while (const auto lineOpt = ParseNextLine(buffer, position))
    {
    }
    return 0;
}

Snippet 4.Parsing temperature.

I know, I know: it’s not the fastest way to parse a temperature, but this article focuses on a baseline implementation, and I want to keep it as simple as possible. We’ll optimize every part in future articles.

Store the stations in a map and calculate min, max, and mean#

There are two associative containers in the C++ standard library that we can use: std::map (ordered, tree-based) and std::unordered_map (hash-based). The unordered_map would be faster in our case, but since the challenge requires the output to be sorted by station name, I’m going to use std::map, which keeps its keys sorted.

We also need a structure to store the min, max, count, and sum of the temperatures. We’ll use the sum and the count to calculate the mean value.

struct SDetail
{
    int64_t count = 0, min = INT64_MAX, max = INT64_MIN, sum = 0;
};

Snippet 5.Define a structure to store temperature details.

We could shrink these variables. For example, min and max fit in a 16-bit integer (the temperatures range from -99.9 to 99.9, which is -999 to 999 after multiplying by 10), so int16_t would be enough. To keep things simple, I’ll leave them as they are.

#include <filesystem>
#include <fstream>
#include <iostream>
#include <vector>
#include <map>
 
using namespace std;
 
struct SDetail
{
    int64_t count = 0, min = INT64_MAX, max = INT64_MIN, sum = 0;
};
 
static void ReadWholeFile(const string& filePath, vector<char>& buffer)
{
    ...
}
 
static optional<tuple<string_view, string_view>> ParseNextLine(const vector<char>& buffer, int64_t& position)
{
    ...
}
 
static int64_t ParseTemperature(const string_view temperature)
{
    ...
}
 
int main()
{
    vector<char> buffer;
    ReadWholeFile(R"(C:\OBC.csv)", buffer);
    int64_t position = 0;
    map<string_view, SDetail> resultMap;
    while (const auto lineOpt = ParseNextLine(buffer, position))
    {
        auto line = lineOpt.value();
        const auto temp = ParseTemperature(get<1>(line));
        auto &detail = resultMap[get<0>(line)];
        detail.count++;
        detail.min = min(detail.min, temp);
        detail.max = max(detail.max, temp);
        detail.sum += temp;
    }
    return 0;
}

Snippet 6.Calculate min, max, count, and sum.

Generate the output#

The challenge asks us to generate the output in the following format and print it to stdout: {station=min/mean/max,...}.

#include <filesystem>
#include <fstream>
#include <iostream>
#include <vector>
#include <map>
 
using namespace std;
 
struct SDetail
{
    int64_t count = 0, min = INT64_MAX, max = INT64_MIN, sum = 0;
};
 
static void ReadWholeFile(const string& filePath, vector<char>& buffer)
{
    ...
}
 
static optional<tuple<string_view, string_view>> ParseNextLine(const vector<char>& buffer, int64_t& position)
{
    ...
}
 
static int64_t ParseTemperature(const string_view temperature)
{
    ...
}
 
int main()
{
    vector<char> buffer;
    ReadWholeFile(R"(C:\OBC.csv)", buffer);
    int64_t position = 0;
    map<string_view, SDetail> resultMap;
    while (const auto lineOpt = ParseNextLine(buffer, position))
    {
        ...
    }
    string result = "{";
    for (auto& [station, detail] : resultMap)
    {
        result.append(format("{}={:.1f}/{:.1f}/{:.1f},", station, static_cast<double>(detail.min) / 10.0,
                             (static_cast<double>(detail.sum) / static_cast<double>(detail.count)) / 10.0, static_cast<double>(detail.max) / 10.0));
    }
    result.back() = '}';
    cout << result << endl;
    return 0;
}

Snippet 7.Generate the output.

Benchmarking and profiling#

I ran the program to parse one billion rows and profiled it to find out which part of the program took most of the time.

The execution time was 436727 ms, which is about seven minutes. I sampled the program with the Visual Studio Performance Profiler, and the results were as follows:

Reading the file took 2.57% of the time.
Parsing temperature values to floating-point numbers took 11.32% of the time.
Map lookup for station names took 76.33% of the time.
Generating the output string took 4.3% of the time.
The remaining 5.5% went to loops and other calculations.

What’s next?#

In the next article, I’m going to optimize this implementation. Then I’ll implement some functions with SIMD, and finally I’ll add parallelism.

Appendix A#

My PC specs:

RAM: 32 GB, 4800 MT/s
Disk: Samsung SSD 990 PRO
CPU: Intel Core i7-12700H

▸ stay subscribed

Liked this?

Drop your email and you'll get the next post when it's published. No tracking, one-click unsubscribe.