# ConcurrentCollections.jl: "lock-free" dictionary, queue, etc. for Julia 1.7

**URL:** <https://discourse.julialang.org/t/concurrentcollections-jl-lock-free-dictionary-queue-etc-for-julia-1-7/72501>\
**Category:** Package Announcements\
**Tags:** multithreading\
**Created:** [December 3, 2021, 3:37am UTC](https://discourse.julialang.org/t/concurrentcollections-jl-lock-free-dictionary-queue-etc-for-julia-1-7/72501 "2021-12-03T03:37:18Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![tkf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkf/32/17635_2.png) [@tkf](https://discourse.julialang.org/u/tkf)\
**Post date:** [December 3, 2021, 3:37am UTC](https://discourse.julialang.org/t/concurrentcollections-jl-lock-free-dictionary-queue-etc-for-julia-1-7/72501/1 "2021-12-03T03:37:18Z")

</div>

I’m happy to announce a new package [ConcurrentCollections.jl](https://github.com/JuliaConcurrent/ConcurrentCollections.jl) that implements a couple of thread-safe collections for Julia 1.7:

- [`DualLinkedConcurrentRingQueue`](https://juliaconcurrent.github.io/ConcurrentCollections.jl/dev/#ConcurrentCollections.DualLinkedConcurrentRingQueue)
- [`DualLinkedQueue`](https://juliaconcurrent.github.io/ConcurrentCollections.jl/dev/#ConcurrentCollections.DualLinkedQueue)
- [`LinkedConcurrentRingQueue`](https://juliaconcurrent.github.io/ConcurrentCollections.jl/dev/#ConcurrentCollections.LinkedConcurrentRingQueue)
- [`ConcurrentQueue`](https://juliaconcurrent.github.io/ConcurrentCollections.jl/dev/#ConcurrentCollections.ConcurrentQueue)
- [`ConcurrentStack`](https://juliaconcurrent.github.io/ConcurrentCollections.jl/dev/#ConcurrentCollections.ConcurrentStack)
- [`WorkStealingDeque`](https://juliaconcurrent.github.io/ConcurrentCollections.jl/dev/#ConcurrentCollections.WorkStealingDeque)
- [`ConcurrentDict`](https://juliaconcurrent.github.io/ConcurrentCollections.jl/dev/#ConcurrentCollections.ConcurrentDict)

These collections supports [non-blocking](https://en.wikipedia.org/wiki/Non-blocking_algorithm) (“lock-free”) APIs whenever appropriate. As a result, these collections are useful for low-level optimizations of communication-intensive multi-threaded programs.

You can install it by simply typing “`using ConcurrentCollections` Enter Enter” in Julia 1.7 (thanks to the new [automatic package installation](https://julialang.org/blog/2021/11/julia-1.7-highlights/#automatic_package_installation)).

ConcurrentCollections.jl is built on top of the shiny new [atomics API for Julia 1.7](https://julialang.org/blog/2021/11/julia-1.7-highlights/#new_threading_capabilities). For more information on Julia’s new atomics capabilities, see [Atomic fields: the new primitives on the block | Jameson Nash | JuliaCon2021 - YouTube](https://www.youtube.com/watch?v=2rBv6sV4Xts).

## Benchmarks

### Dual Linked Concurrent Ring Queue (LCRQ)

ConcurrentCollections.jl implements the “almost non-blocking” dual LCRQ based on [Izraelevitz and Scott (2017)](https://doi.org/10.1145/3040220). This is similar to `Base.Channel`; i.e., a first-in-first-out container where `popfirst!` will wait until the item is available. I [implemented](https://github.com/JuliaConcurrent/ConcurrentCollections.jl/blob/7c3d94b24a36506e2d84161648b95ecf116312bb/benchmark/ConcurrentCollectionsBenchmarks/src/bench_queue_hot_potato.jl) the “hot potato” benchmark similar to the one by them and compare the result with the performance of `Base.Channel`.

 ![image](https://global.discourse-cdn.com/julialang/original/3X/c/f/cfb44328a6dcb762e12dc4f4637bd7b5a17821f2.png)

As you can see, the dual LCRQ (orange) has a much higher throughput than `Base.Channel` (blue). The dual LCRQ performance also is comparable to a “hardware limit” (red) which simply repeatedly executes atomic fetch-and-increment (FAI) instructions from multiple Julia tasks. Note that the original C++ implementation by Izraelevitz and Scott (2017) exhibits the performance much closer to the FAI throughput. So, there is still more room for improvement \[1\]. But I’m glad that we can still write concurrent algorithms in Julia that are in the same order of magnitude as the hardware limit.

Note that this dual LCRQ implementation has a much higher memory footprint than `Base.Channel`. Also, it doesn’t implement `close` API yet.

### `ConcurrentDict`

ConcurrentCollections.jl also implements a mostly lock-free dictionary, inspired by [Maier et al. (2019)](https://dl.acm.org/doi/10.1145/3309206) and [Click (2007)](https://www.youtube.com/watch?v=HJ-719EGIts). As a benchmark, I [implemented](https://github.com/JuliaConcurrent/ConcurrentCollections.jl/blob/c5edb155bcaf6e8100d4b7a1117040136e664352/benchmark/ConcurrentCollectionsBenchmarks/src/bench_dict_histogram.jl) a histogram (“`countmap`”) function using `ConcurrentDict`. For a comparison, I also implemented it using `Base.Dict` based on [the data-parallel approach](https://juliafolds.github.io/data-parallelism/tutorials/mutations/#combining_containers) that I usually recommend.

 ![image](https://global.discourse-cdn.com/julialang/original/3X/0/b/0bb913824848a9c5977ec1bffd1cf5c37600e5a2.png)

As you can see, `ConcurrentDict` (right) performs well across a wide range of access patterns (color). On the other hand, using task-local `Base.Dict`s in a divide-and-conquer fashion (left) performs better when there are many elements per one slot (higher “Access density” \[2\]). This is presumably because the output dictionaries are small and the cost for merging them is not dominating. However, if there is virtually no overlap between the keys processed by different tasks (lower “Access density”), the cost for merging the dictionaries dominates and you can’t expect the speedup. You can also see that `ConcurrentDict` is slower with the single-task case because of the extra overhead for the concurrent algorithm compared to the sequential algorithm in `Base.Dict`. Overall, I think this benchmark indicates “lock-free” is not _always_ a win. However, one of the scenarios where it can shine is when you need to update data structures concurrently and they are too large for each task to have their own working copies.

* * *

1. A quick profiling suggests that a non-negligible amount of the time is spent while zeroing out the arrays with boxed values (required for GC). Creating arrays using `calloc` may be an interesting optimization (ref: [Faster zeros with calloc](https://discourse.julialang.org/t/faster-zeros-with-calloc/69860)). It also may be worth considering switching to a slightly more lockful approach to reduce memory footprint and thus zeroing cost. 

2. The “Access density” reflects how many duplicated elements exist in the data. More precisely, it is defined as `datasize / nkeys` where I generate the data using

---

<div class="post-metadata">

**Author:** ![melonedo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/melonedo/32/15503_2.png) [@melonedo](https://discourse.julialang.org/u/melonedo)\
**Post date:** [December 3, 2021, 5:28am UTC](https://discourse.julialang.org/t/concurrentcollections-jl-lock-free-dictionary-queue-etc-for-julia-1-7/72501/2 "2021-12-03T05:28:50Z")

</div>

Maybe a bit sidestepping, I see a series of `maybe*` methods in your package: `maybeget`, `maybepop!`, etc. Has this been a trend in Julia 1.7, or are you following some guidelines?

---

<div class="post-metadata">

**Author:** ![tkf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkf/32/17635_2.png) [@tkf](https://discourse.julialang.org/u/tkf)\
**Post date:** [December 3, 2021, 5:58am UTC](https://discourse.julialang.org/t/concurrentcollections-jl-lock-free-dictionary-queue-etc-for-julia-1-7/72501/3 "2021-12-03T05:58:07Z")

</div>

I don’t think there’s any established guideline. I just used what _I_ thought least confusing (i.e., treating `Union{Some,Nothing}` as a maybe value). But, in fact, there are a few recent discussions in Julia around this

- [https://github.com/JuliaLang/julia/pull/34821](https://github.com/JuliaLang/julia/pull/34821)
- [https://github.com/JuliaLang/julia/pull/41966](https://github.com/JuliaLang/julia/pull/41966)

It’s also nice to go beyond the “maybe” APIs. When you use concurrent data structures, it’d be nice to have a low-level API that tells you why certain operations failed (empty collection? contention? locked?). Throwing an exception is too slow in a tight loop but there’s no established convention for the success/error sum type. There are ErrorTypes.jl, ResultTypes.jl, and Expect.jl but, IIRC, none of them seem to try to exploit union-split capability in Julia which is rather unfortunate (although there are of course legit reasons why you don’t want to use `Union`). Ref: [[ANN] ErrorTypes.jl - Rust-like safe errors in Julia](https://discourse.julialang.org/t/ann-errortypes-jl-rust-like-safe-errors-in-julia/53953)