2
$\begingroup$

In my programming concept class we learned that for the array type it's faster to index in memory if the length of an element is = $2^n$. This case make us only need to offset instead of actually doing multiplication.

We also learned about the representation of multivariable arrays with row major. It was then said that the array[1...3, 1...2] is faster to index compared to array[1...2, 1...3] because we have the length of an element being = $2^n$. I don't understand why you can determine this?

$\endgroup$
  • $\begingroup$ First, I am not really sure about the notation you used for array [1...3, 1...2]. I guess a 2-dimensional array with 3 rows and 2 columns indexed by positive integer? Not all programming languages declare arrays this way. $\endgroup$ – Apiwat Chantawibul Oct 10 '19 at 3:44
  • $\begingroup$ Second, the class most likely teaching you about efficiently issues specific to some programming languages, model of computation, hardware architecture or any combination of such situations. For example, the mention of $2^n$ is most likely due to hardware architecture having memory indexing represented in base 2. Another hardware architecture which represent memory index in base 3 which could theoretically exist would have entirely different consideration. And so you need to mention your speciifc setting for this question to be objectively answerable. $\endgroup$ – Apiwat Chantawibul Oct 10 '19 at 3:51
  • $\begingroup$ Your instructor has never learned about cache lines and collisions. Having data stored at a distance that is a power of two can absolutely kill performance. $\endgroup$ – gnasher729 Oct 10 '19 at 15:47
4
$\begingroup$

Two-dimensional arrays are stored as one-dimensional arrays. Your first array is stored as $$ A[1,1], A[1,2], A[2,1], A[2,2], A[3,1], A[3,2], $$ so the offset of $A[x,y]$ is $2x+y-3$. In contrast, the third array is stored as $$ A[1,1], A[1,2], A[1,3], A[2,1], A[2,2], A[2,3], $$ so the offset of $A[x,y]$ is $3x+y-4$. Multiplying by 2 could be faster than multiplying by 3 – for example there might be a suitable addressing mode in your instruction set.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.