High performance txt file parsing

Question

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

Answer 1

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).

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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