Array of tuples vs array of arrays

Users
1

I am writing a PDE solver which has several unknowns at each grid point. I could create my array in two ways

param nc = 4;
const nx = 100, ny = 100;
const D = {1..nx,1..ny};
var u : [D] nc*real;       // array of tuples
var v : [D] [0..<nc] real; // array of arrays

It looks like tuples of the form nc*real also obey rules of vector algebra. So I could either one for my problem.

Is there a reason to prefer one over the other ? I know tuple indexing starts at 0 but I can choose my own indexing for the array. Are there any major differences, performance, etc., between the two ?

2

I'll list some differences off-top-of-my-head:

  • Tuple sizes have to be compile-time constant (param), array sizes don't have to be, and as such they could be resized.
  • You can't get too fancy with tuples. e.g. no slicing tuples
  • You can't distribute tuples if that even matters to you in this case.
  • Tuple memory is "inlined" thanks to the compile-time size. Whereas arrays are always dynamically allocated no matter how small they are.
    • So, if you have an array of 100 4-real-tuples, you'll get a 10048 = 3200 bytes of memory where tuples are stashed one after another in memory vs array of 100 4-element arrays will have 100 pointers pointing to potentially scattered locations in memory.
    • The former is better for performance, the latter is better for larger allocations.
  • Using tuples might increase compilation times. Every tuple type will cause the compiler to do more work. Note that 4*real and 5*real are different types, for example. Whereas differently-sized arrays will not impact compilation times directly.
  • Furthermore, the size of tuples will also matter. 64*real will be more work for the compiler compared to 4*real, for example.

In your very specific example, I would go with tuple myself. nc is small enough and it is a param, causing me to believe that tuples will be better for you. What is "small enough", I don't have a great answer. I guess I would start to get worried beyond 8 reals (64 bytes). But what the exact line between tuples and arrays is more of an art then precise science, to me.

Hope this helps.

1 Like
3

As a general rule, I would use multi-dimensional arrays based on tests I did years ago.

Engin, I suggest changing “every” → “even”.

4

Thanks for the explanation on this. I will do some tests with both and see what works better for my case.

5

Engin, I suggest changing “every” → “even”.

Good catch. Fixed!

As a general rule, I would use multi-dimensional arrays based on tests I did years ago.

This is also a good point. If you are thinking of using array-of-arrays where all the inner arrays are of same size, multidimensional arrays will certainly perform better than array of arrays. Semantically they will be different of course and may be slightly less intuitive than array-of-arrays depending on your use case. But nonetheless, they should do the job quickly. Thanks @damianmoz for pointing that out.

6

You mean array of the form

const D = {1..nx, 1..ny, 1..nc};
var u : [D] real;

When I am at a grid point (i,j) I need access to all nc components of u[i,j,..]. How would I do parallel for on (i,j) and still access the nc components at that grid point ?

7

Are you trying to do parallel access on the 3rd dimension? It has only 4 elements, though?

forall k in D.dim(2) do
  ... u[i,j,k] ...

is a way to do that if that's what you want.

A more typical

forall (i,j,k) in D do

would chunk up on the first dimension for a non-distributed D.

8

I need parallel access only on first two indices. My loops will look like

const D = {1..nx, 1..ny, 1..nc};
var u : [D] real;

forall (i,j) in D
{
// do something with u[i,j,..]
}

This doesnt make sense, D has rank 3.

9

Oh, that makes more sense than what I thought the question was :slight_smile:

Yeah, I understand better now. And this is the part where using multidimensional arrays instead of array of tuples might look less intuitive. But still doable. Probably I would write it as:

const LogicalDomain = {1..nx, 1..ny};
// use tuple expansion on LogicalDomains dimensions to get the first 2 dimensions:
const DataDomain = {(...LogicalDomain.dims()), 1..nc};
var u: [DataDomain] real;

forall (i,j) in LogicalDomain {

}
10

I still think for 4-elements, array of tuples is the way to go. Just to be clear.

11

You really need to look at all the operations that will be needed across all parts of the program.

12

Also, if you are accessing

x[i, j, ...]

you might have an excessive slicing overhead