# SIMD struggles, seeking solutions (with KangarooTwelve.jl)

**URL:** <https://discourse.julialang.org/t/simd-struggles-seeking-solutions-with-kangarootwelve-jl/105800>\
**Category:** Performance\
**Created:** [November 4, 2023, 7:40pm UTC](https://discourse.julialang.org/t/simd-struggles-seeking-solutions-with-kangarootwelve-jl/105800 "2023-11-04T19:40:11Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![tecosaur](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tecosaur/32/23206_2.png) [@tecosaur](https://discourse.julialang.org/u/tecosaur)\
**Post date:** [November 4, 2023, 7:40pm UTC](https://discourse.julialang.org/t/simd-struggles-seeking-solutions-with-kangarootwelve-jl/105800/1 "2023-11-04T19:40:11Z")

</div>

A bit ago I mentioned a new hashing library I have been working on:

> [@Improving the fastest pure-Julia cryptographic hash!](https://discourse.julialang.org/t/improving-the-fastest-pure-julia-cryptographic-hash/104386):
>
> Hi All! For another project of mine, I wanted a good fast hash that wasn’t trivial to mock. After an excessive amount of investigation, I’ve settled on KangarooTwelve. To quote the project readme, I think it strikes a really nice balance between: Simplicity (Keccak + sponge + hopping) Security (128-bit, sharing the same cryptographic base as SHA3) Speed (up to ~2bytes/cycle, with AVX512) With a little help from @Lilith, @Sukera, and @Oscar_Smith (big thanks for the help so far …

After a huge amount of effort, I’ve just managed to make the “simple” single-threaded version (`k12_singlethreaded`) zero-alloc and only off the C performance by a factor of 2 (I’m seeing ~1.5 GB/s, should be seeing 3-4 GB/s).

One feature that should help make up the gap is SIMD. I’ve been trying to use SIMD.jl to accelerate the parallel branches of the hashing, however despite my best efforts so far, the SIMD take is:

- Slower
- Sometimes incorrect

To show this, here’s a quick example:

```julia
(KangarooTwelve) julia> bitpattern(num::Int) = Iterators.take(Iterators.cycle(0x00:0xfa), num) |> collect
bitpattern (generic function with 1 method)

(KangarooTwelve) julia> data = bitpattern(17^7);

(KangarooTwelve) julia> @time k12_singlethreaded(data, UInt8[])
  0.238118 seconds (2 allocations: 64 bytes)
0x05d354e539382fe58260c271776a39a4

(KangarooTwelve) julia> @time k12_singlethreaded_simd(data, UInt8[])
  0.977218 seconds (25.05 k allocations: 11.464 MiB)
0x05d354e539382fe58260c271776a39a4

```

We can make the SIMD version faster (new time: ~0.6s) by adding `@inline` to the `rol64` inner function within `keccak_p1600`, however then the results are non-deterministic 😕.

I’d hugely appreciate any help getting this closer to the performance of the C/Rust implementations floating around, and getting SIMD working 🙏.

> **[GitHub - tecosaur/KangarooTwelve.jl: Hashing with hopping](https://github.com/tecosaur/KangarooTwelve.jl/)**
>
> Hashing with hopping. Contribute to tecosaur/KangarooTwelve.jl development by creating an account on GitHub.

---

<div class="post-metadata">

**Author:** ![Zentrik](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/zentrik/32/35409_2.png) [@Zentrik](https://discourse.julialang.org/u/Zentrik)\
**Post date:** [November 4, 2023, 11:03pm UTC](https://discourse.julialang.org/t/simd-struggles-seeking-solutions-with-kangarootwelve-jl/105800/2 "2023-11-04T23:03:21Z")

</div>

I haven’t looked at the code in much detail but I would note SIMD.jl can generate pretty bad code especially compared to established x86 c++ simd libraries. Also, I wonder if your `ntuple` constructions are generating nice code, e.g. in some instances they certainly don’t [Specialize `setindex` for isbits `Tuple`s and `_totuple` for isbits `NTuple`s by Zentrik · Pull Request #51748 · JuliaLang/julia · GitHub](https://github.com/JuliaLang/julia/pull/51748).

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [November 6, 2023, 12:19pm UTC](https://discourse.julialang.org/t/simd-struggles-seeking-solutions-with-kangarootwelve-jl/105800/3 "2023-11-06T12:19:16Z")

</div>

> [@Zentrik](#):
>
> I haven’t looked at the code in much detail but I would note SIMD.jl can generate pretty bad code especially compared to established x86 c++ simd libraries.

One thing that SIMD.jl do different compared to libraries that do native assembly code is that SIMD.jl creates target independent LLVM IR and it relies on LLVM to do the optimization and selection of the actual intrinsics that will run on the native machine. This means that code written with SIMD.jl is portable but if LLVM does not do that great of a job with the assembly generation it will end up slower than hand picked machine specific intrinsics.

---

<div class="post-metadata">

**Author:** ![tecosaur](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tecosaur/32/23206_2.png) [@tecosaur](https://discourse.julialang.org/u/tecosaur)\
**Post date:** [November 6, 2023, 2:18pm UTC](https://discourse.julialang.org/t/simd-struggles-seeking-solutions-with-kangarootwelve-jl/105800/4 "2023-11-06T14:18:45Z")

</div>

The thing that gets me is that this really feels like this is a situation where SIMD _should_ be an easy win. The core permutation function that is SIMD’d is

> <https://github.com/tecosaur/KangarooTwelve.jl/blob/f1758f37e98b390a172a88c60dc02e8eaf9a9497/src/keccak.jl#L73-L89>

Where the operations applied to the SIMD.jl `Vec` are `UInt64` bitshifts, not-s, or-s, and xor-s. Adding `@inline` to the `rol64` function improves the performance of the SIMD method a bit, but also makes the results non-deterministic!!

This leaves me at quite a loss, which is a pity because I suspect this is one of the major factors stopping us from nearing the performance of C/Rust implementations.

---

<div class="post-metadata">

**Author:** ![gbaraldi](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gbaraldi/32/22101_2.png) [@gbaraldi](https://discourse.julialang.org/u/gbaraldi)\
**Post date:** [November 6, 2023, 2:32pm UTC](https://discourse.julialang.org/t/simd-struggles-seeking-solutions-with-kangarootwelve-jl/105800/5 "2023-11-06T14:32:45Z")

</div>

If inlining changes the result it’s either a bug with inlining, or a bug in your code. The second is more likely

---

<div class="post-metadata">

**Author:** ![Zentrik](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/zentrik/32/35409_2.png) [@Zentrik](https://discourse.julialang.org/u/Zentrik)\
**Post date:** [November 6, 2023, 2:50pm UTC](https://discourse.julialang.org/t/simd-struggles-seeking-solutions-with-kangarootwelve-jl/105800/6 "2023-11-06T14:50:55Z")

</div>

`ρs[1] = 0` so in `roll64` you do `a >> 64` is this legal in Julia? I feel like I remember reading how this isn’t well defined in C but I may be wrong.

EDIT:  
Microsoft seems to claim its undefined behaviour [Warning C26452 | Microsoft Learn](https://learn.microsoft.com/en-us/cpp/code-quality/c26452?view=msvc-170).  
Also clang with ubsan does as well, [Compiler Explorer](https://godbolt.org/z/jcKfKq3Ej).

---

<div class="post-metadata">

**Author:** ![tecosaur](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tecosaur/32/23206_2.png) [@tecosaur](https://discourse.julialang.org/u/tecosaur)\
**Post date:** [November 6, 2023, 4:13pm UTC](https://discourse.julialang.org/t/simd-struggles-seeking-solutions-with-kangarootwelve-jl/105800/7 "2023-11-06T16:13:57Z")

</div>

Thanks for that @Zentrik! That is indeed the source of the correctness issue, and I’ve just pushed a fix: [Fix undefined behaviour in rol64 call · tecosaur/KangarooTwelve.jl@d4d95f8 · GitHub](https://github.com/tecosaur/KangarooTwelve.jl/commit/d4d95f8f35f83cce41d27951d93c99e0bc29269f)

Now I just need to work out what’s going on with the SIMD performance difference…

---

<div class="post-metadata">

**Author:** ![Sukera](https://avatars.discourse-cdn.com/v4/letter/s/ce7236/32.png) [@Sukera](https://discourse.julialang.org/u/Sukera)\
**Post date:** [November 6, 2023, 4:19pm UTC](https://discourse.julialang.org/t/simd-struggles-seeking-solutions-with-kangarootwelve-jl/105800/8 "2023-11-06T16:19:02Z")

</div>

> [@Zentrik](#):
>
> `ρs[1] = 0` so in `roll64` you do `a >> 64` is this legal in Julia? I feel like I remember reading how this isn’t well defined in C but I may be wrong.

If the docs are right, it’s not UB in Julia:

```julia
help?> 1 >> 64
  >>(x, n)

  Right bit shift operator, x >> n. For n >= 0, the result is x shifted right by n bits, filling with 0s if x >= 0, 1s if x <
  0, preserving the sign of x. This is equivalent to fld(x, 2^n). For n < 0, this is equivalent to x << -n.

```

Though this may be a case of hardware semantics not exactly lining up with Julia semantics. If that’s the case, a MWE would be a good bug report.

---

<div class="post-metadata">

**Author:** ![Zentrik](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/zentrik/32/35409_2.png) [@Zentrik](https://discourse.julialang.org/u/Zentrik)\
**Post date:** [November 6, 2023, 4:26pm UTC](https://discourse.julialang.org/t/simd-struggles-seeking-solutions-with-kangarootwelve-jl/105800/9 "2023-11-06T16:26:21Z")

</div>

I would profile to find the hotspots, presumably its `keccak_p1600`. Then compare LLVM IR/ assembly to see if there’s a difference there, `perf` could be useful for doing both steps at once.

---

<div class="post-metadata">

**Author:** ![Zentrik](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/zentrik/32/35409_2.png) [@Zentrik](https://discourse.julialang.org/u/Zentrik)\
**Post date:** [November 6, 2023, 4:27pm UTC](https://discourse.julialang.org/t/simd-struggles-seeking-solutions-with-kangarootwelve-jl/105800/10 "2023-11-06T16:27:32Z")

</div>

It does seem like it’s a bug somewhere as there are previous issues/prs [fix #37880, overflow in shift amount range check in codegen by JeffBezanson · Pull Request #37891 · JuliaLang/julia (github.com)](https://github.com/JuliaLang/julia/pull/37891). This also shows some code that’s seems to check for overflow [another fix to run-time `ashr_int` by JeffBezanson · Pull Request #24575 · JuliaLang/julia (github.com)](https://github.com/JuliaLang/julia/pull/24575).

EDIT: wrong function, we’re probably calling `lshr_int` but still shows that this probably should have been checked for.

---

<div class="post-metadata">

**Author:** ![tecosaur](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tecosaur/32/23206_2.png) [@tecosaur](https://discourse.julialang.org/u/tecosaur)\
**Post date:** [November 6, 2023, 4:42pm UTC](https://discourse.julialang.org/t/simd-struggles-seeking-solutions-with-kangarootwelve-jl/105800/11 "2023-11-06T16:42:54Z")

</div>

I think I’ve made some progress on figuring out the performance difference.

It seems like when the SIMD path is used, it makes a big difference whether the input array is `UInt64`s, or _reinterpreted_ `UInt64`s.

```julia-repl
julia> longmsg_u8 = rand(UInt8, 100000000 * 8);

julia> longmsg_u8r64 = reinterpret(UInt64, longmsg_u8);

julia> longmsg_u64 = rand(UInt64, 100000000);

julia> @time KangarooTwelve.turboshake(UInt128, longmsg_u64) # non-SIMD
  0.432940 seconds (4 allocations: 352 bytes)
0x3b5ea3aa194f8f0be7c2986cea24b0b0

julia> @time KangarooTwelve.turboshake(UInt128, longmsg_u8r64) # non-SIMD
  0.440677 seconds (4 allocations: 352 bytes)
0xa8a43cb9fa252800f2d0c4a7a971dbcd

julia> @time KangarooTwelve.turboshake(UInt128, (longmsg_u64, longmsg_u64, longmsg_u64, longmsg_u64))
  1.125633 seconds (3 allocations: 944 bytes)
(0x3b5ea3aa194f8f0be7c2986cea24b0b0, 0x3b5ea3aa194f8f0be7c2986cea24b0b0, 0x3b5ea3aa194f8f0be7c2986cea24b0b0, 0x3b5ea3aa194f8f0be7c2986cea24b0b0)

julia> @time KangarooTwelve.turboshake(UInt128, (longmsg_u8r64, longmsg_u8r64, longmsg_u8r64, longmsg_u8r64))
  4.212588 seconds (3 allocations: 976 bytes)
(0xa8a43cb9fa252800f2d0c4a7a971dbcd, 0xa8a43cb9fa252800f2d0c4a7a971dbcd, 0xa8a43cb9fa252800f2d0c4a7a971dbcd, 0xa8a43cb9fa252800f2d0c4a7a971dbcd)

```

---

<div class="post-metadata">

**Author:** ![cortner](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cortner/32/204_2.png) [@cortner](https://discourse.julialang.org/u/cortner)\
**Post date:** [November 6, 2023, 5:08pm UTC](https://discourse.julialang.org/t/simd-struggles-seeking-solutions-with-kangarootwelve-jl/105800/12 "2023-11-06T17:08:59Z")

</div>

I use PtrArray to get around that.

---

<div class="post-metadata">

**Author:** ![tecosaur](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tecosaur/32/23206_2.png) [@tecosaur](https://discourse.julialang.org/u/tecosaur)\
**Post date:** [November 6, 2023, 5:22pm UTC](https://discourse.julialang.org/t/simd-struggles-seeking-solutions-with-kangarootwelve-jl/105800/13 "2023-11-06T17:22:18Z")

</div>

From glancing at [GitHub - JuliaSIMD/StrideArraysCore.jl: The core AbstractStrideArray type, separated from StrideArrays.jl to avoid circular dependencies.](https://github.com/JuliaSIMD/StrideArraysCore.jl), `PtrArray` just seems like another take on `ReinterpretArray`?

---

<div class="post-metadata">

**Author:** ![nsajko](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nsajko/32/221187_2.png) [@nsajko](https://discourse.julialang.org/u/nsajko)\
**Post date:** [November 6, 2023, 7:46pm UTC](https://discourse.julialang.org/t/simd-struggles-seeking-solutions-with-kangarootwelve-jl/105800/14 "2023-11-06T19:46:33Z")

</div>

Perhaps the compiler has less information on the alignment of reinterpreted data. Just don’t `reinterpret`, in any case.

---

<div class="post-metadata">

**Author:** ![cortner](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cortner/32/204_2.png) [@cortner](https://discourse.julialang.org/u/cortner)\
**Post date:** [November 6, 2023, 9:49pm UTC](https://discourse.julialang.org/t/simd-struggles-seeking-solutions-with-kangarootwelve-jl/105800/15 "2023-11-06T21:49:19Z")

</div>

I think that’s right. You allow it to make assumptions. … that might be wrong (??). So in principle this seems less safe. Experts can say how unsafe.

---

<div class="post-metadata">

**Author:** ![tecosaur](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tecosaur/32/23206_2.png) [@tecosaur](https://discourse.julialang.org/u/tecosaur)\
**Post date:** [November 7, 2023, 2:00am UTC](https://discourse.julialang.org/t/simd-struggles-seeking-solutions-with-kangarootwelve-jl/105800/16 "2023-11-07T02:00:42Z")

</div>

> [@nsajko](#):
>
> Just don’t `reinterpret`, in any case.

Yea, that’s not really a good option here. I need to `xor` with the `UInt64` based state, which means I need `UInt64`s. It would be possible to instead `reinterpret` the `NTuple{25, UInt64}` state as whatever the input vector is (say `UInt8`s), but I’m pretty sure that will reduce performance in another way.

---

<div class="post-metadata">

**Author:** ![gbaraldi](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gbaraldi/32/22101_2.png) [@gbaraldi](https://discourse.julialang.org/u/gbaraldi)\
**Post date:** [November 7, 2023, 2:54am UTC](https://discourse.julialang.org/t/simd-struggles-seeking-solutions-with-kangarootwelve-jl/105800/17 "2023-11-07T02:54:44Z")

</div>

If possible, reintepret each object separately, instead of the whole array.

---

<div class="post-metadata">

**Author:** ![tecosaur](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tecosaur/32/23206_2.png) [@tecosaur](https://discourse.julialang.org/u/tecosaur)\
**Post date:** [November 7, 2023, 4:18am UTC](https://discourse.julialang.org/t/simd-struggles-seeking-solutions-with-kangarootwelve-jl/105800/18 "2023-11-07T04:18:06Z")

</div>

Maybe I’m just not seeing it, but at a glance that sounds arduous/tedious for little benefit?

---

<div class="post-metadata">

**Author:** ![jules](https://avatars.discourse-cdn.com/v4/letter/j/41988e/32.png) [@jules](https://discourse.julialang.org/u/jules)\
**Post date:** [November 7, 2023, 9:04am UTC](https://discourse.julialang.org/t/simd-struggles-seeking-solutions-with-kangarootwelve-jl/105800/19 "2023-11-07T09:04:12Z")

</div>

I think I had performance problems with reinterpreted arrays before. At the time I “solved” it with some pointer hackery, although I’m not sure that’s appropriate for your issue.

In the profiles you can see that a lot of time is spent on indexing.  
This is `@profview KangarooTwelve.turboshake(UInt128, (longmsg_u64, longmsg_u64, longmsg_u64, longmsg_u64))`

 ![image](https://global.discourse-cdn.com/julialang/original/3X/9/a/9a67e7f340b0d2a981a0b6ab379f7ff9fa569b6b.png)

And this the reinterpreted one

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

A single flame on the left looks like this expanded

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

---

<div class="post-metadata">

**Author:** ![jules](https://avatars.discourse-cdn.com/v4/letter/j/41988e/32.png) [@jules](https://discourse.julialang.org/u/jules)\
**Post date:** [November 7, 2023, 9:35am UTC](https://discourse.julialang.org/t/simd-struggles-seeking-solutions-with-kangarootwelve-jl/105800/20 "2023-11-07T09:35:52Z")

</div>

I just played around with this a bit more, and it seems like with this rather hacky reinterpreter that just reads the bytes through a converted pointer access, it’s as fast as the native UInt64 version for me:

```julia
struct UnsafeReinterpretedVector <: AbstractArray{UInt64,1}
  v::Vector{UInt8}
  len::Int
  function UnsafeReinterpretedVector(v::Vector{UInt8})
    length(v) % 8 == 0 || error("Incompatible length")
    new(v, length(v) ÷ 8)
  end
end

Base.size(u::UnsafeReinterpretedVector) = (u.len,)

function Base.getindex(u::UnsafeReinterpretedVector, i::Int)
  0 < i <= u.len || throw(BoundsError(u, i))
  v = u.v
  GC.@preserve v begin
    p = pointer(v)
    p64 = Ptr{UInt64}(p)
    unsafe_load(p64, i)
  end
end

longmsg_unsafe_u64 = UnsafeReinterpretedVector(longmsg_u8);

@time KangarooTwelve.turboshake(UInt128, (longmsg_unsafe_u64, longmsg_unsafe_u64, longmsg_unsafe_u64, longmsg_unsafe_u64))

1.905471 seconds (3 allocations: 976 bytes)
(0xcc093729c8f34a590fb7e34103068fbb, 0xcc093729c8f34a590fb7e34103068fbb, 0xcc093729c8f34a590fb7e34103068fbb, 0xcc093729c8f34a590fb7e34103068fbb)

```

[Next page](https://discourse.julialang.org/t/simd-struggles-seeking-solutions-with-kangarootwelve-jl/105800.md?page=2)