FixedSizeArrays.jl Showcase #62

giordano · 2024-08-22T15:23:26Z

giordano
Aug 22, 2024
Maintainer

I'm starting this discussion to collect examples of how FixedSizeArray can be better (smaller generated code and/or faster) than standard Array. I'll start with the example in the README.md

Simple function which can constant-propagate the size of the array

julia> using FixedSizeArrays

julia> @noinline f(A::AbstractArray) = length(A)
f (generic function with 1 method)

julia> g() = f(FixedSizeVector{Float64}(undef, 3))
g (generic function with 1 method)

julia> h() = f(Vector{Float64}(undef, 3))
h (generic function with 1 method)

julia> code_llvm(g)

; Function Signature: g()
;  @ REPL[9]:1 within `g`
define i64 @julia_g_14341() #0 {
top:
;  @ REPL[9] within `g`
  ret i64 3
}

julia> code_llvm(h)

; Function Signature: h()
;  @ REPL[10]:1 within `h`
define i64 @julia_h_14351() #0 {
top:
  %gcframe1 = alloca [3 x ptr], align 16
  call void @llvm.memset.p0.i64(ptr align 16 %gcframe1, i8 0, i64 24, i1 true)
  %pgcstack = call ptr inttoptr (i64 6483926436 to ptr)(i64 262) #10
  store i64 4, ptr %gcframe1, align 8
  %task.gcstack = load ptr, ptr %pgcstack, align 8
  %frame.prev = getelementptr inbounds ptr, ptr %gcframe1, i64 1
  store ptr %task.gcstack, ptr %frame.prev, align 8
  store ptr %gcframe1, ptr %pgcstack, align 8
; ┌ @ boot.jl:598 within `Array`
; │┌ @ boot.jl:538 within `GenericMemory`
    %"Memory{Float64}[]" = call ptr @jl_alloc_genericmemory(ptr nonnull @"+Core.GenericMemory#14353.jit", i64 3)
; │└
; │ @ boot.jl:599 within `Array`
; │┌ @ boot.jl:544 within `memoryref`
    %.data_ptr = getelementptr inbounds { i64, ptr }, ptr %"Memory{Float64}[]", i64 0, i32 1
    %0 = load ptr, ptr %.data_ptr, align 8
    %gc_slot_addr_0 = getelementptr inbounds ptr, ptr %gcframe1, i64 2
    store ptr %"Memory{Float64}[]", ptr %gc_slot_addr_0, align 8
; │└
   %ptls_field = getelementptr inbounds ptr, ptr %pgcstack, i64 2
   %ptls_load = load ptr, ptr %ptls_field, align 8
   %"new::Array" = call noalias nonnull align 8 dereferenceable(32) ptr @ijl_gc_small_alloc(ptr %ptls_load, i32 616, i32 32, i64 5266096992) #8
   %"new::Array.tag_addr" = getelementptr inbounds i64, ptr %"new::Array", i64 -1
   store atomic i64 5266096992, ptr %"new::Array.tag_addr" unordered, align 8
   %1 = getelementptr inbounds ptr, ptr %"new::Array", i64 1
   store ptr %0, ptr %"new::Array", align 8
   store ptr %"Memory{Float64}[]", ptr %1, align 8
   %"new::Array.size_ptr" = getelementptr inbounds i8, ptr %"new::Array", i64 16
   store i64 3, ptr %"new::Array.size_ptr", align 8
   store ptr %"new::Array", ptr %gc_slot_addr_0, align 8
; └
  %2 = call i64 @j_f_14357(ptr nonnull %"new::Array")
  %frame.prev10 = load ptr, ptr %frame.prev, align 8
  store ptr %frame.prev10, ptr %pgcstack, align 8
  ret i64 %2
}

