# Hazard pointers - in C++26 vs Julia - concurrency/atomics e.g. for UInt128

**URL:** <https://discourse.julialang.org/t/hazard-pointers-in-c-26-vs-julia-concurrency-atomics-e-g-for-uint128/108866>\
**Category:** Offtopic\
**Tags:** atomic, concurrency\
**Created:** [January 16, 2024, 12:48pm UTC](https://discourse.julialang.org/t/hazard-pointers-in-c-26-vs-julia-concurrency-atomics-e-g-for-uint128/108866 "2024-01-16T12:48:08Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![Palli](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/palli/32/3380_2.png) [@Palli](https://discourse.julialang.org/u/Palli)\
**Post date:** [January 16, 2024, 12:48pm UTC](https://discourse.julialang.org/t/hazard-pointers-in-c-26-vs-julia-concurrency-atomics-e-g-for-uint128/108866/1 "2024-01-16T12:48:09Z")

</div>

I hadn’t seen this concept, and wanted to let others know, and ask how it contrasts to Julia, but to answer my own question:

> **[Hazard pointer](https://en.wikipedia.org/wiki/Hazard_pointer)**
>
> In a multithreaded computing environment, hazard pointers are one approach to solving the problems posed by dynamic memory management of the nodes in a lock-free data structure. These problems generally arise only in environments that don't have automatic garbage collection.
> Any lock-free data structure that uses the compare-and-swap primitive must deal with the ABA problem. For example, in a lock-free stack represented as an intrusively linked list, one thread may be attempting to pop an item f...

> In a [multithreaded](https://en.wikipedia.org/wiki/Thread_(computer_science)) [computing](https://en.wikipedia.org/wiki/Computer_science) environment, **hazard pointers** are one approach to solving the problems posed by [dynamic memory management](https://en.wikipedia.org/wiki/Dynamic_memory_management) of the nodes in a [lock-free](https://en.wikipedia.org/wiki/Non-blocking_algorithm) [data structure](https://en.wikipedia.org/wiki/Data_structure). These problems generally arise only in environments that don’t have [automatic garbage collection](https://en.wikipedia.org/wiki/Automatic_garbage_collection).

So Julia doesn’t need it, nor likely much of the new support in C++20, 23 and coming in 26. But you CAN program in Julia at a lower level, avoiding the GC, and then you might…

One way to deal with concurrency is to only use immutables, e.g. ruling out the default Dict. but recent HAMT implementations helps with that. With no mutables (that also includes the default mutable arrays/vectors, but not default strings) there are NO bug or security issues regarding concurrency.

Running Julia as default, i.e. not with -t auto, or some number other than 1, avoids some bug issues. But concurrency is frequently wanted for speed.

Then you need to lock and/or use atomic access. Types up to U/Int64 allow atomic access with the default alignment, but it’s not clear to me with e.g. UInt128. @Elrod On all modern cached CPUs, I believe no problem, assuming the type doesn’t split across cache lines, but it doesn’t have 128-bit alignment, only 64-bit. I think that decision for Julia was done to not waste space, emulating other languages such as C++. It’s been a little hard for me to dig into if it’s atomic in Julia or other languages, as it depends on the CPU more than the lang spec. ChatGPT has npot been very helpful, basically “it depends” on the CPU. But I want a guarantee (for all (modern) CPU, and not just x86. Though even just knowing for most common, e.g. x86 and ARM would be nice.

Is the rule that you are unsafe for larger types/structs? Without explicit locking? I want to know for without, or “lock-free”. Note, I think BigFloat/BigInt are actually safe, since hidden behind a (no large-than) 64-bit pointer.

E.g. a rational of Int64, the default Rational is likely not safe. I’m asking because I’m implementing a new one, SIMD rational…

> **[First Look at Hazard Pointers](https://melodiessim.netlify.app/intro-hazard-ptrs/)**
>
> Hazard pointers are a solution to safe memory reclaimation to lock-free concurrent objects. To motivate the use of hazard pointers, let us consider a problem: we want to implement a concurrent key-value map that satisfy the Write-Rarely-Read-Many...

> To motivate the use of hazard pointers, let us consider a problem: we want to implement a concurrent key-value map that satisfy the Write-Rarely-Read-Many (WRRM) property. WRRM maps are commonly used as caches, and in use cases such as a lookup table for currency to exchange rates where the map is looked up many times but only updated at a comparatively much slower rate.
> 
> In other words, we want to implement a multithreaded-access map interface, using a single threaded map object such as `std::map`.

> **[p2530r3.pdf](https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/p2530r3.pdf)**
>
> 342.40 KB

> 1.4 Rationale for inclusion in C++26  
> This proposal is based on the experience gained from hazard pointer implementation in the Facebook Folly open-source library (since 2016) and its heavy use in production (since 2017)

Why in std:  
[https://www.reddit.com/r/cpp/comments/sywjf3/p2530\_hazard\_pointers\_belong\_in\_the\_standard/](https://www.reddit.com/r/cpp/comments/sywjf3/p2530_hazard_pointers_belong_in_the_standard/)

> I’m nominally a coauthor, although just because of my work on the original hazard pointer paper. The paper gives a pitch for “sooner rather than later”, but doesn’t really emphasize the answer to “why include it” […]

It was a bit too much for me to start a 5 hour video “Implementing Hazard Pointers in Rust” on a language I don’t (currently) use:

[![](https://global.discourse-cdn.com/julialang/original/3X/8/8/8821571eca449c81d618d63bad0cd51a23a1eea0.jpeg "Implementing Hazard Pointers in Rust") ](https://www.youtube.com/watch?v=fvcbyCYdR10)

[![](https://global.discourse-cdn.com/julialang/original/3X/a/e/aee8677b62ed704233587fe165b619dc9016a6d6.jpeg "Hazard Pointer Synchronous Reclamation Beyond Concurrency TS2 - Maged Michael - CppCon 2021") ](https://www.youtube.com/watch?v=lsy8RRq2hHM)

“Brief” introduction:

[![](https://global.discourse-cdn.com/julialang/original/3X/5/1/514eb845ad211df6e56e872b5ac4a71244a13106.jpeg "Brief Announcement: Hazard Pointer Protection of Structures with Immutable Links") ](https://www.youtube.com/watch?v=HYCPN6Kp_Ao)

---

<div class="post-metadata">

**Author:** ![Elrod](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/elrod/32/22461_2.png) [@Elrod](https://discourse.julialang.org/u/Elrod)\
**Post date:** [January 16, 2024, 2:16pm UTC](https://discourse.julialang.org/t/hazard-pointers-in-c-26-vs-julia-concurrency-atomics-e-g-for-uint128/108866/3 "2024-01-16T14:16:11Z")

</div>

> [@Palli](#):
>
> Then you need to lock and/or use atomic access. Types up to U/Int64 allow atomic access with the default alignment, but it’s not clear to me with e.g. UInt128. @Elrod On all modern cached CPUs, I believe no problem, assuming the type doesn’t split across cache lines, but it doesn’t have 128-bit alignment, only 64-bit.

`Threads.Atomic{UInt128}` has 16 byte alignment:

```julia
julia> x = Threads.Atomic{UInt128}(4);

julia> @cl x[]
julia> @code_llvm debuginfo = :none x[]
define void @julia_getindex_306(i128* noalias nocapture noundef nonnull sret(i128) align 8 dereferenceable(16) %0, {}* noundef nonnull align 8 dereferenceable(16) %1) #0 {
top:
  %2 = bitcast {}* %1 to i128*
  %rv.i = load atomic i128, i128* %2 acquire, align 16
  store i128 %rv.i, i128* %0, align 8
  ret void
}

```

so our load here is `align 16`.

If you mark a field `@atomic`, the mutable struct will be padded appropriately:

```julia
julia> mutable struct Foo
           x::Int
           @atomic y::UInt128
           z::Int
       end

julia> mutable struct Bar
           x::Int
           y::UInt128
           z::Int
       end

julia> sizeof(Foo), sizeof(Bar)
(48, 32)

```

but the `Foo` struct itself still has 8-byte alignment instead of 16, defeating the benefit of padding it.  
Thus, loading requires a lock/unlock:

```julia
julia> gety(x::Foo) = x.y
gety (generic function with 1 method)

julia> @cl gety(Foo(1,1,1))
julia> @code_llvm debuginfo = :none gety(Foo(1, 1, 1))
define void @julia_gety_393(i128* noalias nocapture noundef nonnull sret(i128) align 8 dereferenceable(16) %0, {}* noundef nonnull align 8 dereferenceable(48) %1) #0 {
top:
  %2 = bitcast {}* %1 to i8*
  %3 = getelementptr inbounds i8, i8* %2, i64 24
  call void @jl_lock_value({}* %1)
  %4 = bitcast i8* %3 to i128*
  %5 = load i128, i128* %4, align 8
  call void @jl_unlock_value({}* %1)
  store i128 %5, i128* %0, align 8
  ret void
}

```

instead of a single atomic operation.

I would suggest sticking with the primitives, and checking generated code as I did above to get an idea whether codegen was good.  
You could file an issue over the alignment of `Foo` being too small to allow efficient atomic access (or over any other cases with suboptimal codegen you encounter).

---

<div class="post-metadata">

**Author:** ![Palli](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/palli/32/3380_2.png) [@Palli](https://discourse.julialang.org/u/Palli)\
**Post date:** [January 16, 2024, 3:52pm UTC](https://discourse.julialang.org/t/hazard-pointers-in-c-26-vs-julia-concurrency-atomics-e-g-for-uint128/108866/4 "2024-01-16T15:52:28Z")

</div>

I usually trust you since you’re the expert, but I saw:

```julia
8

```

So it only seems to be the “minimum” guaranteed limit. Maybe 16 IS guaranteed on x86, however, but I want that guarantee always(?). Do you think I always have it despite that, or maybe that don’t need it?

It should be 16-byte aligned (by default), but I’m not sure it is/guaranteed on all platforms:

> <https://stackoverflow.com/questions/16703211/why-128bit-variables-should-be-aligned-to-16byte-boundary>

> One reasons is that most SSE2 instructions on X86 require the data to be 128 bit aligned. This design decision would have been made for performance reasons and to avoid overly complex (and hence slow and big) hardware.

FYI, existing on x86:  
[https://www.felixcloutier.com/x86/lddqu](https://www.felixcloutier.com/x86/lddqu)

> LDDQU — Load Unaligned Integer 128 Bits

I do see in Julia.h (implying it might not always be):

> // int128 is 16 bytes aligned on aarch64

In jl\_compute\_field\_offsets (MAX\_ALIGN is only 8):

> <https://github.com/JuliaLang/julia/blob/b058146cafec8405aa07f9647642fd485ea3b5d7/src/datatype.c#L694>

It seems to be fixed in Zig, but not in Rust (any why not for a long time? Seems like a simple fix):

> <https://github.com/rust-lang/rust/issues/54341>
>
> While fixing various bindgen bugs related to \`long double\`, \`int128\`, (https://g…ithub.com/rust-lang-nursery/rust-bindgen/issues/1370, etc).
> 
> I realized that the following Rust program, in my x86\_64 Linux machine:
> 
> \`\`\`rust
> \#\[repr(C)\]
> struct Foo {
> f: u128,
> }
> 
> fn main() {
> println!("Align: {}", ::std::mem::align\_of::\<Foo\>());
> }
> \`\`\`
> 
> Prints \`8\`.
> 
> While the following C program:
> 
> \`\`\`c
> \#include \<stdio.h\>
> 
> struct foo {
> unsigned \_\_int128 t;
> };
> 
> int main() {
> printf("Align: %ld\\n", \_Alignof(struct foo));
> }
> \`\`\`
> 
> Prints \`16\` on the same system. This is pretty unexpected, and means that i128 / u128 are not really usable for FFI / alignment purposes.

> `u128`/`i128` are not FFI-safe when they should be. That’s a bug. That’s why this issue exists and is still open. We also don’t _claim_ that they are FFI safe, so it’s not a soundness bug.

> <https://github.com/ziglang/zig/issues/2987>
>
> \`@cmpxchg\` on x86\_64 supports u128 integers. However \`@alignOf(u128)\` reports 8,… and without \`align(16)\` on the \`u128\`, the code segfaults at runtime. This alignment is reported by LLVM as the "ABI alignment". Is this alignment incorrect? Is the atomic alignment requirement higher? Investigation is needed.
> 
> Here's the test case:
> 
> \`\`\`zig
> test "128-bit cmpxchg" {
> if (builtin.arch != .x86\_64) {
> return error.SkipZigTest;
> }
> var x: u128 = 1234; // segfault at runtime can be fixed by adding align(16) here
> if (@cmpxchgWeak(u128, &x, 99, 5678, .SeqCst, .SeqCst)) |x1| {
> expect(x1 == 1234);
> } else {
> @panic("cmpxchg should have failed");
> }
> 
> while (@cmpxchgWeak(u128, &x, 1234, 5678, .SeqCst, .SeqCst)) |x1| {
> expect(x1 == 1234);
> }
> expect(x == 5678);
> 
> expect(@cmpxchgStrong(u128, &x, 5678, 42, .SeqCst, .SeqCst) == null);
> expect(x == 42);
> }
> \`\`\`

> `@cmpxchg` on x86\_64 supports u128 integers. However `@alignOf(u128)` reports 8, and without `align(16)` on the `u128`, the code segfaults at runtime.

[Now fixed, but if not in Julia, then would also segfault, if using that instruction, so since it’s not likely actually is 16-byte aligned. I suppose that instruction IS used.]

Would you say all structs should be 16 bytes (no larger), 8, 4 etc. for _concurrent programs_ (or use locking)?

Arrays are 64-byte aligned, if large, otherwise only 16-byte aligned, so larger 17, or 32byte has the possibility of straddling cache-line boundary.

> [@Julia alignas: is there a way to specify the alignment of Julia objects in memory?](https://discourse.julialang.org/t/julia-alignas-is-there-a-way-to-specify-the-alignment-of-julia-objects-in-memory/57501/2):
>
> (Julia defaults to 16-byte alignment). If the alignment is just an optimization, however, that may not be so terrible.
> 
> It doesn’t seem crazy to add an `alignment` keyword argument to the `Array` constructor, but the difficulty of supporting Windows is (as usual) a pain point. (You can have an aligned-memory allocator on Windows, but then you can’t use `free` to deallocate it, and so you’d need lower-level hacks for garbage-collection to work.)

---

<div class="post-metadata">

**Author:** ![mkitti](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mkitti/32/12459_2.png) [@mkitti](https://discourse.julialang.org/u/mkitti)\
**Post date:** [January 17, 2024, 5:41pm UTC](https://discourse.julialang.org/t/hazard-pointers-in-c-26-vs-julia-concurrency-atomics-e-g-for-uint128/108866/5 "2024-01-17T17:41:53Z")

</div>

If you can obtain a pointer from somewhere, you can use `unsafe_wrap` to create a Julia array. I created ArrayAllocators.jl to play with the concept.

[https://mkitti.github.io/ArrayAllocators.jl/stable/api/#ArrayAllocators.MemAlign](https://mkitti.github.io/ArrayAllocators.jl/stable/api/#ArrayAllocators.MemAlign)

```julia-repl
julia> using ArrayAllocators

julia> A = Array{Int}(MemAlign(2^16), 16);

julia> pointer(A)
Ptr{Int64} @0x00000000032e0000

julia> B = Array{Int}(MemAlign(2^8), 16);

julia> pointer(B)
Ptr{Int64} @0x00000000025c1100

julia> C = Array{Int}(MemAlign(2^4), 16);

julia> pointer(C)
Ptr{Int64} @0x0000000000728fd0

```

---

<div class="post-metadata">

**Author:** ![jameson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jameson/32/23_2.png) [@jameson](https://discourse.julialang.org/u/jameson)\
**Post date:** [January 24, 2024, 5:30am UTC](https://discourse.julialang.org/t/hazard-pointers-in-c-26-vs-julia-concurrency-atomics-e-g-for-uint128/108866/6 "2024-01-24T05:30:00Z")

</div>

> [@Elrod](#):
>
> the `Foo` struct itself still has 8-byte alignment instead of 16, defeating the benefit of padding it.  
> Thus, loading requires a lock/unlock:

FWIW, the failure here was on the C side, not on Julia’s side: we could not get the supported C compilers to correctly emit this 16 byte load across all of our supported targets. We are fairly close now though and could probably “flip the switch” on these