9
\$\begingroup\$

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 of std::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;
}
\$\endgroup\$
16
  • \$\begingroup\$ What about adversarial input? That is, are input files designed to break the hash data structure you are using allowed? Also, would a randomized algorithm be acceptable? One that is right say 99.99% of the time but sometimes wrong? \$\endgroup\$ Jan 12 '20 at 18:17
  • \$\begingroup\$ @BjörnLindqvist If you mean ill-formed txt filles with letters or space, then no, I am not focused on that right now. If/when we maximise MT parsing, I can reintroduce some checking. Apart from that, how would you break the hashmap? If you send all unique ints, then sure, it will be slower, but it won't break? Regarding probabilistic estimates, I would not like to go there. The idea for me behind this question is to learn more techniques about how to write efficient concurrent algorithms. This is already lock free, but of course that does not mean contention free. So that is the focus. \$\endgroup\$ Jan 12 '20 at 18:22
  • \$\begingroup\$ Not malformed input, algorithmic complexity attacks. You can't break the hashmap, but you likely can trigger worst case performance. \$\endgroup\$ Jan 12 '20 at 18:27
  • \$\begingroup\$ @BjörnLindqvist OK, I am aware of that, and that's an interesting topic. But for me, in this question, I am assuming this is a "controlled file". Like a CSV database backup or large "world state" game engine data file. Something which we "reasonably trust" and hence why we are prepared to parse and interpret GBs of it. \$\endgroup\$ Jan 12 '20 at 18:30
  • 1
    \$\begingroup\$ There's the risk when pinning a thread to a CPU that some other process will also have a thread pinned to that CPU, causing your thread to take much longer to run since it could be starved for CPU time. \$\endgroup\$ Jan 12 '20 at 18:38
7
\$\begingroup\$

I hope you don't mind a pure C solution. For me it is easier to optimize code without C++ abstractions. But it should be straightforward to convert it to idiomatic C++ code.

#include <assert.h>
#include <math.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#ifdef _WIN32
#include <windows.h>
#else
#include <fcntl.h>
#include <pthread.h>
#include <sys/mman.h>
#include <sys/stat.h>
#endif

//////////////////////////////////////////////////////////////////////////////
// Range of numbers, number of numbers and number of parser threads.
//////////////////////////////////////////////////////////////////////////////
#define MIN_VALUE (1 * 1000 * 1000)
#define MAX_VALUE (2 * 1000 * 1000)
#define N_VALUES 400 * 1000 * 1000
#define N_THREADS 8

//////////////////////////////////////////////////////////////////////////////
// Timing functions.
//////////////////////////////////////////////////////////////////////////////
#define NS_TO_S(x)      ((double)(x) / 1000 / 1000 / 1000)

uint64_t
nano_count() {
#ifdef _WIN32
    static double scale_factor;
    static uint64_t hi = 0;
    static uint64_t lo = 0;

    LARGE_INTEGER count;
    BOOL ret = QueryPerformanceCounter(&count);
    if (ret == 0) {
        printf("QueryPerformanceCounter failed.\n");
        abort();
    }
    if (scale_factor == 0.0) {
        LARGE_INTEGER frequency;
        BOOL ret = QueryPerformanceFrequency(&frequency);
        if (ret == 0) {
            printf("QueryPerformanceFrequency failed.\n");
            abort();
        }
        scale_factor = (1000000000.0 / frequency.QuadPart);
  }
#ifdef CPU_64
    hi = count.HighPart;
#else
    if (lo > count.LowPart) {
        hi++;
    }
#endif
    lo = count.LowPart;
    return (uint64_t)(((hi << 32) | lo) * scale_factor);
#else
    struct timespec t;
    int ret = clock_gettime(CLOCK_MONOTONIC, &t);
    if (ret != 0) {
        printf("clock_gettime failed.\n");
        abort();
    }
    return (uint64_t)t.tv_sec * 1000000000 + t.tv_nsec;
#endif
}

