在一个线程上删除具有数百万个字符串的大型哈希映射会影响另一个线程的性能
Deleting large hashmaps with millions of strings on one thread affects performance on another thread
所以我有这个 C++ 程序，它基本上解析巨大的数据集文件并将内容加载到内存中的 hashmap 中（这部分在主线程中受到限制，所以它永远不会消失占用大量时间的方式）。完成后，我将指针翻转到新的内存位置，并对旧内存位置调用 delete。除此之外，该程序通过在内存映射（在主线程上）中查找内容来进行传入请求匹配。假设那些巨大的地图被包裹在 Evaluator class:
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 还是内存带宽瓶颈 ？我在想象只要我把它放在一个单独的线程上我就不会在意它有多慢因为它毕竟必须一个一个地删除字符串对象，所以我没想到它会影响另一个线程......
编辑：感谢夫妇 comments/answers 似乎已经指出了几个可能的原因：
- 内存碎片。因为不常访问的字符串存储在更昂贵的内存位置（所以缓存未命中），或者因为它存储在 unordered_map 中有很多指针，或者因为系统在压缩内存的同时到处删除空洞？但为什么这会影响另一个线程的缓慢？
- 一条评论提到它是由于线程安全锁定导致的堆争用？所以这个程序的整个堆都被锁定了，因为一个线程正忙于删除阻止另一个线程访问堆内存的漏洞？澄清一下，该程序故意从不分配东西并同时释放其他东西，它只有 2 个线程，一个专门用于删除。
那我该怎么办呢？我尝试了 Jemalloc，但不确定我是否完全正确地使用了它 --- 似乎在链接器行中包含 -ljemalloc 只是神奇地替换了 libc 的 malloc？我试过了，没有性能差异，但我可能用错了。我的程序没有执行任何明确的 malloc，所有内容都是 new，大小事先未知，并与指针和 STL 映射连接在一起。
并且存储在 Key 中的所有字符串都专门用于快速查找，因此它们不能存储在带有索引的向量中，即使这会使内存连续 space，找到他们将是可怕的。所以，
- 我如何才能确定以上 2 个内存问题的原因（任何 tools/metrics？）
- 在不将我的消费模式更改为流媒体的情况下，我该怎么做才能解决这个问题？假设根本原因是上述 2 个，似乎我应该做 either/both 两件事：1) 从一个池中分配我所有的 STL 映射以及所有对象？我怎么做？ 2) 减少堆争用（我不知道
Jemalloc 是否解决了我的情况）
您可以尝试使用std::vector来存储内存。 std::vector 元素连续存储，因此会减少缓存未命中（参见 What is a "cache-friendly" code?）
所以你将有一个 map<???,size_t> 而不是 map<???,std::string> 你将有一个间接的方式来获取你的字符串（这意味着额外的 运行 时间成本）但它允许你以更少的缓存未命中方式迭代所有字符串。
这将是一个冗长的答案，因为你的问题非常复杂。
读取程序
当您阅读某些内容时，您会开始为您的应用程序分配内存。现在这在正常情况下是可以的，当您不需要性能时，问题就开始了。
STL maps是红黑树所以有很多指针，这意味着每个元素都是单独分配的，这会造成你的内存space非常碎片化，很难系统有效地释放元素。原因：系统必须遵循指针。
合适的容器
STL地图说明：
Why is std::map implemented as a red-black tree?
这里是关于地图内存管理行为的基本讨论。
https://bytes.com/topic/c/answers/763319-stl-map-memory-management
根据您的描述，您阅读了一个巨大的文件，然后您按顺序流式传输给某人。我的问题是 dis 数据是否可以作为 STL 对存储到连续内存中，因为你说你必须流式传输它？
你必须在那里搜索元素吗？如果是，那么您应该找出频率或频率，这个答案将告诉您 STL 地图是否是一个好的容器，因为它在搜索活动方面很有效。
现在 link 中有一些关于指针引用容器和连续容器的基准测试。
https://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html
我们的想法是，您使用适当的容器，以便您拥有正确的内存管理行为。
Is there any advantage of using map over unordered_map in case of trivial keys?
在您开发出更精确的解决方案之前，这是您的地图的替代方案，它可能是一种廉价的快速破解方法。
内存管理
我在你的问题中的问题是你能清理并重复使用你的容器吗？
由于释放容器是一项昂贵的业务。
您可以使用 STL 映射的环形缓冲区，其中：一个已读取 -> 一个准备好 -> 一个已写入
这将非常有效并且可以给你带来优势，因为你不必释放任何缓冲区，只需在使用后清除即可。
编辑： 这是关于在容器中频繁删除期间发生的内存碎片的答案。
What is memory fragmentation?
你的问题是你使用字符串，它们可以扩展内存，但在它们下面是 char 的 mallocs。现在我不会删除东西，而是将其标记为未使用或其他东西。
如果您在创建字符串时使用字符串保留功能，那么一件小事可能会有所帮助。然后你可以说 128，这意味着 128 个字节，会占用一些内存，但会使碎片处理更容易，并且字符串的重新分配行为不那么困难。
现在这也可能完全没用了。如果您在 Linux.
如果您用 MVCE 重现您遇到的问题并展示它，那就太好了：您知道，很多时候您在想的问题是您的问题……并不是问题所在。
How can I find for sure the above 2 memory issues are the cause (any
tools/metrics?)
鉴于此处的信息，我建议使用分析器 - gprof（使用 -g -pg 编译）是基本分析器。如果您有可用的 Intel 编译器，则可以使用 vtune。
有free version of vtune但我个人只用过商业版
除此之外，您还可以在代码中插入计时：从文本描述中，不清楚填充地图的时间是否与擦除地图所需的时间相当，或者当 运行 同时。我会从如果开始。请注意，当前版本的 malloc() 是 greatly optimized for concurrency too（这是 Linux 吗？- 请在问题中添加标签）。
可以肯定的是，当你擦除地图时，std::~string() 调用了数百万个 free() - 但你需要确定这是否是问题所在：你可以使用更好的方法（在 answers/comments 中提到了很多）或由一个巨大的内存块支持的自定义分配器，您 create/destroy 作为一个单独的单元。
如果您提供一个 MVCE 作为起点，我或其他人将能够提供一个一致的答案（这还不是一个答案 - 但太长了不能作为评论）
Just to clarify, the program deliberately never allocates stuff and
frees others at the same time, and it only has 2 threads, one
dedicated for just deletion.
请记住，映射中的每个字符串都需要一个（或多个）new 和一个 delete（分别基于 malloc() 和 free()），即键或值中的字符串。
你在地图的"values"中有什么？
因为你有 map<string,<set<int>> 你有很多分配：
每次执行新键的 map[string].insert(val) 时，您的代码都会隐式调用 malloc() 字符串和集合。即使键已经在映射中，集合中的新 int 也需要分配集合中的新节点。
所以你在构建结构时确实有很多分配：你的内存在一侧非常碎片化，而且你的代码看起来确实 "malloc intensive"，这原则上可能导致内存调用饿死。
多线程内存allocations/deallocations
现代内存子系统的一个特点是它们针对多核系统进行了优化：当一个线程在一个内核上分配内存时，没有全局锁，而是线程本地锁或内核本地锁线程本地池。
这意味着当一个线程需要释放另一个线程分配的内存时，会涉及非本地（较慢）锁。
这意味着最好的方法是每个线程allocates/deallocates它自己的内存。说原则上您可以使用需要较少 malloc/free 交互的数据结构优化 很多 您的代码，如果您允许，就内存分配而言，您的代码将更加本地化每个线程：
- 得到一个数据块
- 建立
map<string,<set<int>>
- 释放它
并且您有两个线程重复执行此任务。
注意：您需要 enoguht RAM 来处理并发求值器，但现在您已经在使用其中的 2 个并发加载双缓冲方案（一个填充，一个清理）。您确定您的系统不是因为 RAM 耗尽而发生交换吗？
此外，这种方法是可扩展的：您可以根据需要使用任意数量的线程。在您的方法中，您被限制为 2 个线程 - 一个构建结构，一个破坏结构。
正在优化
没有 MVCE，很难给出指示。只是你现在才知道能不能应用的想法：
- 用创建时保留的已排序向量替换集合
- 用等距排序字符串的平面向量替换映射键
- 将字符串键顺序存储在平面向量中，添加哈希以跟踪映射的键。添加哈希映射以跟踪向量中字符串的顺序。
可能值得为所有合并的数据存储一个 std::string，并在地图中使用 std::string_view。这消除了互斥锁争用，因为只需要一个内存分配。 string_view 有一个简单的析构函数，因此您不需要线程。
我之前曾成功使用此技术将程序加速 2500%，但那也是因为此技术减少了总内存使用量。
感谢所有给出的答案和评论，我无法选出最佳答案，部分原因是问题本身含糊不清，没有一个答案能真正涵盖所有问题。但我确实从这些答案中学到了很多东西，因此对其中的大部分都投了赞成票。这是我经过各种实验后发现的，主要问题是：
删除线程操作慢的原因影响了另一个。鉴于它不会在两个线程上同时执行 malloc/dealloc，因此不应该有任何堆争用，一般 CPU 或瓶颈处的可用内存也不存在，唯一合理的解释是 memory带宽耗尽。我发现 this answer to another post 说： it's generally possible for a single core to saturate the memory bus if memory access is all it does. 我的删除线程所做的就是遍历一个巨大的映射并删除其中的每个元素，所以可以想象它会使内存总线饱和，所以另一个线程，它同时进行内存访问和其他计算，大大减慢。从这里开始，我将重点讨论删除速度缓慢的各种原因
地图很大，有数百万个元素和数百兆字节的大小。删除它们中的每一个都需要先访问它们，显然很少有人甚至可以放入 L1/L2/L3 缓存。因此 大量缓存未命中和从 RAM 中获取 。
正如这里提到的一对answers/comments，我在地图中存储了std::string个对象。每个分配有自己的 space 并且必须一个接一个地获取和删除。 通过将 string_view 存储在 map 中，同时将每个字符串的实际字节内容存储在预先分配的连续内存块中，可以更好地提高性能。现在，删除映射中的一百万个对象几乎变成了对 string_view 个对象的简单破坏，这些对象仅仅是指针，而对所有字符串内容的破坏就是对预分配块的破坏。
我在程序的其他部分没有提到我还在其他映射中存储了其他 C++ 对象。他们同样有问题。此类 C++ 对象的类似 "flattening" 是必要的，尽管如果没有像 string_view 这样的现成 类 就更难做到。这个想法是，如果我们可以尽可能多地存储基本类型和指针，并将所有内容（其中大部分内容可以归结为字符串）放在连续的字节缓冲区中。 让一切变得微不足道，破坏是我们的目标。
最后，事实证明销毁地图容器本身的成本非常高，尤其是当它很大时。对于 Node-based std containers traversing and deleting each node handle takes time. What I found is alternative implementations of truly flat hashmap, will make the deletion a lot faster. Examples of such map include Abseil flat_hash_map and this blogger's flat_hash_map. Note that they're both true hash_maps even though they're flat. Boost's flat_map 也可以非常快地删除，但它不是真正的 hashMap，它由严格排序的向量支持，这使得插入（当我的输入未排序时）非常慢。
所以我有这个 C++ 程序，它基本上解析巨大的数据集文件并将内容加载到内存中的 hashmap 中（这部分在主线程中受到限制，所以它永远不会消失占用大量时间的方式）。完成后，我将指针翻转到新的内存位置，并对旧内存位置调用 delete。除此之外，该程序通过在内存映射（在主线程上）中查找内容来进行传入请求匹配。假设那些巨大的地图被包裹在 Evaluator class:
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 还是内存带宽瓶颈 ？我在想象只要我把它放在一个单独的线程上我就不会在意它有多慢因为它毕竟必须一个一个地删除字符串对象，所以我没想到它会影响另一个线程......
编辑：感谢夫妇 comments/answers 似乎已经指出了几个可能的原因：
- 内存碎片。因为不常访问的字符串存储在更昂贵的内存位置（所以缓存未命中），或者因为它存储在 unordered_map 中有很多指针，或者因为系统在压缩内存的同时到处删除空洞？但为什么这会影响另一个线程的缓慢？
- 一条评论提到它是由于线程安全锁定导致的堆争用？所以这个程序的整个堆都被锁定了，因为一个线程正忙于删除阻止另一个线程访问堆内存的漏洞？澄清一下，该程序故意从不分配东西并同时释放其他东西，它只有 2 个线程，一个专门用于删除。
那我该怎么办呢？我尝试了 Jemalloc，但不确定我是否完全正确地使用了它 --- 似乎在链接器行中包含 -ljemalloc 只是神奇地替换了 libc 的 malloc？我试过了，没有性能差异，但我可能用错了。我的程序没有执行任何明确的 malloc，所有内容都是 new，大小事先未知，并与指针和 STL 映射连接在一起。
并且存储在 Key 中的所有字符串都专门用于快速查找，因此它们不能存储在带有索引的向量中，即使这会使内存连续 space，找到他们将是可怕的。所以，
- 我如何才能确定以上 2 个内存问题的原因（任何 tools/metrics？）
- 在不将我的消费模式更改为流媒体的情况下，我该怎么做才能解决这个问题？假设根本原因是上述 2 个，似乎我应该做 either/both 两件事：1) 从一个池中分配我所有的 STL 映射以及所有对象？我怎么做？ 2) 减少堆争用（我不知道
Jemalloc是否解决了我的情况）
您可以尝试使用std::vector来存储内存。 std::vector 元素连续存储，因此会减少缓存未命中（参见 What is a "cache-friendly" code?）
所以你将有一个 map<???,size_t> 而不是 map<???,std::string> 你将有一个间接的方式来获取你的字符串（这意味着额外的 运行 时间成本）但它允许你以更少的缓存未命中方式迭代所有字符串。
这将是一个冗长的答案，因为你的问题非常复杂。
读取程序
当您阅读某些内容时，您会开始为您的应用程序分配内存。现在这在正常情况下是可以的，当您不需要性能时，问题就开始了。
STL maps是红黑树所以有很多指针，这意味着每个元素都是单独分配的，这会造成你的内存space非常碎片化，很难系统有效地释放元素。原因：系统必须遵循指针。
合适的容器
STL地图说明： Why is std::map implemented as a red-black tree?
这里是关于地图内存管理行为的基本讨论。 https://bytes.com/topic/c/answers/763319-stl-map-memory-management
根据您的描述，您阅读了一个巨大的文件，然后您按顺序流式传输给某人。我的问题是 dis 数据是否可以作为 STL 对存储到连续内存中，因为你说你必须流式传输它？
你必须在那里搜索元素吗？如果是，那么您应该找出频率或频率，这个答案将告诉您 STL 地图是否是一个好的容器，因为它在搜索活动方面很有效。
现在 link 中有一些关于指针引用容器和连续容器的基准测试。 https://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html
我们的想法是，您使用适当的容器，以便您拥有正确的内存管理行为。
Is there any advantage of using map over unordered_map in case of trivial keys? 在您开发出更精确的解决方案之前，这是您的地图的替代方案，它可能是一种廉价的快速破解方法。
内存管理
我在你的问题中的问题是你能清理并重复使用你的容器吗？ 由于释放容器是一项昂贵的业务。
您可以使用 STL 映射的环形缓冲区，其中：一个已读取 -> 一个准备好 -> 一个已写入 这将非常有效并且可以给你带来优势，因为你不必释放任何缓冲区，只需在使用后清除即可。
编辑： 这是关于在容器中频繁删除期间发生的内存碎片的答案。 What is memory fragmentation?
你的问题是你使用字符串，它们可以扩展内存，但在它们下面是 char 的 mallocs。现在我不会删除东西，而是将其标记为未使用或其他东西。
如果您在创建字符串时使用字符串保留功能，那么一件小事可能会有所帮助。然后你可以说 128，这意味着 128 个字节，会占用一些内存，但会使碎片处理更容易，并且字符串的重新分配行为不那么困难。
现在这也可能完全没用了。如果您在 Linux.
如果您用 MVCE 重现您遇到的问题并展示它，那就太好了：您知道，很多时候您在想的问题是您的问题……并不是问题所在。
How can I find for sure the above 2 memory issues are the cause (any tools/metrics?)
鉴于此处的信息，我建议使用分析器 - gprof（使用 -g -pg 编译）是基本分析器。如果您有可用的 Intel 编译器，则可以使用 vtune。
有free version of vtune但我个人只用过商业版
除此之外，您还可以在代码中插入计时：从文本描述中，不清楚填充地图的时间是否与擦除地图所需的时间相当，或者当 运行 同时。我会从如果开始。请注意，当前版本的 malloc() 是 greatly optimized for concurrency too（这是 Linux 吗？- 请在问题中添加标签）。
可以肯定的是，当你擦除地图时，std::~string() 调用了数百万个 free() - 但你需要确定这是否是问题所在：你可以使用更好的方法（在 answers/comments 中提到了很多）或由一个巨大的内存块支持的自定义分配器，您 create/destroy 作为一个单独的单元。
如果您提供一个 MVCE 作为起点，我或其他人将能够提供一个一致的答案（这还不是一个答案 - 但太长了不能作为评论）
Just to clarify, the program deliberately never allocates stuff and frees others at the same time, and it only has 2 threads, one dedicated for just deletion.
请记住，映射中的每个字符串都需要一个（或多个）new 和一个 delete（分别基于 malloc() 和 free()），即键或值中的字符串。
你在地图的"values"中有什么？
因为你有 map<string,<set<int>> 你有很多分配：
每次执行新键的 map[string].insert(val) 时，您的代码都会隐式调用 malloc() 字符串和集合。即使键已经在映射中，集合中的新 int 也需要分配集合中的新节点。
所以你在构建结构时确实有很多分配：你的内存在一侧非常碎片化，而且你的代码看起来确实 "malloc intensive"，这原则上可能导致内存调用饿死。
多线程内存allocations/deallocations
现代内存子系统的一个特点是它们针对多核系统进行了优化：当一个线程在一个内核上分配内存时，没有全局锁，而是线程本地锁或内核本地锁线程本地池。
这意味着当一个线程需要释放另一个线程分配的内存时，会涉及非本地（较慢）锁。
这意味着最好的方法是每个线程allocates/deallocates它自己的内存。说原则上您可以使用需要较少 malloc/free 交互的数据结构优化 很多 您的代码，如果您允许，就内存分配而言，您的代码将更加本地化每个线程：
- 得到一个数据块
- 建立
map<string,<set<int>> - 释放它
并且您有两个线程重复执行此任务。
注意：您需要 enoguht RAM 来处理并发求值器，但现在您已经在使用其中的 2 个并发加载双缓冲方案（一个填充，一个清理）。您确定您的系统不是因为 RAM 耗尽而发生交换吗？
此外，这种方法是可扩展的：您可以根据需要使用任意数量的线程。在您的方法中，您被限制为 2 个线程 - 一个构建结构，一个破坏结构。
正在优化
没有 MVCE，很难给出指示。只是你现在才知道能不能应用的想法：
- 用创建时保留的已排序向量替换集合
- 用等距排序字符串的平面向量替换映射键
- 将字符串键顺序存储在平面向量中，添加哈希以跟踪映射的键。添加哈希映射以跟踪向量中字符串的顺序。
可能值得为所有合并的数据存储一个 std::string，并在地图中使用 std::string_view。这消除了互斥锁争用，因为只需要一个内存分配。 string_view 有一个简单的析构函数，因此您不需要线程。
我之前曾成功使用此技术将程序加速 2500%，但那也是因为此技术减少了总内存使用量。
感谢所有给出的答案和评论，我无法选出最佳答案，部分原因是问题本身含糊不清，没有一个答案能真正涵盖所有问题。但我确实从这些答案中学到了很多东西，因此对其中的大部分都投了赞成票。这是我经过各种实验后发现的，主要问题是：
删除线程操作慢的原因影响了另一个。鉴于它不会在两个线程上同时执行 malloc/dealloc，因此不应该有任何堆争用，一般 CPU 或瓶颈处的可用内存也不存在，唯一合理的解释是 memory带宽耗尽。我发现 this answer to another post 说：
it's generally possible for a single core to saturate the memory bus if memory access is all it does.我的删除线程所做的就是遍历一个巨大的映射并删除其中的每个元素，所以可以想象它会使内存总线饱和，所以另一个线程，它同时进行内存访问和其他计算，大大减慢。从这里开始，我将重点讨论删除速度缓慢的各种原因地图很大，有数百万个元素和数百兆字节的大小。删除它们中的每一个都需要先访问它们，显然很少有人甚至可以放入 L1/L2/L3 缓存。因此 大量缓存未命中和从 RAM 中获取 。
正如这里提到的一对answers/comments，我在地图中存储了
std::string个对象。每个分配有自己的 space 并且必须一个接一个地获取和删除。string_view存储在 map 中，同时将每个字符串的实际字节内容存储在预先分配的连续内存块中，可以更好地提高性能。现在，删除映射中的一百万个对象几乎变成了对string_view个对象的简单破坏，这些对象仅仅是指针，而对所有字符串内容的破坏就是对预分配块的破坏。我在程序的其他部分没有提到我还在其他映射中存储了其他 C++ 对象。他们同样有问题。此类 C++ 对象的类似 "flattening" 是必要的，尽管如果没有像
string_view这样的现成 类 就更难做到。这个想法是，如果我们可以尽可能多地存储基本类型和指针，并将所有内容（其中大部分内容可以归结为字符串）放在连续的字节缓冲区中。 让一切变得微不足道，破坏是我们的目标。最后，事实证明销毁地图容器本身的成本非常高，尤其是当它很大时。对于 Node-based std containers traversing and deleting each node handle takes time. What I found is alternative implementations of truly flat hashmap, will make the deletion a lot faster. Examples of such map include Abseil flat_hash_map and this blogger's flat_hash_map. Note that they're both true hash_maps even though they're flat. Boost's flat_map 也可以非常快地删除，但它不是真正的 hashMap，它由严格排序的向量支持，这使得插入（当我的输入未排序时）非常慢。