Allocation free alternative to typeof(similar(...)

General Usage
1

I would like to know the return type of similar(A, T, sz) in a type-stable way, without any allocations.

For example, the following method does what I want:

function similartype(A, T, sz::Dims)
      B = similar(A, T, map(zero, sz))
      return typeof(B)
end

but the allocation of the array B, even if it has length zero, will not be eliminated (I assume this happens because allocating an Array is not a native Julia operation but calls out to C?).

My use case is the following. Over at TensorOperations.jl, I am experimenting with a module global cache dictionoray to hold temporary arrays used for intermediate results when performing tensor contractions. However, since these temporaries can be of any type, the dictionary (its actually an LRUCache) has valtype == Any. Say I get a possible temporary array B from the cache, it’s type cannot be inferred and is Any. But I would then like to pass this through a function, say checked_similar(B, A, T, sz), which checks if B fullfills the requirements, if not, allocates a new temporary, and if so, just returns B but with the correct type annotated.

So something like

checked_similar(B, A, T, sz)
   if B !== nothing && size(B) == sz && eltype(B) == T
             TB = similartype(A, T, sz)
             return B::TB
    else
        return similar(A, T, sz)
   end
end

Unfortunately, I do not know how to implement similartype without it actually allocating something.

2

Hackish but works:

similar_type(A, T, sz) = Core.Compiler.return_type(similar, Tuple{typeof(A), Type{T}, typeof(sz)})
3

This seems to be a bit overly convoluted. Yes, checked_similar without the assertion is sometimes type-unstable, but so is B in the first place (upon grabbing it from your cache). You’re going to pay for the cost of a dynamic dispatch no matter what — all you need is to carefully consider where that happens with a function boundary.

1 Like
4

A typical contraction like
@tensor C[...] = A1[...] * A2[...] * A3[ ... ]
is expanded to something analoguous to

A1temp = cached_similar(A1, ...)
permute!(A1temp, A1, ...)
A2temp = cached_similar(A2, ...)
permute!(A2temp, A2, ...)
B1temp = cached_similar(A1, ...)
mul!(B1temp, A1temp, A2temp)
B1 = cached_similar(....)
permute!(B1, B1temp)
A3temp = cached_similar(A3, ...)
...

where cached_similar gets temporaries from cache (I am hiding the details of how it knows which to get), and calls checked_similar from above. I think ensuring that cached_similar is type stable is really the only way to go. It’s not practicable to define new functions for every step, and furthermore, the end result would still be type unstable.

Is there any problem with the solution of @mohamed82008 ? Can I define this as a Base.@pure function? If, for some user type, similar is type unstable, that’s fine, but at least for regular Arrays I really do want the return type to be inferable.