When to use Tuples instead of Vectors?

General Usage Performance
, , ,
1

Hello,

I’m developing QuantumToolbox.jl for simulating quantum systems in Julia. Everything is based on the QuantumObject constructor, which is currently defined as follows

struct QuantumObject{MT<:AbstractArray,ObjType<:QuantumObjectType} <: AbstractQuantumObject
    data::MT
    type::ObjType
    dims::Vector{Int}
end

Where data is either a matrix or a vector, type tells you what kind of quantum object we are dealing with (Operator, Ket state, ecc…), and dims tells you the space dimension of each subsystem (e.g., [2,2] if I have two qubits).

I was wondering if using dims as a NamedTuple{N,Int} instead of a Vector would be better. This object would include less then 20 subsystems at most (so a maximum length of 20).

Indeed, yesterday I noticed that I have some type instabilities in the ptrace function. Basically, it is related to the reshape(data, dims), which reshapes data depending on dims. This causes type instabilities because the reshaped array is unknown (Array{ComplexF64, N} where N).

Now, I was trying to change dims to NTuple{N,Int}. My first basic question is if this would lead to recompilation of the codes any time the QuantumObject changes its dimensions. Is my case suitable to use NTuple instead of Vector? The functions using dims perform very basic operations like vcat, +, -, repeat and a few others.

During this change I’m facing several test error for both code quality and implementation, which I’m fixing one by one. So that’s why I’m asking if it worth it to make such a significant change.

Thanks.

1 Like
2

Yes.

Are this “preparation” steps or you need these to be performed during the hot part of your calculations?

First, you could use a SVector (from StataicArrays.jl) for which most of these operations are defined already.

But your object will be immutable, operating on it will have to work differently than with the mutable vector. You either have to make all the struct mutable or create a new object everytime something is changed on dims.

If all the changes are outside the hot part, that’s probably worth it. Otherwise don’t.

1 Like
3

Hi @lmiq, thanks for the replay.

What do you mean by “hot part”?

If you are asking whether the functions using dims will be just a preparation, no, they can also run inside the main code, or during time evolution.

4

I mean if the content or dimension of dims will change inside loops that are performance critical.

If the length of dims must vary there, you’ll introduce a nasty type instability by using a tuple. If it is only the content (values) of dims, that can work, but the entire object must be created, as it will be immutable.

5

No, once I create a QuantumObject, I don’t change it, because there is no reason for that.

The operations involving dims would just create some temporary Vectors (or NTuples in this case) for performing operations.

But the dims will never change, because there is a one-to-one correspondence between the specific quantum object and the dimensions. In the limit case I need to change dims, I can do it by creating a new QuantumObject.

For example, you can look at the ptrace function, where I just perform basic operations with dims, but I never change it.

6

What is the relationship between the dims parameter and the data array?

7

Using SVector will probably be nice then. A bare N-tuple will have the complications of defining methods for those basic operations.

2 Likes
8

Hi @DNF,

the relation would just be the kronecker product. If I have two spins, I can create the sigma_x operator of the first spin with kron(sigmax(), eye()), which is the kronecker product of [0 1; 1 0] and [1 0; 0 1]. The dims would simply be [2,2].

Now, it doesn’t make sense to change dims to something like [3,4], because the data is a matrix obtained from the kronecker product of 2x2 matrices, with a specific order.

9

Ok, thanks. Do you recomment SVector event if dims are involved in simple functions?

Do you think it worth to change it to SVector or NTuple? For example, the would the reshape stuff work even for Vectors? I think no, right?

10

Actually it does:

julia> x = SVector{3,Int}(1,1,1)
3-element SVector{3, Int64} with indices SOneTo(3):
 1
 1
 1

julia> reshape(x, (1,3))
1×3 reshape(::SVector{3, Int64}, 1, 3) with eltype Int64:
 1  1  1

Your ptrace function, for instance, just works (I just put some vectors as input, without further thought, and removed the type annotation from the input):

julia> function _ptrace_ket(QO, dims, sel)
           rd = dims
           nd = length(rd)
       
           nd == 1 && return QO, rd
       
           dkeep = rd[sel]
           qtrace = filter!(e -> e ∉ sel, Vector(1:nd))
           dtrace = @view(rd[qtrace])
       
           vmat = reshape(QO, reverse(rd)...)
           topermute = nd + 1 .- vcat(sel, qtrace)
           vmat = PermutedDimsArray(vmat, topermute)
           vmat = reshape(vmat, prod(dkeep), prod(dtrace))
       
           return vmat * vmat', dkeep
       end
_ptrace_ket (generic function with 2 methods)

julia> QO = [1,2,3]; dims=SVector{1,Int}(1); sel=[1,2,3];

