Thoughts on atomics API

[tkf]

Tagged pointer

The state of the slot is stored "within" the key field if possible:

https://github.com/tkf/ConcurrentCollections.jl/blob/03a3aede139e9e7dcfb4dad782410d14ef0772e6/src/dict.jl#L10-L16

If the Key is heap-allocated (e.g., String) or more than 7 bytes (e.g., Int64), the Key or the entire slot (pair) has to go behind a pointer. However, it is wasteful to go through one indirection just for figuring out the state of the slot. It'd be great if these states can be stored in the lower bits of the pointer for the Key.

(This is true in general in non-blocking data structures.)

Function generic over the ordering (or the lack thereof)

There is a case where it'd be useful to use the same interface with and without atomic ordering:

https://github.com/tkf/ConcurrentCollections.jl/blob/03a3aede139e9e7dcfb4dad782410d14ef0772e6/src/dict.jl#L694-L695

This happens because the data structure (here an array newslots) is constructed in a non-atomic data-race-free manner in one phase before it is "published" for concurrent updates.

For this type of usage, it'd make sense to use singleton types as the memory ordering flags, so that they can propagate through function boundaries reliably.

Loading a subset of fields of immutables stored in an array

ConcurrentDict's slots is essentially a Vector{Pair{Key,Value}}. To support the key/value types with 8 <= sizeof(Pair{Key,Value}) <= 16, efficiently, the key and value are loaded with separate instructions ¹. This is for avoiding expensive cmpxchg16b just for loading the keys (probing).

Currently, it's done with manual pointer arithmetics. It'd be nice to create a higher-level API using something akin to ReinterpretArray.

Appendix: LLVM's lowering of 128 bit atomic load

julia> using ConcurrentCollections.Implementations: UnsafeAtomics

julia> @code_llvm UnsafeAtomics.load(Ptr{UInt128}(0))
;  @ /home/arakaki/.julia/dev/ConcurrentCollections/src/UnsafeAtomics.jl:20 within `load'
define void @julia_load_339(i128* noalias nocapture sret %0, i64 zeroext %1) {
top:
;  @ /home/arakaki/.julia/dev/ConcurrentCollections/src/UnsafeAtomics.jl:20 within `load' @ /home/arakaki/.julia/dev/ConcurrentCollections/src/UnsafeAtomics.jl:25
  %ptr.i = inttoptr i64 %1 to i128*
  %rv.i = load atomic i128, i128* %ptr.i seq_cst, align 16
;  @ /home/arakaki/.julia/dev/ConcurrentCollections/src/UnsafeAtomics.jl:20 within `load'
  store i128 %rv.i, i128* %0, align 8
  ret void
}

julia> @code_native UnsafeAtomics.load(Ptr{UInt128}(0))
        .text
; ┌ @ UnsafeAtomics.jl:20 within `load' @ UnsafeAtomics.jl:20
        pushq   %rbx
; │ @ UnsafeAtomics.jl:20 within `load' @ UnsafeAtomics.jl:25
        xorl    %eax, %eax
        xorl    %edx, %edx
        xorl    %ecx, %ecx
        xorl    %ebx, %ebx
        lock
        cmpxchg16b      (%rsi)
; │ @ UnsafeAtomics.jl:20 within `load'
        movq    %rdx, 8(%rdi)
        movq    %rax, (%rdi)
        movq    %rdi, %rax
        popq    %rbx
        retq
        nopw    (%rax,%rax)
; └

Footnotes

1. Torn read of key and value (but not within each) is harmless in this case. See: Maier et al. (2019) Concurrent Hash Tables: Fast and General(?)! https://doi.org/10.1145/3309206 ↩