Databases
StackOverflow2013
Postsdbo
POC/C++ performance of static arrays vs dynamic arrays
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POC/C++ performance of static arrays vs dynamic arrays
    primarykey
    data
    text
    <p>When performance is essential to an application, should consideration be given whether to declare an array on the stack vs the heap? Allow me to outline why this question has come to mind.</p> <p>Since arrays in C/C++ are not objects and decay to pointers, the compiler uses the provided index to perform pointer arithmetic to access elements. My understanding is that this procedure <strong>differs</strong> from a statically declared array to a dynamically declared array when going past the first dimension.</p> <p>If I were to declare an array on the stack as follows;</p> <pre><code> int array[2][3] = { 0, 1, 2, 3, 4, 5 } //In memory { row1 } { row2 } </code></pre> <p>This array would be stored in <strong>Row Major</strong> format in memory since it is stored in a contiguous block of memory. This means when I try to access an element in the array, the compiler must perform some addition and multiplication in order to ascertain the correct location.</p> <p>So if I were to do the following</p> <pre><code> int x = array[1][2]; // x = 5 </code></pre> <p>The compiler would then use this formula where: </p> <p>i = row index j = column index n = size of a single row (here n = 2)<br> array = pointer to first element</p> <pre><code> *(array + (i*n) + j) *(array + (1*2) + 2) </code></pre> <p>This means if I were to loop over this array to access each of its elements, an additional multiplication step is performed for each access by index.</p> <p>Now, in an array declared on the heap, the paradigm is different and requires a multi stage solution. Note: I could also use the C++ new operator here, but I believe there is no difference in how the data is represented.</p> <pre><code> int ** array; int rowSize = 2; // Create a 2 by 3 2d array on the heap array = malloc(2 * sizeof(int*)); for (int i = 0; i &lt; 2; i++) { array[i] = malloc(3 * sizeof(int)); } // Populating the array int number = 0; for (int i = 0; i &lt; 2; i++) { for (int j = 0l j &lt; 3; j++) { array[i][j] = number++; } } </code></pre> <p>Since the array is now dynamic, its representation is a one dimensional array of one dimensional arrays. I will try to draw an ascii picture...</p> <pre><code> int * int int int int ** array-&gt; [0] 0 1 2 [1] 3 4 5 </code></pre> <p>This would imply that multiplication is no longer involved right? If I were to do the following</p> <pre><code>int x = array[1][1]; </code></pre> <p>This would then perform indirection/pointer arithmetic on array[1] to access a pointer to the second row and then perform this once again to access the second element. Am I correct in saying this?</p> <p>Now that there is some context, back to the question. If I am writing code for an application that requires crisp performance, like a game which has around 0.016 seconds to render a frame, should I think twice about using an array on the stack vs the heap? Now I realize there is a one time cost for using malloc or the new operator, but at a certain point (just like Big O analysis) when the data set becomes large, would one be better off iterating through a dynamic array to avoid row major indexing?</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USPaul Renton
    1. USPaul Renton
    plurals
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POC/C++ performance of static arrays vs dynamic arrays
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POC/C++ performance of static arrays vs dynamic arrays
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POC/C++ performance of static arrays vs dynamic arrays
      1. USPaul Renton
      1. VTFavorite
    1. COYou could use [continue memory allocation for 2D](http://stackoverflow.com/a/15062765/1673391) for comparison
      singulars
      1. POC/C++ performance of static arrays vs dynamic arrays
      1. USGrijesh Chauhan
    2. COWhatever you do, you're still doing row major (rather than column major). Try measuring it.
      singulars
      1. POC/C++ performance of static arrays vs dynamic arrays
      1. USdoctorlove
    3. COStack vs. heap is a matter of how large the allocation is and when you know how large it is, not a matter of data layout. As Grijesh Chauhan already said, you can use the same layout as multi-dimensional static array on the heap, you just don't get syntactic sugar for it. You can also have a static array of pointers to arrays (and it sometimes makes sense, though the pointed-too arrays will often be allocated dynamically).
      singulars
      1. POC/C++ performance of static arrays vs dynamic arrays
      1. This table or related slice is empty.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload