Return to Revisions

I am going to try to summarise and incorporate some findings from the very good and lively discussion in the comments above. I have put together a "best case". "Best" without going "totally silly", ie no custom SIMD ASM or anything.

• If the file is OS-cached in RAM the mmap can go very very fast. I have measured up to 7GB/s (140ms for 1GB file). Just with a pointer spinning over the whole file and taking an 8-bit XOR parity checksum.
• If I take a copy of the 1GB file into a string first and then spin over over it, I get about 14GB/s (70ms for 1GB file). That's about my RAM bandwidth since this is an old machine and only has DDR3-1600 memory.
• But is doing no work at all really. Getting to anywhere near that speed in parsing ints is going to be very very hard. Only with SIMD and then totally custom.
• The code below is a tight loop which an exact file format, not negative ints, no illegal chars etc. It cuts out charchonv, my minimal isdigit/isnumeric etc. It's pretty much the tightest loop I can invisage without spending too much time on it. And totally not error tolerant obviously.
• It achieves 1GB/s. Which is 1/7th of what the mmap can give me with an OS cached file and a little over 2x disk speed (should the disk get involved).
• Obviously, at this point, the hashmap is gone so we are not even meeting the spec anymore. Putting it back and finding the group for biggest total as per spec, slows us down to 1.7s or ~530MB/s. (Note this is a very low cardinality file with < 1000 unique ints).

We might be able to use multiple threads/cores to parse and process the ints, but the synchronisation on the hash_map and also the contention on the memory bus will likely affect us quite badly.

So, task can be "just about reasonably" done at 530MB/s or 1.7s for the 1GB file or about 2ms (plus probably some overhead there) for the small 1MB file which they gave in the reddit post.

Thanks everyone. I learnt a few more tricks.

#include "flat_hash_map/bytell_hash_map.hpp"
#include "os/fs.hpp"
#include <cmath>
#include <cstdint>
#include <iostream>

template <typename T>
T yahtzee_upper(const std::string& filename) {
  auto mfile  = os::fs::MemoryMappedFile{filename};
  auto buffer = mfile.get_buffer();
  const char*       begin = buffer.begin();
  const char*       curr  = begin;
  const char* const end   = buffer.end();

  auto dist = ska::bytell_hash_map<T, T>{};
  auto val = T{0};
  auto max_total = T{0};
  while (curr != end) {
    if (*curr == '\n') {
      auto total = dist[val] += val;
      if (total > max_total) max_total = total;
      val = 0;
    } else {
      val = val * 10 + (*curr - '0');
    }
    ++curr;
  }
  return max_total;
}

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

EDIT: I worked on a threaded parser. Simple implementation below. I am far from a concurrency expert, so bear with me. No locks or atomics. Doesn't need it. "Wait-free", is that what they say? Memory locality / bus are the limits to scalability.

Output and simple performance stats below (baseline from above is 1.7s single threaded for the same work, and 140ms of "overhead" to spin through the mmap'd file with no work):

4 threads:

spawn=0.218369ms
work=680.104ms
finalise=0.17976ms
8605974989487699234

6 threads

spawn=0.451396ms
work=437.958ms
finalise=0.151554ms
8605974989487699234

8 threads:

spawn=0.441865ms
work=390.369ms
finalise=0.202808ms
8605974989487699234

Pretty happy with sub 400ms? Any feedback on the concurrent code warmly welcome. Is there a cleaner way to pass and/or return from the threads?

#include "flat_hash_map/bytell_hash_map.hpp"
#include "os/bch.hpp"
#include "os/fs.hpp"
#include <cstdint>
#include <iostream>
#include <string>
#include <thread>
#include <vector>

template <typename T>
T yahtzee_upper(const std::string& filename) {
  auto mfile     = os::fs::MemoryMappedFile{filename};
  auto max_total = std::int64_t{0};

  const unsigned n_threads = std::thread::hardware_concurrency();
  auto           threads   = std::vector<std::thread>{};
  auto maps = std::vector<ska::bytell_hash_map<T, T>>{n_threads, ska::bytell_hash_map<T, T>{}};
  std::cout << n_threads << " threads" << "\n";
  {
    auto tim = os::bch::Timer("spawn");
    auto        chunk = std::ptrdiff_t{(mfile.end() - mfile.begin()) / n_threads};
    const char* end   = mfile.begin();
    for (unsigned i = 0; end != mfile.end() && i < n_threads; ++i) {
      const char* begin = end;
      end               = std::min(begin + chunk, mfile.end());

      while (end != mfile.end() && *end != '\n') ++end; // ensure we have a whole line
      if (end != mfile.end()) ++end;                    // one past the end

      threads.push_back(std::thread(
          [&maps](int id, const char* begin, const char* const end) {
            auto& map = maps[id];

            const char* curr = begin;
            auto        val  = std::int64_t{0};
            while (curr != end) {
              if (*curr == '\n') {
                map[val] += val;
                val = 0;
              } else {
                val = val * 10 + (*curr - '0');
              }
              ++curr;
            }
          },
          i, begin, end));
    }
  }
  {
    auto tim = os::bch::Timer("work");
    for (auto&& t: threads) t.join();
  }
  {
    auto tim       = os::bch::Timer("finalise");
    auto final_map = ska::bytell_hash_map<T, T>{};

    for (auto&& m: maps) {
      for (auto p: m) {
        std::int64_t total = final_map[p.first] += p.second;
        if (total > max_total) max_total = total;
      }
    }
  }
  return max_total;
}

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