julia> _ptrace_ket(QO, dims, sel)
([1, 2, 3], [1])
11

I do not understand the specifics of this, I just wanted to make sure that dims isn’t just equal to size(data), or some value trivially calculated from size(data), in which case it would be redundant.

12

Note that, depending if that makes sense to you (if all vectors involved are small), making everything static has a performance benefit:

julia> QO = SVector(1,2,3); dims=SVector(1); sel=SVector(1,2,3);

julia> @btime _ptrace_ket($QO, $dims, $sel)
  1.644 ns (0 allocations: 0 bytes)
([1, 2, 3], [1])

vs (non-static):

julia> QO = [1,2,3]; dims=[1]; sel=[1,2,3];

julia> @btime _ptrace_ket($QO, $dims, $sel)
  8.423 ns (1 allocation: 32 bytes)
([1, 2, 3], [1])
13

Thanks,

No data is usually large, so I can’t use it as an SVector, but the QuantumObject is very general, so it supports almost any kind of AbstractMatrix.

So you definitely recommend to use SVector?

Actually what I meant was if reshape(data, dims...) would work also for dims as a Vector instead of a NTuple or SVector. I mean just in terms of type-stability. I think that there is no way to fix type-instability for Vectorss, do you agree?

14

Well, it would work, of course, you can reshape your data with a SVector as the dims:

julia> reshape([1,2,3,4], SVector(1,4)...)
1×4 Matrix{Int64}:
 1  2  3  4

But that doesn’t solve (or introduce) a stability problem related to other alternative, caused by the conversion of the vector to a matrix, no.

15

But I think that if dims is a NTuple or SVector, it would fix the type stability, because the length is known at compile time

julia> function reshape_test(data, dims)
           reshape(data, dims...)
       end
julia> data = rand(2^3, 2^3)
8×8 Matrix{Float64}:
 0.616376   0.450066  0.0584313  0.721622   0.296208   0.0534047  0.753409   0.0866117
 0.0245175  0.280099  0.160382   0.901469   0.0560182  0.889231   0.0267238  0.444358
 0.932813   0.954797  0.199523   0.326285   0.230656   0.226991   0.353326   0.314231
 0.274211   0.300454  0.300257   0.0339734  0.58597    0.190892   0.513806   0.383873
 0.605115   0.869242  0.569965   0.0425941  0.486396   0.106659   0.66755    0.967982
 0.787707   0.297594  0.107276   0.874543   0.485379   0.598539   0.283138   0.9489
 0.824404   0.608007  0.802067   0.755053   0.223589   0.243299   0.789504   0.940064
 0.0344286  0.158932  0.0207953  0.469507   0.0865818  0.650184   0.783382   0.202822

julia> dims = (2,2,2,2,2,2)
(2, 2, 2, 2, 2, 2)

julia> @code_warntype reshape_test(data, dims)
MethodInstance for reshape_test(::Matrix{Float64}, ::NTuple{6, Int64})
  from reshape_test(data, dims) @ Main REPL[1]:1
Arguments
  #self#::Core.Const(reshape_test)
  data::Matrix{Float64}
  dims::NTuple{6, Int64}
Body::Array{Float64, 6}
1 ─ %1 = Main.reshape::Core.Const(reshape)
│   %2 = Core.tuple(data)::Tuple{Matrix{Float64}}
│   %3 = Core._apply_iterate(Base.iterate, %1, %2, dims)::Array{Float64, 6}
└──      return %3

julia> dims_vec = collect(dims)
6-element Vector{Int64}:
 2
 2
 2
 2
 2
 2

julia> @code_warntype reshape_test(data, dims_vec)
MethodInstance for reshape_test(::Matrix{Float64}, ::Vector{Int64})
  from reshape_test(data, dims) @ Main REPL[1]:1
Arguments
  #self#::Core.Const(reshape_test)
  data::Matrix{Float64}
  dims::Vector{Int64}
Body::Array{Float64}
1 ─ %1 = Main.reshape::Core.Const(reshape)
│   %2 = Core.tuple(data)::Tuple{Matrix{Float64}}
│   %3 = Core._apply_iterate(Base.iterate, %1, %2, dims)::Array{Float64}
└──      return %3

The vector case creates type-instbailities. The only way to fix it would be using either NTuple or SVector, right?

16

Yes, that may help. If data is a static array as well (which can be if it is small), then you can do these operations without instability and without allocations:

julia> data = rand(SMatrix{8,8,Float64});

julia> dims = SVector(2,2,2,2,2,2);

julia> @btime reshape_test($data, $dims);
  11.448 ns (0 allocations: 0 bytes)

Something worth considering if the size of data allows, and this is called many times.

1 Like
17

Thanks a lot, so I will try to implement it with SVector!