高性能txt文件解析

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

#1 楼

在不牺牲任何内容的情况下，您可能可以通过使用诸如posix_fadvise(POSIX_FADV_WILLNEED)之类的提示来获得最多的（墙上时间）。或者，如果可移植性不是最重要的，则类似readahead（Windows调用该函数PrefetchVirtualMemory）。请务必阅读文档并注意“ blocking”之类的词。

要预取的原因是，尽管mmap确实以其自身的方式很棒，并且完全优于任何I / O功能（更不用说C ++ iostream了，它“慢”，因为它做很多事情，并且非常通用和灵活，就性能而言，它几乎可以做所有事情，包括适当的错误报告），这是一个很大的误解，人们常常会迷上它：

mmap很棒，但是却没有魔术效果。

mmap确实可以预取，但算法非常精巧，块大小很小（通常约为128k） ），并且序列非常不理想（仍然比其他I / O更好）。另外，线性扫描提示也不是真正的“魔术”工具，它们通常只是预取大小的两倍，而预取大小仍然很小。

理论上，事情看起来像这样：

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

实际上，情况看起来像这样：

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

即使有提示或显式的预读，从磁盘（或SSD）读取也是当然，解析仍然比解析慢得多，因此不可避免地会停滞。没有办法避免这种情况。最后，我们试图获得此结果：

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

您无法阻止自己最终超出磁盘并阻塞磁盘。但是，您可以减少停顿数，将第一个停顿的时间推迟，并且可以消除两次​​请求之间的往返时间，从而最大程度地提高吞吐量。当然，一次预取几兆字节的效率（即使在驱动程序级别分解为较小的请求）也比临时执行许多小的请求要高效，因为页面错误是通过它们之间的同步点实现的，即一定是满档。

尝试调整实际的解析不太可能带来可观的收益。使用自定义的isnumeric可能是一开始的最佳选择，但是超出此范围的收益可能不会很大。

原因是您正试图改变错误的旋钮（出于同样的原因，引起人们广泛关注的意识形态驱动的环境狂热正在失败）。事实是，即使您将占总数3％的东西减少到一半，或者完全消除了，收益也不是很大。但是，如果减少其他97％，则收益是可观的。不幸的是，这很难做到，因为这是前面提到的磁盘访问，其次是内存带宽和内存延迟。

解析非常简单的数据（一行上的整数），即使执行不当也很容易在“每秒十亿字节”的领域。转换数字的速度非常快，并且几乎可以肯定它被内存延迟所掩盖。

您的CPU缓存可能没有多大帮助，而预取也无济于事。原因是获取缓存行大约需要300-400个周期，而且您几乎不需要那么多数据来解析数据。您仍然会受到内存带宽的约束（除了受I / O约束）。

还有一些要考虑的TLB（CPU通常仅缓存约50-60个条目）。在接下来的几页中编写“ TLB入门”可能是非常值得的。那是一个或多或少的无操作，它以某种方式读取/访问内存位置，但不使用结果，因此不包含任何依赖链。因此，处理器管道将（希望）使延迟不可见，但仍会做一些事情。此后不久，当您真正访问该位置时，可以确保不会发生TLB遗漏，并且将要获取运气的情况下，已经读取了待读取的缓存行。 TLB错过很痛苦。每个内存页面上保存了大约数千个周期。
您必须尝试。但是要警惕页面错误会阻塞线程，使用专用的预取器线程可能是一个优点（取决于生成错误和页面错误的成本，肯定只适合较大的数据集）。

取消哈希图会有所帮助，但这仅在您实际上不需要地图时才起作用。一个公平的假设是您确实需要它（或者您不会使用它！），因此这可能不是一个选择。如果您需要一些东西，那么就需要它。但我真的很想知道探查者对此有何评论。我没有根据的猜测是，您的“解析”时间中有50-70％的时间花在了哈希图内。

与理论相反，哈希图在性能方面完全是不良的数据结构。不像其他结构那么糟糕，但是......

