Nested List Structure

Help
1

A super newbie question here, but first a little background:
I am working with the BLAS library, which often needs c-pointers to arrays. I’ve found that the following works for example

array := [4]f64{0,1,2,3}
// calling blas function that sums up array
cblas_dasum(c.int(4), raw_data(array[:]), c.int(1)) // len(array), multi-ptr to array, stride through array

but interestingly (because it might make more complicated matrix multiplications easier) I have also found that

array := [2][2]f64{[2]f64{0,1},[2]f64{2,3}}
cblas_dasum(c.int(4), raw_data(raw_data(array[:])), c.int(1))

works and gives the same answer. This makes it seem like nested arrays are stored contiguously, so

  1. Is this true in general, or is it a product of the default memory allocator (okay you caught me I still don’t really understand how memory allocation works in odin)?
  2. Are the nested raw data calls returning 1 single pointer to a contiguous block of memory or is it someother mess of pointers?
  3. If it is true in general, in what order are the numbers stored (in the second example {0,1,2,3} or {0,2,1,3})?
  4. Is this deeply sinful and I should reform my ways by flattening arrays before-hand, or I can I get away without reformatting nested arrays for my scientific compute needs?

Related to this question about C I think

2

Fixed arrays are stored contiguously in memory. [4]f64, for instance, is just 4 f64s stored contiguously in memory, in the indexed order (0, 1, 2, 3). There’s no “real” allocation or pointer indirection going on here–[4]f64 is 4 f64s stored wherever the type is declared. For a local variable, this space will be on the stack; for a struct field, the array’s data will be inlined into the struct.

This all applies when the fixed array contains fixed arrays too. array: [2][2]f64 is 2 arrays of 2 f64s, all stored contiguously in memory. So the overall order in memory is array[0][0], array[0][1], array[1][0], array[1][1]. The inner arrays still have their data contiguous too! So when you do:

array := [2][2]f64{ {0, 1}, {2, 3} }

They are in exactly that order in memory: 0, 1, 2, 3.

Now, raw_data just returns a pointer to the underlying data–it doesn’t allocate anything new or otherwise copy it. Likewise witharray[:]; a slice is just a pointer to some underlying data, plus the number of values there. Using raw_data on a slice just returns the underlying pointer, exactly as-is.

You can use raw_data on a fixed array too, but it needs to be a pointer to a fixed array. This is why raw_data(raw_data(array[:])) works (and raw_data(raw_data(&array)) would too); the first/inner call returns [^][2]f64–a pointer to some number of [2]f64 in memory. This will point to the first sub-array. The second/outer call will do the same, returning the [^]f64–a pointer to some number of f64. This will point to the first value in the first sub-array–which is the first value in memory. What you end up with is effectively &array[0][0].

As far as whether you should do this or not, there’s nothing inherently wrong with it. However, for small-sized matrices, consider using a built-in matrix (e.g. matrix[2,2]f64) instead. Though, there are some things to note here:

  • Odin’s built-in matrices do support some of the operations you might expect (e.g. multiplication). There are also a number of matrix operations available in core:math/linalg).
  • The built-in matrices have a fairly small maximum size; they can only be up to 16 elements total (4x4, 8x2, etc.).
  • Built-in matrices are stored in column-major order by-default. That means that, say, a 3x3 matrix would be stored like in memory:
0  3  6 -> 0 1 2 3 4 5 6 7 8
1  4  7
2  5  8

You can change this by declaring the type as #row_major matrix[2,2]f64 instead. This doesn’t change much about how they’re used–only how they’re stored internally. If you do access a vector, however, your indexing will change (i.e. m[0] is the first column for a column-major matrix, but the first row for a row-major matrix).

  • Additionally, matrices are intended to be indexed via m[row,column], regardless of storage order (column-major or row-major).

Note that all of the above only really covers fixed-size arrays/matrices. If you need dynamically-sized matrices, then things get more complicated.

2 Likes