mold 中的 oneTBB 并发容器从 concurrent_hash_map 到 concurrent_queue 的实战指南【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/mold本文以 mold 仓库内置的 oneTBBthird-party/tbb用户指南《Containers》为核心系统讲解concurrent_hash_map、concurrent_vector、concurrent_queue/concurrent_bounded_queue等并发容器的设计动机、API 语义与使用边界并结合 oneTBB 头文件实现及 mold 链接器自身的源码说明这些容器在真实项目中的落地方式。读完本文你将掌握并发容器的选择依据、accessor 读写锁语义、无锁增长机制以及队列阻塞与非阻塞的取舍能够直接在多线程项目中正确使用它们。为什么需要并发容器STL 容器的并发困境mold 链接器的核心卖点是“现代、极速”其多线程并行化依赖 oneTBBIntel oneAPI Threading Building Blocks提供的高并发容器。oneTBB 在用户指南《Containers》中明确指出这些容器既可以配合 Windows* / Linux* 原生线程使用也可以与基于任务task的编程模型结合使用。典型的 C STL 容器不允许并发更新。多个线程同时修改同一个std::vector或std::map几乎必然导致数据结构损坏内存越界、迭代器失效、链表断裂等。常规的补救办法是给容器套一把互斥锁mutex让任意时刻只有一个线程操作容器——这确实保证了安全但彻底消灭了并发性多核带来的并行加速荡然无存。oneTBB 提供的容器通过以下两种机制之一或两者结合实现了远高于 STL锁 的并发度细粒度锁Fine-grained locking多个线程只锁定它们真正需要操作的那部分数据。只要不同线程访问的是不同区域它们就能并行推进互不阻塞。无锁技术Lock-free techniques不同线程通过“记录并修正其他线程的干扰效果”来协调而不是靠互斥等待。从源码结构看这两种策略在 oneTBB 头文件中有清晰的分工concurrent_hash_map使用分桶加锁的方式实现见 concurrent_hash_map.h 中的class concurrent_hash_map定义而concurrent_vector和队列类则大量依赖原子操作与无锁内存序管理。并发容器的代价与使用前提指南特别提醒高并发容器是有成本的。它们的单次操作开销通常高于普通 STL 容器单线程场景下可能更慢。因此只有当下述条件成立时才应该使用并发容器并发度提升带来的加速收益大于其顺序性能较慢的代价。换句话说先想清楚“这里真的有多线程同时访问同一容器吗”再决定是否引入。一个必须遵守的纪律构造/析构不可并发文档用一个 CAUTION 强调了重要约束与 C 中大多数对象一样容器的构造函数或析构函数绝不能与对同一对象的其他操作并发执行否则竞争会导致操作作用在“未定义的对象”上。这条规则对上述所有并发容器一律适用——并发安全的只是容器内部的读写操作而不是对象的生命周期管理。concurrent_hash_map并发哈希表与 accessor 读写语义concurrent_hash_mapKey, T, HashCompare是一张允许并发访问的哈希表完成从键Key到值T的映射。特征类型HashCompare负责两件事如何对键做哈希hash以及如何比较两个键是否相等equal。经典示例并行统计字符串出现次数指南给出了一个完整可运行示例统计数组Data中每个字符串出现的次数用parallel_for并行填充一张concurrent_hash_mapstring, int#include oneapi/tbb/concurrent_hash_map.h #include oneapi/tbb/blocked_range.h #include oneapi/tbb/parallel_for.h #include string using namespace oneapi::tbb; using namespace std; // 定义用户类型的哈希与比较操作 struct MyHashCompare { size_t hash( const string x ) const { size_t h 0; for( const char* s x.c_str(); *s; s ) h (h*17)^*s; return h; } // 字符串相等判断 bool equal( const string x, const string y ) const { return xy; } }; // 字符串 - 整数 的并发哈希表 typedef concurrent_hash_mapstring,int,MyHashCompare StringTable; // 统计字符串出现次数的函数对象 struct Tally { StringTable table; Tally( StringTable table_ ) : table(table_) {} void operator()( const blocked_rangestring* range ) const { for( string* prange.begin(); p!range.end(); p ) { StringTable::accessor a; table.insert( a, *p ); a-second 1; } } }; const size_t N 1000000; string Data[N]; void CountOccurrences() { StringTable table; // 构造空表 parallel_for( blocked_rangestring*( Data, DataN, 1000 ), Tally(table) ); // 并行填入出现次数 // 输出结果 for( StringTable::iterator itable.begin(); i!table.end(); i ) printf(%s %d\n,i-first.c_str(),i-second); }注意Tally::operator()中的关键点table.insert(a, *p)返回一个accessor随后a-second 1直接修改元素。因为accessor持有的是写权限这段并行代码中同一个键的计数更新是线程安全的。accessor 与 const_accessor读写权限的智能指针concurrent_hash_map本质是std::pairconst Key, T元素的容器。当访问某个元素时你通常要么更新它、要么读取它。为此模板类提供了两个充当智能指针的嵌套类accessor表示更新写访问。只要它指向某个元素所有其他线程对该键的查找都会被阻塞直到该accessor结束。这保证了“读-改-写”的原子性。const_accessor表示只读访问。多个const_accessor可以同时指向同一个元素。在“频繁读、偶尔写”的场景下这一特性可以显著提升并发度。find和insert方法都接收accessor或const_accessor作为参数通过传入类型告诉concurrent_hash_map你请求的是更新还是只读访问。一旦方法返回访问会一直持续到accessor/const_accessor被销毁。务必尽量缩短 accessor 的生命周期——因为持有访问权会阻塞其他线程。做法是把 accessor 声明在最内层代码块中如果需要在块结束前就释放访问权可以显式调用release()方法。指南给出了同一个循环体的改写版本StringTable accessor a; for( string* prange.begin(); p!range.end(); p ) { table.insert( a, *p ); a-second 1; a.release(); // 提前释放而不是等块结束析构 }erase(key)同样可以并发执行。它隐式请求写访问因此在真正删除键之前会等待该键上所有其他存活的访问结束。更灵活为自定义键类型定制 HashCompareconcurrent_hash_map的第三个模板参数HashCompare可以按多种方式适配自定义类型详见用户指南 More_on_HashCompare.rst显式指定HashCompare参数如上面的MyHashCompare让HashCompare默认取tbb_hash_compareKey然后为tbb_hash_compareKey定义特化。例如若键类型为Foo且已定义operator只需提供tbb_hasher即可size_t tbb_hasher(const Foo f) { size_t h ...compute hash code for f... return h; }tbb_hash_compare类模板在 _hash_compare.h 中定义。无论走哪条路HashCompare都必须提供两个签名hash把Key映射为size_tequal判断两个键是否相等。这两个签名必须放在同一个类中因为存在硬性不变量如果两个键相等它们必须哈希到同一个值否则哈希表可能无法正常工作。技术上你可以让所有键都哈希为0来满足该不变量但那会导致灾难性的性能下降理想情况下每个键应哈希到不同值至少要让不同键哈希冲突的概率足够低。HashCompare的方法默认应为static只有当需要“不同实例行为不同”时才做成非静态并用接受HashCompare参数的构造函数构造容器。指南给出了一个实例相关区分大小写的完整示例class VariantHashCompare { bool ignore_case; // 为 true 时忽略字母大小写 public: size_t hash(const string x) const { size_t h 0; for(const char* s x.c_str(); *s; s) h (h*16777179)^*(ignore_case?tolower(*s):*s); return h; } bool equal(const string x, const string y) const { if( ignore_case ) return strcasecmp(x.c_str(), y.c_str())0; else return xy; } VariantHashCompare(bool ignore_case_) : ignore_case(ignore_case_) {} }; typedef concurrent_hash_mapstring,int, VariantHashCompare VariantStringTable; VariantStringTable CaseSensitiveTable(VariantHashCompare(false)); VariantStringTable CaseInsensitiveTable(VariantHashCompare(true));concurrent_vector可并发增长的动态数组concurrent_vectorT是一个可以动态增长的T数组。它的核心特性是在其他线程正在操作元素、甚至同时增长它时仍然可以安全地增长。为了支持动态数组的常见用法它提供了三个增长方法push_back(x)安全地把x追加到数组末尾grow_by(n)安全地追加n个用T()初始化的连续元素grow_to_at_least(n)若数组长度不足n则增长到n。前两个方法都返回指向第一个追加元素的迭代器。指南给出的Append示例展示了如何使用grow_by安全追加 C 字符串void Append( concurrent_vectorchar vector, const char* string ) { size_t n strlen(string)1; std::copy( string, stringn, vector.grow_by(n) ); }size()、迭代器与“元素永不移动”保证size()返回的元素个数可能包含仍在并发构造中即push_back、grow_by或grow_to_at_least尚未完成的元素。并发调用增长方法时返回顺序不一定与元素实际追加顺序一致。上面示例特意使用std::copy和迭代器、而不是strcpy和裸指针是因为concurrent_vector的元素可能不在连续地址上。只要迭代器不越过当前end()的值在增长过程中使用迭代器是安全的但迭代器可能引用到正在并发构造的元素构造与访问之间的同步需要你自己负责。另一个独特优势concurrent_vectorT在数组被clear()之前从不移动元素——这一点即使对单线程代码也比std::vector有优势std::vector扩容时会把已有元素搬移到新内存导致指针/引用失效。当然它也比std::vector开销更大所以文档建议只有当你确实需要“在其他访问进行中动态扩容”或者“要求元素永不移动”时才使用它。指南的 CAUTION 再次强调边界concurrent_vector的并发安全仅针对“增长”不针对清空或销毁。若还有其他操作正在进行绝不要调用clear()。从实现看concurrent_vector通过分段segment机制实现元素地址稳定与无锁增长类定义位于 concurrent_vector.hgrow_by系列方法含带初值重载grow_by(delta, value)也在同一头文件中实现。并发队列concurrent_queue 与 concurrent_bounded_queue模板类concurrent_queueT,Alloc实现一个元素类型为T的并发队列多个线程可以同时 push 和 pop。它是无界的且没有阻塞操作。两个基本操作是push行为与std::queue::push一致try_pop若队列中有元素则弹出检查与弹出必须合并为单一操作才能保证线程安全。指南用一个反例说明了为什么需要try_pop这种原子式操作。下面这段串行代码即使每个std::queue方法本身都线程安全整体组合依然不安全extern std::queueT MySerialQueue; T item; if( !MySerialQueue.empty() ) { item MySerialQueue.front(); MySerialQueue.pop_front(); ... process item... }问题在于empty()刚返回true另一个线程可能恰好抢走了最后一个元素。而等价的 oneTBB 写法是原子且安全的extern concurrent_queueT MyQueue; T item; if( MyQueue.try_pop(item) ) { ...process item... }顺序保证与 size() 的“负值”语义单线程程序里队列是严格 FIFO先进先出。但当多线程并发 push/pop 时“谁是最先”本身就变得不确定。concurrent_queue给出的保证是若一个线程先后 push 两个值另一个线程 pop 这两个值时弹出的顺序与 push 的顺序一致同一生产者线程内的相对顺序得以保持。concurrent_queue无界且没有等待方法避免溢出或等待队列非空需要用户自行提供同步——这通常适用于“同步要在更高层做”的场景。值得特别注意size()的语义它定义为“已开始的 push 操作数减去已开始的 pop 操作数”。当 pop 多于 push 时size()会变成负数。例如队列为空但有n个挂起的 pop 操作时size()返回-n——这为生产者提供了一种简单的方式可以得知有多少消费者正在等待。相应地empty()被定义为“当且仅当size()不大于 0 时为真”。concurrent_bounded_queue加容量上限与阻塞语义concurrent_bounded_queueT,Alloc是concurrent_queue的变体增加了阻塞操作与容量指定能力其关键方法pop(item)等待直到可以成功弹出push(item)等待直到不超过队列容量、可以成功压入try_push(item)仅当不会超出容量时才压入size()返回有符号整数可能为负。默认情况下concurrent_bounded_queue是无界的——可以容纳任意数量的值直到内存耗尽。通过set_capacity设置容量后才变为有界设置容量后push会阻塞直到队列有空间。文档特别提醒有界队列比无界队列慢如果程序其他地方已有约束、队列本身不会无限膨胀最好不要设置容量如果不需要边界也不需要阻塞 pop请优先考虑concurrent_queue。两个队列类的实现均位于 concurrent_queue.hconcurrent_queue在 L53concurrent_bounded_queue在 L321底层由detail/_concurrent_queue_base.h提供无锁的环形缓冲与原子计数支持。调试专用遍历队列concurrent_queue与concurrent_bounded_queue支持 STL 风格迭代但仅供调试例如 dump 队列内容。迭代器只能单向前进速度太慢不适合生产代码一旦队列被修改指向它的所有迭代器都会失效。使用方法如下operator需为Foo定义concurrent_queueFoo q; ... typedef concurrent_queueFoo::const_iterator iter; for(iter i(q.unsafe_begin()); i!q.unsafe_end(); i ) { cout *i; }方法名上的unsafe_前缀就是提醒你这些操作不是并发安全的。何时不要用队列并行程序中队列常被用于解耦生产者与消费者。但指南建议在使用显式队列之前先考虑用parallel_for_each或parallel_pipeline替代因为它们在多数情况下更高效队列天然是瓶颈因为它必须维护 FIFO 顺序正在 pop 的线程可能空转等待值被 push 进来队列是被动数据结构线程 push 一个值后可能要过很久才被 pop期间该值及其引用的数据在缓存中变“冷”更糟的是另一个线程 pop 后该值还要被搬运到另一个处理器。相比之下parallel_pipeline规避了这些瓶颈它的线程调度是隐式的工作线程在值到来之前可以做其他工作并且会尽量让数据在缓存中保持“热”。详见用户指南 When_Not_to_Use_Queues.rst。容器总览与选择建议《Summary of Containers》指出oneTBB 的高层容器支持常见的并发访问惯用法适合“原本会用一个串行容器加锁”的场景。归纳一下各容器的定位容器数据结构并发机制典型用途注意点concurrent_hash_map哈希表分桶细粒度锁 accessor 读写权限键值查找、并行计数、去重accessor 生命周期越短越好concurrent_vector可增长数组无锁分段增长并行收集结果、元素地址须稳定增长安全clear()不安全concurrent_queue无界 FIFO无锁 原子操作生产者-消费者解耦、任务分发无阻塞操作需自建同步concurrent_bounded_queue有界 FIFO无锁 阻塞语义有容量上限的流水线缓冲比无界队列慢concurrent_priority_queue优先队列细粒度锁按优先级取任务见 concurrent_priority_queue.h选择原则一句话只有当多线程确实需要同时读写同一容器、且并发加速超过其单线程开销时才使用并发容器能用parallel_for_each/parallel_pipeline表达的数据流优先用它们而非显式队列。mold 中的真实用法并发容器支撑链接器并行化这些并发容器并非纸上谈兵——mold 链接器自身就是 oneTBB 并发容器的大规模使用者在src/目录下随处可见tbb::concurrent_vector、tbb::concurrent_hash_map通过 mold.h 引入合并节merged sections收集mold.h 中用tbb::concurrent_vectorArenaObjectPtrMergedSectionE merged_sections和tbb::concurrent_vectorstd::unique_ptrTimerRecord timer_records让多个工作线程并行产出结果、再汇总正是concurrent_vector“并发增长、元素稳定”特性的典型应用unsorted_input_filesmold.h同理。符号-节映射mapfile.cc 定义tbb::concurrent_hash_mapInputSectionE *, std::vectorSymbolE *用于并行建立节到符号的映射多个线程并发插入互不冲突。ICF 去重icf.cc 引入concurrent_vector并在 icf.cc 用tbb::concurrent_vectorInputSectionE * leader_sections收集各组的“代表节”。隐藏符号收集passes.cc 用tbb::concurrent_vectorSymbolE * hidden并行收集需要隐藏的符号。这些用法与文档描述的语义完全一致concurrent_vector用于“多线程各自产出、地址稳定、事后统一遍历”concurrent_hash_map用于“多线程并发按 key 建表”。如果你想看并发容器在真实大型 C 项目中的最佳实践mold 的src/就是现成的参考样本。参考文档容器总览Containers.rst并发哈希表concurrent_hash_map.rst、More_on_HashCompare.rst并发数组concurrent_vector_ug.rst并发队列Concurrent_Queue_Classes.rst、Iterating_Over_a_Concurrent_Queue_for_Debugging.rst、When_Not_to_Use_Queues.rst容器总结Summary_of_Containers.rst【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/mold创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考