对于Robin Hood哈希（例如引用的实现中使用的东西）也是如此。尽管它是更好的实现之一，并且可能是最好的实现之一，但它仍然对性能不利。
理论上，哈希映射为O（1），实际上它们是一些计算加上两个保证的高速缓存未命中每次访问，通常更多。从理论上讲，罗宾汉散列具有一定的上限，等等。实际上，它还保证了在插入数据时的额外访问。从理论上讲，RH哈希显示出较低的方差，因此以缓存友好的方式将内存访问聚集在一起。实际上，当您解析兆字节的数据时，没有诸如高速缓存之类的东西。您正在读取千兆字节的数据，这就是缓存中的内容。没有一个哈希映射。每次访问都是（除了绝对的随机运气之外）一定会错过。

存在一些非常快速的JSON和XML解析器，它们之所以如此之快是因为它们可以就地工作。它们执行零分配，并且不会在内存中跳来跳去。简单，顺序的处理，从前到后，覆盖现有内容。那样就可以了。

请注意，简单数据文件中可能存在一些问题。一位数字加换行符是两个字节，但整数是四个字节（double为8）。因此，对于您的示例中的一般情况而言，这可能不太理想（使用XML会使您的工作变得容易得多，因为周围有很多额外的<和>，以及许多其他噪音，因此您可以轻松存储自己的数据）。

另一个问题是您需要一种不修改映射文件的方法。当然，私有映射可以工作，但是会标记页面为COW，并且可能会导致每个修改的页面上的内存副本出现故障，具体取决于内存系统的编码方式（实际上，仅当修改了私有映射时，才需要复制私有映射）。一个以上的映射）。如果发生的话，那并不是最佳选择。我也不知道是否有某种方式可以暗示内存管理器出现这种行为。
有MADV_DONTNEED在某些平台上具有破坏性，因此可以在正常映射中使用它，但具有破坏性它不是标准的，也不是便携式的，并且也不能正常（即可靠地）工作。它可能会对您不想要的原始文件（甚至部分！）做一些您不想要的事情。因此，这不是一个真正的选择。

最后，您可能必须做一个memcpy或从一个只读映射中读取，然后写入另一个线性缓冲区（位置不太正确） ，但在访问模式和缓存方面仍然好几个数量级。

#2 楼

您说您的文件仅包含整数。但是您的解析代码调用trim_lower，这根本没有任何意义。

我希望您实现的不是C ++标准库中的tolower，因为不得使用signed char或char调用后者。作为参数。

proc_words函数在内部创建许多std::string对象，这是不必要的。难怪您的代码要花这么长时间。由于数字不是单词，因此您使用的是完全错误的工具。您应该定义for_each_token而不是proc_words。

isnumeric函数也不适合。您需要在这里isdigit。

#3 楼

更新


我制作了一个简单的yahtzee求解器，在纯C ++中没有错误检查（没有mmap）。该代码比mmapping复杂得多，但是更可移植，更通用，并且似乎可以正常工作。

具有单一生产者-单消费者模式和64k缓冲区（任意），并且（0.97s）：

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

我与mmap实现（不使用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几乎没有系统时间，而fstream却有系统时间，大概是memcpying或缓冲。 C ++ / fstream具有大致相同的延迟，并使用较少的内存，但使用更多的处理时间。我推测较低的峰值内存使用率是由于系统能够比mmap更快地调出内存。这是测试代码。这是很草率的，我并没有在想这个。

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

互联网告诉我，典型的SSD可能以500MB / s的速度读取，即0.5MB / ms。或1ms in 2ms。 8ms非常快，并且也非常接近理论极限。实际上，仅读取HDD上的文件可能会更慢。

如果您确定输入始终是每行int，则解析代码将执行许多不必要的工作。

您正在积累哈希通过添加值在表中，但是实际上您只需要存储出现次数，因为总数可以从计数和键中得出。如果只有100,000个值（最大值为999,999,999个），则可以存储4个字节的整数，而不是8个字节，这减小了哈希表的大小，尽管它已经很小，所以可能无关紧要。

您可以保留哈希表空间，尽管您可能不想保留太多。

您可以尝试将标志传递给mmap以通知os它将被读取按顺序读取所有文件，或尝试预取内存。

如果当前值不能大于当前最大值，则可以跳过更新表。例如，如果读入1，而当前的最大总数超过100,000，则不可能将1设为最高数字类，因此它们不需要访问哈希表。

对于少量数据，数组可能比哈希映射更快。

