How to avoid the 2 allocations for any struct?

New to Julia
1

I illustrate my problem with an example. Say I work heavily with small permutations (elements of the
symmetric group) and want to multiply them as fast as possible.

A permutation of 1:n is just given by giving the images of the integers 1 to n as a Vector
so I could do

Perm=Vector{Int}
a=[5,4,3,2,1]
b=[2,1,4,3,5]
function mult(a::Perm,b::Perm)
  r=similar(a)
@inbounds  for (i,v) in enumerate(a) r[i]=b[v] end
  r
end

and this works quite well:

julia> @btime mult($a,$b)
  31.705 ns (1 allocation: 128 bytes)
5-element Array{Int64,1}:
 5
 3
 4
 1
 2

However the problem is that I must write mult(a,b)and not a*b as I would like, because
contrary to what I could do in a language like C++, Perm is just an alias and not a type by itself,
thus if I define

Base.:*(a::Perm,b::Perm)=...

I am doing an horrible type hijacking (defining multiplication on Vector{Int}).

The only thing I know how to do in Julia is define a struct with a field:

struct Perm
  d::Vector{Int}
end

pa=Perm(a)
pb=Perm(b)

Now I can overload * without problems

function Base.:*(a::Perm,b::Perm)
  r=similar(a.d)
  @inbounds for (i,v) in enumerate(a.d) r[i]=b.d[v] end
  Perm(r)
end

but I am not as efficient: the multiplication does 2 allocations, since Julia allocates the struct and
its field d separately:

julia> @btime $pa*$pb
  38.247 ns (2 allocations: 144 bytes)
Perm([5, 3, 4, 1, 2])

So my question is: can I avoid that? What is the best design in Julia?

2

[quote=“Jean_Michel, post:1, topic:24590”]
How to avoid the 2 allocations for any struct?

Perm=Vector{Int}
a=[5,4,3,2,1]
b=[2,1,4,3,5]
function mult(a::Perm,b::Perm)
  r=similar(a)
  @inbounds  for (i,v) in enumerate(a)
    r[i]=b[v]
  end
  r
end

*(a::Perm,b::Perm) = mult(a,b)

Single allocation, problem solved.

Sorry, I forgot about the Perm. Perm is a type of Vector{Int}

3

so you are Hijacking the multiplication for Vector{Int} that I said one should avoid

1 Like
4

I don’t kow what you mean by hijacking. That’s the way you are suppose to write code in Julia. You have a type and you overload the type for the operator *

1 Like
5

In Julia you can write

Base.:+(a,b)=0

but you won’t like the consequences. This is what is called hijacking

6

Here look at my code

    # Basic arithmetic functions
    +(x::PDFP, y::PDFP) = PDFP_add(x,y)

    -(x::PDFP) = PDFP_isError(x) ? x : PDFP((x.s+1)%2, x.expo, x.m)

    -(x::PDFP, y::PDFP) = PDFP_sub(x,y)

    *(x::PDFP, y::PDFP) = PDFP_mul(x,y)

    /(x::PDFP, y::PDFP) = PDFP_div(x,y)
7

You should never write code like that. You should ALWAYS define what type variable “a” and what type variable “b” is in your code.

What you have basically written is

Base.:+(a::Any,b::Any)=0

which is terrible code.

8

Base.:+(a::Float64,b::Float64)=0
is also hijacking

1 Like
9

That just tells Julia that the “+” operator takes two Float64 variables and returns Int64 “0”

If that is WHAT YOU WANT then Julia will give it to you.

1 Like
10

This is called ‘type piracy’, @StevenSiew, and is strongly discouraged.

1 Like
11

I can’t immediately tell why you are getting two allocations, it seems a bit odd. But I wonder about the use of @inline annotation. I’ve never seen it used like that. You normally use it to mark functions for inlining.

It probably doesn’t have anything to do with your issue, but I can’t see it helping.

12

sorry. inline was a typo for inbounds made when I copied the code by hand. Fixed.

13

Maybe define your type as

Perm = Tuple{Vector{Int}}

14

It’s possible that there is some benchmarking artefact, even though you seem to interpolate correctly. Perhaps you can try to wrap your tests in functions to see if it makes a difference.

15

This doesn’t directly answer your question, but if you’re dealing with lots of small vectors, StaticArrays will likely help performance a lot! However, some things like sort are not defined. To work around that, I use TupleTools to provide e.g. an allocation-free sort method:

using StaticArrays, TupleTools
import Base.sort
sort(p::SVector{d,T}; rev::Bool = false) where {d,T} = SVector{d,T}(TupleTools.sort(Tuple(p); rev=rev))
3 Likes
16

No you can’t get rid of the allocation in this context but that doesn’t really matter since it can be optimal zed out if the function is inlined.

1 Like
17

Do I have to declare the function @inline explicitly or will the inlining happen automatically?

18

Inlining mostly happens automatically, if the compiler decides that it’s worthwhile. But you can ask it more forcefully with @inline (not sure if that will absolutely guarantee inlining, though).

19

I think that one should be somewhat cautious with overriding the compiler’s inline decisions.

Even if it happens to yield an improvement in a benchmark with the current Julia version, the compiler improves a lot with every release under the hood, so unless these choices are revisited from time to time (which rarely ever happens in practice) they can easily end up forcing something that is suboptimal within 4–12 months, which is usually much shorter than the lifespan of most code.

There are packages out there with code that have a ton of @inline directives dating from the 0.5–0.6 era, which may no longer be necessary or optimal.

20

or

Both result in type-piracy when you do:

You need to do:

struct Perm
    data:: Vector{Int}
end

and appropriately access the fields.
Extension via composition

1 Like