# Allocation and slow down when # of types involved increase (slower than C++ virtual methods)

**URL:** <https://discourse.julialang.org/t/allocation-and-slow-down-when-of-types-involved-increase-slower-than-c-virtual-methods/87656>\
**Category:** Performance\
**Tags:** question, hep\
**Created:** [September 22, 2022, 3:43pm UTC](https://discourse.julialang.org/t/allocation-and-slow-down-when-of-types-involved-increase-slower-than-c-virtual-methods/87656 "2022-09-22T15:43:34Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![jling](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jling/32/212909_2.png) [@jling](https://discourse.julialang.org/u/jling)\
**Post date:** [September 22, 2022, 3:43pm UTC](https://discourse.julialang.org/t/allocation-and-slow-down-when-of-types-involved-increase-slower-than-c-virtual-methods/87656/1 "2022-09-22T15:43:34Z")

</div>

## \*Happy to pay someone to spend time investigating this

The context is @peremato trying to present a Julia case for detector simulation used at e.g. CERN (the LHC) and other accelerator/medical research places: [https://indico.cern.ch/event/1202075/contributions/5056320/attachments/2511955/4317921/Geom4hep-202206.pdf](https://indico.cern.ch/event/1202075/contributions/5056320/attachments/2511955/4317921/Geom4hep-202206.pdf)

* * *

As far as we can tell, the allocation and speed different (order of magnitude) purely comes from the fact that one file contains more geometry types during run time than the other file.

but I will summarize finding and steps to reproduce:

1. `git clone https://github.com/peremato/Geom4hep/`
2. `cd Geom4hep/`

open `examples/XRay.jl` and comment out everything below line 54 (only keep definitions)

1. `julia --project=.`
2. `] instantiate`
3. `julia> using Revise, Geom4hep`
4. `julia> includet("./examples/XRay.jl")`
5. compare these two:

```julia-auto
const full = processGDML("examples/trackML.gdml", Float64)
const volume = full[2,1]
const world = getWorld(volume)
const nav = BVHNavigator(world)
@time generateXRay(nav, world, 1e4, 1);
@time generateXRay(nav, world, 1e4, 1);
  0.013423 seconds (9 allocations: 80.453 KiB)

```

```julia-auto
const full2 = processGDML("examples/cms2018.gdml", Float64)
const volume2 = full2[1,7,1]
const world2 = getWorld(volume2)
const nav2 = BVHNavigator(world2)
@time generateXRay(nav2, world2, 1e4, 1);
@time generateXRay(nav2, world2, 1e4, 1);
  2.723019 seconds (29.79 M allocations: 757.602 MiB, 2.67% gc time)

```

The other finding and bread crumbs can be found: [Hunting allocation · Issue #1 · peremato/Geom4hep · GitHub](https://github.com/peremato/Geom4hep/issues/1#issuecomment-1228836714)

---

<div class="post-metadata">

**Author:** ![jling](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jling/32/212909_2.png) [@jling](https://discourse.julialang.org/u/jling)\
**Post date:** [September 22, 2022, 3:48pm UTC](https://discourse.julialang.org/t/allocation-and-slow-down-when-of-types-involved-increase-slower-than-c-virtual-methods/87656/2 "2022-09-22T15:48:59Z")

</div>

the various `distanceToOut` and `distanceToIn` which takes different types, and often call these function with different types (because geometry can nest within each other), is what we think the problem is at

and seems to be a fundamental limitation of Julia types at this point

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [September 22, 2022, 4:02pm UTC](https://discourse.julialang.org/t/allocation-and-slow-down-when-of-types-involved-increase-slower-than-c-virtual-methods/87656/3 "2022-09-22T16:02:02Z")

</div>

Dynamic dispatch is slow in Julia — slower than C++ virtual methods, because C++ method dispatch only depends on a _single_ object type (`this`) and hence can use [vtable](https://en.wikipedia.org/wiki/Virtual_method_table) lookup.

High-performance code in Julia always relies on devirtualizing critical code. This also means that you can’t easily write performant geometry code in Julia by having an array of geometric objects of different types and relying on dynamic dispatch to execute different methods (determined at _runtime_) for different objects — you need to implement a different dispatch strategy.

See also this discussion: [Union splitting vs C++](https://discourse.julialang.org/t/union-splitting-vs-c/61772)

---

<div class="post-metadata">

**Author:** ![jling](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jling/32/212909_2.png) [@jling](https://discourse.julialang.org/u/jling)\
**Post date:** [September 22, 2022, 4:04pm UTC](https://discourse.julialang.org/t/allocation-and-slow-down-when-of-types-involved-increase-slower-than-c-virtual-methods/87656/4 "2022-09-22T16:04:25Z")

</div>

> [@stevengj](#):
>
> can’t easily write performant geometry code in Julia by having an array of geometric objects

ah yes, and C++ single dispatch is much easier also makes sense.

The question is what are some known solution that doesn’t break code organization and extensibility, unrolling is probably not an option here.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [September 22, 2022, 4:06pm UTC](https://discourse.julialang.org/t/allocation-and-slow-down-when-of-types-involved-increase-slower-than-c-virtual-methods/87656/5 "2022-09-22T16:06:16Z")

</div>

> [@jling](#):
>
> The question is what are some known solution that doesn’t break code organization and extensibility, unrolling is probably not an option here.

I think you basically need to implement your own vtable as discussed in the other thread.

---

<div class="post-metadata">

**Author:** ![Raf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/raf/32/3383_2.png) [@Raf](https://discourse.julialang.org/u/Raf)\
**Post date:** [September 22, 2022, 4:10pm UTC](https://discourse.julialang.org/t/allocation-and-slow-down-when-of-types-involved-increase-slower-than-c-virtual-methods/87656/6 "2022-09-22T16:10:26Z")

</div>

I havent tried it but maybe this will help?

> **[GitHub - thautwarm/Virtual.jl](https://github.com/thautwarm/Virtual.jl)**
>
> Contribute to thautwarm/Virtual.jl development by creating an account on GitHub.

---

<div class="post-metadata">

**Author:** ![jling](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jling/32/212909_2.png) [@jling](https://discourse.julialang.org/u/jling)\
**Post date:** [September 22, 2022, 4:18pm UTC](https://discourse.julialang.org/t/allocation-and-slow-down-when-of-types-involved-increase-slower-than-c-virtual-methods/87656/7 "2022-09-22T16:18:50Z")

</div>

> <https://github.com/thautwarm/Virtual.jl/issues/3>
>
> \`\`\`julia
> \[Info: Precompiling Geom4hep \[eb5d0804-93e0-431a-a4d4-b4f95b95575a\]
> …ERROR: LoadError: setfield! fields of Types should not be changed
> Stacktrace:
> \[1\] error(s::String)
> @ Base ./error.jl:35
> \[2\] setproperty!(x::Type, f::Symbol, v::Symbol)
> @ Base ./Base.jl:34
> \[3\] parse\_function\_header!(ln::LineNumberNode, self::Virtual.FuncInfo, header::Expr; is\_lambda::Bool, allow\_lambda::Bool)
> @ Virtual C:\\Users\\twshe\\Desktop\\Git\\Virtual\\src\\reflection.jl:230
> \[4\] parse\_function(ln::LineNumberNode, ex::Expr; fallback::Virtual.Undefined, allow\_short\_func::Bool, allow\_lambda::Bool)
> @ Virtual C:\\Users\\twshe\\Desktop\\Git\\Virtual\\src\\reflection.jl:186
> \[5\] var"@override"(\_\_source\_\_::LineNumberNode, \_\_module\_\_::Module, func\_def::Any)
> @ Virtual ~/.julia/packages/Virtual/OLENd/src/Virtual.jl:256
> \[6\] include(mod::Module, \_path::String)
> @ Base ./Base.jl:419
> \[7\] include(x::String)
> @ Geom4hep ~/Documents/github/Geom4hep/src/Geom4hep.jl:1
> \`\`\`
> 
> is this problem of how I'm using the package or Virtual.jl doesn't work on 1.8?

---

<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:** [September 22, 2022, 4:47pm UTC](https://discourse.julialang.org/t/allocation-and-slow-down-when-of-types-involved-increase-slower-than-c-virtual-methods/87656/8 "2022-09-22T16:47:53Z")

</div>

> [@stevengj](#):
>
> slower than C++ virtual methods, because C++ method dispatch only depends on a _single_ object type (`this`) and hence can use [vtable](https://en.wikipedia.org/wiki/Virtual_method_table) lookup.

It’s good to have this confirmed, but while the topic was “when # of types increases”, I’m curious, 1) is it for sure slower when there’s actually only one type involved. And 2) when 2+ for one or more extra type, do you think it gets rapidly slower? [I’m not too concerned about that vs C++, since multiple dispatch is more powerful than C++, and I’m not sure C++ has anything to emulate it faster (or slower or at all), though Stroustrup had a, not yet implemented, proposal.]

I’m guessing Julia is optimized for the multiple case, not single, so Julia doesn’t use a vtable even if it could sometimes? So what’s the alternative in the single case? I think basically a big old (C-like) `switch` (and `@goto` only as a macro, maybe vtable could be built?).

Except Julia doesn’t have `switch` (yet) either, but a big if-else should be as fast:

> <https://github.com/JuliaLang/julia/issues/18285>
>
> \# Proposal
> 
> This is a Julep suggested by @StefanKarpinski during this \[julia-u…sers group discussion\](https://groups.google.com/forum/#!topic/julia-users/7IqQROx\_zIo).
> 
> Julia lacks a C-style \[switch\](http://en.wikipedia.org/wiki/Switch\_statement) statement. This issue has \[come up\](https://github.com/JuliaLang/julia/issues/5410) \[before\](https://groups.google.com/forum/#!topic/julia-users/pnEqF5w4GJY/discussion) on various fora. Unsurprisingly, Julia also lacks \[pattern matching\](https://en.wikipedia.org/wiki/Pattern\_matching), a useful generalization of case and switch, which has been implemented as a \[macro\](https://github.com/kmsquire/Match.jl) for Julia.
> 
> This proposal is concerned with using switch statements over integral (isbits) types to exploit the ability of LLVM's \[switch instruction\](http://llvm.org/docs/LangRef.html#switch-instruction) to provide a \[branch table\](https://en.wikipedia.org/wiki/Branch\_table) implementation of switch, which is more performant than a sequence of \`if-else\` conditionals. It should be amenable to supporting extended switch and pattern capabilities in the future; for that reason I'll suggest using adding the \`case\` keyword to introduce the form. If it's desired that the statement only be used as a C style switch and that pattern matching be introduced separately, perhaps \`switch\` is the better choice.
> 
> I'll skip the arguments in around whether to include such a feature at all; interested readers can review some of those arguments in the context of \[Python\](http://www.python.org/dev/peps/pep-3103/) or \[Lua\](http://lua-users.org/wiki/SwitchStatement), as the arguments on both sides would be similar for Julia.
> \# Syntax
> 
> If we'd like to subsume this in a future pattern matching Julia extension, I suggest a syntax influenced by the \[Match.jl\](https://github.com/kmsquire/Match.jl) macro, replacing \`@match\` with the keyword \`case\` ~~, and adding a new keyword \`of\` to use instead of \`begin\`. I chose \`of\` because that's used in many other languages that use \`case\`, and because Julia constructs like \`if/for/while\` don't require a \`begin\` for their \`end\`~~ (Objection sustained).
> 
> \`\`\` Erlang
> case case\_expr
> case0 =\> expr0
> case1 =\> expr1
> .
> .
> .
> caseNMinusOne =\> exprNMinusOne
> else =\> exprN
> end
> \`\`\`
> 
> The optional \`else\` at the end could be replaced by \`\_\` or even \`otherwise\` or \`default\`, at the cost of using more keywords.
> 
> Each case above could be preceded by an \`of\` if that syntax is preferable. It strikes me as a little wordy but it's a syntax used in other languages and perhaps people find it more readable.
> 
> \`\`\` Erlang
> case case\_expr
> of case0 =\> expr0
> of case1 =\> expr1
> .
> .
> .
> of caseNMinusOne =\> exprNMinusOne
> else =\> exprN
> end
> \`\`\`
> \# Examples
> 
> \`\`\` Erlang
> n = rand(0:32)
> function print\_if\_lt\_3(n)
> case n
> 0 =\> println("zero")
> 1 =\> println("one")
> 2 =\> println("two")
> else =\> println("too big")
> end
> end
> \`\`\`
> 
> Should be semantically equivalent to
> 
> \`\`\` Julia
> n = rand(0:32)
> function print\_if\_lt\_3(n)
> if n == 0 
> println("zero")
> elseif n == 1
> println("one")
> elseif n == 2
> println("two")
> else
> println("too big")
> end
> end
> \`\`\`
> 
> An example with enums
> 
> \`\`\` Erlang
> @enum Dir north northeast east southeast south southwest west northwest
> function degree\_of\_dir(d)
> case d
> north =\> 90
> northeast =\> 45
> east =\> 0
> southeast =\> 315
> south =\> 270
> southwest =\> 225
> west =\> 180
> northwest =\> 135
> end
> end
> \`\`\`
> 
> The intent is that \`@enum\` should work well with this \`case\` statement, which means that the conversion to the enum's Int value should be implicit, as above.

Julia neither has pattern matching built in (like Scala, and recently added to Python and Java), but it’s available with e.g. this package:

> **[GitHub - JuliaServices/Match.jl: Advanced Pattern Matching for Julia](https://github.com/JuliaServices/Match.jl)**
>
> Advanced Pattern Matching for Julia. Contribute to JuliaServices/Match.jl development by creating an account on GitHub.

Do you know if that is the main package, or at least if it (or any of the many alternatives) are as fast as C’s `switch`?

---

<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:** [September 22, 2022, 4:49pm UTC](https://discourse.julialang.org/t/allocation-and-slow-down-when-of-types-involved-increase-slower-than-c-virtual-methods/87656/9 "2022-09-22T16:49:46Z")

</div>

A sequence of if elses or using short circuit evaluation in place of a switch(I like this a lot) will lower to efficient structures (jump tables etc…) if LLVM thinks it will be faster.

See [Do C++ performance optimisations apply to Julia? - #30 by gbaraldi](https://discourse.julialang.org/t/do-c-performance-optimisations-apply-to-julia/82567/30)

---

<div class="post-metadata">

**Author:** ![jling](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jling/32/212909_2.png) [@jling](https://discourse.julialang.org/u/jling)\
**Post date:** [September 22, 2022, 4:49pm UTC](https://discourse.julialang.org/t/allocation-and-slow-down-when-of-types-involved-increase-slower-than-c-virtual-methods/87656/10 "2022-09-22T16:49:47Z")

</div>

> [@Palli](#):
>
> 1. is it for sure slower when there’s actually only one type involved. And 2) when 2+ for one or more extra type, do you think it gets rapidly slower?

it gets rapidly slower when reaching 5, see the C++ Union splitting thread linked above. other wise comparable in performance because static dispatch has no overhead at run time

---

<div class="post-metadata">

**Author:** ![jling](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jling/32/212909_2.png) [@jling](https://discourse.julialang.org/u/jling)\
**Post date:** [September 22, 2022, 5:33pm UTC](https://discourse.julialang.org/t/allocation-and-slow-down-when-of-types-involved-increase-slower-than-c-virtual-methods/87656/11 "2022-09-22T17:33:01Z")

</div>

> [@stevengj](#):
>
> I think you basically need to implement your own vtable as discussed in the other thread.

I have hoped that I can get away with something like:

```julia
function distanceToIn(shape, point, dir)
    if shape isa Trap
        distanceToIn_trap(shape, point, dir)
    elseif shape isa Trd
        distanceToIn_trd(shape, point, dir)
    elseif shape isa Cone
        distanceToIn_cone(shape, point, dir)
    elseif shape isa Box
        distanceToIn_box(shape, point, dir)
    elseif shape isa Tube
        distanceToIn_tube(shape, point, dir)
    elseif shape isa Volume
        distanceToIn_volume(shape, point, dir)
    elseif shape isa Polycone
        distanceToIn_polycone(shape, point, dir)
    elseif shape isa CutTube
        distanceToIn_cuttube(shape, point, dir)
    elseif shape isa Boolean
        distanceToIn_boolean(shape, point, dir)
    end
end

```

but it made no difference. The example you linked seems to suggest this has to go inside the loop directly?

---

<div class="post-metadata">

**Author:** ![pdeffebach](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pdeffebach/32/10320_2.png) [@pdeffebach](https://discourse.julialang.org/u/pdeffebach)\
**Post date:** [September 22, 2022, 5:58pm UTC](https://discourse.julialang.org/t/allocation-and-slow-down-when-of-types-involved-increase-slower-than-c-virtual-methods/87656/12 "2022-09-22T17:58:52Z")

</div>

Add `@nospecialize`?

---

<div class="post-metadata">

**Author:** ![jling](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jling/32/212909_2.png) [@jling](https://discourse.julialang.org/u/jling)\
**Post date:** [September 22, 2022, 6:09pm UTC](https://discourse.julialang.org/t/allocation-and-slow-down-when-of-types-involved-increase-slower-than-c-virtual-methods/87656/13 "2022-09-22T18:09:59Z")

</div>

around this steering function? no help

---

<div class="post-metadata">

**Author:** ![jling](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jling/32/212909_2.png) [@jling](https://discourse.julialang.org/u/jling)\
**Post date:** [September 22, 2022, 6:26pm UTC](https://discourse.julialang.org/t/allocation-and-slow-down-when-of-types-involved-increase-slower-than-c-virtual-methods/87656/14 "2022-09-22T18:26:59Z")

</div>

manual splitting actually made performance much worse [Trying manual splitting (regression) by Moelf · Pull Request #2 · peremato/Geom4hep · GitHub](https://github.com/peremato/Geom4hep/pull/2/files#diff-a794b080eabe904cd3c1e79bfa4171f4ed5455dab8443dde48d76b76688f31d6R2)

splitted into `Distance.jl` and `Inside.jl`

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [September 22, 2022, 8:06pm UTC](https://discourse.julialang.org/t/allocation-and-slow-down-when-of-types-involved-increase-slower-than-c-virtual-methods/87656/15 "2022-09-22T20:06:00Z")

</div>

> [@jling](#):
>
> `distanceToIn_trap(shape, point, dir)`

Does it make a difference if you do `distanceToIn_trap(shape::Trap, point, dir)` to make sure that the compiler is using the type information here?

---

<div class="post-metadata">

**Author:** ![jling](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jling/32/212909_2.png) [@jling](https://discourse.julialang.org/u/jling)\
**Post date:** [September 22, 2022, 8:18pm UTC](https://discourse.julialang.org/t/allocation-and-slow-down-when-of-types-involved-increase-slower-than-c-virtual-methods/87656/16 "2022-09-22T20:18:53Z")

</div>

no difference.

maybe I’m not finding the correct function that causes the issue… but again, Profiler is not helpful here so it has been really hard to pin down the problem

---

<div class="post-metadata">

**Author:** ![jling](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jling/32/212909_2.png) [@jling](https://discourse.julialang.org/u/jling)\
**Post date:** [September 22, 2022, 9:06pm UTC](https://discourse.julialang.org/t/allocation-and-slow-down-when-of-types-involved-increase-slower-than-c-virtual-methods/87656/17 "2022-09-22T21:06:58Z")

</div>

by annotating the individual function with types, I’m able to recover the original performance (i.e. much slower than C++) and I feel like essentially I have re-created how Julia does things but manually and with no performance improvement

> <https://github.com/peremato/Geom4hep/pull/2/commits/2f2a458d8e3cb7c409f917e43a8c38319d246eee>

---

<div class="post-metadata">

**Author:** ![jling](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jling/32/212909_2.png) [@jling](https://discourse.julialang.org/u/jling)\
**Post date:** [September 22, 2022, 9:41pm UTC](https://discourse.julialang.org/t/allocation-and-slow-down-when-of-types-involved-increase-slower-than-c-virtual-methods/87656/18 "2022-09-22T21:41:33Z")

</div>

we might have a thread:  
this change of 4 lines ([Trying manual splitting by Moelf · Pull Request #2 · peremato/Geom4hep · GitHub](https://github.com/peremato/Geom4hep/pull/2/commits/eafe81e0c735a4c6c7daa0d7a3937e074638613e))

seems to make time 2x worse and allocation 10x larger, all I’m doing here is manual splitting like I did for other shape

---

<div class="post-metadata">

**Author:** ![Mason](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mason/32/2423_2.png) [@Mason](https://discourse.julialang.org/u/Mason)\
**Post date:** [September 22, 2022, 9:50pm UTC](https://discourse.julialang.org/t/allocation-and-slow-down-when-of-types-involved-increase-slower-than-c-virtual-methods/87656/19 "2022-09-22T21:50:55Z")

</div>

Have you tried out using [GitHub - YingboMa/Unityper.jl](https://github.com/YingboMa/Unityper.jl) ? It has some annoying ergonomics like requiring a default keword argument field for every struct, but it is designed to solve this exact performance problem you’re having.

---

<div class="post-metadata">

**Author:** ![jling](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jling/32/212909_2.png) [@jling](https://discourse.julialang.org/u/jling)\
**Post date:** [September 22, 2022, 9:56pm UTC](https://discourse.julialang.org/t/allocation-and-slow-down-when-of-types-involved-increase-slower-than-c-virtual-methods/87656/20 "2022-09-22T21:56:06Z")

</div>

the function we call inside the loop is recursive and branch to different types, this is different from most manual union splitting example (and YingboMa’s example)

[Next page](https://discourse.julialang.org/t/allocation-and-slow-down-when-of-types-involved-increase-slower-than-c-virtual-methods/87656.md?page=2)