在一个线程上删除具有数百万个字符串的大型哈希图会影响另一个线程的性能

Question

所以我有这个 C++ 程序，它基本上解析巨大的数据集文件并将内容加载到内存中的 hashmap 中（这部分在主线程中受到限制，所以它永远不会占用大量时间）。完成后，我将指针翻转到新的内存位置，并对旧的内存位置调用 delete。除此之外，程序通过在内存映射（在主线程上）中查找内容来进行传入请求匹配。假设那些巨大的地图被包裹在Evaluator类中：

Evaluator* oldEvaluator = mEvaluator;
Evaluator* newEvaluator = parseDataSet();
mEvaluator = newEvaluator;
delete oldEvaluator;

//And then on request processing:
mEvaluator.lookup(request)

映射可以包含数百万个字符串对象作为键。它们是常规字符串，可以是 ip、UserAgent 等请求属性，但每个字符串都是插入到 STL unordered_map 中的字符串对象。

数据集会定期更新，但大多数情况下，程序只是对内存中的数据集进行请求属性匹配，它很好，高效且没有错误，除非发生新数据集的批量消耗。使用这个大型数据集的另一种方法是使用流，但这是一个相对长期的解决方案。

它曾经是一个使用事件驱动模型的单线程程序，但是每次放置一个完整的新集合并调用销毁时，删除整个事物花费的时间太长，从而阻塞了请求处理。

所以我把这种地图的删除放到了一个单独的线程上。问题是现在删除和请求处理似乎同时发生，我可以看到请求处理线程非常明显，急剧放缓。

当然，主机上还有其他进程在运行，我确实希望这 2 个线程竞争 CPU 周期。但我没想到请求匹配线程会大幅放缓。平均而言，一个请求应该被处理 500us 级别，但是当删除线程正在运行时，它会慢到 5ms。有时 cpu 会中断匹配的线程（因为它花费的时间太长），它可能会持续 50 毫秒，或 120 毫秒等。在极端情况下，一个请求可能需要整个 1000 毫秒来处理，这大约是整个时间数据结构删除需要另一个线程。

了解这种减速的根本原因的最佳方法是什么？它更像是 CPU 还是内存带宽瓶颈？我想象着只要我把它放在一个单独的线程上，我就不会在乎它有多慢，因为它毕竟必须一个一个地删除字符串对象，所以我没想到它会影响另一个线程......

编辑：多亏了一些评论/答案似乎已经指出了几个可能的原因：

1. 内存碎片。因为不太常访问的字符串存储在更昂贵的内存位置（因此缓存未命中），或者因为它存储在具有许多指针的 unordered_map 中，或者因为系统在执行内存压缩的同时删除所有地方的孔？但是为什么这会影响另一个线程的缓慢？
2. 一条评论提到这是由于线程安全锁定导致的堆争用？所以这个程序的整个堆都锁定了，因为一个线程正忙于删除阻止另一个线程访问堆内存的漏洞？为了澄清一下，该程序故意从不分配东西并同时释放其他东西，并且它只有 2 个线程，一个专用于删除。

那我该怎么办呢？我试过Jemalloc虽然不确定我是否完全正确地使用了它——它似乎包含-ljemalloc在链接器行中只是神奇地替换了 libc 的 malloc？我试过了，没有性能差异，但我可能用错了。我的程序没有做任何显式的 malloc，一切都是new事先未知大小，并与指针和 STL 映射连接在一起。

而且所有存储在Key中的字符串都专门用于快速查找，因此它们不能存储在带有索引的向量中，即使这会产生连续的内存空间，定位它们也会很糟糕。所以，

1. 我如何才能确定上述 2 个内存问题是原因（任何工具/指标？）
2. 在不将消费模型更改为流媒体的情况下，我可以做些什么来修复它？假设根本原因是上述 2，似乎我应该做两件事之一/两件事：1）分配我所有的 STL 映射以及所有来自一个池的对象？我怎么做？2）减少堆争用（我不知道Jemalloc在我的情况下是否解决了这两个问题）

Answer 1

std::string为所有合并的数据只存储一个并std::string_view在地图中使用可能是值得的。这消除了互斥量争用，因为只需要一个内存分配。string_view有一个简单的析构函数，所以你不需要线程。

我以前成功地使用过这种技术将程序加速了 2500%，但这也是因为这种技术减少了总内存使用量。

Answer 2

因此，由于给出的所有答案和评论，我无法选出最好的答案，因为问题本身很模糊，而且没有一个答案真正涵盖了所有内容。但我确实从这些答案中学到了很多东西，因此对其中的大多数都投了赞成票。经过各种实验，我发现主要问题是：

1. 删除线程操作缓慢的原因会影响另一个原因。鉴于它不会在两个线程上同时执行 malloc/dealloc，因此不应存在任何堆争用，也不应出现一般 CPU 或可用内存的瓶颈，唯一合理的解释是内存带宽耗尽。我发现另一篇文章的答案说：it's generally possible for a single core to saturate the memory bus if memory access is all it does.我的所有删除线程所做的就是遍历一个巨大的地图并删除其中的每个元素，因此可以想象它会使内存总线饱和，因此正在执行内存访问和其他计算的另一个线程会大大减慢向下。从这里开始，我将重点关注删除速度缓慢的各种原因

2. 该地图非常庞大，有数百万个元素，大小数百兆字节。删除它们中的每一个都需要先访问它们，而且显然很少有它们甚至可以放入 L1/L2/L3 缓存。因此存在大量的缓存未命中和从 RAM 中获取的情况。

3. 正如这里提到的几个答案/评论，我将std::string对象存储在地图中。每一个都分配有自己的空间，必须一一取出和删除。MSalters 的建议通过存储 在 map 中，同时将每个字符串的实际字节内容存储在预先分配的连续内存块中，可以更好地提高性能。string_view现在，删除映射中的一百万个对象几乎变成了对string_view仅是指针的对象的微不足道的破坏，并且所有字符串内容的破坏都是对预分配块的破坏。

4. 我没有在程序的其他部分提到我还在其他映射中存储其他 C++ 对象。他们同样也有问题。对此类 C++ 对象进行类似的“扁平化”是必要的，尽管如果没有像string_view. 这个想法是，如果我们可以存储尽可能多的原始类型和指针，并将所有内容（其中大多数可以归结为字符串）放在连续的字节缓冲区中。让一切变得微不足道，去摧毁才是目标。

5. 最后，事实证明，地图容器本身的销毁成本可能相当高，尤其是当它很大时。对于基于节点的std 容器，遍历和删除每个节点句柄需要时间。我发现真正平面哈希图的替代实现将使删除速度更快。此类映射的示例包括Abseil flat_hash_map和该博主的 flat_hash_map。请注意，尽管它们是平坦的，但它们都是真正的 hash_map。Boost 的flat_map也可以非常快地删除，但它不是真正的 hashMap，它由严格排序的向量支持，这使得插入（当我的输入未排序时）非常慢。