The fastest way to move simple data types in an array to specific positions

Question

What is the fastest way to move simple data types in an array of known size to specific positions?

The specific case that I had was a rotation of the playing field stored as int [9]
[0,1,2,3,4,5,6,7,8] becomes [6,3,0,7,4,1,8,5,2]

---

In my use case, I had a vector of these arrays, each of which needed rotation.

Board Layout:

 board1|corners|centers 0 1 2 | 0 2 | 1 3 4 5 | | 3 5 6 7 8 | 6 8 | 7 board2|corners|centers 6 3 0 | 6 0 | 3 7 4 1 | | 7 1 8 5 2 | 8 2 | 5 

The fastest method I came across was to create a public variable for assigning array entries and then copy the memory back.

 int layout[9]; int pub_layout[9]; #include <cstring> // for std::memcpy void rotate(int layout[]) { pub_layout[4] = layout[4]; // center pub_layout[0] = layout[6]; // corner four pub_layout[6] = layout[8]; pub_layout[8] = layout[2]; pub_layout[2] = layout[0]; pub_layout[1] = layout[3]; // center four pub_layout[3] = layout[7]; pub_layout[7] = layout[5]; pub_layout[5] = layout[1]; std::memcpy(layout,pub_layout,sizeof(pub_layout)); } 

I saw a similar question here that recommends int[] b = new int[] {b[6], b[3], b[0], b[7], b[4], b[1], b[8], b[5], b[2]};
(although it works much slower (less than half the speed on a single thread)

---

Both are relatively fast ( see test here )

If this is not the fastest way, what is it? I suspect that the algorithm will be the same in both C and C ++.

Answer 1

With this, you will receive a memcpy call and assignment [4] - [4]. You lose two assignments to putAside . So this, of course, is a little faster.

 int layout[9]; int putAside; void rotate(int[] layout) { putAside = layout[0]; layout[0] = layout[6]; // corner four layout[6] = layout[8]; layout[8] = layout[2]; layout[2] = putAside; putAside = layout[1]; layout[1] = layout[3]; // center four layout[3] = layout[7]; layout[7] = layout[5]; layout[5] = putAside; } 

Answer 2

The fastest way is to use the processor cache in a very narrow loop:

 void rotate(int in[3][3], int out[3][3]) { int i, j, k; for (i=0,k=2;i<3;i++,k--) for (j=0;j<3;j++) out[j][k] = in[i][j]; } 

Note: board[9] equivalent to board[3][3] and treats 9 int as 3 sequences of 3 integer sequences in memory, so if you like:

 void rotate(int in[9], int out[9]) { int i, j, k; for (i=0,k=2;i<3;i++,k--) for (j=0;j<3;j++) out[j*3+k] = in[i*3+j]; } 

If you want in and out to be the same, you should use the following:

 void rotate(int in[9], int out[9]) { int tmp[9]; int i, j, k; for (i=0,k=2;i<3;i++,k--) for (j=0;j<3;j++) tmp[j*3+k] = in[i*3+j]; //memcpy(out,tmp, sizeof(tmp)); // use this... for(i=0;i<9;i++) out[i]=tmp[i]; //..or this, whichever clocks faster } 

Answer 3

If you want a more flexible way to apply some kind of transformation, something like the following will also be pretty fast:

 template <int _1, int _2, int _3, int _4, int _5, int _6, int _7, int _8, int _9> struct transfomer { board& _in; operator board() const { return { _in[_1], _in[_2], _in[_3], _in[_4], _in[_5], _in[_6], _in[_7], _in[_8], _in[_9] }; } }; void rotate3(board& layout) { layout = transfomer<6, 3, 0, 7, 4, 1, 8, 5, 2>{layout}; } 

Here I defined board as:

 typedef array<int, 9> board; 

And yes, it relies on an implicit conversion operator (usually it's an evil IMO, but it is useful here.) (NOTE: I adapted your test a bit to work with array<> and performed the same tests that the above code is about the same, if not slightly better on average than the manual solution from @Joel)