27
\$\begingroup\$

EDIT2: There is a summary below of the findings with new improved code and run time results achieved.

Multi threaded follow up has been posted here.


I find, in my daily programming, that text-file parsing (various CSV, and ad-hoc formats etc) is still very common. When data size gets to >1MB, performance becomes a critical aspect. Reading files, parsing for separators and converting contents (often to floats or ints) can be a very slow process.

The approach was to pull in existing tools, which can help, and make them convenient, rather than to reinvent the wheel. So I have curated and written helpers for some tools to help make this process convenient while achieving very high performance.

The "Yahtzee" programming challenge shall serve as an illustrative example. Clearly this is not a real world problem, but not much imagination is required to see how it translates. Follow that link for full details, but the task is basically:

  • Read ~1MB file with about ~100,000 whitespace separated ints
  • Group them by hash map (most efficient?)
  • Find the group with the largest sum

The code below achieves complete parse and compute in < 8ms on my machine (i7 2600 with SSD) for the provided 1MB file on github. Most of that is read & parse (~7ms). This represents about a 5x gain on the "naive" approach using <iostream> or std::getline parsing and converting. (For reference the output is "31415926535" as the sum of the largest group.)

Performance techniques / tricks used are:

  • Use memory mapped file -- mmap . Wrapped in an RAII convenience class.
  • Use a piping mentality throughout. Never accumulate data.
  • Make no std::string and no copies. Use std::string_view throughout.
  • The mmap file gives a const char* buffer which we can parse over and access using std::string_view .
  • Don't use std::isnumeric because it is locale dependent. Use an optimised replacement which assumes ASCII and has knowledge about the format.
  • Use <charchonv> from_chars because it's very fast. (Only MSVC supports floats, but on gcc/clang we could use Ryu)
  • Use the awesome ska::bytell_hash_map from here
  • All the os::... utility wrappers are my own from here.
  • Compiled with clang-9 -O3 for x64. Platform is Kubuntu 19.10.

The mmap is key at this file size. It dropped time from ~38ms to 20ms immediately. (I realise that mmap is not optimal for smaller files, but those are "fast" anyway.)

skarupke's ska::bytell_hash_map is also a sigificant gain on the compute side. See here for why.

Clearly mmap is not very portable, but accepting that, does this represent about the best we can do?

Is there any other feedback about the approach or the code (including the code in os:: namespace on github link)?

EDIT: Based on some feedback, just a clarification. The 1MB is what I have found to be smallest size where this sort of approach makes sense. Of course 8ms is pretty quick. But the speedup from 40ms is still very relevant because the actual use case may involve either hundreds of such 1MB files or one much bigger file. We can make a large file with: for i in {1..1000}; do cat yahtzee-upper-1.txt >> yahtzee-upper-big.txt ; done which gives a ~1GB file. That runs in 5.8seconds on my machine. ie the whole process scales almost perfectly linearly.

The idea is not to optimise away every last cycle given the exact nature of this task/file. Because that tends to a) quickly have diminishing returns and b) remove any re-usability. Instead I am trying to get 80% of the possible speedup by using a few big tools (mmap, charconv, ska::bytell_hashmap, ...) and then make them conveniently usable for many many different kinds of parsing tasks with minimal or no code change.

#include "flat_hash_map/bytell_hash_map.hpp"
#include "os/fs.hpp"
#include "os/str.hpp"
#include <cstdint>
#include <iostream>
#include <string>
#include <string_view>

// code extracts for from os/str.hpp for hot-path 
// see github link above for complete code