//////////////////////////////////////////////////////////////////////////////
// Generate the data file.
//////////////////////////////////////////////////////////////////////////////
static int
rand_in_range(int lo, int hi) {
    int range = hi - lo;
    int val = (rand() & 0xff) << 16 |
        (rand() & 0xff) << 8 |
        (rand() & 0xff);
    return (val % range) + lo;
}

static void
run_generate(const char *path) {
    srand(1234);
    FILE *f = fopen(path, "wb");
    for (int i = 0; i < N_VALUES; i++) {
        fprintf(f, "%d\n", rand_in_range(MIN_VALUE, MAX_VALUE));
    }
    fclose(f);
}

//////////////////////////////////////////////////////////////////////////////
// Fast number parser using loop unrolling macros.
//////////////////////////////////////////////////////////////////////////////
#define PARSE_FIRST_DIGIT              \
    if (*at >= '0')         {          \
        val = *at++ - '0';             \
    } else {                           \
        goto done;                     \
    }
#define PARSE_NEXT_DIGIT               \
    if (*at >= '0') {                  \
        val = val*10 + *at++ - '0';    \
    } else {                           \
        goto done;                     \
    }

static void
parse_chunk(char *at, const char *end, size_t *accum) {
    uint64_t val = 0;
    while (at < end) {
        // Parse up to 7 digits.
        PARSE_FIRST_DIGIT;
        PARSE_NEXT_DIGIT;
        PARSE_NEXT_DIGIT;
        PARSE_NEXT_DIGIT;
        PARSE_NEXT_DIGIT;
        PARSE_NEXT_DIGIT;
        PARSE_NEXT_DIGIT;
    done:
        #ifdef _WIN32
        InterlockedExchangeAdd64(&accum[val], val);
        #else
        __sync_fetch_and_add(&accum[val], val);
        #endif
        // Skip newline character.
        at++;
    }
}

//////////////////////////////////////////////////////////////////////////////
// Thread definition
//////////////////////////////////////////////////////////////////////////////
typedef struct {
    char *chunk_start;
    char *chunk_end;
    uint64_t *accum;
} parse_chunk_thread_args;

#ifdef _WIN32
static DWORD WINAPI
parse_chunk_thread(LPVOID args) {
    parse_chunk_thread_args *a = (parse_chunk_thread_args *)args;
    parse_chunk(a->chunk_start, a->chunk_end, a->accum);
    return 0;
}
#else
static void*
parse_chunk_thread(void *args) {
    parse_chunk_thread_args *a = (parse_chunk_thread_args *)args;
    parse_chunk(a->chunk_start, a->chunk_end, a->accum);
    return NULL;
}
#endif

