3

Hello I'm in an intermediary C class right now and this thought just came to my mind:

int multi[3][4]; // const multidimensional array

int* ptr = *multi; // ptr is a pointer variable that hold the address of multi const array

So, what is faster/smaller/optimized for access a multidimensional array position?

This:

multi[3][1]; // index the value position

or

*(*(multi+2)+1); // pointer to the position on the array

or (UPDATED)

ptr += 9; // pointer arithmetic using auxiliary pointer

Since "multi" is an const array the compiler should "know" already the localization of the element position, in case of using an variable pointer pointing to that array that could take more processing time, on the other hand could be faster when searching for the item that I want to display. What is the faster/smaller/optimized approach?

Thank you in advance.

Improve this question
6
  • 4
    You should be caring more about the readability of the code. Most people don't realize that you can't answer "nano" performance comparisons about C. You can answer such questions, but you have to specify an implementation(or a set of implementations). Commented Jan 25, 2011 at 18:38
  • 2
    Make it readable. Even if there were performance gains to be had -- and I doubt there are -- go with the readable version. "Premature optimization is the root of all evil." -Knuth Commented Jan 25, 2011 at 18:45
  • C is already a tough language to work with. Why would you want to make it harder? Commented Jan 25, 2011 at 19:10
  • Well someone should say that to my professor. His words: 1.*(ptr+1) is cheating; 2. you should never user arr[row][col]; etc Commented Jan 25, 2011 at 21:36
  • 1
    @Maris Melo: sigh. This is yet another argument against using C as a teaching language; the amount of folklore, misinformation, and plain bad practice that has been institutionalized is staggering. The reason so many students have problems with C is because it's usually taught badly. Tell your professor to code up and profile the different versions; he may be amazed at the results. Commented Jan 26, 2011 at 21:11

5 Answers 5

Reset to default
8

They're all compiled in the same way, *(pointer_to_first_element + x + y).

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

See my answer below. Using regular subscript operators resulted in the fewest instructions (for that code and compiler settings).
@john: I guess 5 of my 7 upvotes should be for you.. ;) I did a similar work for single-dimensional arrays and the asm generated was the same, so I supposed the asm would be the same for bi-dimensional array too.
6

Firstly

int multi[3][4];

is not a const array. There is nothing const in this declaration.

Secondly, 

int* ptr = *multi;

will make ptr point to the element multi[0][0]. Numerically it is the same as the address of multi[0] and the address of the entire multi, but the types are different.

Thirdly, 

multi[3][1];

is by definition the same as 

*(*(multi + 3) + 1);

so there can be no justified difference in performance. How it is connected to what was said above is not clear.

Fourthly, 

*ptr + 9;

has no "pointer arithmetic" in it whatsoever. It is equivalent to 

multi[0][0] + 9;

which is an ordinary integral addition. Again, how it is connected to what was said above is not clear.

Finally, your question is titled as "Constant pointer array or pointer to an array", while in the actual text of the question I see neither.

Improve this answer

11 Comments

Regarding *ptr + 9, it is worth mentioning it contains no pointer arithmetic because unary * operator has higher priority than binary +. Had the code been *ptr++ it would have contained pointer arithmetic. ++ has equal priority as *, but in this case, the operators are evaluated right-to-left. These rules are by no means simple to keep track of, and this is why you shouldn't rely on operator precedence but use parenthesis, whenever mixing multiple operators on one line.
@Lundin: I don't know why you overcomplicate the "priority" issue so much. In C/C++ unary operators always have higher priority than binary operators, and postfix operators always have higher priority thna prefix ones. What's the point of assigning equal priority for unary * and postfix ++?
It is the standard which overcomplicates it. Actually I wasn't correct, postfix++ has higher priority than *, I confused the postfix priority with the prefix one. My point is, these operator presedence rules are a pain to keep track of, so use parenthesis! Don't rely on them nor assume that programmers know them or remember them.
@Lundin: The standard does not have any operator precedence rules. The standard has the grammar that defines the grouping of operators and operands. And in this specific case it is very simple, again: unary operators have higher priority than binary operators, and postfix operators have higher priority than prefix ones.
@Andrey You are correct about the grouping, although they are part of the operator precedence rules. See ISO 9899:1999 6.5 $3 "The grouping of operators and operands is indicated by the syntax. 74)", Note 74: "The syntax specifies the precedence of operators in the evaluation of an expression, which is the same as the order of the major subclauses of this subclause, highest precedence first."
|
4

It doesn't matter how fast your code is if it gets tossed because nobody else can understand and maintain it; also, tricky code can sometimes prevent your compiler from making a better optimization.

For example: 

int main(void)
{
  int arr[3][4] = {{0,1,2,3},{4,5,6,7},{8,9,10,11}};
  int *p = *arr; // == arr[0] == &arr[0][0]

  int x;

  x = arr[2][3];         // Straightforward array access
  x = *(*(arr+2)+3);     // Ugly pointer arithmetic
  x = *(ptr + 11);       // Slightly less ugly pointer arithmetic

  return 0;
}

I ran the above through gcc -c -g -Wa,-a,-ad > foo.lst to get the generated assembly and source code interleaved.

Here's the translation for x = arr[2][3];: 

movl      -16(%ebp), %eax     
movl      %eax, -8(%ebp)

Here's the translation for x = *(*(arr+2)+3);:

leal      -60(%ebp), %eax
addl      $44, %eax
movl      (%eax), %eax
movl      %eax, -8(%ebp)

And finally, the translation for x = *(ptr + 11);:

movl      -12(%ebp), %eax
addl      $44, %eax
movl      (%eax), %eax
movl      %eax, -8(%ebp)

Don't try to outsmart your compiler. This isn't the 1970s anymore. gcc knows how to do array accesses efficiently without you having to tell it.

You shouldn't even be thinking about performance at this level unless you've tuned your algorithm and data structures, used the highest optimization settings on your compiler (FWIW, -O1 generates the same code for all three versions), and you're still failing to meet a hard performance requirement (in which case, the right answer is usually to buy faster hardware). And you shouldn't change anything without first running your code through a profiler to find the real bottlenecks. Measure, don't guess.

EDIT

Naturally, when the literals 2 and 3 are replaced by variables, the situation changes. In that case, the *(ptr + offset); comes out looking the best. But not by much. And I'll still argue that clarity matters more at this level.

Improve this answer

Comments

2

a[i] means *(a+i), in fact you can also write i[a] and your compiler will accept it.

*(ptr+i) anyway could be slightly faster than ptr[j][k] in theory, since you're doing a single addition (while ptr[j][k] could require 2).

Improve this answer

1 Comment

a[i] means *(a+i) not (a+i)
1

I'm not sure where the const arrays came from, but for the discussion, lets assume there were some in the original post.

As the original poster didn't explicitly mention PC programming, const arrays and regular arrays are not necessarily compiled in the same way.

In embedded systems, const arrays may be slower than non-const ones, if the const arrays are allocated in true non-volatile memory, ie an embedded application with real ROM. The slowness is related to access times of the ROM, and highly hardware-specific.

Regarding pointer arithmetic, that is the only way to access arrays. The array syntax in the C language is what the compiler people call "syntactic sugar", i.e it is just there for looks. An array access like

arr[i]

is translated by the compiler to

*(arr+i)

and they are equivalent in performance and function.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.