julia> versioninfo()
Julia Version 1.12.0-DEV.1082
Commit 58c7186d19* (2024-08-22 02:53 UTC)
Platform Info:
  OS: macOS (arm64-apple-darwin23.4.0)
  CPU: 8 × Apple M1
  WORD_SIZE: 64
  LLVM: libLLVM-18.1.7 (ORCJIT, apple-m1)
Threads: 1 default, 0 interactive, 1 GC (on 4 virtual cores)

giordano · 2024-08-22T15:57:35Z

giordano
Aug 22, 2024
Maintainer Author

Adding vectors of `BFloat16`

julia> using BenchmarkTools, BFloat16s, FixedSizeArrays

julia> @benchmark A .= A .+ A setup=(A=ones(BFloat16, 1_000)) evals=1
BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):  861.000 ns …  3.886 μs  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     891.000 ns              ┊ GC (median):    0.00%
 Time  (mean ± σ):   893.142 ns ± 49.696 ns  ┊ GC (mean ± σ):  0.00% ± 0.00%

                                     █▁
  ▂▂▁▁▁▁▁▁▁▁▁▄▃▁▁▁▁▁▁▁▁▁▁▅▃▁▁▁▁▁▁▁▁▁▁██▁▁▁▁▁▁▁▁▁▁▇▄▁▁▁▁▁▁▁▁▁▃▃ ▂
  861 ns          Histogram: frequency by time          912 ns <

 Memory estimate: 0 bytes, allocs estimate: 0.

julia> @benchmark A .= A .+ A setup=(A=FixedSizeVector(ones(BFloat16, 1_000))) evals=1
BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):  570.000 ns …  3.936 μs  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     591.000 ns              ┊ GC (median):    0.00%
 Time  (mean ± σ):   596.819 ns ± 60.906 ns  ┊ GC (mean ± σ):  0.00% ± 0.00%

                      █
  ▂▁▁▁▁▁▁▁▁▃█▁▁▁▁▁▁▁▁▄█▁▁▁▁▁▁▁▁▃█▁▁▁▁▁▁▁▁▂▆▁▁▁▁▁▁▁▁▂▃▁▁▁▁▁▁▁▁▂ ▂
  570 ns          Histogram: frequency by time          631 ns <

 Memory estimate: 0 bytes, allocs estimate: 0.

julia> versioninfo()
Julia Version 1.12.0-DEV.1082
Commit 58c7186d198 (2024-08-22 02:53 UTC)
Build Info:
  Official https://julialang.org/ release
Platform Info:
  OS: Linux (x86_64-linux-gnu)
  CPU: 384 × AMD EPYC 9654 96-Core Processor
  WORD_SIZE: 64
  LLVM: libLLVM-18.1.7 (ORCJIT, znver4)
Threads: 1 default, 0 interactive, 1 GC (on 384 virtual cores)

(@v1.12) pkg> st
Status `~/.julia/environments/v1.12/Project.toml`
  [ab4f0b2a] BFloat16s v0.5.0 `https://github.com/JuliaMath/BFloat16s.jl.git#b5312dd`
  [6e4b80f9] BenchmarkTools v1.5.0
  [3821ddf9] FixedSizeArrays v0.1.0 `https://github.com/JuliaArrays/FixedSizeArrays.jl#main`

Note that this processor has the avx512_bf16 extension.

0 replies

giordano · 2024-08-22T16:53:50Z

giordano
Aug 22, 2024
Maintainer Author

Reshaping `FixedSizeArray`s vs `Array`s

Taken from #41 (comment)

julia> using FixedSizeArrays

julia> @noinline f(v::AbstractVector{Float64}) = reshape(v, 2, 2)
f (generic function with 1 method)

julia> g3() = f(FixedSizeVector{Float64}(undef, 3))
g3 (generic function with 1 method)

julia> g4() = f(FixedSizeVector{Float64}(undef, 4))
g4 (generic function with 1 method)

julia> h3() = f(Vector{Float64}(undef, 3))
h3 (generic function with 1 method)