您可能会使用多个线程，但是在小型数据集上克服仅创建它们的开销可能会遇到挑战。

此时，您还可以手动优化解析。考虑到文件如果格式正确，将具有（[0-9] + \ n）+的严格模式。因此，这可能是一个循环，它读取一个字节，将当前值乘以10，然后添加新值-'0'，或者如果它是\ n，则消耗当前值。

也许可以编译一下标志也是如此，特别是可能使代码加载速度加快的事情，可能会减小可执行文件的大小，从而减少了加载量。

哈希映射可能会分配堆内存，但是如果您使用大块的0初始化的全局内存，那可能会更快，因为它会跳过分配，而应该在程序启动时释放。

#4 楼

构建用户级线程预取

除了Damon出色的答案外，我想强调一下：尝试添加仅受磁盘吞吐量限制的任何优化都是浪费时间。

这是很难看甚至难以相信的事情。所以这个答案就这样。

您的台式机可能有多个CPU，并且现在您的代码可以运行的任何服务器肯定会由数十个CPU组成。

便携式解决方案，获得关键性能的80％是编写线程文件预取器。假设有一个单独的线程专用于读取N大小的M顺序预分配缓冲区，而解析发生在另一个线程中。

N和M留给您进行实验，因为您最有可能会发现解析即使调整了这些数字，大多数时间线程也会饿死。在SSD驱动程序的世界中，情况更是如此，在这种情况下，并行调度磁盘读取不再具有显着效果。

您可以在预取器中添加警报，以警告缓冲区已满，并且仅在担心解析器或处理优化时才使用。

然后构建线程解析器

每花费一毫秒的阅读时间，就浪费了解析的时间。

使您的特定代码简单易读，但是具有少量数据累积的线程解析器可能会带来重大改进。

#5 楼

我将尝试在上面的评论中总结并结合来自非常好而生动的讨论的一些发现。我整理了一个“最佳案例”。 “最佳”，而不会“完全傻”，即没有自定义SIMD ASM或其他任何东西。


如果文件在OS中缓存在RAM中，则mmap可以非常快速地运行。我测得的速度高达7GB / s（1GB文件为140ms）。只需指针旋转整个文件并进行8位XOR奇偶校验和即可。
如果我先将1GB文件的副本复制到字符串中，然后将其旋转，则速度约为14GB / s（1GB文件为70ms）。那是关于我的RAM带宽，因为这是一台旧机器，只有DDR3-1600内存。
但实际上根本没有任何工作。在解析int时要达到这样的速度将非常困难。仅使用SIMD
，然后完全自定义。
下面的代码是一个紧密循环，精确的文件格式，没有负整数，没有非法字符等。它剪切出charchonv，我的最小isdigit / isnumeric等。这几乎是我可以不花钱就可以看到的最紧密循环很多时间。而且完全不容错。
它达到1GB / s。这是mmap可以为我提供的操作系统缓存文件和2倍多的磁盘速度（如果要使用磁盘的话）所能提供的功能的1/7。
显然，在这一点上，哈希图不见了，所以我们什至不符合规范。放回原处，并根据规格找到最大的组，会使我们降至1.7s或〜530MB / s。 （请注意，这是基数非常小的文件，具有<1000个唯一整数）。

我们也许可以使用多个线程/核来解析和处理int，但是hash_map上的同步以及内存总线上的争用可能会严重影响我们。

因此，对于1GB文件，任务可以以530MB / s或1.7s的速度“合理地”完成，而对于1MB的小文件，则大约需要2ms（加上一些开销）。 reddit帖子。

谢谢大家。我学到了更多技巧。

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

编辑：我研究过线程分析器。下面的简单实现。我距离并发专家还很远，所以请多多包涵。没有锁或原子。不需要：令人尴尬的并行吗？哈希映射的内存位置/总线或L1 / L2 / L3高速缓存大小是可伸缩性的限制-不确定。

下面的输出和简单性能统计信息（上面的基准是相同线程的1.7s单线程工作，并且140ms的“开销”无功通过mmap文件旋转）：

4个线程：

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

6线程

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

8个线程：

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

400毫秒以下的时间很满意吗？热烈欢迎对并发代码的任何反馈。

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