Accessing elements of a double std::array

Question

My question is about efficiency of accessing elements of a double std::array. Since the std::array is a static-sized container, I expect its data to be stored in a continuous block of memory and accessing the elements of the std::array to be same as C-style arrays. The use of std::array should not add any additional overhead.

Is accessing elements of double arrays std::array<std::array<T,N>,M> optimised?

For example I have to source code below.

#include <array>
#include <random>

int main(){
  std::array<std::array<int,4>,2> a;

  for(int j=0;j<4;j++)
    a[0][j] = rand();

  for(int j=0;j<4;j++)
    a[1][j] = rand();

  int r = a[0][1] + a[1][3];
  return r;
}

Does a uses a single block of memory?
Is accessing an element with constant indices (ie a[1][3]) a single or a double shift in memory?
How many shifts is needed in accessing the element in a loop (ie a[1][j])

I used godbolt.org in the above example to check the assembly code and it seems that gcc -O4does a pretty good job.

For example access to a[1][3] and a[0][1] is compiled as :

    mov     eax, DWORD PTR [rsp+28]
    add     eax, DWORD PTR [rsp+4]

However can I use this finding in a more complex example? Or should I stick to simple std::arrays to control access efficiency?

Is there any ISO standards description in the double std::array?

What do you mean by "shift in memory"? Are you sure you're not doing premature optimization which is generally bad? Have you *measured* (or profiled or benchmarked) that this is a bottleneck in your program? Concentrate on making well-written, readable, understandable, maintainable and *working* code first of all. *Then* if the "performance" is not up to the existing requirements you measure and profile to find the hot-spots and bottlenecks, and concentrate your optimization efforts on those where it will matter, with plenty of documentation and comments about what you're doing. — Some programmer dude, Jun 15 '17 at 09:58
Use `std::vector` unless you need an `std::array` for some well defined purpose. And measure before thinking about optimisation. Looking at code generated for modern CPUs that have branch prediction, out of order execution, speculative execution ... etc is almost meaningless unless you already have very specialised knowledge. — Richard Critten, Jun 15 '17 at 10:00
There is no `-O4`. But the `std::array`s are one contiguous block. — Galik, Jun 15 '17 at 10:09
@Someprogrammerdude with the term "shift in memory" I tried to summarise the double lookup we do for example in `std::vector>`. My question is not about optimising my source. It is about `std::array` definition and description. — ztik, Jun 15 '17 at 10:11
`std::array`'s store their data inside themselves. So it's all in one contiguous block of memory but the internal array elements may not be contiguous between `std::array` instances. — Galik, Jun 15 '17 at 10:14
An `std::array` object is a very thin wrapper around plain C-style arrays, and as such store their memory in a contiguous block. If the contents of an `std::array` is another `std::array` then it work just like a C-style array of C-style arrays (e.g. `int a[2][4]`), and all memory is stored as a contiguous block of contiguous blocks. I.e. it's all contiguous. — Some programmer dude, Jun 15 '17 at 10:16
related/dupe: https://stackoverflow.com/questions/30263303/stdarray-vs-array-performance — NathanOliver, Jun 15 '17 at 11:41
@Galik there is an `-O4`. There's even an `-O999999999`. These all (**currently**) just map to `-O3`. — rubenvb, Jun 15 '17 at 12:27
Thanks @NathanOliver, it is quite related. Then perhaps I should ask how C optimises use of 2d arrays... — ztik, Jun 15 '17 at 13:23

Curious · Answer 1 · 2017-06-15T10:23:02.613

Yes it is in a contiguous block of memory
There is no shifting involved, there will be no shifting involved (other than the simple one possibly used to index into a one dimensional array if at all) in optimized or even non-optimized code for that matter. std::array differs from regular C style arrays in that it is not up to the compiler to determine how the array will be laid out in memory (i.e. whether the rows will be first or the columns, most compilers lay it out in row order but that is not important), how indexing will be resolved (whether any multiplicational "shifts" will be involved), etc. It is a simple one dimensional array where each element is of a given type (in your case, each element is an array itself). The following example should demonstrate what I am saying.
No shifts, see above and below

#include <iostream>

using std::cout;
using std::endl;

template <int size>
using int_arr = int[5];

int main() {
    // an array of 5 arrays, unlike int arr[5][5]; 
    int_arr<5> arr[5];

    // first operator[] will resolve to the first array, return a 
    // reference to it and then the second will resolve to the correct
    // integer.  Similar to ((arr[0])[0])
    arr[0][0] = 12;
    cout << arr[0][0] << endl;

    return 0;
}

Thanks. In my example accessing `a[1][3]` compiler converts is as `mov eax, DWORD PTR [rsp+28]`, which is not similar to what you describe in 2 — ztik, Jun 15 '17 at 10:24
@ztik thats the compiler optimizing your access from `[rsp+16]` (to get an array one from the starting location and then `[rsp + 12]` to get the 3rd integer in the 2nd level array to one instruction. It is still conceptually the same as what I described in 2 — Curious, Jun 15 '17 at 10:27

Accessing elements of a double std::array

1 Answers1