9 replies to this topic

[DarkLordoftheMonkeys]

I've been reading The C Programming Language, the original book by Brian Kernighan and Dennis Ritchie, and right now I'm at the part where it's listing the uses for pointers.

I have two functions here that I've written and tested. Both do exactly the same thing - calculate the length of a string - but they use two different methods:

Accessing through indexes:

int strlength( char arr[] ){

	int length = 0;

	for( int i = 0;; i++ ){

		if( arr[i] > 0 ){

		// if not the end of the string

			length++;

		}

		else{

			break;

		}

	}

	return length;

}

Accessing through pointers:

int strlength( char arr[] ){

	int length = 0;

	char *arrptr;

	arrptr = &arr[0];

	for( int i = 0;; i++ ){

		if( *(arrptr + i) > 0 ){

			length++;

		}

		else{

			break;

		}

	}

	return length;

}

Apparently, the second version of the function will be faster because it uses pointers to access the array elements rather than accessing them through their indexes. I can understand why this would be, as pointers are closer to the hardware and there is no need for the program to calculate the address based on the index.

Do you think this is an accurate assessment?

[dcs]

DarkLordoftheMonkeys said:

Apparently, the second version of the function will be faster because it uses pointers to access the array elements rather than accessing them through their indexes. I can understand why this would be, as pointers are closer to the hardware and there is no need for the program to calculate the address based on the index.

Do you think this is an accurate assessment?

No. The code is equivalent. Compiler optimization would probably result in the same output generated for both.

[SolidState]

I thought that it would be faster because of not duplicating the value since the pointer is referencing the data from that particular memory address. Or is that only with objects that are passed into functions that make function local copies through the copy constructor that benefit from the use of pointers in this way?

[Guest]

They are the same speed, because accessing an array index just adds i to the array, just as you would through a pointer. This code would be faster though:

int strlength(char *arr){
	char *arrptr=arr;
	while(*arrptr!=0) arrptr++;
	return arrptr-arr;
}

Instead of adding to i each time and calculating i+arrptr, you just add to arrptr. Also, you don't need a length variable if you can just subtract the resulting pointer from the original.
Heres another tip:

&array[0]==array

Of course these little optimizations aren't a huge deal, because computers are fast today, and compilers are pretty good at optimization.

[John]

With GCC you can always compile your code with the -S flag. This will output your code in assembly language. I *think* by analyzing that, you will be able to see which _is_ more efficient.

[Guest]

Doing what John said, I have created some assembly code.
This is the first solution with the arrays, it is 26 lines of code.

	.file	"test.c"

	.text

.globl strlength

	.type	strlength, @function

strlength:

	pushl	%ebp

	movl	%esp, %ebp

	subl	$16, %esp

	movl	$0, -4(%ebp)

	movl	$0, -8(%ebp)

.L3:

	movl	-8(%ebp), %eax

	addl	8(%ebp), %eax

	movzbl	(%eax), %eax

	testb	%al, %al

	jle	.L2

	addl	$1, -4(%ebp)

	addl	$1, -8(%ebp)

	jmp	.L3

.L2:

	movl	-4(%ebp), %eax

	leave

	ret

	.size	strlength, .-strlength

	.ident	"GCC: (Ubuntu 4.4.1-4ubuntu8) 4.4.1"

	.section	.note.GNU-stack,"",@progbits

This is the second solution with pointers, it is 28 lines of code.

	.file	"test.c"

	.text

.globl strlength

	.type	strlength, @function

strlength:

	pushl	%ebp

	movl	%esp, %ebp

	subl	$16, %esp

	movl	$0, -4(%ebp)

	movl	8(%ebp), %eax

	movl	%eax, -8(%ebp)

	movl	$0, -12(%ebp)

.L3:

	movl	-12(%ebp), %eax

	addl	-8(%ebp), %eax

	movzbl	(%eax), %eax

	testb	%al, %al

	jle	.L2

	addl	$1, -4(%ebp)

	addl	$1, -12(%ebp)

	jmp	.L3

.L2:

	movl	-4(%ebp), %eax

	leave

	ret

	.size	strlength, .-strlength

	.ident	"GCC: (Ubuntu 4.4.1-4ubuntu8) 4.4.1"

	.section	.note.GNU-stack,"",@progbits

And finally, my solution, which is 28 lines of code.

	.file	"test.c"

	.text

.globl strlength

	.type	strlength, @function

strlength:

	pushl	%ebp

	movl	%esp, %ebp

	subl	$16, %esp

	movl	8(%ebp), %eax

	movl	%eax, -4(%ebp)

	jmp	.L2

.L3:

	addl	$1, -4(%ebp)