namespace os::str {
namespace ascii {

inline constexpr bool isnumeric(char c) {
  return (c >= '0' && c <= '9') || c == '+' || c == '-' || c == '.' || c == ',' || c == '^' ||
         c == '*' || c == 'e' || c == 'E';
}
} // namespace ascii

/// ... skip

inline std::optional<std::string> trim_lower(std::string_view word) {
  word = trim_if(word, ascii::isalpha);
  if (!word.empty()) {
    std::string output{word};
    // tolower is redundant for this example, but not significant
    std::transform(output.begin(), output.end(), output.begin(),
                   [](auto c) { return ascii::tolower(c); });
    return std::optional<std::string>{output};
  }
  return std::nullopt;
}

template <typename ActionFunction, typename Predicate = decltype(ascii::isalpha)>
void proc_words(std::string_view buffer, const ActionFunction& action,
                const Predicate& pred = ascii::isalpha) {

  const char*       begin = buffer.begin();
  const char*       curr  = begin;
  const char* const end   = buffer.end();

  while (curr != end) {
    if (!pred(*curr)) {
      auto maybe_word =
          trim_lower(std::string_view{&*begin, static_cast<std::size_t>(curr - begin)});
      if (maybe_word) action(*maybe_word);
      begin = std::next(curr);
    }
    std::advance(curr, 1);
  }
}
} // namespace os::str

// EOF os/str.hpp

// start main code

std::uint64_t yahtzee_upper(const std::string& filename) {
  auto mfile = os::fs::MemoryMappedFile{filename};

  auto max_total = std::uint64_t{0};
  auto accum     = ska::bytell_hash_map<std::uint64_t, std::uint64_t>{};

  os::str::proc_words(
      mfile.get_buffer(),
      [&](std::string_view word) {
        auto die   = os::str::from_chars<std::uint64_t>(word);
        auto total = accum[die] += die;
        if (total > max_total) max_total = total;
      },
      os::str::ascii::isnumeric);
  return max_total;
}

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

\$\endgroup\$
  • 1
    \$\begingroup\$ Can you try to put the code in one file? It would be easier to review and benchmark that way. \$\endgroup\$ – Björn Lindqvist Jan 8 at 19:28
  • 2
    \$\begingroup\$ @BjörnLindqvist if you want something that "just compiles and runs" I have concatenated everything into one file here (3000+ lines!, because it includes the ska::hashmap): gist.github.com/oschonrock/6ee9ff225f0805d82e31351c6204c8d3 \$\endgroup\$ – Oliver Schönrock Jan 8 at 19:56
  • 2
    \$\begingroup\$ Thanks! As @butt said in the answer, it matters a lot if the file is cached or not. So when benchmarking, you need to run sync; echo 3 > /proc/sys/vm/drop_caches between runs to clear caches, otherwise you'll be measuring the wrong thing. \$\endgroup\$ – Björn Lindqvist Jan 8 at 21:12
  • 2
    \$\begingroup\$ @BjörnLindqvist I agree it matters. But I think I want it cached. I don't want to measure disk performance. I want to measure file read, parse and compute performance. So I was actively looking for OS caching..? \$\endgroup\$ – Oliver Schönrock Jan 8 at 21:13
  • 3
    \$\begingroup\$ Yes, mmap is excellent, especially for files that are hot in the pagecache. (Even if not, faultaround / speculative prefault helps). Possible downsides include not using hugepages, which might make it worse for multiple passes over the input data. Things to try: mmap(MAP_POPULATE) if your file isn't huge and you expect it to be hot in pagecache. That should wire up the page tables, avoiding soft page faults as you read it. But if it's not in RAM at all, that prevents overlapping I/O with computation on the first part of the file :/ \$\endgroup\$ – Peter Cordes Jan 9 at 7:04
22
\$\begingroup\$

Without sacrifying something, you can probably gain the most (wall time) by using a hint such as posix_fadvise(POSIX_FADV_WILLNEED). Or, if portability is not paramount, something like readahead (Windows calls that function PrefetchVirtualMemory). Be sure to read the docs and watch for words like "blocking".

The reason for wanting to prefetch is that while mmap is indeed awesome in its own way and totally superior to any I/O functions (let alone C++ iostream which is "slow" because it does a lot of stuff and is very general and flexible, it can do pretty much everything, including proper error reporting) in terms of performance, there is a huge misconception that people often fall for:

mmap is awesome, but it does not do magic.

While mmap does prefetch, the algorithm is very non-ingenious, block sizes are small (usually something like 128k), and the sequence is very non-optimal (still, much better than other I/O). Also, linear scan hints do not really do "magic" either, they usually just double the prefetch size, which is still small.

