mold 仓库内 TBB 文档精读concurrent_unordered_multiset 的 Bucket 接口与 unsafe_* 系列 API 源码解析【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/mold本文基于 Intel oneAPI TBB作为 mold 构建链的第三方依赖收录于本仓库规范文档 bucket_interface.rst完整讲解concurrent_unordered_multiset的桶bucket接口unsafe_begin/unsafe_end、unsafe_bucket_count/unsafe_max_bucket_count、unsafe_bucket_size/unsafe_bucket的语义、串行使用约束并结合 concurrent_unordered_base 实现 与 公共测试代码 逐条印证其底层行为帮助读者掌握并发无序容器在同步窗口内做桶级遍历与负载诊断的方法。1. 桶接口的定位串行执行的诊断 APIconcurrent_unordered_multiset是一类基于开放寻址/分段链表组织的并发无序容器其元素通过哈希值被分派到若干桶bucket中每个桶内部是一条按 order key 排序的单向链表。桶接口提供的就是一组面向单个桶的遍历与查询操作与 C 标准库中unordered_*容器的begin(n)/end(n)/bucket_count()等方法一一对应。规范文档开篇即给出两条核心契约迭代器类别concurrent_unordered_multiset::local_iterator与const_local_iterator满足 ISO C 标准[forward.iterators]一节对ForwardIterator的要求。串行约束本节所有方法只能串行执行。如果在调用这些成员函数期间与其他成员函数包括线程安全的成员函数并发执行行为未定义undefined。也就是说尽管容器本身提供大量线程安全的并发操作桶接口被 TBB 明确划入unsafe不安全类别——这正是这些方法都以unsafe_前缀命名的原因。其设计意图是程序在某个时刻主动建立同步点例如持有互斥锁、或所有工作线程已完成然后以串行方式对整个容器做桶级检视。2. 迭代器类型与 ForwardIterator 的实现依据在实现层local_iterator并非独立类型而是普通迭代器的别名。见 concurrent_unordered_base.h 第 210-213 行using iterator solist_iteratorself_type, value_type; using const_iterator solist_iteratorself_type, const value_type; using local_iterator iterator; using const_local_iterator const_iterator;即全局迭代器与桶内局部迭代器共享同一个solist_iteratorsegmented ordered list iterator实现区别仅在于构造时传入的起始节点不同全局begin()从容器头节点my_head开始第 399-401 行而unsafe_begin(n)从第n个桶的首节点开始。从 solist_iterator 定义第 56-122 行 的源码结构看它提供前缀自增operator()第 93 行与后缀自增operator(int)第 102 行跨 const 的可比较性友元operator/operator!允许solist_iteratorSolist, T与solist_iteratorSolist, U相互比较第 66、68 行这保证了local_iterator ! const_local_iterator的比较合法例如for (auto it c.unsafe_begin(n); it ! c.unsafe_end(n); it)中it为可写迭代器而end一侧是 const 版本。这些接口恰好覆盖了 ForwardIterator 所需的最小集合解引用、自增、可比较、可复制印证了规范中满足 ForwardIterator 要求的表述。3. 桶的起点与终点unsafe_begin / unsafe_end3.1 接口签名继承自规范文档// 桶起点 local_iterator unsafe_begin( size_type n ); const_local_iterator unsafe_begin( size_type n ) const; const_local_iterator unsafe_cbegin( size_type n ) const; // 返回指向编号为 n 的桶中第一个元素的迭代器。 // 桶终点 local_iterator unsafe_end( size_type n ); const_local_iterator unsafe_end( size_type n ) const; const_local_iterator unsafe_cend( size_type n ) const; // 返回指向编号为 n 的桶中最后一个元素之后位置的迭代器。三个 const 变体的差异const对象上调用unsafe_begin(n)返回const_local_iteratorunsafe_cbegin(n)即使在非 const 对象上也恒返回const_local_iterator与标准库cbegin语义一致。3.2 源码实现要点见 第 613-640 行local_iterator unsafe_begin( size_type n ) { return local_iterator(first_value_node(get_bucket(n))); } local_iterator unsafe_end( size_type n ) { size_type bucket_count my_bucket_count.load(std::memory_order_relaxed); return n ! bucket_count - 1 ? unsafe_begin(get_next_bucket_index(n)) : local_iterator(nullptr); }两个实现细节值得注意unsafe_end的下一个桶起点技巧桶n的终点被实现为桶n1的起点只有最后一个桶n bucket_count - 1的终点是空迭代器local_iterator(nullptr)。这与规范描述指向桶中最后一个元素之后的元素完全吻合也解释了为什么迭代器比较必须跨 const 类型成立。内存序选择桶接口的原子读取统一使用std::memory_order_relaxed如第 628、642、653 行。这是合理的文档已声明串行调用是前置条件调用者自己负责建立同步关系桶接口只需一次宽松读取即可。4. 桶数量unsafe_bucket_count 与 unsafe_max_bucket_count规范定义size_type unsafe_bucket_count() const; // 返回容器中桶的数量 size_type unsafe_max_bucket_count() const; // 返回容器可容纳的最大桶数对应实现第 642-646 行size_type unsafe_bucket_count() const { return my_bucket_count.load(std::memory_order_relaxed); } size_type unsafe_max_bucket_count() const { return max_size(); }从源码结构看两个补充事实桶数恒为 2 的幂。构造函数中my_bucket_count(round_up_to_power_of_two(bucket_count))第 235-247 行把用户给定的初始桶数向上取整为 2 的幂后续的rehash同样只允许把桶数增大到另一个 2 的幂第 670-676 行compare_exchange_strong仅在current_bucket_count bucket_count时更新。因此unsafe_bucket_count()的返回值始终是 2 的幂且单调不减。unsafe_max_bucket_count()的实现是转发到max_size()即受容器元素总量上限约束测试代码中也只断言其 unsafe_bucket_count()见下文测试部分。5. 桶规模与桶编号unsafe_bucket_size 与 unsafe_bucket5.1 unsafe_bucket_sizesize_type unsafe_bucket_size( size_type n ) const; // 返回编号为 n 的桶中元素的数量实现第 648-650 行是直接遍历计数size_type unsafe_bucket_size( size_type n ) const { return size_type(std::distance(unsafe_begin(n), unsafe_end(n))); }可以推断其复杂度与桶内元素个数线性相关——它并没有为每个桶维护独立的原子计数器而是复用迭代器对[unsafe_begin(n), unsafe_end(n))求距离。在桶很少被高频查询的诊断场景下这是足够廉价的。5.2 unsafe_bucket键到桶号的映射size_type unsafe_bucket( const key_type key ) const; // 返回键为 key 的元素所存储的桶的编号实现第 652-654 行size_type unsafe_bucket( const key_type key ) const { return my_hash_compare(key) % my_bucket_count.load(std::memory_order_relaxed); }即桶号 用户哈希函数结果 % 当前桶数。该接口最重要的用途是定位——给定一个键算出它必然所在的桶再用unsafe_begin(bucket)/unsafe_end(bucket)在该桶内线性查找。注意由于unsafe_bucket读取的桶数与unsafe_begin(n)定位的桶数组必须一致再次印证了整组接口必须串行、且调用期间容器不被rehash修改的约束。6. 测试代码中的行为验证TBB 的公共测试框架 concurrent_unordered_common.h 为 set/multiset/map/multimap 一族容器共享同一套桶接口断言可作为行为验收依据桶数断言第 80-92 行容器清空后插入 256 个元素断言unsafe_bucket_count() 16默认初始桶数取 2 的幂并对i ∈ [0, 256)逐一断言unsafe_bucket(i) 16验证桶号始终落在合法区间。桶规模守恒断言第 94-103 行for (unsigned int i 0; i 16; i) { bucketSizeSum cont.unsafe_bucket_size(i); for (auto bit cont.unsafe_begin(i); bit ! cont.unsafe_end(i); bit) iteratorSizeSum; } REQUIRE_MESSAGE(bucketSizeSum 256, sum of bucket counts incorrect); REQUIRE_MESSAGE(iteratorSizeSum 256, sum of iterator counts incorrect);两条和都等于容器总量 256分别验证了unsafe_bucket_size与[unsafe_begin, unsafe_end)遍历结果的完备性、无重复性。多接口一致性断言第 158-179 行CustomExamine中同时用unsafe_begin/unsafe_end与unsafe_cbegin/unsafe_cend、const 与非常量对象四个组合测量每桶距离并要求相等断言unsafe_max_bucket_count() unsafe_bucket_count()再对每个已知元素先用unsafe_bucket(key)定位桶再在[unsafe_begin(index), unsafe_end(index))内用std::search确认元素确实落在自己哈希到的桶中。这套断言完整覆盖了规范文档中返回第一个元素迭代器/最后一个元素之后迭代器/桶数量/桶内元素数/键的桶号的全部语义是理解各方法行为边界的最佳范例。7. 典型使用模式与适用前提综合规范约束与实现细节一个典型的桶级诊断片段如下示意tbb::concurrent_unordered_multisetint s; // ... 并发阶段多线程并发 insert / find / erase ... // —— 进入串行窗口例如所有并发写入已结束或持有外部同步—— for (tbb::concurrent_unordered_multisetint::size_type n 0; n s.unsafe_bucket_count(); n) { auto sz s.unsafe_bucket_size(n); // 桶内元素数 for (auto it s.unsafe_begin(n); it ! s.unsafe_end(n); it) ; // 桶内逐个元素处理 if (sz 0 s.max_load_factor() 0.0f) ; // 结合负载因子判断哈希分布是否均匀 } // 定位某个键所在桶 auto b s.unsafe_bucket(42); auto it std::find(s.unsafe_begin(b), s.unsafe_end(b), 42);适用前提与限制均以仓库证据为准串行性是硬约束文档明文规定并发调用时行为未定义实现中unsafe_end内先宽松读取桶数、再取下一桶起点的两步操作在容器被rehash或元素被并发删除时会产生悬空或错位迭代器因此调用期间容器结构必须处于静止状态。桶数只增不减且恒为 2 的幂rehash/reserve第 670-693 行只把my_bucket_count向上调整不存在缩桶因此诊断代码看到的桶号空间是稳定的前提仍是串行窗口。unsafe_bucket_size是遍历式计数O(桶内元素数)不要在热路径中高频调用。典型场景调试期输出桶分布、计算碰撞率、校验键到桶映射、在同步点做整桶快照或导出以及测试代码中此类守恒断言。8. 相关章节索引该规范文档是 concurrent_unordered_multiset 类文档 的一个小节同目录下可按需继续深入迭代器iterators.rst全局迭代器与local_iterator的完整语义哈希策略hash_policy.rstload_factor/max_load_factor/rehash/reserve与桶数变化直接相关不安全修改器unsafe_modifiers.rst同属串行窗口的 unsafe 系列接口并行遍历parallel_iteration.rst与串行桶接口相对的并发安全遍历方式观察者observers.rst、大小与容量size_and_capacity.rstmax_size()等与unsafe_max_bucket_count的关联。实现集中在 third-party/tbb/include/oneapi/tbb/detail/_concurrent_unordered_base.hset/multiset/map/multimap 共用的基类容器对外声明在 third-party/tbb/include/oneapi/tbb/concurrent_unordered_set.h行为验收见 third-party/tbb/test/common/concurrent_unordered_common.h。【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/mold创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 mold 仓库内 TBB 文档精读：concurrent_unordered_multiset 的 Bucket 接口与 unsafe_* 系列 API 源码解析
mold 仓库内 TBB 文档精读concurrent_unordered_multiset 的 Bucket 接口与 unsafe_* 系列 API 源码解析【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/mold本文基于 Intel oneAPI TBB作为 mold 构建链的第三方依赖收录于本仓库规范文档 bucket_interface.rst完整讲解concurrent_unordered_multiset的桶bucket接口unsafe_begin/unsafe_end、unsafe_bucket_count/unsafe_max_bucket_count、unsafe_bucket_size/unsafe_bucket的语义、串行使用约束并结合 concurrent_unordered_base 实现 与 公共测试代码 逐条印证其底层行为帮助读者掌握并发无序容器在同步窗口内做桶级遍历与负载诊断的方法。1. 桶接口的定位串行执行的诊断 APIconcurrent_unordered_multiset是一类基于开放寻址/分段链表组织的并发无序容器其元素通过哈希值被分派到若干桶bucket中每个桶内部是一条按 order key 排序的单向链表。桶接口提供的就是一组面向单个桶的遍历与查询操作与 C 标准库中unordered_*容器的begin(n)/end(n)/bucket_count()等方法一一对应。规范文档开篇即给出两条核心契约迭代器类别concurrent_unordered_multiset::local_iterator与const_local_iterator满足 ISO C 标准[forward.iterators]一节对ForwardIterator的要求。串行约束本节所有方法只能串行执行。如果在调用这些成员函数期间与其他成员函数包括线程安全的成员函数并发执行行为未定义undefined。也就是说尽管容器本身提供大量线程安全的并发操作桶接口被 TBB 明确划入unsafe不安全类别——这正是这些方法都以unsafe_前缀命名的原因。其设计意图是程序在某个时刻主动建立同步点例如持有互斥锁、或所有工作线程已完成然后以串行方式对整个容器做桶级检视。2. 迭代器类型与 ForwardIterator 的实现依据在实现层local_iterator并非独立类型而是普通迭代器的别名。见 concurrent_unordered_base.h 第 210-213 行using iterator solist_iteratorself_type, value_type; using const_iterator solist_iteratorself_type, const value_type; using local_iterator iterator; using const_local_iterator const_iterator;即全局迭代器与桶内局部迭代器共享同一个solist_iteratorsegmented ordered list iterator实现区别仅在于构造时传入的起始节点不同全局begin()从容器头节点my_head开始第 399-401 行而unsafe_begin(n)从第n个桶的首节点开始。从 solist_iterator 定义第 56-122 行 的源码结构看它提供前缀自增operator()第 93 行与后缀自增operator(int)第 102 行跨 const 的可比较性友元operator/operator!允许solist_iteratorSolist, T与solist_iteratorSolist, U相互比较第 66、68 行这保证了local_iterator ! const_local_iterator的比较合法例如for (auto it c.unsafe_begin(n); it ! c.unsafe_end(n); it)中it为可写迭代器而end一侧是 const 版本。这些接口恰好覆盖了 ForwardIterator 所需的最小集合解引用、自增、可比较、可复制印证了规范中满足 ForwardIterator 要求的表述。3. 桶的起点与终点unsafe_begin / unsafe_end3.1 接口签名继承自规范文档// 桶起点 local_iterator unsafe_begin( size_type n ); const_local_iterator unsafe_begin( size_type n ) const; const_local_iterator unsafe_cbegin( size_type n ) const; // 返回指向编号为 n 的桶中第一个元素的迭代器。 // 桶终点 local_iterator unsafe_end( size_type n ); const_local_iterator unsafe_end( size_type n ) const; const_local_iterator unsafe_cend( size_type n ) const; // 返回指向编号为 n 的桶中最后一个元素之后位置的迭代器。三个 const 变体的差异const对象上调用unsafe_begin(n)返回const_local_iteratorunsafe_cbegin(n)即使在非 const 对象上也恒返回const_local_iterator与标准库cbegin语义一致。3.2 源码实现要点见 第 613-640 行local_iterator unsafe_begin( size_type n ) { return local_iterator(first_value_node(get_bucket(n))); } local_iterator unsafe_end( size_type n ) { size_type bucket_count my_bucket_count.load(std::memory_order_relaxed); return n ! bucket_count - 1 ? unsafe_begin(get_next_bucket_index(n)) : local_iterator(nullptr); }两个实现细节值得注意unsafe_end的下一个桶起点技巧桶n的终点被实现为桶n1的起点只有最后一个桶n bucket_count - 1的终点是空迭代器local_iterator(nullptr)。这与规范描述指向桶中最后一个元素之后的元素完全吻合也解释了为什么迭代器比较必须跨 const 类型成立。内存序选择桶接口的原子读取统一使用std::memory_order_relaxed如第 628、642、653 行。这是合理的文档已声明串行调用是前置条件调用者自己负责建立同步关系桶接口只需一次宽松读取即可。4. 桶数量unsafe_bucket_count 与 unsafe_max_bucket_count规范定义size_type unsafe_bucket_count() const; // 返回容器中桶的数量 size_type unsafe_max_bucket_count() const; // 返回容器可容纳的最大桶数对应实现第 642-646 行size_type unsafe_bucket_count() const { return my_bucket_count.load(std::memory_order_relaxed); } size_type unsafe_max_bucket_count() const { return max_size(); }从源码结构看两个补充事实桶数恒为 2 的幂。构造函数中my_bucket_count(round_up_to_power_of_two(bucket_count))第 235-247 行把用户给定的初始桶数向上取整为 2 的幂后续的rehash同样只允许把桶数增大到另一个 2 的幂第 670-676 行compare_exchange_strong仅在current_bucket_count bucket_count时更新。因此unsafe_bucket_count()的返回值始终是 2 的幂且单调不减。unsafe_max_bucket_count()的实现是转发到max_size()即受容器元素总量上限约束测试代码中也只断言其 unsafe_bucket_count()见下文测试部分。5. 桶规模与桶编号unsafe_bucket_size 与 unsafe_bucket5.1 unsafe_bucket_sizesize_type unsafe_bucket_size( size_type n ) const; // 返回编号为 n 的桶中元素的数量实现第 648-650 行是直接遍历计数size_type unsafe_bucket_size( size_type n ) const { return size_type(std::distance(unsafe_begin(n), unsafe_end(n))); }可以推断其复杂度与桶内元素个数线性相关——它并没有为每个桶维护独立的原子计数器而是复用迭代器对[unsafe_begin(n), unsafe_end(n))求距离。在桶很少被高频查询的诊断场景下这是足够廉价的。5.2 unsafe_bucket键到桶号的映射size_type unsafe_bucket( const key_type key ) const; // 返回键为 key 的元素所存储的桶的编号实现第 652-654 行size_type unsafe_bucket( const key_type key ) const { return my_hash_compare(key) % my_bucket_count.load(std::memory_order_relaxed); }即桶号 用户哈希函数结果 % 当前桶数。该接口最重要的用途是定位——给定一个键算出它必然所在的桶再用unsafe_begin(bucket)/unsafe_end(bucket)在该桶内线性查找。注意由于unsafe_bucket读取的桶数与unsafe_begin(n)定位的桶数组必须一致再次印证了整组接口必须串行、且调用期间容器不被rehash修改的约束。6. 测试代码中的行为验证TBB 的公共测试框架 concurrent_unordered_common.h 为 set/multiset/map/multimap 一族容器共享同一套桶接口断言可作为行为验收依据桶数断言第 80-92 行容器清空后插入 256 个元素断言unsafe_bucket_count() 16默认初始桶数取 2 的幂并对i ∈ [0, 256)逐一断言unsafe_bucket(i) 16验证桶号始终落在合法区间。桶规模守恒断言第 94-103 行for (unsigned int i 0; i 16; i) { bucketSizeSum cont.unsafe_bucket_size(i); for (auto bit cont.unsafe_begin(i); bit ! cont.unsafe_end(i); bit) iteratorSizeSum; } REQUIRE_MESSAGE(bucketSizeSum 256, sum of bucket counts incorrect); REQUIRE_MESSAGE(iteratorSizeSum 256, sum of iterator counts incorrect);两条和都等于容器总量 256分别验证了unsafe_bucket_size与[unsafe_begin, unsafe_end)遍历结果的完备性、无重复性。多接口一致性断言第 158-179 行CustomExamine中同时用unsafe_begin/unsafe_end与unsafe_cbegin/unsafe_cend、const 与非常量对象四个组合测量每桶距离并要求相等断言unsafe_max_bucket_count() unsafe_bucket_count()再对每个已知元素先用unsafe_bucket(key)定位桶再在[unsafe_begin(index), unsafe_end(index))内用std::search确认元素确实落在自己哈希到的桶中。这套断言完整覆盖了规范文档中返回第一个元素迭代器/最后一个元素之后迭代器/桶数量/桶内元素数/键的桶号的全部语义是理解各方法行为边界的最佳范例。7. 典型使用模式与适用前提综合规范约束与实现细节一个典型的桶级诊断片段如下示意tbb::concurrent_unordered_multisetint s; // ... 并发阶段多线程并发 insert / find / erase ... // —— 进入串行窗口例如所有并发写入已结束或持有外部同步—— for (tbb::concurrent_unordered_multisetint::size_type n 0; n s.unsafe_bucket_count(); n) { auto sz s.unsafe_bucket_size(n); // 桶内元素数 for (auto it s.unsafe_begin(n); it ! s.unsafe_end(n); it) ; // 桶内逐个元素处理 if (sz 0 s.max_load_factor() 0.0f) ; // 结合负载因子判断哈希分布是否均匀 } // 定位某个键所在桶 auto b s.unsafe_bucket(42); auto it std::find(s.unsafe_begin(b), s.unsafe_end(b), 42);适用前提与限制均以仓库证据为准串行性是硬约束文档明文规定并发调用时行为未定义实现中unsafe_end内先宽松读取桶数、再取下一桶起点的两步操作在容器被rehash或元素被并发删除时会产生悬空或错位迭代器因此调用期间容器结构必须处于静止状态。桶数只增不减且恒为 2 的幂rehash/reserve第 670-693 行只把my_bucket_count向上调整不存在缩桶因此诊断代码看到的桶号空间是稳定的前提仍是串行窗口。unsafe_bucket_size是遍历式计数O(桶内元素数)不要在热路径中高频调用。典型场景调试期输出桶分布、计算碰撞率、校验键到桶映射、在同步点做整桶快照或导出以及测试代码中此类守恒断言。8. 相关章节索引该规范文档是 concurrent_unordered_multiset 类文档 的一个小节同目录下可按需继续深入迭代器iterators.rst全局迭代器与local_iterator的完整语义哈希策略hash_policy.rstload_factor/max_load_factor/rehash/reserve与桶数变化直接相关不安全修改器unsafe_modifiers.rst同属串行窗口的 unsafe 系列接口并行遍历parallel_iteration.rst与串行桶接口相对的并发安全遍历方式观察者observers.rst、大小与容量size_and_capacity.rstmax_size()等与unsafe_max_bucket_count的关联。实现集中在 third-party/tbb/include/oneapi/tbb/detail/_concurrent_unordered_base.hset/multiset/map/multimap 共用的基类容器对外声明在 third-party/tbb/include/oneapi/tbb/concurrent_unordered_set.h行为验收见 third-party/tbb/test/common/concurrent_unordered_common.h。【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/mold创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考