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

General Usage Performance
,
21

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

22

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

23

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

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

nospecialize

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> mainbench()
  0.012904 seconds (9 allocations: 80.453 KiB)
  2.708566 seconds (29.79 M allocations: 757.602 MiB, 3.69% gc time)
24

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

1 Like
25

right, I’m having a hard time fighting the union splitting limit, we might just use a single type and encode the “type” in some Enum

26

Isn’t that basically what Unityper does?

2 Likes
27

Yes.

28

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

2 Likes
29

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

30

it’s T… basically eltype(p)

adding

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

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

changes nothing

1 Like
31

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.

32

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:

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.

3 Likes
34

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

I have learned 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

35

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

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

4 Likes
36

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

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

37

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

38

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. :slight_smile:

So, perhaps your real issue here is using recursion.

1 Like
39

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”

40
3 Likes
41

8 posts were split to a new topic: Tail-call recursion