julia> h4() = f(Vector{Float64}(undef, 4))
h4 (generic function with 1 method)

julia> code_llvm(g3, (); debuginfo=:none)

; Function Signature: g3()
; Function Attrs: noreturn
define void @julia_g3_6466() #0 {
top:
  %gcframe1 = alloca [4 x ptr], align 16
  call void @llvm.memset.p0.i64(ptr align 16 %gcframe1, i8 0, i64 32, i1 true)
  %gc_slot_addr1 = getelementptr inbounds ptr, ptr %gcframe1, i64 3
  %0 = getelementptr inbounds ptr, ptr %gcframe1, i64 2
  %1 = alloca { ptr, [2 x i64] }, align 8
  %2 = alloca { ptr, [1 x i64] }, align 8
  %pgcstack = call ptr inttoptr (i64 6483926436 to ptr)(i64 262) #9
  store i64 8, ptr %gcframe1, align 8
  %task.gcstack = load ptr, ptr %pgcstack, align 8
  %frame.prev = getelementptr inbounds ptr, ptr %gcframe1, i64 1
  store ptr %task.gcstack, ptr %frame.prev, align 8
  store ptr %gcframe1, ptr %pgcstack, align 8
  %"Memory{Float64}[]" = call ptr @jl_alloc_genericmemory(ptr nonnull @"+Core.GenericMemory#6468.jit", i64 3)
  store ptr %"Memory{Float64}[]", ptr %gc_slot_addr1, align 8
  store ptr %"Memory{Float64}[]", ptr %2, align 8
  %.fca.1.0.gep = getelementptr inbounds { ptr, [1 x i64] }, ptr %2, i64 0, i32 1, i64 0
  store i64 3, ptr %.fca.1.0.gep, align 8
  call void @j_f_6470(ptr noalias nocapture noundef nonnull sret({ ptr, [2 x i64] }) %1, ptr noalias nocapture noundef nonnull %0, ptr nocapture nonnull readonly %2)
  call void @llvm.trap()
  unreachable
}

julia> code_llvm(g4, (); debuginfo=:none)

; Function Signature: g4()
define void @julia_g4_6479(ptr noalias nocapture noundef nonnull sret({ ptr, [2 x i64] }) align 8 dereferenceable(24) %sret_return, ptr noalias nocapture noundef nonnull align 8 dereferenceable(8) %return_roots) #0 {
top:
  %gcframe1 = alloca [4 x ptr], align 16
  call void @llvm.memset.p0.i64(ptr align 16 %gcframe1, i8 0, i64 32, i1 true)
  %gc_slot_addr1 = getelementptr inbounds ptr, ptr %gcframe1, i64 3
  %0 = getelementptr inbounds ptr, ptr %gcframe1, i64 2
  %1 = alloca { ptr, [2 x i64] }, align 8
  %2 = alloca { ptr, [1 x i64] }, align 8
  %pgcstack = call ptr inttoptr (i64 6483926436 to ptr)(i64 262) #11
  store i64 8, ptr %gcframe1, align 8
  %task.gcstack = load ptr, ptr %pgcstack, align 8
  %frame.prev = getelementptr inbounds ptr, ptr %gcframe1, i64 1
  store ptr %task.gcstack, ptr %frame.prev, align 8
  store ptr %gcframe1, ptr %pgcstack, align 8
  %"Memory{Float64}[]" = call ptr @jl_alloc_genericmemory(ptr nonnull @"+Core.GenericMemory#6482.jit", i64 4)
  store ptr %"Memory{Float64}[]", ptr %gc_slot_addr1, align 8
  store ptr %"Memory{Float64}[]", ptr %2, align 8
  %.fca.1.0.gep = getelementptr inbounds { ptr, [1 x i64] }, ptr %2, i64 0, i32 1, i64 0
  store i64 4, ptr %.fca.1.0.gep, align 8
  call void @j_f_6484(ptr noalias nocapture noundef nonnull sret({ ptr, [2 x i64] }) %1, ptr noalias nocapture noundef nonnull %0, ptr nocapture nonnull readonly %2)
  %3 = load ptr, ptr %1, align 8
  store ptr %3, ptr %return_roots, align 8
  call void @llvm.memcpy.p0.p0.i64(ptr noundef nonnull align 8 dereferenceable(24) %sret_return, ptr noundef nonnull align 8 dereferenceable(24) %1, i64 24, i1 false)
  %frame.prev5 = load ptr, ptr %frame.prev, align 8
  store ptr %frame.prev5, ptr %pgcstack, align 8
  ret void
}

