I need to display an array of about 1000x1000. If you constantly refer to the elements of an array through [] [], it takes a long time. I want to do through pointers. It should also be faster. How better to make a run on such an array with the shortest time through pointers?

  • 2
    No, it should not be faster. Someone misinformed you. - VladD
  • one
    You can have sex, allocate memory in one piece, then generate an array of pointers, place them on this piece of memory and iterate as @aknew says about the static array. It turns out one dereference instead of two, and that's good. But is the game worth the candle? Once again, output in 90% of cases is slower than access. codepaste.net/oddae7 - free_ze
  • Otherwise, allocating a dynamic array, allocating lines separately, they will be stored separately. Those. First you need to find a pointer to the desired string (once dereferenced), then with offset we dereference and a pointer to a specific element (two). Indirect treatment is longer than immediate, because the less dereferencing the better. - free_ze
  • one
    @ Dexter384 In order to move from one line to another without a pointer to the beginning of a line, calculating only the offset from the element (0; 0), you need to know exactly where the next line begins. If you make new for each line, then you cannot know this, because the BOX controls the standard allocator! - free_ze
  • one
    @ Dexter384 Yes. I repeat once again: memory is allocated once for the entire matrix by a row (one-dimensional array or "buffer"). Line by line, i.e. after the extreme element of each line is the first element of the next. We also create an array of pointers to strings (so that it is convenient, as before, to walk arr [i] [j]), with a cycle we force them to point to the first element of each row. In summary: we can navigate quickly using the syntax arr [i + j] and as before, but longer - arr [i] [j]. - free_ze

3 answers 3

Do you think if the gain would be, the compiler would not have thought to optimize ptr [i] [j] as

*( *( prt + i ) + j )

?

And, with a high degree of probability, you will have output functions, not access, with bottleneck.

  • one
    only not ((a + i) + j), but ((a + i * length) + j), where length is the length of a single line. But in general, everything is correct - the compiler itself copes well with such optimizations, and the readability of the code will most likely fall - aknew
  • @aknew Do you think that the rows of a two-dimensional array necessarily follow each other? - free_ze
  • just so, memory is one-dimensional, so two-dimensional arrays by default are a bunch of one-dimensional ones written down one after another. I really do not remember the rows there or columns to be honest. By your own formula it is impossible to distinguish a [2] [5] from a [5] [2] - aknew
  • @aknew Did you notice dereference operators in my code? Backfill question: allocating memory dynamically, you create an array of pointers, then allocate a memory buffer for each of these pointers. Question: Will these buffers be located one after the other? Is there any difference in how these buffers are created? And finally, how will your code behave there? - free_ze
  • No, I missed the name, I repent. As for the second, we are talking about static, otherwise our phrases about the smart compiler lose their meaning. For dynamics, as I understand it, we have an array of pointers to the first elements of the array-lines (located not in order in the array, but in the order of allocation and strictly speaking not even in one memory area) and all this stuff is located on the heap ( static can be on the stack). Only then can we still say "what if there is a list instead of an array?" and then address arithmetic will generally smoke on the sidelines - aknew

And why are you sure that this will give a performance boost? After all, the announcement of the form

 #define WIDTH 1000 #define HEIGHT 1000 int a[WIDTH][HEIGHT];

almost the same (if you do not take into account the memory fragmentation and algorithms of the allocator) for this:

 int ** a = new int*[WIDTH]; for (int i = 0; i < WIDTH; i++) { a[i] = new int[HEIGHT]; }

Declaring arrays through pointers only makes sense if you do not know in advance (at the compilation stage) the size of the array and are forced to allocate memory dynamically. But what can really speed up the work with a two-dimensional array is declaring it as one-dimensional and accessing its elements through address arithmetic:

 int a[WIDTH * HEIGHT]; a[i * WIDTH + j];

This entry is similar to this:

 int a[WIDTH][HEIGHT]; a[i][j];
  • @ fori1ton, maybe it depends on the compiler, but for most, the access speed is what a [i * WIDTH + j]; what to a [i] [j]; will be the same. - But, this technique is extremely useful to remember for flexible work with matrices that are passed as a parameter to a function. - avp
  • one
    @avp, I think not. In the first case there will be two readings from memory, and in the second one. - dzhioev
  • one
    @zhioev, what is it like? If we assume that we are talking about local variables and WIDTH known at compile time, in both cases it will be necessary to extract only i and j from the memory (well, and machine instructions with coded constants ( WIDTH (when writing a[i][j] WIDTH is the size of the string, it is known to the compiler, but is clearly not present in the program text), sizeof(a[0][0]) and offset a[0][0] from fp (stack frame pointer)). both there and there are 3 hits (counting the sample a[i][j] ). - avp

Once there was such a binge, I’ll tell you a little about pointers that point to two-dimensional arrays in memory.

 int** mat = new int*[N];

Here the n-th number of pointers that follow each other will be highlighted (you can check it easily).

 ptrdiff_t diff = (mat + N) - mat;

Next, we allocate memory for these mat[n] = PTR pointers, because the memory manager is not required to allocate memory strictly one after the other because it does not contradict the very idea of ​​pointers (here, fragmentation as such does not matter). Take, for example, a discharged matrix in which each row is a simply connected list.

 node** mat = new node*[N]; m[0] - здесь связной список m[1] - здесь связной список m[n]...

And here is an example of how to walk alone with pointers on a dynamic two-dimensional array.

 #include <stdio.h> #define ROWS 10 #define COLS 20 int main(void) { int** mat = new int*[ROWS]; for(int j = 0; j < ROWS; ++j) mat[j] = new int[COLS]; int** ptr = (int**)mat; int** end = (int**)mat + ROWS; int* e; while(ptr != end) { e = (int*)*ptr + COLS; // конечный запредельный адрес текущего массива for(int* i = *ptr; i != e; ) *i++ = 0; ++ptr; // смещаемся к следующему массиву } for(int r = 0; r < ROWS; ++r) delete[] mat[r]; delete[] mat; return 0; }

Another thing is a static two-dimensional array: just here the matrix elements are located in memory one after another.

 #include <stdio.h> #define ROWS 10 #define COLS 20 int main(void) { int mat[ROWS][COLS]; int* ptr = (int*)mat; int* end = (int*)mat[ROWS]; while(ptr != end) *ptr++ = 0; return 0; }

Dexter384, so in your question there will be no savings on matches. In asm, for convenience, there is also an indexing of arrays, only the array index is multiplied by the size of the type, that is, it is convenient that once again the register does not move back and forth. In C / C ++, the compiler does this work for us, that is, it multiplies by the size of the type, if access to the array is by index, and if through a pointer it is an offset by n-bytes (that is, by the size of the type).

 #include <stdio.h> //asm(INTEL) x86 32-bits int main(void) { int _arr[4]; __asm { mov edx, 100 mov ebx, 200 lea esi, _arr // записываем в третий элемент массива по-индексу mov [esi+2*4], ebx // смещаемся ко второму элементу ++ptr add esi, 4 mov [esi], edx }; printf("%d\n%d\n", _arr[1], _arr[2]); return 0; }

And the last - in order to once again the heap is not fragmented, it is better to use

 int* mat = new int[ROWS*COLS];