EDIT
A port of Björn's answer to C++ with further improvements at bottom achieving up to 2.4GB/s on the reference machine.
Text file parsing and processing continues to be a common task. Often it's slow, and can become a performance bottleneck if data is large or many files need to be processed.
Background
This is the next stage on from this question. As before the "Yahtzee" programming challenge shall serve as an illustrative example. Follow that link for full details, but the task is basically:
- Read ~1MB file with about ~100,000 newline separated ints (we are using that file repeated x1,000 because we got too fast => ~900MB; see below).
- Group them by hash map. We are using the 3rd party,
ska::bytell_hash_map, instead ofstd::unordered_map, because it is about 2.5x faster. - Find the group with the largest sum and return that sum.
In the first code review I focused on:
- How to read the file efficiently => conclusion
mmap(linux specific, see the other question for details and alternatives). - How to parse efficiently => once we are efficiently reading the file, parsing becomes the bottleneck. The other question progressively moved to stripping the parsing right down to a tight loop incrementing a pointer over the mmap file with minimal checking / branching.
The file format here is very simple. One integer per line terminated with '\n'. We are assuming the data is in ASCII and no illegal characters exist; only [0-9].
The test file we used initially is this repeated a 1,000 times with: for i in {1..1000}; do cat yahtzee-upper-1.txt >> yahtzee-upper-big.txt ; done. This produces a file about 900MB in size, but with a very low cardinality (only 791 unique integers), which means the hashmap part of the algorithm is not too much of a bottleneck. See below for the second part of the challenge with a file with higher cardinality. With such stripped down code and mmap we were able to achieve ~540MB/s (1.7seconds for this file) using a single thread.
(All timings are for a i7-2600 Sandy Bridge processor with 16GB of DDR3-1600 and a 500MB/s SSD, but note that we ensure that the file is OS cached so already in RAM. Hence the 500MB/s is not really relevant.)
The next level
In order to go faster still this question / code review focuses on going multi-threaded for the parsing. It turns out that the algorithm is Embarrassingly parallel if we chunk the mmap and just let each thread build its own hashmap and then combine them at the end. This last step is not significant (certainly not for the yahtzee-upper-big.txt file due to the low cardinality).
Code is at bottom. It can achieve < 400ms for the full (cached)read, parse, hashmap and combine using 8 threads (that CPU has 4 cores + HT). (Note the os::fs::MemoryMappedFile class is my own RAII convenience wrapper for mmap). Scaling is not bad to 8 threads, but it visibly tails off. (Note that a tight single threaded loop spinning a pointer through the mmap takes ~140ms).
1 thread: ~1700ms
4 threads: ~680ms
6 threads: ~437ms
8 threads: ~390ms
This is quite good, although I would welcome feedback on the concurrency coding / style.
The real challenge for this approach comes when we use a file with a higher cardinality (ie more unique integers and therefore a much bigger hashmap with more entries).
Here is a small utility to generate a more challenging file:
#include <iostream>
#include <random>
#include <fstream>
#include <iomanip>
int main(int argc, char* argv[]) {
if (argc < 2) return 1;
auto gen = std::mt19937{std::random_device{}()};
std::uniform_int_distribution<unsigned> dist(1'000'000, 2'000'000);
auto file = std::ofstream{argv[1]}; // NOLINT
for (std::size_t i = 0; i < 100'000'000; ++i) {
file << dist(gen) << '\n';
}
return 0;
}
run like this to make ~800MB file with cardinality 1,000,001.
./build/bin/yahtzee_gen yahtzee-upper-big2.txt
The performance of this file, despite being slightly smaller, is much slower: ~2.1s on 8 threads. The single threaded performance is: 4.7seconds showing poor scalability. perf stat reports this:
Performance counter stats for 'build/bin/yahtzee_mthr yahtzee-upper-big2.txt':
14,159.77 msec task-clock # 6.044 CPUs utilized
2,789 context-switches # 0.197 K/sec
8 cpu-migrations # 0.001 K/sec
169,114 page-faults # 0.012 M/sec
49,300,366,303 cycles # 3.482 GHz (83.26%)
44,125,329,192 stalled-cycles-frontend # 89.50% frontend cycles idle (83.26%)
39,070,916,691 stalled-cycles-backend # 79.25% backend cycles idle (66.68%)
16,818,483,760 instructions # 0.34 insn per cycle
# 2.62 stalled cycles per insn (83.36%)
2,613,261,878 branches # 184.555 M/sec (83.47%)
24,712,823 branch-misses # 0.95% of all branches (83.33%)
2.342779054 seconds time elapsed
13.755426000 seconds user
0.412222000 seconds sys
Note the front and back-end idle cycles. I suspect that this kind of poor scalability can be typical where we are iterating through a large file whilst building up a significant size data structure from the input. A common use case?
Note: We attempted CPU pinning (before switching from std::thread to std::async / std::future), but that made little difference.
Feedback / Ideas Wanted
- Coding style and technique for the concurrent implementation.
- Ideas / code / tuning suggestions for helping improve the multi-threaded performance of the high cardinality file.
And finally here is the code:
#include "flat_hash_map/bytell_hash_map.hpp"
#include "os/fs.hpp"
#include <cstdint>
#include <future>
#include <iostream>
#include <string>
#include <string_view>
#include <vector>
using uint64 = std::uint64_t;
using map_t = ska::bytell_hash_map<uint64, uint64>;
std::pair<const char* const, const char* const> from_sv(std::string_view sv) {
return std::make_pair(sv.data(), sv.data() + sv.size());
}
std::string_view to_sv(const char* const begin, const char* const end) {
return std::string_view{begin, static_cast<std::size_t>(end - begin)};
}
map_t parse(std::string_view buf) {
auto map = map_t{};
auto [begin, end] = from_sv(buf);
const char* curr = begin;
uint64 val = 0;
while (curr != end) {
if (*curr == '\n') {
map[val] += val;
val = 0;
} else {
val = val * 10 + (*curr - '0');
}
++curr; // NOLINT
}
return map;
}
std::vector<std::string_view> chunk(std::string_view whole, int n_chunks, char delim = '\n') {
auto [whole_begin, whole_end] = from_sv(whole);
auto chunk_size = std::ptrdiff_t{(whole_end - whole_begin) / n_chunks};
auto chunks = std::vector<std::string_view>{};
const char* end = whole_begin;
for (int i = 0; end != whole_end && i < n_chunks; ++i) {
const char* begin = end;
if (i == n_chunks - 1) {
end = whole_end; // always ensure last chunk goes to the end
} else {
end = std::min(begin + chunk_size, whole_end); // NOLINT std::min for OOB check
while (end != whole_end && *end != delim) ++end; // NOLINT ensure we have a whole line
if (end != whole_end) ++end; // NOLINT one past the end
}
chunks.push_back(to_sv(begin, end));
}
return chunks;
}
uint64 yahtzee_upper(const std::string& filename) {
auto mfile = os::fs::MemoryMappedFile{filename};
unsigned n_threads = std::thread::hardware_concurrency();
auto fut_maps = std::vector<std::future<map_t>>{};
for (std::string_view chunk: chunk(mfile.get_buffer(), n_threads)) { // NOLINT
fut_maps.push_back(std::async(std::launch::async, parse, chunk));
}
uint64 max_total = 0;
auto final_map = map_t{};
for (auto&& fut_map: fut_maps) {
map_t map = fut_map.get();
for (auto pair: map) {
uint64 total = final_map[pair.first] += pair.second;
if (total > max_total) max_total = total;
}
}
std::cout << final_map.size() << "\n";
return max_total;
}
int main(int argc, char* argv[]) {
if (argc < 2) return 1;
std::cout << yahtzee_upper(argv[1]) << '\n'; // NOLINT
return 0;
}
