en	﻿[#concurrent] = Concurrent Containers
zh-hans	= 并发容器

en	:idprefix: concurrent_

en	Boost.Unordered provides `boost::concurrent_node_set`, `boost::concurrent_node_map`, `boost::concurrent_flat_set` and `boost::concurrent_flat_map`, hash tables that allow concurrent write/read access from different threads without having to implement any synchronzation mechanism on the user's side.
zh-hans	Boost.Unordered 提供 `boost::concurrent_node_set` 、 `boost::concurrent_node_map` 、 `boost::concurrent_flat_set` 和 `boost::concurrent_flat_map` ，这些哈希表允许不同线程进行并发读写访问，无需用户实现任何同步机制。

en	In the example above, threads access `m` without synchronization, just as we'd do in a single-threaded scenario. In an ideal setting, if a given workload is distributed among _N_ threads, execution is _N_ times faster than with one thread —this limit is never attained in practice due to synchronization overheads and _contention_ (one thread waiting for another to leave a locked portion of the map), but Boost.Unordered concurrent containers are designed to perform with very little overhead and typically achieve _linear scaling_ (that is, performance is proportional to the number of threads up to the number of logical cores in the CPU).
zh-hans	在上例中，线程无需同步即可访问 `m` ，这与单线程场景中的操作方式一致。在理想情况下，若将给定工作负载分配给 _N_ 个线程，其执行速度相较单线程提升 _N_ 倍——由于同步开销与__争用__的存在（某线程等待其他线程离开容器的锁定区域），实践中无法达到此理论极限。但 Boost.Unordered 并发容器设计为以极低开销运行，通常可实现__线性扩展__（即性能提升与线程数量成正比，直至达到 CPU 的逻辑核心数）。

en	Visitation-based API
zh-hans	基于访问的 API

en	The first thing a new user of Boost.Unordered concurrent containers will notice is that these classes _do not provide iterators_ (which makes them technically not https://en.cppreference.com/w/cpp/named_req/Container[Containers^] in the C++ standard sense). The reason for this is that iterators are inherently thread-unsafe. Consider this hypothetical code:
zh-hans	Boost.Unordered 并发容器的新用户首先会注意到：这些类__不提供迭代器__（它们在技术层面上不符合 C{plus}{plus} 标准中的 https://en.cppreference.com/w/cpp/named_req/Container[容器] 定义）。因为迭代器本质上是线程不安全的。请参考以下假设代码：

en	In a multithreaded scenario, the iterator `it` may be invalid at point B if some other thread issues an `m.erase(k)` operation between A and B. There are designs that can remedy this by making iterators lock the element they point to, but this approach lends itself to high contention and can easily produce deadlocks in a program. `operator[]` has similar concurrency issues, and is not provided by `boost::concurrent_flat_map`/`boost::concurrent_node_map` either. Instead, element access is done through so-called _visitation functions_:
zh-hans	多线程场景中，若其他线程在 A 和 B 之间执行 `m.erase(k)` 操作，迭代器 `it` 可能在 B 点失效。虽然存在通过锁定指向元素来修复此问题的设计方案，但这种方法容易引发高竞争并可能导致程序死锁。 `operator++[]++` 也存在类似并发问题，因此 `boost::concurrent++_++flat++_++map` / `boost::concurrent++_++node++_++map` 也未提供该操作。替代方案是通过__访问函数__操作元素：

en	The visitation function passed by the user (in this case, a lambda function) is executed internally by Boost.Unordered in a thread-safe manner, so it can access the element without worrying about other threads interfering in the process.
zh-hans	用户传递的访问函数（此处为 lambda 函数）由 Boost.Unordered 在内部以线程安全的方式执行，因此该函数可以安全访问目标元素，无需担心其他线程在此过程中造成干扰。

en	On the other hand, a visitation function can _not_ access the container itself:
zh-hans	另一方面，访问函数__无法__访问容器本身：

en	Access to a different container is allowed, though:
zh-hans	但允许访问其他容器：

en	But, in general, visitation functions should be as lightweight as possible to reduce contention and increase parallelization. In some cases, moving heavy work outside of visitation may be beneficial:
zh-hans	但通常而言，访问函数应尽可能轻量以减少争用并提升并行性。在某些情况下，将繁重操作移出访问函数可能更优：

en	Visitation is prominent in the API provided by concurrent containers, and many classical operations have visitation-enabled variations:
zh-hans	访问机制在并发容器 API 中占据核心地位，许多经典操作都提供了支持访问机制的变体：

en	Note that in this last example the visitation function could actually _modify_ the element: as a general rule, operations on a concurrent map `m` will grant visitation functions const/non-const access to the element depending on whether `m` is const/non-const. Const access can be always be explicitly requested by using `cvisit` overloads (for instance, `insert_or_cvisit`) and may result in higher parallelization. For concurrent sets, on the other hand, visitation is always const access.
zh-hans	注意此例中访问函数可__修改__元素：作为通用规则，对并发映射 `m` 的操作将根据 `m` 是否为常量类型，授予访问函数对元素的常量/非常量访问权限。 通过使用 `cvisit` 重载（如 `insert++_++or++_++cvisit` ）可始终显式请求常量访问，这可能提升并行性。而并发集合的访问始终为常量访问。

en	Although expected to be used much less frequently, concurrent containers also provide insertion operations where an element can be visited right after element creation (in addition to the usual visitation when an equivalent element already exists):
zh-hans	尽管预期使用频率较低，并发容器还提供在元素创建后立即进行访问的插入操作（除在已存在等价元素时执行常规访问之外）：

en	Consult the references of `xref:reference/concurrent_node_set.adoc#concurrent_node_set[boost::concurrent_node_set]`, `xref:reference/concurrent_node_map.adoc#concurrent_node_map[boost::concurrent_node_map]`, `xref:reference/concurrent_flat_set.adoc#concurrent_flat_set[boost::concurrent_flat_set]` and `xref:reference/concurrent_flat_map.adoc#concurrent_flat_map[boost::concurrent_flat_map]` for the complete list of visitation-enabled operations.
zh-hans	支持访问功能的完整操作列表请参阅 xref:reference/concurrent_node_set.adoc#concurrent_node_set[`boost::concurrent++_++node++_++set`] 、 xref:reference/concurrent_node_map.adoc#concurrent_node_map[`boost::concurrent++_++node++_++map`] 、 xref:reference/concurrent_flat_set.adoc#concurrent_flat_set[`boost::concurrent++_++flat++_++set`] 和 xref:reference/concurrent_flat_map.adoc#concurrent_flat_map[`boost::concurrent++_++flat++_++map`] 的参考文档。

en	Whole-Table Visitation
zh-hans	全表访问

en	In the absence of iterators, `visit_all` is provided as an alternative way to process all the elements in the container:
zh-hans	在缺乏迭代器的情况下， `visit++_++all` 提供处理容器内全部元素的替代方案：

en	In C++17 compilers implementing standard parallel algorithms, whole-table visitation can be parallelized:
zh-hans	在支持标准并行算法的 C{plus}{plus}17 编译器中，全表遍历访问可进行并行化处理：

en	Traversal can be interrupted midway:
zh-hans	遍历过程可中途中断：

en	There is one last whole-table visitation operation, `erase_if`:
zh-hans	最后一项全表访问操作是 `erase++_++if` ：

en	`visit_while` and `erase_if` can also be parallelized. Note that, in order to increase efficiency, whole-table visitation operations do not block the table during execution: this implies that elements may be inserted, modified or erased by other threads during visitation. It is advisable not to assume too much about the exact global state of a concurrent container at any point in your program.
zh-hans	`visit++_++while` 与 `erase++_++if` 同样支持并行化。需要注意的是，为提升执行效率，全表遍历操作在运行期间不会锁定整个容器：这意味着在遍历过程中，其他线程可能同时执行元素的插入、修改或删除操作。建议在程序中避免对并发容器在任意时间点的全局状态做过强的假设。

en	Bulk visitation
zh-hans	批量访问

en	Suppose you have an `std::array` of keys you want to look up for in a concurrent map:
zh-hans	假设有一个 `std::array` 存储了需要在并发映射中查找的键：

en	_Bulk visitation_ allows us to pass all the keys in one operation:
zh-hans	__批量访问__允许用户通过单次操作传入所有键：

en	This functionality is not provided for mere syntactic convenience, though: by processing all the keys at once, some internal optimizations can be applied that increase performance over the regular, one-at-a-time case (consult the xref:benchmarks.adoc#benchmarks_boostconcurrent_flatnode_map[benchmarks]). In fact, it may be beneficial to buffer incoming keys so that they can be bulk visited in chunks:
zh-hans	提供此功能并非仅出于语法便利性考量：通过一次性处理所有键，可应用内部优化提升性能（详见 xref:benchmarks.adoc#benchmarks_boostconcurrent_flatnode_map[基准测试]）。实际上，用户可通过缓冲输入键值以实现分块批量访问，从而进一步提升效率：

en	There's a latency/throughput tradeoff here: it will take longer for incoming keys to be processed (since they are buffered), but the number of processed keys per second is higher. `bulk_visit_size` is the recommended chunk size —smaller buffers may yield worse performance.
zh-hans	这里存在延迟与吞吐量的权衡：缓冲机制会延长单个键的处理延迟，但每秒处理的键总数（吞吐量）会更高。 `bulk++_++visit++_++size` 是推荐的缓冲区块大小——过小的缓冲区可能导致性能下降。

en	Blocking Operations
zh-hans	阻塞式操作

en	Concurrent containers can be copied, assigned, cleared and merged just like any other Boost.Unordered container. Unlike most other operations, these are _blocking_, that is, all other threads are prevented from accesing the tables involved while a copy, assignment, clear or merge operation is in progress. Blocking is taken care of automatically by the library and the user need not take any special precaution, but overall performance may be affected.
zh-hans	并发容器可像其他 Boost.Unordered 容器一样支持复制、赋值、清空和合并操作。与大多数其他操作不同，这些属于__阻塞式操作__：在执行期间，其他线程将被阻止访问相关容器。该阻塞机制由库自动处理，用户无需采取特殊预防措施，但整体性能可能受到影响。

en	Another blocking operation is _rehashing_, which happens explicitly via `rehash`/`reserve` or during insertion when the table's load hits `max_load()`. As with non-concurrent containers, reserving space in advance of bulk insertions will generally speed up the process.
zh-hans	另一阻塞操作是__重哈希__，该操作可通过 `rehash` / `reserve` 显式触发，或在插入过程中当容器负载达到 `max++_++load()` 时自动执行。与非并发容器类似，在批量插入前预先分配空间通常能加速处理过程。

en	Interoperability with non-concurrent containers
zh-hans	与非并发容器的互操作性

en	As open-addressing and concurrent containers are based on the same internal data structure, they can be efficiently move-constructed from their non-concurrent counterpart, and vice versa.
zh-hans	由于开放寻址容器与并发容器基于相同的内部数据结构，它们可以高效地通过移动构造从其非并发对应容器转换而来，反之亦然。

en	^|`boost::concurrent_node_set` ^|`boost::unordered_node_set`

en	^|`boost::concurrent_node_map` ^|`boost::unordered_node_map`

en	^|`boost::concurrent_flat_set` ^|`boost::unordered_flat_set`

en	^|`boost::concurrent_flat_map` ^|`boost::unordered_flat_map`
zh-hans	^|`boost::concurrent_flat_set` ^|`boost::unordered_flat_set`

en	This interoperability comes handy in multistage scenarios where parts of the data processing happen in parallel whereas other steps are non-concurrent (or non-modifying). In the following example, we want to construct a histogram from a huge input vector of words: the population phase can be done in parallel with `boost::concurrent_flat_map` and results then transferred to the final container.
zh-hans	此互操作性适用于多阶段场景：部分数据处理环节需要并行执行，而其他步骤采用非并发（或只读）模式。下例中，我们需要从一个庞大的单词输入向量构建词频统计直方图：填充阶段用 `boost::concurrent++_++flat++_++map` 并行执行，随后将结果转移至最终容器。