# How to construct a struct with common field values efficiently

**URL:** <https://discourse.julialang.org/t/how-to-construct-a-struct-with-common-field-values-efficiently/104047>\
**Category:** Performance\
**Tags:** question\
**Created:** [September 20, 2023, 2:44am UTC](https://discourse.julialang.org/t/how-to-construct-a-struct-with-common-field-values-efficiently/104047 "2023-09-20T02:44:19Z")\
**Posts on this page:** 13\
**Page:** 2

<div class="post-metadata">

**Author:** ![lukemin](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lukemin/32/215974_2.png) [@lukemin](https://discourse.julialang.org/u/lukemin)\
**Post date:** [September 20, 2023, 6:32am UTC](https://discourse.julialang.org/t/how-to-construct-a-struct-with-common-field-values-efficiently/104047/21 "2023-09-20T06:32:31Z")

</div>

```julia
# Cooley-Tukey over C[X]/(Xᴺ+1).
# Based on https://eprint.iacr.org/2016/504
function fft!(a::Vector{ModNum}, Ψ::Vector{ModNum})
    N = length(a)
    m, logkp1, k = 2, trailing_zeros(N) - 1, N >> 1

    @inbounds @simd for j = 1 : k
        t, u = a[j], a[j+k] * Ψ[m+1]
        a[j], a[j+k] = t + u, t - u
    end
    k >>= 1

    while logkp1 > 0
        @inbounds @simd for i = 0 : m-1
            j1 = i << logkp1 + 1; j2 = j1 + k - 1
            @inbounds @simd for j = j1 : j2
                t, u = a[j], a[j+k] * Ψ[m+i+1]
                a[j], a[j+k] = t + u, t - u
            end
        end
        m <<= 1; logkp1 -= 1; k >>= 1
    end
end

# Gentleman-Sande over C[X]/(Xᴺ+1).
# Based on https://eprint.iacr.org/2016/504
function ifft!(a::Vector{ModNum}, Ψinv::Vector{ModNum}) 
    N = length(a)
    m, logkp1, k = N >> 1, 1, 1

    while m > 1
        @inbounds @simd for i = 0 : m - 1
            j1 = i << logkp1 + 1; j2 = j1 + k - 1
            @inbounds @simd for j = j1 : j2
                t, u = a[j], a[j+k]
                a[j], a[j+k] = t + u, Ψinv[m+i+1] * (t - u)
            end
        end
        m >>= 1; logkp1 += 1; k <<= 1
    end

    @inbounds @simd for j = 1 : k
        t, u = a[j], a[j+k]
        a[j], a[j+k] = t + u, Ψinv[m+1] * (t - u)
    end
end

```

I cannot guarantee the correctness without proper code for root-of-unity generation, but here is my NTT code. I also updated the code above for addition and subtraction between `ModNum`.

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [September 20, 2023, 6:35am UTC](https://discourse.julialang.org/t/how-to-construct-a-struct-with-common-field-values-efficiently/104047/22 "2023-09-20T06:35:43Z")

</div>

oh this makes perfect sense vector{modnum} is a bad data layout because it wastes half the space.

---

<div class="post-metadata">

**Author:** ![lukemin](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lukemin/32/215974_2.png) [@lukemin](https://discourse.julialang.org/u/lukemin)\
**Post date:** [September 20, 2023, 6:40am UTC](https://discourse.julialang.org/t/how-to-construct-a-struct-with-common-field-values-efficiently/104047/23 "2023-09-20T06:40:58Z")

</div>

So I should use `Vector{UInt64}` for `a` and `\Psi` with extra input `Q::Modulus`? Or possibly define a new data type which stores `Vector{UInt64}` and `Modulus` for modulo reduction?

---

<div class="post-metadata">

**Author:** ![Salmon](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/salmon/32/22968_2.png) [@Salmon](https://discourse.julialang.org/u/Salmon)\
**Post date:** [September 20, 2023, 6:44am UTC](https://discourse.julialang.org/t/how-to-construct-a-struct-with-common-field-values-efficiently/104047/24 "2023-09-20T06:44:02Z")

</div>

By the way I cannot reproduce the performance loss upon using an immutable struct:

> **Full code Mutable struct**
>
> ```julia
> module A
> mutable struct Modulus
> const Q::UInt64
> const Q⁻¹::UInt64
> const R⁻¹::UInt128
> const mask::UInt128
> const logR::Int64
> 
> function Modulus(Q::Integer)
> @assert isodd(Q) "Modulus should be an odd number."
> 
> Q⁻¹ = UInt64(invmod(-Q, 0x00000000000000010000000000000000))
> R⁻¹ = UInt128(invmod(0x00000000000000010000000000000000, Q))
> new(Q, Q⁻¹, R⁻¹, 0x0000000000000000ffffffffffffffff, 64)
> end
> end
> 
> Base.mod(x::Integer, Q::Modulus) = mod(x, Q.Q)
> Base.invmod(x::Integer, Q::Modulus) = invmod(UInt64(x), Q.Q)
> 
> struct ModNum <: Unsigned
> val::UInt64
> Q::Modulus
> end
> 
> mform(x::ModNum) = ModNum(UInt64(mod(UInt128(mod(x.val, x.Q)) << x.Q.logR, x.Q)), x.Q)
> imform(x::ModNum) = ModNum(UInt64(mod(x.val * x.Q.R⁻¹, x.Q)), x.Q)
> 
> mul(a::UInt64, b::UInt64, Q::Modulus) = begin
> q, q⁻¹ = Q.Q, Q.Q⁻¹
> 
> ab = UInt128(a) * UInt128(b)
> w = UInt64((ab + q * UInt128(UInt64(ab & Q.mask) * q⁻¹)) >> Q.logR)
> w ≥ q ? w - q : w
> end
> 
> Base.:*(a::ModNum, b::ModNum) = begin
> @assert a.Q.Q == b.Q.Q
> ModNum(mul(a.val, b.val, a.Q), a.Q)
> end
> 
> function f(n, Q)
> a = ModNum(1,Q)
> for i in 1:n
> a *= ModNum(i,Q)
> end
> a
> end
> end
> 
> ```

```julia
julia> Q = A.Modulus(113);

julia> @btime A.f(1000, $Q);
  6.239 μs (0 allocations: 0 bytes)

```

while

> **immutable**
>
> ```julia
> struct Modulus
> Q::UInt64
> Q⁻¹::UInt64
> R⁻¹::UInt128
> mask::UInt128
> logR::Int64
> 
> function Modulus(Q::Integer)
> @assert isodd(Q) "Modulus should be an odd number."
> 
> Q⁻¹ = UInt64(invmod(-Q, 0x00000000000000010000000000000000))
> R⁻¹ = UInt128(invmod(0x00000000000000010000000000000000, Q))
> new(Q, Q⁻¹, R⁻¹, 0x0000000000000000ffffffffffffffff, 64)
> end
> end
> 
> ```

gives

```julia
WARNING: replacing module A.
julia> Q = A.Modulus(113);

julia> @btime A.f(1000, $Q);
  6.232 μs (0 allocations: 0 bytes)

```

weirdly,

> **mutable and no const**
>
> ```julia
> mutable struct Modulus
> Q::UInt64
> Q⁻¹::UInt64
> R⁻¹::UInt128
> mask::UInt128
> logR::Int64
> 
> function Modulus(Q::Integer)
> @assert isodd(Q) "Modulus should be an odd number."
> 
> Q⁻¹ = UInt64(invmod(-Q, 0x00000000000000010000000000000000))
> R⁻¹ = UInt128(invmod(0x00000000000000010000000000000000, Q))
> new(Q, Q⁻¹, R⁻¹, 0x0000000000000000ffffffffffffffff, 64)
> end
> end
> 
> ```

is even a bit faster

```julia
WARNING: replacing module A.
julia> Q = A.Modulus(113);

julia> @btime A.f(1000, $Q);
  6.132 μs (0 allocations: 0 bytes)

```

---

<div class="post-metadata">

**Author:** ![lukemin](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lukemin/32/215974_2.png) [@lukemin](https://discourse.julialang.org/u/lukemin)\
**Post date:** [September 20, 2023, 6:57am UTC](https://discourse.julialang.org/t/how-to-construct-a-struct-with-common-field-values-efficiently/104047/25 "2023-09-20T06:57:32Z")

</div>

I may have misled everybody, sorry. That performance loss comes from the NTT actually, and weirdly enough, the performance loss does not happen in the REPL, but in written code only.

```julia
  27.458 μs (0 allocations: 0 bytes)
  27.916 μs (0 allocations: 0 bytes)

```

This is NTT test with dimension N=1024, with immutable Modulus.

```julia
  21.542 μs (0 allocations: 0 bytes)
  25.833 μs (0 allocations: 0 bytes)

```

This is NTT test with dimension N=1024, with mutable Modulus.

---

<div class="post-metadata">

**Author:** ![Salmon](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/salmon/32/22968_2.png) [@Salmon](https://discourse.julialang.org/u/Salmon)\
**Post date:** [September 20, 2023, 7:09am UTC](https://discourse.julialang.org/t/how-to-construct-a-struct-with-common-field-values-efficiently/104047/26 "2023-09-20T07:09:18Z")

</div>

I’m interested, but I cannot run your fft! function, probably because I don’t know much about how it is supposed to be used:

```julia
Q = A.Modulus(113);
a = [A.ModNum(1,Q) for i in 1:10];
Ψ = [A.ModNum(3,Q) for i in 1:10];
ERROR: promotion of types Main.A.ModNum and Main.A.ModNum failed to change any arguments

```

Can you give an example how to benchmark?

---

<div class="post-metadata">

**Author:** ![lukemin](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lukemin/32/215974_2.png) [@lukemin](https://discourse.julialang.org/u/lukemin)\
**Post date:** [September 20, 2023, 7:13am UTC](https://discourse.julialang.org/t/how-to-construct-a-struct-with-common-field-values-efficiently/104047/27 "2023-09-20T07:13:37Z")

</div>

```julia
Q = Modulus(1088516530177)
a = [ModNum(1, Q) for _ = 1 : 1024];
Ψ = [ModNum(1, Q) for _ = 1 : 1024];
@btime fft!(a, Ψ)
@btime ifft!(a, Ψ)

```

This should work.

---

<div class="post-metadata">

**Author:** ![Salmon](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/salmon/32/22968_2.png) [@Salmon](https://discourse.julialang.org/u/Salmon)\
**Post date:** [September 20, 2023, 7:33am UTC](https://discourse.julialang.org/t/how-to-construct-a-struct-with-common-field-values-efficiently/104047/28 "2023-09-20T07:33:15Z")

</div>

Ah, looks like I was missing a few functions, now I can reproduce the strange performance difference:

```julia

WARNING: replacing module A.
[ Info: This the mutable const struct

  57.214 μs (0 allocations: 0 bytes)

```

```julia
WARNING: replacing module A.
[ Info: This the immutable struct

  62.827 μs (0 allocations: 0 bytes)

```

---

<div class="post-metadata">

**Author:** ![lukemin](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lukemin/32/215974_2.png) [@lukemin](https://discourse.julialang.org/u/lukemin)\
**Post date:** [September 20, 2023, 8:02am UTC](https://discourse.julialang.org/t/how-to-construct-a-struct-with-common-field-values-efficiently/104047/29 "2023-09-20T08:02:34Z")

</div>

I also thought that immutable struct should be faster, hope someone can actually explain why! Maybe it depends on which machine you are using, it makes more performance improvement in my laptop and linux server.

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [September 20, 2023, 1:07pm UTC](https://discourse.julialang.org/t/how-to-construct-a-struct-with-common-field-values-efficiently/104047/30 "2023-09-20T13:07:36Z")

</div>

This is exactly what we would expect. With the immutable struct, the `ModNum` has 5 fields instead of 2, so `Vector{ModNum}` is an extra 2x worse. All in all, I think it probably makes sense to have an interface that requires explicitly passing the `Modulus` around (especially because your operations only make sense with one of them).

---

<div class="post-metadata">

**Author:** ![lukemin](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lukemin/32/215974_2.png) [@lukemin](https://discourse.julialang.org/u/lukemin)\
**Post date:** [September 20, 2023, 1:16pm UTC](https://discourse.julialang.org/t/how-to-construct-a-struct-with-common-field-values-efficiently/104047/31 "2023-09-20T13:16:19Z")

</div>

Thanks a lot! It’s a shame that I cannot take advantage from the operator overloading for ModNum. At least there are well-known optimisation techniques that I can make use of if I use `UInt64` arrays. I really appreciate your help and thank everyone involved in the discussion again.

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [September 20, 2023, 3:36pm UTC](https://discourse.julialang.org/t/how-to-construct-a-struct-with-common-field-values-efficiently/104047/32 "2023-09-20T15:36:42Z")

</div>

What if you use the immutable structure, but make the Modulus a reference instead of the actual value?

---

<div class="post-metadata">

**Author:** ![lukemin](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lukemin/32/215974_2.png) [@lukemin](https://discourse.julialang.org/u/lukemin)\
**Post date:** [September 21, 2023, 3:13am UTC](https://discourse.julialang.org/t/how-to-construct-a-struct-with-common-field-values-efficiently/104047/33 "2023-09-21T03:13:35Z")

</div>

I also tried that, but such adjustment made the code a little bit slower.

[Previous page](https://discourse.julialang.org/t/how-to-construct-a-struct-with-common-field-values-efficiently/104047.md?page=1)