julia> code_llvm(h3, (); debuginfo=:none)

; Function Signature: h3()
define nonnull ptr @julia_h3_6493() #0 {
top:
  %gcframe1 = alloca [3 x ptr], align 16
  call void @llvm.memset.p0.i64(ptr align 16 %gcframe1, i8 0, i64 24, i1 true)
  %pgcstack = call ptr inttoptr (i64 6483926436 to ptr)(i64 262) #9
  store i64 4, ptr %gcframe1, align 8
  %task.gcstack = load ptr, ptr %pgcstack, align 8
  %frame.prev = getelementptr inbounds ptr, ptr %gcframe1, i64 1
  store ptr %task.gcstack, ptr %frame.prev, align 8
  store ptr %gcframe1, ptr %pgcstack, align 8
  %"Memory{Float64}[]" = call ptr @jl_alloc_genericmemory(ptr nonnull @"+Core.GenericMemory#6495.jit", i64 3)
  %.data_ptr = getelementptr inbounds { i64, ptr }, ptr %"Memory{Float64}[]", i64 0, i32 1
  %0 = load ptr, ptr %.data_ptr, align 8
  %gc_slot_addr_0 = getelementptr inbounds ptr, ptr %gcframe1, i64 2
  store ptr %"Memory{Float64}[]", ptr %gc_slot_addr_0, align 8
  %ptls_field = getelementptr inbounds ptr, ptr %pgcstack, i64 2
  %ptls_load = load ptr, ptr %ptls_field, align 8
  %"new::Array" = call noalias nonnull align 8 dereferenceable(32) ptr @ijl_gc_small_alloc(ptr %ptls_load, i32 616, i32 32, i64 4659479392) #7
  %"new::Array.tag_addr" = getelementptr inbounds i64, ptr %"new::Array", i64 -1
  store atomic i64 4659479392, ptr %"new::Array.tag_addr" unordered, align 8
  %1 = getelementptr inbounds ptr, ptr %"new::Array", i64 1
  store ptr %0, ptr %"new::Array", align 8
  store ptr %"Memory{Float64}[]", ptr %1, align 8
  %"new::Array.size_ptr" = getelementptr inbounds i8, ptr %"new::Array", i64 16
  store i64 3, ptr %"new::Array.size_ptr", align 8
  store ptr %"new::Array", ptr %gc_slot_addr_0, align 8
  %2 = call nonnull ptr @j_f_6499(ptr nonnull %"new::Array")
  %frame.prev10 = load ptr, ptr %frame.prev, align 8
  store ptr %frame.prev10, ptr %pgcstack, align 8
  ret ptr %2
}

julia> code_llvm(h4, (); debuginfo=:none)

