Vector of Vectors / Vector of Tuples

General Usage Performance
1

I am making a simulator and need to store data in pre-allocated storages. But, I am a bit confused and worried about the performance. I have two ways to create storage element.

First way:

storage = [
            (x1, y1, z1), 
            (x2, y2, z2), 
            (x3, y3, z3),
             ..........
            (xn, yn, zn)
          ]

Second way:

storage = [ 
            [x1, x2, x3, ... xn],
            [y1, y2, y3, ... yn],
            [z1, z2, z3, ... zn],
          ]

So, would love to get some advices about which one has more potential to be much faster.

Thank You.

2

Probably Tuples, as those might be stored inline, though that heavily depends on what you’re putting in those Tuples. You’ll want to check if isbitstype(eltype(storage)) is true. Mutable Vectors on the other hand must be allocated elsewhere (isbitstype will return false), and you lose out on some CPU optimizations the more you have to jump around in virtual memory. Depending on how you’re accessing the data, you could also benefit from splitting fields into separate arrays (look up Struct of Arrays vs Array of Structs, and there are a few Julia libraries to help with that but I’m not familiar).

4 Likes
3

This is the old structure of arrays problem. Package StrucArrays.jl is also another possibility where you store the array the second way and access each individual point in the first way.

1 Like
4

It sounds like people’s above suggestions for StructArrays.jl might serve you well. But in case you’re after an actual vector of vectors (rather than mere collections of values, where structs or tuples are more flexible) and those inner vectors are of small (<100 elements) and constant size, consider using SVector from StaticArrays.jl. SVector is just a NTuple wrapped to behave like a (immutable) vector. This means it’s just as fast as a NTuple or struct but you get all the linear algebra of an AbstractVector.

1 Like
5

I assume that each data point has size 3 and x, y, and z have the same types, otherwise there are more things to consider.

It also depends how you access your data. If you access x_i, y_i, and z_i always at the same time, then the first solution will be more performant, as the values can be fetched together from memory and will also be cached together.

Another solutions that have not been mentioned yet is to use a Matrix of dimension (3, n) or (n, 3). Julia uses column-major order, therefore the dimension (3, n) is similar to your first solution and (n, 3) is similar to your second solution.

And one option that should be mentioned for completeness - but is unlikely to fit your case - is using a DataFrame from DataFrames.j. A DataFrame is collection of columns therefore this would also resemble your second solution.

1 Like
6

My tip would be to write the code first, in the way that makes it cleanest and easiest to read and write. Then worry about the most efficient storage later.

1 Like
7

If these are (x,y,z) values representing a point in 3D, that you will be doing lots of 3-component vector calculations with, you should really consider an array of 3-component SVectors from StaticArrays.jl, since then not only will the storage be more efficient but also the 3-vector calculations will also be much quicker.

This just further illustrates @simonschoelly’s point that the best choice of datastructure depends on what you want to do with the data. You haven’t told us, so we are all just speculating.

3 Likes