.L2:

	movl	-4(%ebp), %eax

	movzbl	(%eax), %eax

	testb	%al, %al

	jne	.L3

	movl	-4(%ebp), %edx

	movl	8(%ebp), %eax

	movl	%edx, %ecx

	subl	%eax, %ecx

	movl	%ecx, %eax

	leave

	ret

	.size	strlength, .-strlength

	.ident	"GCC: (Ubuntu 4.4.1-4ubuntu8) 4.4.1"

	.section	.note.GNU-stack,"",@progbits

So the Assembly output would seem to indicate that arrays are the most efficient, which is just strange. My solution's assembly output was longer, although I completely omitted two extra variables and extra addition. :blink:

[John]

The number of lines doesn't necessary mean it is more quicker. You have to account for the loops (which I'm too lazy to do) and I believe memory access takes longer than mov/add/sub ect...

[Guest]

That's why I said the output would seem to indicate arrays are more efficient. I don't know assembly though, so I can't properly analyze it.

[dcs]

First, I wouldn't take any implementation's output as an answer to "which is more efficient" anyways. And I certainly wouldn't be looking to micro-optimize early on ("premature optimization is the root of all evil").

Second, I'd at least turn on optimizations before attempting to compare to hand-coded assembly. But I'd generally avoid the hand-coded assembly because of item #1.

And regarding this:

Quote

I thought that it would be faster because of not duplicating the value since the pointer is referencing the data from that particular memory address. Or is that only with objects that are passed into functions that make function local copies through the copy constructor that benefit from the use of pointers in this way?

The constructs A and *(A + i) are [I]equivalent. Whether you write one version or the other, the compiler might see the same, which might be either.

But when you actually have two different things: an array in scope or a pointer to that array, the pointer must go through an extra level of indirection that direct array access would not.

Question 6.2

Quote

It is useful to realize that a reference like x[3] generates different code depending on whether x is an array or a pointer. Given the declarations above, when the compiler sees the expression a[3], it emits code to start at the location ``a'', move three past it, and fetch the character there. When it sees the expression p[3], it emits code to start at the location ``p'', fetch the pointer value there, add three to the pointer, and finally fetch the character pointed to. In other words, a[3] is three places past (the start of) the object named a, while p[3] is three places past the object pointed to by p. In the example above, both a[3] and p[3] happen to be the character 'l', but the compiler gets there differently. (The essential difference is that the values of an array like a and a pointer like p are computed differently whenever they appear in expressions, whether or not they are being subscripted, as explained further in question 6.3.) See also question 1.32.

But of course, if you "pass an array" to a function, the array is no longer in scope and you are only dealing with a pointer.

One further note: when you try to get "tricky" with the compiler and choose funky notation -- such as using the pointer equivalent version instead of the simpler to read and understand array index notation, you might actually confuse the compiler into generating less efficient code.

[dcs]

There really isn't much difference between these 3:

#include <stdio.h>


int foo(const  char arr[])

{

   int i;

   for ( i = 0; arr[i] != '\0'; ++i )

   {

   }

   return i;

}


int bar(const  char arr[])

{

   int i;

   for ( i = 0; *(arr + i) != '\0'; ++i )

   {

   }

   return i;

}


int baz(const char *arr)

{

   const char *arrptr=arr;

   while ( *arrptr!=0 ) arrptr++;

   return arrptr-arr;

}


int main()

{

   const char text[] = "The quick brown fox jumps over the lazy dog.";

   int (*function[])(const char *) = { foo, bar, baz};

   size_t i;

   for ( i = 0; i < sizeof function / sizeof *function; ++i )

   {

      int len = function[i](text);

      printf("function[%d] : %d\n", i, len);

   }

   return 0;

}

C:\Projects\scratch>gcc -O3 -S main.c

_foo:

	pushl	%ebp

	xorl	%eax, %eax

	movl	%esp, %ebp

	movl	8(%ebp), %edx

	cmpb	$0, (%edx)

	jmp	L10

	.p2align 4,,7

L12:

	incl	%eax

	cmpb	$0, (%eax,%edx)

L10:

	jne	L12

	popl	%ebp

	ret

	.p2align 4,,15

.globl _bar

	.def	_bar;	.scl	2;	.type	32;	.endef

_bar:

	pushl	%ebp

	xorl	%eax, %eax

	movl	%esp, %ebp

	movl	8(%ebp), %edx

	cmpb	$0, (%edx)

	jmp	L22

	.p2align 4,,7

L23:

	incl	%eax

	cmpb	$0, (%eax,%edx)

L22:

	jne	L23

	popl	%ebp

	ret

	.p2align 4,,15

.globl _baz

	.def	_baz;	.scl	2;	.type	32;	.endef

_baz:

	pushl	%ebp

	movl	%esp, %ebp

	movl	8(%ebp), %edx

	cmpb	$0, (%edx)

	movl	%edx, %eax

	jmp	L32

	.p2align 4,,7

L33:

	incl	%eax

	cmpb	$0, (%eax)

L32:

	jne	L33

	popl	%ebp

	subl	%edx, %eax

	ret

As expected, foo and bar generate identical output.