In theory, things look like this:

(OS)   read + awesome magic
(app)  work, work, work, work

In practice, things look like this:

(OS)   read               ... queue, read               ... queue, read
(app)        work, FAULT, ...              work, FAULT, ...
       ^^^^^^      ^^^^^^^^^^^^^^^^^^^^^^^       ^^^^^^^^^^^^^^^^^^^^^^^
                   nothing happens here!         nothing happens here!

Even with hinting or explicit readahead, reading from disk (or SSD) is of course still much slower than your parsing so inevitably you will stall. There is no way to avoid that. In the end, we're trying to get this:

(OS)   read, read, read, read, read, read, read
(app)        work, work, work, work, FAULT ...   work
                                     ^^^^^^^^^^^^
                                     aww too bad, can't help this!

You can't prevent yourself from eventually outrunning the disk and blocking. However, you can reduce the number of stalls, push the time of the first stall back, and you can eliminate several round trip times between requests, maximizing throughput. Certainly, prefetching a couple of megabytes in one go is more efficient (even if broken down to smaller requests at driver level) than to do a lot of small requests ad-hoc as page faults are realized with sync-points in between, which are necessarily full stalls.

Trying to tune the actual parsing is unlikely to give very substantial gains. Using a custom isnumeric as you've done is probably the single best thing to start with, but the gains beyond that won't likely be great.

The reason is that you're trying to turn the wrong knob (for the same reason, the ideology-driven environmental craze that is so much en vogue is failing). Thing is, even if you reduce something that makes up 3% of the total to one half, or eliminate it altogether, the gains are not very substantial. The gains, however, are substantial if you reduce the other 97%. Which, unluckily, is hard to do because that's forementioned disk access, followed by memory bandwidth and memory latency.

Parsing of very simple data (integers on a line), even badly implemented easily runs in the "dozen gigabyte per second" realm. Converting numbers is very fast and almost certainly hidden by memory latency.

Your CPU cache is probably not much help, and prefetching most likely will not help much either. The reason being that fetching a cache line takes something around 300-400 or so cycles, and you hardly need that much to parse the data. You're still going to be memory bandwidth bound (in addition to being I/O bound).

There's the TLB to consider, though (the CPU typically only caches ~50-60 entries). It may very much be worth it to code a "TLB primer" into the next couple of pages. That's a more or less no-op which somehow reads/accesses a memory location but doesn't use the result, and thus bears no dependency chain. The processor pipeline will thus (hopefully) make the latency invisible, but it will still do something. Very soon after, when you really access that location, it is guaranteed that no TLB miss happens and the to-be read cache line will, with some luck, already have been fetched already, too. TLB misses are painful. That's a few thousand or so cycles saved on every memory page.
You'll have to try. Be wary of page faults blocking your thread though, it might be an advantage of having a dedicated prefetcher thread (depends on cost of spawning vs. page faults, surely only worth it for larger data sets).

Doing away with the hashmap would help, but that only works if you do not actually need a map. It's a fair assumption that you do need it (or you wouldn't be using it!) so that's probably not an option. If you need something, well, then you need it. But I would really be interested in seeing what a profiler has to say about it. My uneducated guess would be 50-70% of your "parse" time being spent somewhere inside the hash map.

Hash maps are, contrary to theory, utterly bad data structures performance-wise. Not as bad as some other structures, but still...

That is also true for Robin Hood hashing (such as what's used in the implementation that you cite). While it is one of the better, and probably one of the best implementations, still it is adverse to performance.
In theory, hash maps are O(1), in practice they're some calculations plus two guaranteed cache misses on every access, and usually more. Robin Hood hashing in theory has a guaranteed upper bound, blah blah. In practice, it also has guaranteed extra accesses as data is inserted. In theory, RH hashing shows low variance and thus clusters memory accesses together in a cache-friendly manner. In practice, when you parse megabytes of data, there is no such thing as a cache. You're reading gigabytes of data, and that is what's in your cache. None of the hash map is. Every access is (except for sheer random luck!) a guaranteed miss.

There exist some very fast JSON and XML parsers which are so fast for the sole reason that they work in-place. They do zero allocations, and no jumping around in memory. Simple, sequential processing, front to back, overwriting stuff as they go. That's as good as it can get.

Note that there are a couple of possible issues with that in your simple datafile. A single digit plus newline is two bytes, but an integer is four bytes (a double is 8). So, that probably doesn't work too well for the general case in your example (your life is much easier with XML since there's lots of extra < and >s around, and a lot of other noise, so you have no trouble storing your data in-place).