//////////////////////////////////////////////////////////////////////////////
// Parse the whole file.
//////////////////////////////////////////////////////////////////////////////
static bool
run_test(const char *path) {
    uint64_t time_start = nano_count();

    #ifdef _WIN32
    FILE *f = fopen(path, "rb");
    fseek(f, 0, SEEK_END);
    uint64_t n_bytes = ftell(f);
    fseek(f, 0, SEEK_SET);
    char *buf_start = (char *)malloc(sizeof(char) * n_bytes);
    char *buf_end = buf_start + n_bytes;
    assert(fread(buf_start, 1, n_bytes, f) == n_bytes);
    fclose(f);
    #else
    int fd = open(path, O_RDONLY);
    if (fd == -1) {
        return false;
    }
    struct stat sb;
    if (fstat(fd, &sb) == -1) {
        return false;
    }
    uint64_t n_bytes = sb.st_size;
    char *buf_start = mmap(NULL, n_bytes, PROT_READ, MAP_PRIVATE, fd, 0);
    char *buf_end = buf_start + n_bytes;
    #endif

    uint64_t time_read = nano_count();

    char *chunks[N_THREADS];
    for (int i = 0; i < N_THREADS; i++) {
        chunks[i] = buf_start + (n_bytes / N_THREADS) * i;
        if (i > 0) {
            // Adjust the chunks starting points until they reach past
            // a newline.
            while (*chunks[i] != '\n') {
                chunks[i]++;
            }
            chunks[i]++;
        }
    }
    uint64_t *accum = calloc(MAX_VALUE, sizeof(uint64_t));

    #if _WIN32
    HANDLE threads[N_THREADS];
    #else
    pthread_t threads[N_THREADS];
    #endif
    parse_chunk_thread_args args[N_THREADS];
    for (int i = 0; i < N_THREADS; i++) {
        char *chunk_start = chunks[i];
        char *chunk_end = buf_end;
        if (i < N_THREADS - 1) {
            chunk_end = chunks[i + 1];
        }
        args[i].chunk_start = chunk_start;
        args[i].chunk_end = chunk_end;
        args[i].accum = accum;
        #if _WIN32
        threads[i] = CreateThread(NULL, 0, parse_chunk_thread,
                                  &args[i], 0, NULL);
        #else
        pthread_create(&threads[i], NULL, parse_chunk_thread, &args[i]);
        #endif
    }
    for (int i = 0; i < N_THREADS; i++) {
        #if _WIN32
        WaitForSingleObject(threads[i], INFINITE);
        #else
        pthread_join(threads[i], NULL);
        #endif
    }
    uint64_t max = 0;
    for (int i = 0; i < MAX_VALUE; i++) {
        uint64_t val = accum[i];
        if (val > max) {
            max = val;
        }
    }
    uint64_t time_parsed = nano_count();

    free(accum);
    #if _WIN32
    free(buf_start);
    #else
    if (munmap(buf_start, n_bytes) == -1) {
        return false;
    }
    #endif

    // Print timings.
    double read_secs = NS_TO_S(time_read - time_start);
    double parse_secs = NS_TO_S(time_parsed - time_read);
    double total_secs = NS_TO_S(time_parsed - time_start);
    printf("Read  : %.3f seconds\n", read_secs);
    printf("Parse : %.3f seconds\n", parse_secs);
    printf("Total : %.3f seconds\n", total_secs);
    printf("-- Max: %zu\n", max);
    return true;
}

int
main(int argc, char *argv[]) {
    if (argc != 3) {
        printf("%s: [generate|test] path\n", argv[0]);
        return EXIT_FAILURE;
    }
    char *cmd = argv[1];
    if (strcmp(cmd, "generate") == 0) {
        run_generate(argv[2]);
    } else if (strcmp(cmd, "test") == 0) {
        if (!run_test(argv[2])) {
            printf("Test run failed!\n");
            return EXIT_FAILURE;
        }
    } else {
        printf("%s: [generate|test] path\n", argv[0]);
        return EXIT_FAILURE;
    }
    return EXIT_SUCCESS;
}

On my i7-6700 CPU desktop with 32 GB RAM, my code parses a 3.2 GB file in about 1.62 seconds and your code takes about eight seconds. I compile both programs with -march=native -mtune=native -O3

The main difference is that I'm using an array shared by all threads while you are using a hashmap for each thread. That is inefficient since the range of possible values is only one million. A hashmap would have the advantage over an array if the range of values was much larger than the number of values but that is not the case in your scenario.

The array can be concurrently modified by all threads by using locking compiler intrinsics:

#ifdef _WIN32
InterlockedExchangeAdd64(&accum[val], val);
#else
__sync_fetch_and_add(&accum[val], val);
#endif

The intrinsics ensure that the updates are atomic and that threads don't interfere with each other.

The last difference is

#define PARSE_FIRST_DIGIT              \
    if (*at >= '0') {                  \
        val = *at++ - '0';             \
    } else {                           \
        goto done;                     \
    }
#define PARSE_NEXT_DIGIT               \
    if (*at >= '0') {                  \
        val = val*10 + *at++ - '0';    \
    } else {                           \
        goto done;                     \
    }