; Function Signature: h4()
define nonnull ptr @julia_h4_6500() #0 {
top:
  %gcframe1 = alloca [3 x ptr], align 16
  call void @llvm.memset.p0.i64(ptr align 16 %gcframe1, i8 0, i64 24, i1 true)
  %pgcstack = call ptr inttoptr (i64 6483926436 to ptr)(i64 262) #9
  store i64 4, ptr %gcframe1, align 8
  %task.gcstack = load ptr, ptr %pgcstack, align 8
  %frame.prev = getelementptr inbounds ptr, ptr %gcframe1, i64 1
  store ptr %task.gcstack, ptr %frame.prev, align 8
  store ptr %gcframe1, ptr %pgcstack, align 8
  %"Memory{Float64}[]" = call ptr @jl_alloc_genericmemory(ptr nonnull @"+Core.GenericMemory#6502.jit", i64 4)
  %.data_ptr = getelementptr inbounds { i64, ptr }, ptr %"Memory{Float64}[]", i64 0, i32 1
  %0 = load ptr, ptr %.data_ptr, align 8
  %gc_slot_addr_0 = getelementptr inbounds ptr, ptr %gcframe1, i64 2
  store ptr %"Memory{Float64}[]", ptr %gc_slot_addr_0, align 8
  %ptls_field = getelementptr inbounds ptr, ptr %pgcstack, i64 2
  %ptls_load = load ptr, ptr %ptls_field, align 8
  %"new::Array" = call noalias nonnull align 8 dereferenceable(32) ptr @ijl_gc_small_alloc(ptr %ptls_load, i32 616, i32 32, i64 4659479392) #7
  %"new::Array.tag_addr" = getelementptr inbounds i64, ptr %"new::Array", i64 -1
  store atomic i64 4659479392, ptr %"new::Array.tag_addr" unordered, align 8
  %1 = getelementptr inbounds ptr, ptr %"new::Array", i64 1
  store ptr %0, ptr %"new::Array", align 8
  store ptr %"Memory{Float64}[]", ptr %1, align 8
  %"new::Array.size_ptr" = getelementptr inbounds i8, ptr %"new::Array", i64 16
  store i64 4, ptr %"new::Array.size_ptr", align 8
  store ptr %"new::Array", ptr %gc_slot_addr_0, align 8
  %2 = call nonnull ptr @j_f_6506(ptr nonnull %"new::Array")
  %frame.prev10 = load ptr, ptr %frame.prev, align 8
  store ptr %frame.prev10, ptr %pgcstack, align 8
  ret ptr %2
}

Julia correctly realises that g3 throws, although it doesn't remove the memory allocation.

Also, inferred effects are much better:

julia> Base.infer_effects(g3, ())
(+c,+e,!n,+t,+s,+m,+u,+o,+r)

julia> Base.infer_effects(g4, ())
(?c,+e,+n,+t,+s,+m,+u,+o,+r)

julia> Base.infer_effects(h3, ())
(!c,!e,!n,!t,!s,!m,!u,+o,!r)

julia> Base.infer_effects(h4, ())
(!c,!e,!n,!t,!s,!m,!u,+o,!r)

System:

julia> versioninfo()
Julia Version 1.12.0-DEV.1082
Commit 58c7186d19* (2024-08-22 02:53 UTC)
Platform Info:
  OS: macOS (arm64-apple-darwin23.4.0)
  CPU: 8 × Apple M1
  WORD_SIZE: 64
  LLVM: libLLVM-18.1.7 (ORCJIT, apple-m1)
Threads: 1 default, 0 interactive, 1 GC (on 4 virtual cores)

0 replies

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

FixedSizeArrays.jl Showcase #62

{{title}}

Replies: 2 comments

{{title}}

{{title}}

{{editor}}'s edit

{{editor}}'s edit

Select a reply

FixedSizeArrays.jl Showcase #62

giordano Aug 22, 2024 Maintainer

Simple function which can constant-propagate the size of the array

Replies: 2 comments

giordano Aug 22, 2024 Maintainer Author

Adding vectors of BFloat16

giordano Aug 22, 2024 Maintainer Author

Reshaping FixedSizeArrays vs Arrays

giordano
Aug 22, 2024
Maintainer

giordano
Aug 22, 2024
Maintainer Author

Adding vectors of `BFloat16`

giordano
Aug 22, 2024
Maintainer Author

Reshaping `FixedSizeArray`s vs `Array`s