Another issue is that you need a way of not modifying the mapped file. Private mapping works, of course, but that'll mark pages COW and may cause a fault with a memory copy on every modified page, depending on how intelligent the memory system is coded (private mappings actually only need to be copied when modified while there's more than one mapping). Which, if it happens, isn't precisely optimal. I wouldn't know if there is a way of somehow hinting the memory manager towards such a behavior either.
There is MADV_DONTNEED which is destructive on some platforms, so one could use that on a normal mapping, but that being destructive is not standard, not portable, and doesn't work properly (i.e. reliably) either. It might very well do something to your original file (and partly, even!) that you don't want. So that's not a real option.

In the end, you will probably either have to do a memcpy or read from a readonly mapping, and write to another linear buffer (which isn't quite in-place, but still orders of magnitude better in terms of access pattern and caching).

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ This is very good. You've understood the issues very well. Plenty of hints for me to investigate. Thank you for your time. \$\endgroup\$ – Oliver Schönrock Jan 9 at 20:33
  • 1
    \$\begingroup\$ BTW, you are right about the hash map -- not for that particular file because it has very low cardinality (< 1000 unique ints). But in general, as soon as the cardinality goes up, the hash map blows it out of the water. I always comment it out when concentrating on the reading/parsing code/pipeline. \$\endgroup\$ – Oliver Schönrock Jan 9 at 20:42
  • 2
    \$\begingroup\$ @Voo What you say is true. As someone else also pointed out <iostream> gets a lot better if you do std::ios::sync_with_stdio(false); stackoverflow.com/questions/1042110/… The approach outlined here is still ~4x faster though, but least we can outrun the disk if we turn off the sync! \$\endgroup\$ – Oliver Schönrock Jan 10 at 14:52
  • 2
    \$\begingroup\$ @Damon I can see your point, although I'd argue that people being able to do things like (while (!file.eof())) and you still needing to check return values means it's not that fool proof either. Personally I prefer say Go's approach to handling io, but they had a long time to learn from the mistakes of their predecessors. And the whole Java/.NET approach of needing several wrapper classes for optimal usage leaves a lot to be desired too. \$\endgroup\$ – Voo Jan 10 at 15:31
  • 2
    \$\begingroup\$ @OliverSchonrock: I just accidentially stumbled upon this: usenix.org/sites/default/files/conference/protected-files/… -- interesting read, in particular pages 11-16. TL;DR: Demand paging is slow. Use MAP_POPULATE, or better yet use MADV_SEQUENTIAL|MADV_WILLNEED to pre-fault. Allegedly, the latter is running highly asynchronously and is up to 38% faster with fewer page faults. Not sure what kernel versions support aggressive prefaulting, but I guess the worst thing to happen if unsupported is that it's none faster. \$\endgroup\$ – Damon Jan 10 at 16:35
11
\$\begingroup\$

You say your file contains integers only. Yet your parsing code calls trim_lower, which doesn't make sense at all.

At least I hope you implemented tolower other than in the C++ standard library, since the latter must not be called with signed char or char as argument.

The proc_words function creates lots of std::string objects internally, which is unnecessary. No wonder your code takes so long. Since numbers are not words, you are using the completely wrong tool for this job. You should rather define for_each_token instead of proc_words.

The isnumeric function is inappropriate as well. You need isdigit here.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ These are all valid points. Remember that these are a generic set of parsing tools and not 100% specialised for this file. proc_words was written for a different task originally. And yes you are right there are gains here. See my comment in @butt 's answer above. However "no wonder your code is so slow" is not reasonable. The change which eliminates the last std::string and the toupper makes a 2.8ms gain. We started at 40ms. So yes it's a good point, but it only became relevant to look at when the other 80% was done. We want re-usable component, not "last cycle optimisations". \$\endgroup\$ – Oliver Schönrock Jan 9 at 7:31
  • 1
    \$\begingroup\$ If you can suggest a generic architecture which supports a composable set of separator parsing, trimming and "munging" operators (eg tolower) which retains 80-90% of the performance of custom code, then that would be awesome. proc_words is a step in that direction, but I acknowledge it is far from complete. The other changes (eg mmap and not using <iostream> / getline) are much bigger gains. \$\endgroup\$ – Oliver Schönrock Jan 9 at 7:35
  • 2
    \$\begingroup\$ BTW did you look at the implementation of tolower it is basically return c | 0x20;. \$\endgroup\$ – Oliver Schönrock Jan 9 at 7:43
  • 2
    \$\begingroup\$ I think you are missing the point. But I assure you. Luck has nothing to do with it. \$\endgroup\$ – Oliver Schönrock Jan 10 at 1:08
  • 2
    \$\begingroup\$ You can write an efficient ASCII-only tolower that doesn't assume alphabetic to start with. It's only a couple extra operations. Using the name tolower for c|0x20 is misleading: standard C tolower is supposed to leave non-alphabetic characters unmodified. c|0x20 has its uses as a building block, e.g. for ASCII isalpha like (c|0x20) - 'a' < (unsigned)('z'-'a'). See What is the idea behind ^= 32, that converts lowercase letters to upper and vice versa? for that, and SIMD Convert a String In C++ To Upper Case \$\endgroup\$ – Peter Cordes Jan 10 at 22:41
8
\$\begingroup\$

Update

I made a bare-bones yahtzee solver with no error checking in pure C++ (no mmap). The code is considerably more complex than mmapping, but is more portable, more generic, and seems to work just fine.

With a single-producer-single-consumer pattern and 64k buffers(arbitrary) and got (0.97s):

$ /usr/bin/time -f "%e %U %S %M" ./a ~/yahtzee-upper-big.txt 
31415926535000
0.97 1.01 0.37 663528

I compared to an mmap implementation (without using the SPSC) (1.04s):

/usr/bin/time -f "%e %U %S %M" ./a ~/yahtzee-upper-big.txt 
31415926535000
1.04 0.98 0.05 884192

mmap has almost no system time while fstream does, presumably memcpying or buffering. C++/fstream has about the same latency and uses less memory, but uses much more processing time. I speculate that the lower peak memory usage is due to the system being able to page-out memory faster than mmap.

Here's the test code. It's pretty sloppy and I wasn't thinking too hard about it. It is not meant to be a reference.

#include <condition_variable>
#include <fstream>
#include <iostream>
#include <thread>
#include <vector>

auto constexpr kReadBlockSize = size_t{1ull << 15ull};

int main(int argc, char** argv) {
  if (argc != 2) return -1;

  auto input_path_argument = argv[1];
  auto file_stream = std::ifstream{input_path_argument, std::ios::binary};
  if (file_stream.bad()) return -1;

  auto mutex = std::mutex{};
  auto condition_variable = std::condition_variable{};
  auto shared_is_finished_reading = false;
  auto shared_buffer_pool = std::vector<std::vector<uint8_t>>{};
  auto shared_buffers = std::vector<std::vector<uint8_t>>{};
  auto producer_thread = std::thread{[&]() {
    auto producer_buffer = std::vector<uint8_t>{};
    while (file_stream.good()) {
      producer_buffer.resize(kReadBlockSize);
      if (!file_stream.read(reinterpret_cast<char*>(producer_buffer.data()),
                            producer_buffer.size())) {
        producer_buffer.resize(file_stream.gcount());
      }

      {
        auto lock = std::lock_guard<std::mutex>{mutex};
        shared_buffers.push_back(std::move(producer_buffer));

        if (!shared_buffer_pool.empty()) {
          producer_buffer = std::move(shared_buffer_pool.back());
          shared_buffer_pool.pop_back();
        } else {
          producer_buffer = std::vector<uint8_t>{};
        }
      }
      condition_variable.notify_all();
    }

    {
      auto lock = std::lock_guard<std::mutex>{mutex};
      shared_is_finished_reading = true;
    }
    condition_variable.notify_all();
  }};

  auto max_yahtzee_roll = 0ull;
  auto consumer_buffers = std::vector<std::vector<uint8_t>>{};
  auto is_finished_reading = false;
  auto current_parsed_value = 0;
  auto occurrance_counts = std::vector<uint32_t>();

  while (!is_finished_reading) {
    {
      auto lock = std::unique_lock<std::mutex>{mutex};
      condition_variable.wait(lock, [&]() {
        return !shared_buffers.empty() || shared_is_finished_reading;
      });

      is_finished_reading = shared_is_finished_reading;
      shared_buffer_pool.insert(
          shared_buffer_pool.end(),
          std::make_move_iterator(consumer_buffers.begin()),
          std::make_move_iterator(consumer_buffers.end()));
      std::swap(shared_buffers, consumer_buffers);
    }

    for (auto& buffer : consumer_buffers) {
      for (auto c : buffer) {
        if (auto digit_value = c - '0'; digit_value >= 0 && digit_value <= 9) {
          current_parsed_value *= 10u;
          current_parsed_value += digit_value;
        } else {
          if (occurrance_counts.capacity() <= current_parsed_value) {
            occurrance_counts.reserve(2ull * current_parsed_value + 1ull);
          }
          auto current_value_count = ++occurrance_counts[current_parsed_value];
          max_yahtzee_roll = std::max<uint64_t>(
              max_yahtzee_roll,
              (uint64_t)current_value_count * current_parsed_value);
          current_parsed_value = 0;
        }
      }
    }
  }

  std::cout << max_yahtzee_roll << std::endl;

  producer_thread.join();
  return 0;
}


The internet tells me a typical SSD might read at 500MB/s, which is 0.5MB/ms or 1M in 2ms. 8ms is incredibly fast and also very close to the theoretical limit. In fact, just reading that file on a HDD is probably slower.

The parsing code is doing a lot of unnecessary work if you're positive that the input will always be an int-per-line.

You're accumulating the hash table by adding the value, but you actually only need to store the occurrence count since the total can be derived from the count and the key. You could store 4 byte ints instead of 8 bytes if there's only 100,000 values with a max value of 999,999,999, reducing the hash table size, though it's already so small this probably won't matter.

You could reserve hash table space, though you might not want to reserve too much.

You could try passing flags to the mmap to notify the os that it will be read sequentially and all the file will be read, or try to prefetch memory.

You can skip updating the table if the current value cannot possibly be higher than the current max. For example, if a 1 is read in and the current max total is over 100,000 there's no possible way for 1s to be the highest number class so they don't need to hit the hash table.

For small sets of data, an array might be faster than the hash map.

You could maybe use multiple threads, but that could be challenging on small data sets to overcome the overhead of just creating them.

At this point you could also hand optimize the parsing. Consider that the file, if well formed, will have a strict pattern of ([0-9]+\n)+. So it could be a loop that reads a byte, multiplies the current value by 10 and adds the new value - '0', or consumes the current value if it's a \n.

Maybe play with compile flags too, in particular things that might make the code load faster, perhaps reducing the executable size so there's less to load.

The hash map probably allocates heap memory, but if you made it use a giant chunk of 0-initialized global memory, that might be faster since it skips an allocation and should instead come free when the program launches.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Comments are not for extended discussion; this conversation has been moved to chat. \$\endgroup\$ – Jamal Jan 12 at 6:40
4
\$\begingroup\$

Build a userland threaded prefetch

In addition of Damon excellent answer, I would like emphasize this: trying to add any optimization only to be limited by disk throughput is a waste of time.

It's something that's hard to see and even harder to believe. And so this answer.

Your desktop machine probably has more than one CPU, and certainly any server your code may run will be by dozen of CPUs by now.

So a portable solution the get 80% of that critical performance is to code a threaded file prefetcher. Say, a separate thread dedicated to read N sequencial pre-allocated buffers of M size, while the parsing occurs in another thread.

N and M are left for your experimentation because you most probably will discover the parsing thread will be starving most of time, even after tweaking these numbers. This is even more true in the world of SSD drivers, where scheduling disk reads in parallel does not have a dramatic effect anymore.

You can add a alert into the prefetcher to warn about a full buffers situation, and only when worry about parser or processing optimization.

Then build a thread parser

Every ms spend in reading is a ms wasted in parsing. And other ms wasted in processing.

Leave your specific code simple and readable, but a thread parser, with small data accumulation may be a significant improvement.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Yes, this is true. And that is part of why mmap brings benefits, because (without having to code it ourselves), the kernel is working alongside the userland code (pre-)fetching the data. mmap scheduler won't be ideal hence Damon's and other's suggestions above trying to tune it -- I am yet to see a benefit from that. I am getting >400MB/s parsing now. Which is close to the disk speed, but I am not convinced that my SSD is the bottleneck. Because the 1GB file should be cached after the first run (16GB ram). \$\endgroup\$ – Oliver Schönrock Jan 10 at 16:31
  • 2
    \$\begingroup\$ You may be not convinced that disk is you bottleneck, but consider this: every ms spend in reading is a wasted ms of parsing plus a wasted ms of processing. If you a are close to the disk limit anyway, the best bang for you buck is simple: threads. \$\endgroup\$ – André LFS Bacci Jan 10 at 17:33
  • 1
    \$\begingroup\$ Threads for what? Parsing? If I comment out the parsing (just a placebo XOR to prevent the code disappearing), I get >1GB/sec (0.8s for 900MB file -- down from 2s). That is at 2x disk speed, so this is not about that. A 2x gain is possible before hitting wall with mmap. But only by radically refactoring the parsing code or using threads for that (and that will introduce massive memory/cache contention)..... I would stop here TBH. \$\endgroup\$ – Oliver Schönrock Jan 10 at 17:40
  • 1
    \$\begingroup\$ Updated answer. Two (additional) threads. One for reading, other for parsing (with I believe is general in your case). Leave your specific code simple. The threaded parser produces a single linked list of parsed data to the processing code to pull and slab free. \$\endgroup\$ – André LFS Bacci Jan 10 at 17:54
  • \$\begingroup\$ (Down-voters please comment.) \$\endgroup\$ – greybeard Jan 10 at 18:25
3
\$\begingroup\$

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: Embarrassingly parallel? Memory locality / bus or L1/L2/L3 cache size for hashmap are the limits to scalability -- not sure.

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.

#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(
          [](const char* begin, const char* const end, ska::bytell_hash_map<T, T>& map) {

            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;
            }
          },
          begin, end, std::ref(maps[i])));
    }
  }
  {
    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;
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Comments are not for extended discussion; this conversation has been moved to chat. \$\endgroup\$ – Jamal Jan 12 at 6:40
  • \$\begingroup\$ @Jamal Most of the value of this question and its answers is in the comments. If you can't see that, then either you need to modify your "policy" or we need to use a different platform to share and create value... \$\endgroup\$ – Oliver Schönrock Jan 12 at 11:34
  • 1
    \$\begingroup\$ That's a Stack Exchange wide policy, not mine specifically. Comments aren't meant for this exact purpose, hence the applicable tools for moving comments to chat. Implementation of this can be found here. \$\endgroup\$ – Jamal Jan 13 at 5:40
  • \$\begingroup\$ @Jamal I understand that. It is about the interpretation (!) of the policy. IMO 80% of the value of this page is in the comments. Very few people wrote answers. Some of the best "partial answers" are in comments. The comments discuss the trade-offs, because there is no "one answer". Non trivial questions tend to work like this. By moving the comments to chat you have significantly reduced the value of the page for everyone involved, the whole community and stack exchange. \$\endgroup\$ – Oliver Schönrock Jan 13 at 7:09

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.