mold 链接器背后的 TBB concurrent_vector一个可并发增长的容器设计与实战解析【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/moldconcurrent_vector是 oneTBBIntel 线程构建模块随 mold 仓库以third-party/tbb形式内置提供的一种可被多线程并发增长和并发访问的序列容器。mold 这个现代链接器正是依赖它在符号解析、GC、ICF、性能计时等阶段让多个工作线程安全地边扫描边追加数据而不需要给容器加全局互斥锁。读完本篇你既能掌握concurrent_vector的完整接口、类型要求与异常安全语义又能从 TBB 源码和 mold 链接器的真实调用点看清它的分段实现原理与实际工程用法。一、定位它是为并行扫描 并发追加设计的容器规格文档 concurrent_vector_cls.rst 对oneapi::tbb::concurrent_vector的定义可以概括为三条核心特性多个线程可以并发地增长容器并追加新元素grow append支持按下标随机访问第一个元素下标为 0增长容器不会使任何已存在的迭代器或下标失效。这三条特性决定了它和std::vector的根本差异std::vector扩容时可能移动全部元素、使指针失效因此多线程不能同时对它push_back而concurrent_vector从设计上就放弃元素连续存放的强约束通过分段存储实现换来迭代器/下标在增长过程中的稳定性。这正是链接器这类大量线程并行读取、同时往公共池子里收集结果场景所需要的容器形态。二、类模板总览Class Template Synopsis规格文档给出的完整接口如下定义于头文件oneapi/tbb/concurrent_vector.h// Defined in header oneapi/tbb/concurrent_vector.h namespace oneapi { namespace tbb { template typename T, typename Allocator cache_aligned_allocatorT class concurrent_vector { using value_type T; using allocator_type Allocator; using size_type implementation-defined unsigned integer type; using difference_type implementation-defined signed integer type; using reference value_type; using const_reference const value_type; using pointer typename std::allocator_traitsallocator_type::pointer; using const_pointer typename std::allocator_traitsallocator_type::const_pointer; using iterator implementation-defined RandomAccessIterator; using const_iterator implementation-defined constant RandomAccessIterator; using reverse_iterator std::reverse_iteratoriterator; using const_reverse_iterator std::reverse_iteratorconst_iterator; using range_type implementation-defined ContainerRange; using const_range_type implementation-defined constant ContainerRange; // Construction, destruction, copying concurrent_vector(); explicit concurrent_vector( const allocator_type alloc ) noexcept; explicit concurrent_vector( size_type count, const value_type value, const allocator_type alloc allocator_type() ); explicit concurrent_vector( size_type count, const allocator_type alloc allocator_type() ); template typename InputIterator concurrent_vector( InputIterator first, InputIterator last, const allocator_type alloc allocator_type() ); concurrent_vector( std::initializer_listvalue_type init, const allocator_type alloc allocator_type() ); concurrent_vector( const concurrent_vector other ); concurrent_vector( const concurrent_vector other, const allocator_type alloc ); concurrent_vector( concurrent_vector other ) noexcept; concurrent_vector( concurrent_vector other, const allocator_type alloc ); ~concurrent_vector(); concurrent_vector operator( const concurrent_vector other ); concurrent_vector operator( concurrent_vector other ) noexcept(/*See details*/); concurrent_vector operator( std::initializer_listvalue_type init ); void assign( size_type count, const value_type value ); template typename InputIterator void assign( InputIterator first, InputIterator last ); void assign( std::initializer_listvalue_type init ); // Concurrent growth iterator grow_by( size_type delta ); iterator grow_by( size_type delta, const value_type value ); template typename InputIterator iterator grow_by( InputIterator first, InputIterator last ); iterator grow_by( std::initializer_listvalue_type init ); iterator grow_to_at_least( size_type n ); iterator grow_to_at_least( size_type n, const value_type value ); iterator push_back( const value_type value ); iterator push_back( value_type value ); template typename... Args iterator emplace_back( Args... args ); // Element access value_type operator[]( size_type index ); const value_type operator[]( size_type index ) const; value_type at( size_type index ); const value_type at( size_type index ) const; value_type front(); const value_type front() const; value_type back(); const value_type back() const; // Iterators iterator begin(); const_iterator begin() const; const_iterator cbegin() const; iterator end(); const_iterator end() const; const_iterator cend() const; reverse_iterator rbegin(); const_reverse_iterator rbegin() const; const_reverse_iterator crbegin() const; reverse_iterator rend(); const_reverse_iterator rend() const; const_reverse_iterator crend() const; // Size and capacity size_type size() const noexcept; bool empty() const noexcept; size_type max_size() const noexcept; size_type capacity() const noexcept; // Concurrently unsafe operations void reserve( size_type n ); void resize( size_type n ); void resize( size_type n, const value_type value ); void shrink_to_fit(); void swap( concurrent_vector other ) noexcept(/*See details*/); void clear(); allocator_type get_allocator() const; // Parallel iteration range_type range( size_type grainsize 1 ); const_range_type range( size_type grainsize 1 ) const; }; // class concurrent_vector } // namespace tbb } // namespace oneapi对照 TBB 的实现头文件 concurrent_vector.h 可以看到规范中的实现定义类型在实现里是具体落地的size_type是std::size_tdifference_type是std::ptrdiff_t见 concurrent_vector.h 中class concurrent_vector的类型别名段iterator/const_iterator是vector_iteratorconcurrent_vector, value_type一个基于下标而非裸指针的随机访问迭代器默认Allocator为tbb::cache_aligned_allocatorT即段segment内存按缓存行对齐分配减少多线程并发读写时的伪共享。三、类型要求Requirements规格文档对模板参数有明确约束使用容器前应先确认自己的元素类型满足元素类型T必须满足 ISO C 标准 [container.requirements] 中的Erasable要求T的析构函数不得抛出异常如果T的默认构造函数可能抛异常则其析构函数必须是非虚的并且能在全零填充的内存上正确工作。这条要求非常关键它直接支撑了后文异常安全一节中零填充元素的语义——容器内部会用零填充内存作为已分配但未构造状态的占位因此析构函数必须能安全地处理这种字节模式成员函数按操作类型的不同可能对T提出更严格的要求例如push_back要求CopyInsertableemplace_back要求EmplaceConstructible见下文Allocator必须满足 ISO C [allocator.requirements] 的分配器要求。四、并发增长接口Concurrent growth规格文档的 toctree 中并发增长是独立的一章concurrent_growth.rst。其首要结论是本节所有成员函数之间、与元素访问之间、与容器遍历之间都可以并发执行。各重载的精确语义如下4.1 grow_byiterator grow_by( size_type delta );在向量末尾追加delta个就地默认构造的新元素返回指向所追加序列首元素的迭代器。要求T满足DefaultConstructible与EmplaceConstructible。iterator grow_by( size_type delta, const value_type value );追加value的delta份拷贝。要求T满足CopyInsertable。template typename InputIterator iterator grow_by( InputIterator first, InputIterator last );把半开区间[first, last)的全部元素追加到末尾。仅当InputIterator满足 ISO C [input.iterators] 的输入迭代器要求时才参与重载决议。iterator grow_by( std::initializer_listvalue_type init );等价于grow_by(init.begin(), init.end())。4.2 grow_to_at_leastiterator grow_to_at_least( size_type n ); // 默认构造填充至 size() n iterator grow_to_at_least( size_type n, const value_type value ); // 用 value 拷贝填充追加使size() n所需的最少元素返回所追加序列的起点迭代器。适合在不知道当前size()它可能正被其他线程改变的前提下把容器扩容到某个目标水位。4.3 push_back / emplace_backiterator push_back( const value_type value ); // 拷贝插入要求 CopyInsertable iterator push_back( value_type value ); // 移动插入要求 MoveInsertable template typename... Args iterator emplace_back( Args... args ); // 就地构造要求 EmplaceConstructiblepush_back(value_type)会把源对象留在有效但未指定的状态三个函数都返回指向被追加元素的迭代器。注意所有增长函数返回的是迭代器而不是void这让调用者拿到本线程刚追加的那段元素的起点可以立即就地初始化这批元素而不用担心其他线程的追加插队进来。五、异常安全语义broken vector模型规格文档 concurrent_vector_cls.rst 的 Exception Safety 一节给出了一个诚实且有实用价值的结论并发增长与理想异常安全strong guarantee在原理上互斥但concurrent_vector提供了一个实用级别的异常安全保证。具体规则当增长或赋值过程中抛出异常时后果取决于异常来源异常来自元素构造函数所追加序列中所有后续元素将被零填充zero-filled异常来自分配器例如内存耗尽容器进入broken损坏状态。所追加序列中的每个元素处于三种状态之一已构造constructed、零填充zero-filled、内存未分配unallocated。对 broken 容器的访问规则用at访问未分配元素会抛出std::range_error用其他方法访问未分配元素是未定义行为capacity()和size()的值可能小于预期通过back()访问 broken 容器是未定义行为。但以下两条保证无论容器是否 broken 都成立若k是某个未分配元素的下标则size() capacity() k增长操作永远不会使size()或capacity()减小。另外一个重要保证是一次并发增长若成功完成那么它追加的序列即使在后续其他增长操作失败之后依然有效且可访问。这套语义解释了为什么前面类型要求中规定默认构造可能抛异常时析构函数必须能对零填充内存正确工作——零填充内存是已占位但构造未完成的显式中间状态容器析构时会对这些区域调用析构函数因此必须有此约定。六、元素访问、迭代器与并行迭代从规格文档 synopsis 可以直接读出以下访问与迭代接口元素访问operator[]不检查边界、at越界或未分配时抛std::range_error、front、back迭代器完整的begin/end/cbegin/cend与rbegin/rend/crbegin/crend反向迭代器规模与容量size、empty、max_size、capacity均为noexcept并行迭代range_type range( size_type grainsize 1 )及其 const 版本返回可直接喂给 TBB 并行算法如parallel_for的范围对象。规格文档还专门标注了一组并发不安全Concurrently unsafe操作reserve、resize、shrink_to_fit、swap、clear、get_allocator。也就是说只有增长类接口和读取类接口被设计为可并发改变整体布局的接口需要在无并发访问的静默期调用。使用时的正确姿势是多线程阶段只用push_back/grow_by/range等并发安全接口单线程阶段再做shrink_to_fit、clear等整理。七、源码级原理分段表让增长不失效成为可能接下来结合 TBB 实现头文件 concurrent_vector.h 看上述语义是怎么落地的。7.1 底层是 segment_table而非一整块连续内存__TBB_GLOBAL_VAR constexpr std::size_t embedded_table_num_segments 3; template typename T, typename Allocator tbb::cache_aligned_allocatorT class concurrent_vector : private segment_tableT, Allocator, concurrent_vectorT, Allocator, embedded_table_num_segmentsconcurrent_vector私有继承自segment_table定义于detail/_segment_table.h元素按段segment块状连续内存存放段之间由一张段表索引。对象内嵌前 3 个段槽embedded_table_num_segments 3且allow_table_extending true表示段表本身可以再扩展。从源码结构看这一设计直接实现了规格中的两条保证增长不失效迭代器/下标新元素总被追加到新段或当前段尾部之后旧段内存不动因此旧下标对应的地址永远不变size()/capacity()只增不减增长只是追加段/追加槽从不回收。7.2 迭代器下标 缓存指针实现中的vector_iterator只持有三样东西指向容器的指针、一个size_type下标my_index、以及一个mutable value_type* my_item缓存指针vector_iterator operator() { my_index; if (my_item ! nullptr) { if (vector_type::is_first_element_in_segment(my_index)) { // If the iterator crosses a segment boundary, the pointer become invalid // as possibly next segment is in another memory location my_item nullptr; } else { my_item; } } return *this; }细节值得品味迭代器在段内移动时用my_item指针步进快路径一旦跨段就把缓存置空因为下一段可能在完全不同的内存位置下次解引用再通过internal_subscript(my_index)走段表查地址慢路径。这样迭代器比较、差值运算都只是下标运算operator只比较my_vector和my_index代价小且天然与增长追加新段无冲突——这也正是规格中iterator 为实现定义 RandomAccessIterator背后的具体形态。7.3 noexcept 语义由分配器 traits 决定synopsis 中operator(concurrent_vector)与swap标注的noexcept(/*See details*/)在实现里是这样计算的static constexpr bool is_noexcept_assignment allocator_traits_type::propagate_on_container_move_assignment::value || allocator_traits_type::is_always_equal::value; static constexpr bool is_noexcept_swap allocator_traits_type::propagate_on_container_swap::value || allocator_traits_type::is_always_equal::value;即只有当分配器支持移动传播或者两个分配器恒等可比is_always_equal时移动赋值/交换才能承诺noexcept。这是遵循 [allocator.requirements] 的标准做法也提醒使用者自定义Allocator会影响容器的异常保证强度。八、非成员函数与推导指南规格文档还列出了容器级别的六个关系运算符与swaptemplate typename T, typename Allocator bool operator( const concurrent_vectorT, Allocator lhs, const concurrent_vectorT, Allocator rhs ); // 另有 operator!、operator、operator、operator、operator // 均为按字典序lexicographical比较 template typename T, typename Allocator void swap( concurrent_vectorT, Allocator lhs, concurrent_vectorT, Allocator rhs );文档同时说明一个实现自由度这些非成员函数所在的命名空间未指定只要对相应的比较/交换操作可达即可例如实现可以定义在内部命名空间而oneapi::tbb::concurrent_vector是一个类型别名非成员函数仅通过参数依赖查找可达。子文档 non_member_binary_comparisons.rst、non_member_lexicographical_comparisons.rst 与 non_member_swap.rst 分别细化了二元比较、字典序比较和 swap 的行为另见 deduction_guides.rst 中的 CTAD 推导指南。九、在 mold 链接器中的真实用法mold 默认把 oneTBB 以子目录方式静态内置见 CMakeLists.txtMOLD_USE_SYSTEM_TBB选项默认 OFF直接add_subdirectory(third-party/tbb)并链接TBB::tbb因此下文所有调用点都是 mold 自身代码。concurrent_vector在 mold 中的使用高度契合它的并行扫描 并发追加定位9.1 全局 Context 中的多线程共享池mold.h 中ContextE结构体集中声明了一批容器级对象池tbb::concurrent_vectorstd::pairstd::vectoru32, InputFileE * unsorted_input_files; tbb::concurrent_vectorArenaObjectPtrMergedSectionE merged_sections; tbb::concurrent_vectorstd::unique_ptrTimerRecord timer_records; tbb::concurrent_vectorArenaObjectPtrObjectFileE obj_pool; tbb::concurrent_vectorArenaObjectPtrSharedFileE dso_pool; tbb::concurrent_vectorstd::unique_ptru8[] string_pool; tbb::concurrent_vectorstd::unique_ptrMappedFile mf_pool; tbb::concurrent_vectorstd::unique_ptrChunkE chunk_pool;从源码结构看mold 把输入文件去重池obj_pool/dso_pool、合并段池merged_sections、字符串池、chunk 池全部建成concurrent_vector解析阶段大量工作线程通过tbb::parallel_for_each并行扫描对象文件随时往这些池里push_back新条目而下标/指针不因增长而失效保证了已发布的ArenaObjectPtr等引用在并发窗口内持续有效。9.2 hidden 符号解析循环src/passes.cc 中 hidden 可见性符号的再解析循环是一个典型用例for (;;) { tbb::concurrent_vectorSymbolE * hidden; ctx.symbol_map.parallel_for_each( { if (sym.file sym.file-is_dso sym.file-is_reachable sym.visibility STV_HIDDEN) { sym.skip_dso true; hidden.push_back(sym); } }); if (hidden.empty()) break; ... }多工作线程在parallel_for_each中对符号表做只读扫描发现需要跳过 DSO 重新解析的 hidden 符号就并发push_back进hidden循环体在下一轮之前单线程地遍历该向量并clear_symbol然后再次并行解析。这正是并发安全接口push_back用于并行窗口、非并发接口留到静默期使用的标准范式。9.3 GC 根集与 ICF 去重集合gc-sections.cc 中collect_root_set返回tbb::concurrent_vectorInputSectionE *多线程收集 GC 根节随后做可达性分析icf.cc 中tbb::concurrent_vectorInputSectionE * leader_sections;用于 ICF相同代码折叠阶段并发登记 leader 节。9.4 启动期 reader 任务与性能计时main.cc 中tbb::concurrent_vectorReaderJob scripts;收集各线程发现的输入任务perf.cc 与 lib.h 中tbb::concurrent_vectorstd::unique_ptrTimerRecord保存各线程产生的计时记录供-v的耗时报告汇总。这些调用点共同印证了规格文档描述的容器画像只增长、只读遍历、追加后立刻可用且增长不打断正在进行的遍历——恰好是链接器多遍并行处理所需要的容器契约。十、使用要点小结接口选型并行阶段只用push_back/emplace_back/grow_by/grow_to_at_least与range()resize/clear/reserve/shrink_to_fit/swap属于并发不安全操作必须放在无并发访问的窗口执行元素类型约束默认构造可抛异常的类型必须保证析构函数非虚且能对零填充内存正确工作否则违反规格要求异常安全预期不要期待 strong guarantee。分配器抛异常后容器可能 broken此时用at探测未分配区域抛std::range_error依赖size() capacity() k与size()/capacity()单调不减两条不变量做恢复逻辑迭代器模型实现上是下标 段内缓存指针的随机访问迭代器跨段自动失效缓存因此旧迭代器在并发增长下永远有效但段内缓存要求元素一经构造不被移动——这与分段存储是同一枚硬币的两面allocator 影响 noexcept移动赋值/交换的noexcept由分配器的propagate_on_*与is_always_equaltraits 决定自定义分配器时需注意这一耦合。规格文档其余章节construct_destroy_copy.rst、element_access.rst、iterators.rst、size_and_capacity.rst、unsafe_operations.rst、parallel_iteration.rst对上述各组成员函数有逐条的更细粒度规定可作为接口行为的权威依据。【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/mold创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 mold 链接器背后的 TBB concurrent_vector：一个可并发增长的容器设计与实战解析
mold 链接器背后的 TBB concurrent_vector一个可并发增长的容器设计与实战解析【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/moldconcurrent_vector是 oneTBBIntel 线程构建模块随 mold 仓库以third-party/tbb形式内置提供的一种可被多线程并发增长和并发访问的序列容器。mold 这个现代链接器正是依赖它在符号解析、GC、ICF、性能计时等阶段让多个工作线程安全地边扫描边追加数据而不需要给容器加全局互斥锁。读完本篇你既能掌握concurrent_vector的完整接口、类型要求与异常安全语义又能从 TBB 源码和 mold 链接器的真实调用点看清它的分段实现原理与实际工程用法。一、定位它是为并行扫描 并发追加设计的容器规格文档 concurrent_vector_cls.rst 对oneapi::tbb::concurrent_vector的定义可以概括为三条核心特性多个线程可以并发地增长容器并追加新元素grow append支持按下标随机访问第一个元素下标为 0增长容器不会使任何已存在的迭代器或下标失效。这三条特性决定了它和std::vector的根本差异std::vector扩容时可能移动全部元素、使指针失效因此多线程不能同时对它push_back而concurrent_vector从设计上就放弃元素连续存放的强约束通过分段存储实现换来迭代器/下标在增长过程中的稳定性。这正是链接器这类大量线程并行读取、同时往公共池子里收集结果场景所需要的容器形态。二、类模板总览Class Template Synopsis规格文档给出的完整接口如下定义于头文件oneapi/tbb/concurrent_vector.h// Defined in header oneapi/tbb/concurrent_vector.h namespace oneapi { namespace tbb { template typename T, typename Allocator cache_aligned_allocatorT class concurrent_vector { using value_type T; using allocator_type Allocator; using size_type implementation-defined unsigned integer type; using difference_type implementation-defined signed integer type; using reference value_type; using const_reference const value_type; using pointer typename std::allocator_traitsallocator_type::pointer; using const_pointer typename std::allocator_traitsallocator_type::const_pointer; using iterator implementation-defined RandomAccessIterator; using const_iterator implementation-defined constant RandomAccessIterator; using reverse_iterator std::reverse_iteratoriterator; using const_reverse_iterator std::reverse_iteratorconst_iterator; using range_type implementation-defined ContainerRange; using const_range_type implementation-defined constant ContainerRange; // Construction, destruction, copying concurrent_vector(); explicit concurrent_vector( const allocator_type alloc ) noexcept; explicit concurrent_vector( size_type count, const value_type value, const allocator_type alloc allocator_type() ); explicit concurrent_vector( size_type count, const allocator_type alloc allocator_type() ); template typename InputIterator concurrent_vector( InputIterator first, InputIterator last, const allocator_type alloc allocator_type() ); concurrent_vector( std::initializer_listvalue_type init, const allocator_type alloc allocator_type() ); concurrent_vector( const concurrent_vector other ); concurrent_vector( const concurrent_vector other, const allocator_type alloc ); concurrent_vector( concurrent_vector other ) noexcept; concurrent_vector( concurrent_vector other, const allocator_type alloc ); ~concurrent_vector(); concurrent_vector operator( const concurrent_vector other ); concurrent_vector operator( concurrent_vector other ) noexcept(/*See details*/); concurrent_vector operator( std::initializer_listvalue_type init ); void assign( size_type count, const value_type value ); template typename InputIterator void assign( InputIterator first, InputIterator last ); void assign( std::initializer_listvalue_type init ); // Concurrent growth iterator grow_by( size_type delta ); iterator grow_by( size_type delta, const value_type value ); template typename InputIterator iterator grow_by( InputIterator first, InputIterator last ); iterator grow_by( std::initializer_listvalue_type init ); iterator grow_to_at_least( size_type n ); iterator grow_to_at_least( size_type n, const value_type value ); iterator push_back( const value_type value ); iterator push_back( value_type value ); template typename... Args iterator emplace_back( Args... args ); // Element access value_type operator[]( size_type index ); const value_type operator[]( size_type index ) const; value_type at( size_type index ); const value_type at( size_type index ) const; value_type front(); const value_type front() const; value_type back(); const value_type back() const; // Iterators iterator begin(); const_iterator begin() const; const_iterator cbegin() const; iterator end(); const_iterator end() const; const_iterator cend() const; reverse_iterator rbegin(); const_reverse_iterator rbegin() const; const_reverse_iterator crbegin() const; reverse_iterator rend(); const_reverse_iterator rend() const; const_reverse_iterator crend() const; // Size and capacity size_type size() const noexcept; bool empty() const noexcept; size_type max_size() const noexcept; size_type capacity() const noexcept; // Concurrently unsafe operations void reserve( size_type n ); void resize( size_type n ); void resize( size_type n, const value_type value ); void shrink_to_fit(); void swap( concurrent_vector other ) noexcept(/*See details*/); void clear(); allocator_type get_allocator() const; // Parallel iteration range_type range( size_type grainsize 1 ); const_range_type range( size_type grainsize 1 ) const; }; // class concurrent_vector } // namespace tbb } // namespace oneapi对照 TBB 的实现头文件 concurrent_vector.h 可以看到规范中的实现定义类型在实现里是具体落地的size_type是std::size_tdifference_type是std::ptrdiff_t见 concurrent_vector.h 中class concurrent_vector的类型别名段iterator/const_iterator是vector_iteratorconcurrent_vector, value_type一个基于下标而非裸指针的随机访问迭代器默认Allocator为tbb::cache_aligned_allocatorT即段segment内存按缓存行对齐分配减少多线程并发读写时的伪共享。三、类型要求Requirements规格文档对模板参数有明确约束使用容器前应先确认自己的元素类型满足元素类型T必须满足 ISO C 标准 [container.requirements] 中的Erasable要求T的析构函数不得抛出异常如果T的默认构造函数可能抛异常则其析构函数必须是非虚的并且能在全零填充的内存上正确工作。这条要求非常关键它直接支撑了后文异常安全一节中零填充元素的语义——容器内部会用零填充内存作为已分配但未构造状态的占位因此析构函数必须能安全地处理这种字节模式成员函数按操作类型的不同可能对T提出更严格的要求例如push_back要求CopyInsertableemplace_back要求EmplaceConstructible见下文Allocator必须满足 ISO C [allocator.requirements] 的分配器要求。四、并发增长接口Concurrent growth规格文档的 toctree 中并发增长是独立的一章concurrent_growth.rst。其首要结论是本节所有成员函数之间、与元素访问之间、与容器遍历之间都可以并发执行。各重载的精确语义如下4.1 grow_byiterator grow_by( size_type delta );在向量末尾追加delta个就地默认构造的新元素返回指向所追加序列首元素的迭代器。要求T满足DefaultConstructible与EmplaceConstructible。iterator grow_by( size_type delta, const value_type value );追加value的delta份拷贝。要求T满足CopyInsertable。template typename InputIterator iterator grow_by( InputIterator first, InputIterator last );把半开区间[first, last)的全部元素追加到末尾。仅当InputIterator满足 ISO C [input.iterators] 的输入迭代器要求时才参与重载决议。iterator grow_by( std::initializer_listvalue_type init );等价于grow_by(init.begin(), init.end())。4.2 grow_to_at_leastiterator grow_to_at_least( size_type n ); // 默认构造填充至 size() n iterator grow_to_at_least( size_type n, const value_type value ); // 用 value 拷贝填充追加使size() n所需的最少元素返回所追加序列的起点迭代器。适合在不知道当前size()它可能正被其他线程改变的前提下把容器扩容到某个目标水位。4.3 push_back / emplace_backiterator push_back( const value_type value ); // 拷贝插入要求 CopyInsertable iterator push_back( value_type value ); // 移动插入要求 MoveInsertable template typename... Args iterator emplace_back( Args... args ); // 就地构造要求 EmplaceConstructiblepush_back(value_type)会把源对象留在有效但未指定的状态三个函数都返回指向被追加元素的迭代器。注意所有增长函数返回的是迭代器而不是void这让调用者拿到本线程刚追加的那段元素的起点可以立即就地初始化这批元素而不用担心其他线程的追加插队进来。五、异常安全语义broken vector模型规格文档 concurrent_vector_cls.rst 的 Exception Safety 一节给出了一个诚实且有实用价值的结论并发增长与理想异常安全strong guarantee在原理上互斥但concurrent_vector提供了一个实用级别的异常安全保证。具体规则当增长或赋值过程中抛出异常时后果取决于异常来源异常来自元素构造函数所追加序列中所有后续元素将被零填充zero-filled异常来自分配器例如内存耗尽容器进入broken损坏状态。所追加序列中的每个元素处于三种状态之一已构造constructed、零填充zero-filled、内存未分配unallocated。对 broken 容器的访问规则用at访问未分配元素会抛出std::range_error用其他方法访问未分配元素是未定义行为capacity()和size()的值可能小于预期通过back()访问 broken 容器是未定义行为。但以下两条保证无论容器是否 broken 都成立若k是某个未分配元素的下标则size() capacity() k增长操作永远不会使size()或capacity()减小。另外一个重要保证是一次并发增长若成功完成那么它追加的序列即使在后续其他增长操作失败之后依然有效且可访问。这套语义解释了为什么前面类型要求中规定默认构造可能抛异常时析构函数必须能对零填充内存正确工作——零填充内存是已占位但构造未完成的显式中间状态容器析构时会对这些区域调用析构函数因此必须有此约定。六、元素访问、迭代器与并行迭代从规格文档 synopsis 可以直接读出以下访问与迭代接口元素访问operator[]不检查边界、at越界或未分配时抛std::range_error、front、back迭代器完整的begin/end/cbegin/cend与rbegin/rend/crbegin/crend反向迭代器规模与容量size、empty、max_size、capacity均为noexcept并行迭代range_type range( size_type grainsize 1 )及其 const 版本返回可直接喂给 TBB 并行算法如parallel_for的范围对象。规格文档还专门标注了一组并发不安全Concurrently unsafe操作reserve、resize、shrink_to_fit、swap、clear、get_allocator。也就是说只有增长类接口和读取类接口被设计为可并发改变整体布局的接口需要在无并发访问的静默期调用。使用时的正确姿势是多线程阶段只用push_back/grow_by/range等并发安全接口单线程阶段再做shrink_to_fit、clear等整理。七、源码级原理分段表让增长不失效成为可能接下来结合 TBB 实现头文件 concurrent_vector.h 看上述语义是怎么落地的。7.1 底层是 segment_table而非一整块连续内存__TBB_GLOBAL_VAR constexpr std::size_t embedded_table_num_segments 3; template typename T, typename Allocator tbb::cache_aligned_allocatorT class concurrent_vector : private segment_tableT, Allocator, concurrent_vectorT, Allocator, embedded_table_num_segmentsconcurrent_vector私有继承自segment_table定义于detail/_segment_table.h元素按段segment块状连续内存存放段之间由一张段表索引。对象内嵌前 3 个段槽embedded_table_num_segments 3且allow_table_extending true表示段表本身可以再扩展。从源码结构看这一设计直接实现了规格中的两条保证增长不失效迭代器/下标新元素总被追加到新段或当前段尾部之后旧段内存不动因此旧下标对应的地址永远不变size()/capacity()只增不减增长只是追加段/追加槽从不回收。7.2 迭代器下标 缓存指针实现中的vector_iterator只持有三样东西指向容器的指针、一个size_type下标my_index、以及一个mutable value_type* my_item缓存指针vector_iterator operator() { my_index; if (my_item ! nullptr) { if (vector_type::is_first_element_in_segment(my_index)) { // If the iterator crosses a segment boundary, the pointer become invalid // as possibly next segment is in another memory location my_item nullptr; } else { my_item; } } return *this; }细节值得品味迭代器在段内移动时用my_item指针步进快路径一旦跨段就把缓存置空因为下一段可能在完全不同的内存位置下次解引用再通过internal_subscript(my_index)走段表查地址慢路径。这样迭代器比较、差值运算都只是下标运算operator只比较my_vector和my_index代价小且天然与增长追加新段无冲突——这也正是规格中iterator 为实现定义 RandomAccessIterator背后的具体形态。7.3 noexcept 语义由分配器 traits 决定synopsis 中operator(concurrent_vector)与swap标注的noexcept(/*See details*/)在实现里是这样计算的static constexpr bool is_noexcept_assignment allocator_traits_type::propagate_on_container_move_assignment::value || allocator_traits_type::is_always_equal::value; static constexpr bool is_noexcept_swap allocator_traits_type::propagate_on_container_swap::value || allocator_traits_type::is_always_equal::value;即只有当分配器支持移动传播或者两个分配器恒等可比is_always_equal时移动赋值/交换才能承诺noexcept。这是遵循 [allocator.requirements] 的标准做法也提醒使用者自定义Allocator会影响容器的异常保证强度。八、非成员函数与推导指南规格文档还列出了容器级别的六个关系运算符与swaptemplate typename T, typename Allocator bool operator( const concurrent_vectorT, Allocator lhs, const concurrent_vectorT, Allocator rhs ); // 另有 operator!、operator、operator、operator、operator // 均为按字典序lexicographical比较 template typename T, typename Allocator void swap( concurrent_vectorT, Allocator lhs, concurrent_vectorT, Allocator rhs );文档同时说明一个实现自由度这些非成员函数所在的命名空间未指定只要对相应的比较/交换操作可达即可例如实现可以定义在内部命名空间而oneapi::tbb::concurrent_vector是一个类型别名非成员函数仅通过参数依赖查找可达。子文档 non_member_binary_comparisons.rst、non_member_lexicographical_comparisons.rst 与 non_member_swap.rst 分别细化了二元比较、字典序比较和 swap 的行为另见 deduction_guides.rst 中的 CTAD 推导指南。九、在 mold 链接器中的真实用法mold 默认把 oneTBB 以子目录方式静态内置见 CMakeLists.txtMOLD_USE_SYSTEM_TBB选项默认 OFF直接add_subdirectory(third-party/tbb)并链接TBB::tbb因此下文所有调用点都是 mold 自身代码。concurrent_vector在 mold 中的使用高度契合它的并行扫描 并发追加定位9.1 全局 Context 中的多线程共享池mold.h 中ContextE结构体集中声明了一批容器级对象池tbb::concurrent_vectorstd::pairstd::vectoru32, InputFileE * unsorted_input_files; tbb::concurrent_vectorArenaObjectPtrMergedSectionE merged_sections; tbb::concurrent_vectorstd::unique_ptrTimerRecord timer_records; tbb::concurrent_vectorArenaObjectPtrObjectFileE obj_pool; tbb::concurrent_vectorArenaObjectPtrSharedFileE dso_pool; tbb::concurrent_vectorstd::unique_ptru8[] string_pool; tbb::concurrent_vectorstd::unique_ptrMappedFile mf_pool; tbb::concurrent_vectorstd::unique_ptrChunkE chunk_pool;从源码结构看mold 把输入文件去重池obj_pool/dso_pool、合并段池merged_sections、字符串池、chunk 池全部建成concurrent_vector解析阶段大量工作线程通过tbb::parallel_for_each并行扫描对象文件随时往这些池里push_back新条目而下标/指针不因增长而失效保证了已发布的ArenaObjectPtr等引用在并发窗口内持续有效。9.2 hidden 符号解析循环src/passes.cc 中 hidden 可见性符号的再解析循环是一个典型用例for (;;) { tbb::concurrent_vectorSymbolE * hidden; ctx.symbol_map.parallel_for_each( { if (sym.file sym.file-is_dso sym.file-is_reachable sym.visibility STV_HIDDEN) { sym.skip_dso true; hidden.push_back(sym); } }); if (hidden.empty()) break; ... }多工作线程在parallel_for_each中对符号表做只读扫描发现需要跳过 DSO 重新解析的 hidden 符号就并发push_back进hidden循环体在下一轮之前单线程地遍历该向量并clear_symbol然后再次并行解析。这正是并发安全接口push_back用于并行窗口、非并发接口留到静默期使用的标准范式。9.3 GC 根集与 ICF 去重集合gc-sections.cc 中collect_root_set返回tbb::concurrent_vectorInputSectionE *多线程收集 GC 根节随后做可达性分析icf.cc 中tbb::concurrent_vectorInputSectionE * leader_sections;用于 ICF相同代码折叠阶段并发登记 leader 节。9.4 启动期 reader 任务与性能计时main.cc 中tbb::concurrent_vectorReaderJob scripts;收集各线程发现的输入任务perf.cc 与 lib.h 中tbb::concurrent_vectorstd::unique_ptrTimerRecord保存各线程产生的计时记录供-v的耗时报告汇总。这些调用点共同印证了规格文档描述的容器画像只增长、只读遍历、追加后立刻可用且增长不打断正在进行的遍历——恰好是链接器多遍并行处理所需要的容器契约。十、使用要点小结接口选型并行阶段只用push_back/emplace_back/grow_by/grow_to_at_least与range()resize/clear/reserve/shrink_to_fit/swap属于并发不安全操作必须放在无并发访问的窗口执行元素类型约束默认构造可抛异常的类型必须保证析构函数非虚且能对零填充内存正确工作否则违反规格要求异常安全预期不要期待 strong guarantee。分配器抛异常后容器可能 broken此时用at探测未分配区域抛std::range_error依赖size() capacity() k与size()/capacity()单调不减两条不变量做恢复逻辑迭代器模型实现上是下标 段内缓存指针的随机访问迭代器跨段自动失效缓存因此旧迭代器在并发增长下永远有效但段内缓存要求元素一经构造不被移动——这与分段存储是同一枚硬币的两面allocator 影响 noexcept移动赋值/交换的noexcept由分配器的propagate_on_*与is_always_equaltraits 决定自定义分配器时需注意这一耦合。规格文档其余章节construct_destroy_copy.rst、element_access.rst、iterators.rst、size_and_capacity.rst、unsafe_operations.rst、parallel_iteration.rst对上述各组成员函数有逐条的更细粒度规定可作为接口行为的权威依据。【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/mold创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考