# 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:** 2

<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, 10:00pm UTC](https://discourse.julialang.org/t/allocation-and-slow-down-when-of-types-involved-increase-slower-than-c-virtual-methods/87656/21 "2022-09-22T22:00:33Z")

</div>

Have you tried it? It works by making everything a packed, concrete struct rather than a collection of different structs. Recusion and branching wouldn’t be a problem for that, but maybe it’s too painful (and non-extensible) to convert your code to it

---

<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, 10:01pm UTC](https://discourse.julialang.org/t/allocation-and-slow-down-when-of-types-involved-increase-slower-than-c-virtual-methods/87656/22 "2022-09-22T22:01:23Z")

</div>

> [@Mason](#):
>
> Have you tried it?

no, but I also have tried a lot of things including the non-working Virtual.jl and manual splitting and there’s no sign of any changes.

I would like to try things manually to make sure there’s ANY difference before re-writing 3k lines of code

---

<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, 10:18pm UTC](https://discourse.julialang.org/t/allocation-and-slow-down-when-of-types-involved-increase-slower-than-c-virtual-methods/87656/23 "2022-09-22T22:18:11Z")

</div>

> [@pdeffebach](#):
>
> Add `@nospecialize`?

this makes allocation worse probably because the calls are recursive and nospecialize makes more boxing

```julia-auto
function distanceToIn(shape, point, dir)
    @nospecialize shape
    if shape isa Trap
        distanceToIn_trap(shape, point, dir)
    elseif shape isa Trd
    ...
    ..
    .

```

## nospecialize

```julia-auto
julia> mainbench()
  0.028915 seconds (616.33 k allocations: 32.053 MiB)
  9.259798 seconds (222.40 M allocations: 11.224 GiB, 15.68% gc time)

```

## original

```julia-auto
julia> mainbench()
  0.012904 seconds (9 allocations: 80.453 KiB)
  2.708566 seconds (29.79 M allocations: 757.602 MiB, 3.69% gc time)

```

---

<div class="post-metadata">

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

</div>

Just a side note: It is possible to try different approaches to this kind of problems by using wrappers over types while keeping the core code intact (generic). I had experimented with that in here: [RayTracingInOneJulia.jl/main.jl at material\_approaches · cdsousa/RayTracingInOneJulia.jl · GitHub](https://github.com/cdsousa/RayTracingInOneJulia.jl/blob/material_approaches/devel/main.jl#L59-L88)

---

<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, 10:50pm UTC](https://discourse.julialang.org/t/allocation-and-slow-down-when-of-types-involved-increase-slower-than-c-virtual-methods/87656/25 "2022-09-22T22:50:25Z")

</div>

right, I’m having [a hard time](https://github.com/peremato/Geom4hep/issues/1#issuecomment-1255629844) fighting the union splitting limit, we might just use a single type and encode the “type” in some Enum

---

<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, 11:33pm UTC](https://discourse.julialang.org/t/allocation-and-slow-down-when-of-types-involved-increase-slower-than-c-virtual-methods/87656/26 "2022-09-22T23:33:37Z")

</div>

Isn’t that basically what Unityper does?

---

<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, 11:37pm UTC](https://discourse.julialang.org/t/allocation-and-slow-down-when-of-types-involved-increase-slower-than-c-virtual-methods/87656/27 "2022-09-22T23:37:15Z")

</div>

Yes.

---

<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 23, 2022, 12:25am UTC](https://discourse.julialang.org/t/allocation-and-slow-down-when-of-types-involved-increase-slower-than-c-virtual-methods/87656/28 "2022-09-23T00:25:16Z")

</div>

well ok so I shouldn’t expect Unityper helps.

Btw, I also increased the compiler constant regarding union splitting and other stuff from 4 → 10, didn’t help

---

<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 23, 2022, 3:10am UTC](https://discourse.julialang.org/t/allocation-and-slow-down-when-of-types-involved-increase-slower-than-c-virtual-methods/87656/29 "2022-09-23T03:10:51Z")

</div>

> [@jling](#):
>
> ```julia
> distanceToIn_boolean(shape, point, dir)
> end
> 
> ```

Don’t you need a fallback here to guarantee that the same type of value is returned always?

---

<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 23, 2022, 3:13am UTC](https://discourse.julialang.org/t/allocation-and-slow-down-when-of-types-involved-increase-slower-than-c-virtual-methods/87656/30 "2022-09-23T03:13:39Z")

</div>

> [@lmiq](#):
>
> same type of value

it’s `T`… basically `eltype(p)`

adding

```julia
function distanceToIn(shape, point::Point3{T}, dir)::T where T

function distanceToOut(shape, point::Point3{T}, dir)::T where T

```

changes nothing

---

<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 23, 2022, 3:19am UTC](https://discourse.julialang.org/t/allocation-and-slow-down-when-of-types-involved-increase-slower-than-c-virtual-methods/87656/31 "2022-09-23T03:19:21Z")

</div>

> [@jling](#):
>
> ```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
> 
> ```

Sorry, probably irrelevant, but as is this function may return `nothing` if the input shape does not match any case. Maybe it is better to guarantee that it returns `zero(eltype(p))` with an `else` fallback.

---

<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 23, 2022, 3:31am UTC](https://discourse.julialang.org/t/allocation-and-slow-down-when-of-types-involved-increase-slower-than-c-virtual-methods/87656/32 "2022-09-23T03:31:21Z")

</div>

> [@jling](#):
>
> well ok so I shouldn’t expect Unityper helps.
> 
> Btw, I also increased the compiler constant regarding union splitting and other stuff from 4 → 10, didn’t help

To be extra clear, since this point seems to have been missed multiple times now: Unityper is _not_ related to Union Splitting. There are no unions with unityper, there’s only ever one type (hence the name). What Gabriel and I were saying is that It’s more or less equivalent to what you were saying here:

> [@jling](#):
>
> we might just use a single type and encode the “type” in some Enum

That is, Unityper gives you a way to compactify your collections of types into one efficient struct to eliminate dynamic dispatches, and instead pattern match on which instance it is supposed to be.

---

<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 23, 2022, 6:51pm UTC](https://discourse.julialang.org/t/allocation-and-slow-down-when-of-types-involved-increase-slower-than-c-virtual-methods/87656/34 "2022-09-23T18:51:14Z")

</div>

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

Unityper doesn’t help, exact same number as before.

[I have learned](https://github.com/peremato/Geom4hep/issues/1#issuecomment-1256335289) that the problem is around the `BooleanUnion/Subtraction/Intersection`, not so much to do with the number of types in the `Shape{T}` union, so I extracted the Booleans into a Unitype, and it didn’t change allocation number at all

---

<div class="post-metadata">

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

</div>

I apologize in advance if you find my comment useless, but we have been solving exactly the same problem for our course on Julia. We had an environment with different type of agents which can interact together (like eat themselves).

Originally, we had all animals in a vector, which of course had to be `Vector{AbstractAgent}`, but it was not type stable (not suprisingly). We then change the representation to a `(Named)Tuple` of vectors, where each vector contained agent of particular type. This made it type stable with additional benefit that when you search for specific type of agent (to eat him), you can search through a smaller vector. It is kind of hairy, but it would work. We have time it in our implementation and speed improvement was like 4x. The implementation in our zoo is here

> <https://github.com/JuliaTeachingCTU/EcosystemCore.jl/blob/bench/src/world.jl>

but it does not tell more then I have written above.

---

<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 23, 2022, 8:14pm UTC](https://discourse.julialang.org/t/allocation-and-slow-down-when-of-types-involved-increase-slower-than-c-virtual-methods/87656/36 "2022-09-23T20:14:38Z")

</div>

thanks for the information, no comments is useless when we have no idea what to try next!

> [@Tomas\_Pevny](#):
>
> We then change the representation to a `(Named)Tuple` of vectors

right, but in our case, Agent have sub-fields that is different type of Agents (because Geometry can mutually nest each other, in particular, you can have a `BooleanIntersection{Boolean{Left, Right}, Box{..}}}`)

so the loop over things is not a flat single pass

---

<div class="post-metadata">

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

</div>

Then I do not know, sorry. Seems like the only solution would be to decrease variability in types, if possible.

---

<div class="post-metadata">

**Author:** ![CameronBieganek](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cameronbieganek/32/6915_2.png) [@CameronBieganek](https://discourse.julialang.org/u/CameronBieganek)\
**Post date:** [September 24, 2022, 12:07am UTC](https://discourse.julialang.org/t/allocation-and-slow-down-when-of-types-involved-increase-slower-than-c-virtual-methods/87656/38 "2022-09-24T00:07:27Z")

</div>

> [@jling](#):
>
> the function we call inside the loop is recursive

Purely anecdotal information here, but one time I wrote a recursive function, and it was slow. I rewrote the function using a `while` loop, and it was fast. 🙂

So, perhaps your real issue here is using recursion.

---

<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 24, 2022, 2:48am UTC](https://discourse.julialang.org/t/allocation-and-slow-down-when-of-types-involved-increase-slower-than-c-virtual-methods/87656/39 "2022-09-24T02:48:04Z")

</div>

yeah ideally, but if you look at the code, just grep for `distanceToIn` and `distanceToOut` and `inside(` you will know why it’s not as simple as “just don’t use recursion”

---

<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 26, 2022, 3:02pm UTC](https://discourse.julialang.org/t/allocation-and-slow-down-when-of-types-involved-increase-slower-than-c-virtual-methods/87656/40 "2022-09-26T15:02:18Z")

</div>

> <https://github.com/peremato/Geom4hep/issues/1#issuecomment-1257833119>
>
> if I run through \`--track-allocation=user\`, the only allocation I see is:
> \`\`\`ju…lia
> 
> julia\> generateXRay(nav2, world2, 1000, 1);
> 
> julia\> Profile.clear\_malloc\_data()
> 
> julia\> generateXRay(nav2, world2, 1000, 1);
> 
> - function getClosestDaughter(nav::NAV, volume::Volume{T}, point::Point3{T}, dir::Vector3{T}, step\_limit::T ) where {T,NAV}
> - step = step\_limit
> - candidate = 0
> - #---Linear loop over the daughters-------------------------------------------------
> 0 for pvol in intersectedDaughters(nav, volume, point, dir)
> - #---Assuming that it is not yet inside the daughter (otherwise it returns -1.)
> 59378816 dist = distanceToIn(pvol, point, dir)
> 0 dist \< 0. && return (zero(T), pvol.idx ) 
> 0 if dist \> 0. && dist != Inf && dist \< step
> - step = dist
> 0 candidate = pvol.idx
> - end
> 0 end
> 0 return step, candidate
> - end
> - 
> - #---Update the NavigatorState and get the step (distance)
> - function computeStep!(state::NavigatorState{T,NAV}, gpoint::Point3{T}, gdir::Vector3{T}, step\_limit::T) where {T,NAV}
> 0 lpoint, ldir = transform(state.tolocal, gpoint, gdir) 
> 0 volume = currentVolume(state)
> 0 step, idx = getClosestDaughter(state.navigator, volume, lpoint, ldir, step\_limit)
> - #---If didn't hit any daughter return distance to out
> 0 if idx == 0
> 3914320 step = distanceToOut(volume.shape, lpoint, ldir)
> 0 if step \> -kTolerance(T)
> 0 popOut!(state)
> 0 elseif step \< 0
> 0 shape = volume.shape
> 0 volstack = state.volstack
> 0 error(lazy"Negative distanceToOut. \\nstep = $step \\nshape = $shape \\nvolstack = $volstack \\npoint = $lpoint \\ndir = $ldir" )
> - end
> - else
> - #---We hit a daughter, push it into the stack
> 0 step += kPushTolerance(T) # to ensure that do not stay in the surface of the daughter
> 0 pvol = volume.daughters\[idx\]
> 0 pushIn!(state, pvol)
> - end
> 0 return step
> - end
> \`\`\`

---

<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 27, 2022, 12:34am UTC](https://discourse.julialang.org/t/allocation-and-slow-down-when-of-types-involved-increase-slower-than-c-virtual-methods/87656/41 "2022-09-27T00:34:46Z")

</div>

8 posts were split to a new topic: [Tail-call recursion](https://discourse.julialang.org/t/tail-call-recursion/87847)

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

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