while (buf < end) {
    // Parse up to 7 digits.
    PARSE_FIRST_DIGIT;
    PARSE_NEXT_DIGIT;
    PARSE_NEXT_DIGIT;
    PARSE_NEXT_DIGIT;
    PARSE_NEXT_DIGIT;
    PARSE_NEXT_DIGIT;
    PARSE_NEXT_DIGIT;
  done:

Here I have manually unrolled the parsing loop using macros. It improves performance by about 100 ms over your formulation when compiling with gcc.

Linux vs. Windows

On my laptop, the code runs a lot faster on Linux than on Windows. On Windows with an 1 600 MB file and 4 threads:

Read  : 1.170 seconds
Parse : 3.119 seconds
Total : 4.289 seconds
-- Max: 498631000

Same setup on Linux:

Read  : 0.000 seconds
Parse : 2.814 seconds
Total : 2.814 seconds
-- Max: 498631000
\$\endgroup\$
14
  • \$\begingroup\$ Thanks. I like the approach. You are tackling the obvious bottleneck, ie the shared state. I will look into it further. As I see (apart from the manual unrolling) you have done 2 fundamental things: 1. used shared state for summing with atomics, rather than separate + combine 2. switched to different kinds of data structure. They are connected, but fundamentally: 1. is to do with concurrency and 2 is about a universality / efficiency trade-off. ie we could do 2 in a single threaded environment and it would also be faster at the cost being less universal. Agree? \$\endgroup\$ Jan 13 '20 at 18:39
  • \$\begingroup\$ Correct. 1. I experimented with giving each thread its own array but that seemed slightly slower (and consumed 8 times as much memory). If there are lots of different numbers, contention shouldn't be bad. 2. If you know that the number of actual numbers is much smaller than the number of possible numbers, then a hashmap is better. For example, if there is only one million unique numbers, but the range is 2^64. \$\endgroup\$ Jan 13 '20 at 21:22
  • \$\begingroup\$ Firstly: I like your C-style. Nice code. Secondly: I compiled it and my original "big2" file as above runs in ~0.53s on my machine that is about 4x gain over the 8 separate bytell_hashmaps in my code. So well done #2! Thirdly I translated your idea into c++. Wasn't too hard a good exercise for me, about what you can't do with std::atomic. You can't put them in std::vectors. So I used a std::unique_ptr<std::atomic<uint64>>[1'000'001]. Thirdly you had an "off-by-one" bug in your code for values 1M -> 2M the array needs to be size=1M+1 for the orig file which includes 2M (your file=OK) \$\endgroup\$ Jan 13 '20 at 23:03
  • \$\begingroup\$ I also experimented with a single, concurrent hashmap: github.com/efficient/libcuckoo but this brought only small gains vs single-thread and was slower than the separate hashmaps and certainly slower than yours. The only slightly "unsatisfying" thing about your solution is that it assumes "A LOT" of knowledge about the file. I didn't implement the hand-unrolled-parse, because I felt it assumed too much (my C++ port of your code, is practically the same speed without it). But the assumptions about min/max and therefore map size are critical.... I guess it depends on the real scenario. \$\endgroup\$ Jan 13 '20 at 23:08
  • \$\begingroup\$ BTW the distribution of numbers and therefore concurrent access to the array is such that there is almost zero contention on the atomics. How do I know? Before I worked out how to coax the atomics out of c++ abstractions, I ran it without. Always gave the correct answer. So the chance of the clash, ie the atomic having to retry, is very very small. \$\endgroup\$ Jan 13 '20 at 23:11
4
\$\begingroup\$

C++ port of Björn's code using a single large array instead of one hashmap per thread. Björn's C code is very nice, but this question was tagged C++ so i thought it was worth showing that too. The changes from my code above are very small:

  • Using std::thread instead of std::async, because we don't need to return anything
  • Use a std::unique_ptr of std::atomic<uint64_t>[1'000'001] as the central datastructure and update with .fetch_add() (std::vector doesn't like atomics without writing wrappers). Note that Björn's array is 2M entries and mine is 1M+1, because I subtract min_val from key.
  • the zero initialisation of the array was slightly tricky to find the right syntax for. can't do it with make_unique until we get make_unique_init in c++20 so used empty brace initialisation instead, see code. --- EDIT: this is incorrect. It's not complicated. I proved that the array is always zero initialised. Both with make_unique, and with new[]{} and got a detailed explanation of the standardese here. So I have changed the code to the more idiomatic make_unique<>.
  • I didn't include Björn's hand-unrolling of the parsing. I tried limiting the loop iterations to 7, and as soon as I did that, the compiler automatically unrolled it for me. But I felt this was too restrictive on the file format and didn't provide any measurable performance benefit.

For discussion of the prons/cons of this approach see comments under Björn's answer.

Performance of this code on the yahtzee-upper-big2.txt (800MB of 100M 7digit ints with cardinality 1M+1) is ~0.55s on my machine. This is a 4x speedup against the original "1x bytell_hash_map per thread" approach at top. Putting it another way this is parsing ~1.7GB/s which is a fair clip on this old machine.

The obvious downside is that it makes assumptions about the range of ints in the input file (they must be min=1M and max=2M inclusive).

Björn put it well when he said in comments above: The global atomic array works very well when we have a relatively small range but many numbers. Whereas when we have a very large range (worst case 2^64) and not so many unique numbers (eg the original, low cardinality, "-big" file), then a hash map per thread is fastest.

EDIT: I changed the code to use std::unit32_t as the main value type in the array. Then just count each value and multiply during the final loop. This optimisation was suggested by someone else, in the previous question, but it never made a measurable difference for me. However, now that this array is central to the performance, particularly whether this array can fit in L3 cache, should make a bigger difference. At 1M * 4bytes => 4MB, it just about might and sure enough, I got a 33% performance gain. The "big2" file now runs in ~350ms, which is about 2.4GB/s.

When you have a windfall, you should treat yourself just a little, so I reintroduced some parsing checks. ie the range of the integers is now checked, so we don't access out of bounds memory for UB, and the range of characters is strictly limited to [0-9\n]. Performance is hardly affected by these "never taken" branches thanks to the CPU's branch predictor.

On the subject of: "Is this realistic? Why are you doing it cached? The disk will always be the bottleneck.": I did some quick shopping and it seems that, even as of Q4 2017, there are NVMe SSDs which do sequential reads at a blistering 1800MB/s. So it seems we need to work quite hard to stay ahead of these devices.

#include "os/fs.hpp"
#include <cstdint>
#include <future>
#include <iostream>
#include <memory>
#include <string>
#include <string_view>
#include <vector>

using val_t = std::uint32_t;

constexpr val_t      min_val  = 1'000'000;
constexpr val_t      max_val  = 2'000'000;
constexpr std::size_t map_size = max_val - min_val + 1;

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)};
}

