# Union splitting vs C++

**URL:** <https://discourse.julialang.org/t/union-splitting-vs-c/61772>\
**Category:** Performance\
**Created:** [May 25, 2021, 12:21pm UTC](https://discourse.julialang.org/t/union-splitting-vs-c/61772 "2021-05-25T12:21:49Z")\
**Posts on this page:** 3\
**Page:** 2

<div class="post-metadata">

**Author:** ![Stephen\_Vavasis](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stephen_vavasis/32/3389_2.png) [@Stephen\_Vavasis](https://discourse.julialang.org/u/Stephen_Vavasis)\
**Post date:** [May 26, 2021, 1:29am UTC](https://discourse.julialang.org/t/union-splitting-vs-c/61772/21 "2021-05-26T01:29:14Z")

</div>

Someone asked much farther above in this thread whether a jump-table is possible in Julia. I discovered by poring over machine-code that Julia (an old version possibly pre-1.0 when I was experimenting) indeed will produce a jump-table for the following style of code:

```julia
if ltype == 1
   <do the first thing>
elseif ltype == 2
   <do the second thing>
elseif ltype == 3
   <do the third thing>

```

etc, with the same variable on the LHS of each equality test and the RHS’s being consecutive integers.

---

<div class="post-metadata">

**Author:** ![melonedo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/melonedo/32/15503_2.png) [@melonedo](https://discourse.julialang.org/u/melonedo)\
**Post date:** [July 8, 2021, 3:54pm UTC](https://discourse.julialang.org/t/union-splitting-vs-c/61772/22 "2021-07-08T15:54:27Z")

</div>

Hello! I created an experimental package [SingleDispatchArrarys.jl](https://github.com/melonedo/SingleDispatchArrays.jl) that generates dispatch table for non-homogeneous arrays, which achieves c++ like performance for non-homogeneous arrays and is much more flexible to manage than manual switch-case.

However, c++ like performance is not necessary a good thing. With long if-elseif-elseif chain, LLVM generates jump table for this. On x86 machines, loading a jump table is nearly as fast as branching, but on Raspberry pi 4b, jump table is actually twice as slow as branching(20ms vs 10ms), looks like LLVM has made a bad choice.

---

<div class="post-metadata">

**Author:** ![melonedo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/melonedo/32/15503_2.png) [@melonedo](https://discourse.julialang.org/u/melonedo)\
**Post date:** [July 9, 2021, 12:32am UTC](https://discourse.julialang.org/t/union-splitting-vs-c/61772/23 "2021-07-09T00:32:18Z")

</div>

As can be seen on Elrod’s LLVM output, the optimizer has figured out that all these branches are really the same thing, so no branch is used at all!  
We could disable it by inserting a few “trouble makers”, then the result is as usual:

```julia
struct Distraction1 <: LineAbstract length::Float64 end
struct Distraction2 <: LineAbstract length::Float64 end
paint(l :: Distraction1) = sin(l.length)
paint(l :: Distraction2) = exp(l.length)
const LineUnion = Union{Line1,Line2,Line3,Line4,Line5,
                        Line6,Line7,Line8,Line9,Line10,
                        Line11,Line12,Line13,Line14,Line15,
                        Line16,Line17,Line18,Line19,Line20,
                        Distraction1, Distraction2}

```

Other code are untouched, particularly, `line_types` in function `test` only uses Line1 ~ Line20. However, the compiler will not know this, thus code for `Distraction1` and `Distraction2` must be included in `paint3`. The results are more reasonable:

```julia
julia> Lines.test(1000000)
result = 500137.3913335729
 with runtime dispatch: 210.302 ms (2000000 allocations: 30.52 MiB)
 with splitting: 22.213 ms (0 allocations: 0 bytes)
 with compiler splitting: 511.819 ms (6998980 allocations: 122.05 MiB)
 with runtime dispatch 3: 207.581 ms (2000000 allocations: 30.52 MiB)
 with compiler splitting 3: 16.938 ms (0 allocations: 0 bytes)
500137.3913335729

```

> **full code**
>
> ```julia
> module Lines
> 
> export test
> export Line1, Line2, Line3, Line4, Line5, Line6, Line7, Line8, Line9, Line10,
> Line11, Line12, Line13, Line14, Line15, Line16, Line17, Line18, Line19, Line20
> export LineUnion, Picture, Picture2
> 
> using BenchmarkTools
> using Test
> 
> abstract type LineAbstract end
> 
> struct Line1 <: LineAbstract length::Float64 end
> struct Line2 <: LineAbstract length::Float64 end
> struct Line3 <: LineAbstract length::Float64 end
> struct Line4 <: LineAbstract length::Float64 end
> struct Line5 <: LineAbstract length::Float64 end
> struct Line6 <: LineAbstract length::Float64 end
> struct Line7 <: LineAbstract length::Float64 end
> struct Line8 <: LineAbstract length::Float64 end
> struct Line9 <: LineAbstract length::Float64 end
> struct Line10 <: LineAbstract length::Float64 end
> struct Line11 <: LineAbstract length::Float64 end
> struct Line12 <: LineAbstract length::Float64 end
> struct Line13 <: LineAbstract length::Float64 end
> struct Line14 <: LineAbstract length::Float64 end
> struct Line15 <: LineAbstract length::Float64 end
> struct Line16 <: LineAbstract length::Float64 end
> struct Line17 <: LineAbstract length::Float64 end
> struct Line18 <: LineAbstract length::Float64 end
> struct Line19 <: LineAbstract length::Float64 end
> struct Line20 <: LineAbstract length::Float64 end
> struct Distraction1 <: LineAbstract length::Float64 end
> struct Distraction2 <: LineAbstract length::Float64 end
> 
> paint(l :: Line1) = l.length
> paint(l :: Line2) = l.length
> paint(l :: Line3) = l.length
> paint(l :: Line4) = l.length
> paint(l :: Line5) = l.length
> paint(l :: Line6) = l.length
> paint(l :: Line7) = l.length
> paint(l :: Line8) = l.length
> paint(l :: Line9) = l.length
> paint(l :: Line10) = l.length
> paint(l :: Line11) = l.length
> paint(l :: Line12) = l.length
> paint(l :: Line13) = l.length
> paint(l :: Line14) = l.length
> paint(l :: Line15) = l.length
> paint(l :: Line16) = l.length
> paint(l :: Line17) = l.length
> paint(l :: Line18) = l.length
> paint(l :: Line19) = l.length
> paint(l :: Line20) = l.length
> paint(l :: Distraction1) = sin(l.length)
> paint(l :: Distraction2) = exp(l.length)
> 
> struct Picture{T<:LineAbstract}
> lines::Vector{T}
> end 
> 
> const LineUnion = Union{Line1,Line2,Line3,Line4,Line5,
> Line6,Line7,Line8,Line9,Line10,
> Line11,Line12,Line13,Line14,Line15,
> Line16,Line17,Line18,Line19,Line20,
> Distraction1, Distraction2}
> struct Picture2{T<:LineUnion}
> lines::Vector{T}
> end 
> 
> # Dynamical dispatch at runtime
> 
> function paint1(p)
> s = 0.
> for l in p.lines
> s += paint(l)
> end
> s
> end
> 
> function paint3(p)
> s = 0.
> @inbounds for i in eachindex(p.lines)
> s += paint(p.lines[i])
> end
> s
> end
> 
> # Union splitting
> 
> function paint2(p)
> s = 0.
> for l in p.lines
> if l isa Line1 s += paint(l)
> elseif l isa Line2 s += paint(l)
> elseif l isa Line3 s += paint(l)
> elseif l isa Line4 s += paint(l)
> elseif l isa Line5 s += paint(l)
> elseif l isa Line6 s += paint(l)
> elseif l isa Line7 s += paint(l)
> elseif l isa Line8 s += paint(l)
> elseif l isa Line9 s += paint(l)
> elseif l isa Line10 s += paint(l)
> elseif l isa Line11 s += paint(l)
> elseif l isa Line12 s += paint(l)
> elseif l isa Line13 s += paint(l)
> elseif l isa Line14 s += paint(l)
> elseif l isa Line15 s += paint(l)
> elseif l isa Line16 s += paint(l)
> elseif l isa Line17 s += paint(l)
> elseif l isa Line18 s += paint(l)
> elseif l isa Line19 s += paint(l)
> elseif l isa Line20 s += paint(l)
> end
> end
> s
> end
> 
> function test(n)
> 
> line_types = [ Line1, Line2, Line3, Line4, Line5, 
> Line6, Line7, Line8, Line9, Line10, 
> Line11, Line12, Line13, Line14, Line15, 
> Line16, Line17, Line18, Line19, Line20 ]
> p = Picture([line_types[rand(1:20)](rand()) for i in 1:n])
> p2 = Picture2(convert(Vector{LineUnion},p.lines))
> 
> global pic1 = p
> global pic2 = p2
> @test paint1(p) ≈ paint2(p)
> println("result = ", paint1(p))
> 
> print(" with runtime dispatch: "); @btime paint1($p) 
> print(" with splitting: "); @btime paint2($p) 
> print(" with compiler splitting: "); @btime paint1($p2) 
> print(" with runtime dispatch 3: "); @btime paint3($p) 
> print(" with compiler splitting 3: "); @btime paint3($p2) 
> 
> end
> 
> end
> 
> using .Lines
> test(1_000_000)
> 
> ```

[Previous page](https://discourse.julialang.org/t/union-splitting-vs-c/61772.md?page=1)