void parse(std::string_view buf, std::atomic<val_t> map[]) {
  auto [begin, end] = from_sv(buf);
  const char* curr  = begin;
  val_t      val   = 0;
  while (curr != end) {
    if (*curr == '\n') {
      assert(min_val <= val && val <= max_val);
      map[val - min_val].fetch_add(1); // NOLINT
      val = 0;
    } else if ('0' <= *curr && *curr <= '9') {
      val = val * 10 + (*curr - '0');
    }
    ++curr; // NOLINT
  }
}

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;
}

val_t yahtzee_upper(const std::string& filename) {
  auto     mfile     = os::fs::MemoryMappedFile{filename};
  unsigned n_threads = std::thread::hardware_concurrency();
  // zero initialised via the empty {} and that's why we didn't use std::make_unique
  auto map = std::make_unique<std::atomic<val_t>[]>(map_size);
  auto     threads   = std::vector<std::thread>{};

  for (std::string_view chunk: chunk(mfile.get_buffer(), n_threads)) // NOLINT
    threads.emplace_back(parse, chunk, map.get());

  for (auto& t: threads) t.join();

  std::uint64_t max_total = 0;
  for (std::size_t i = 0; i < map_size; ++i) {
    std::uint64_t s = map[i].load() * (i + min_val);
    if (s > max_total) max_total = s;
  }
  return max_total;
}

int main(int argc, char* argv[]) {
  if (argc < 2) return 1;
  std::cout << yahtzee_upper(argv[1]) << '\n'; // NOLINT
  return 0;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.