Want Faster Code? Be Careful!
SHA Newsletter: Vol 1. No. 8

Want Faster Code? Be Careful!

Often, when you write a program, you want to make sure you have written efficient code. But efficiency, like beauty, is in the eye of the beholder.

Here’s an example function f(), which returns a value from a lookup table. There are two versions. Let’s see which is more efficient. First, let’s make an array of constants:

unsigned int f (unsigned int arg) {

const unsigned int array1[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

return array1[arg];

}

Here’s the same function, this time written with a static array instead of a const

unsigned int f (unsigned int arg) {

static unsigned int array1[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

return array1[arg];

}

Which one is more efficient? You might think that the const version is, and you would not be alone. After all, this code tells the compiler that you are definitely not going to change the contents of the array. That way, it can write more efficient code, right?

Let’s look at the resulting assembler code, that I created using gcc on an x86 system.

Here’s the const version:

_f:
pushl %ebp
movl %esp, %ebp
subl $56, %esp
movl $0, -56(%ebp)
movl $1, -52(%ebp)
movl $2, -48(%ebp)
movl $3, -44(%ebp)
movl $4, -40(%ebp)
movl $5, -36(%ebp)
movl $6, -32(%ebp)
movl $7, -28(%ebp)
movl $8, -24(%ebp)
movl $9, -20(%ebp)
movl 8(%ebp), %eax
movl -56(%ebp,%eax,4), %eax
leave
ret
.def _f; .scl 2; .type 32; .endef
.def _printf; .scl 2; .type 32; .endef

and the static version:

_array1.0:
.long 0
.long 1
.long 2
.long 3
.long 4
.long 5
.long 6
.long 7
.long 8
.long 9
.text
.globl _f
.def _f; .scl 2; .type 32; .endef
_f:
pushl %ebp
movl %esp, %ebp
movl 8(%ebp), %eax
movl _array1.0(,%eax,4), %eax
popl %ebp
ret

Which one is more efficient?

The const version uses ten movl instructions to set up the const array; the static version adds push/pop instructions but does the array lookup with a single movl instruction. The program will execute more instructions for each call of f() if the lookup table is defined as const instead of static. And it will use twice as much memory because the actual values are included in the instructions and are also stored in memory when the instructions get executed.

In the static version of the program, the constants are set up at compile time and can be directly referenced in memory. This saves space and time.

This kind of idea is used wherever a lookup table is needed. A lookup table that has many values (such as for trigonometric functions) will take a lot longer to execute if you declare the table const vs. static. In a real-time embedded system, with a slow processor and limited memory, you might not have the luxury of doing that.

Let’s think about why the compiler does things this way. Is there any benefit to the code in the const example? Certainly, there is. The const code never places the unchangeable data where external code can modify it. The extra instructions make sure that the correct constants are loaded on every call of f(). For data integrity, these are good things. On a complex project, it can be more efficient, in terms of debugging time, to add that extra level of protection.

But if you are working on a small embedded system, you might not want that protection. It comes at a price in both memory consumption and execution time. In this case, the static code is more efficient, in terms of your scarce CPU resources. Which way you go depends on what you want to accomplish.

Please note: Any trademarks and trade names of others mentioned in this message are the property of their owners, and not Stoney Hill Associates, LLC. We respect the intellectual property of others. The information provided is believed to be reliable, but we cannot guarantee that the procedures and information given here will work correctly for your specific situation.

If you would like help with a computer or software problem you face, contact us. Send an email to request@stoneyhillassociates.com.

Want to subscribe to this newsletter? Just join our mailing list:

© 2006 Stoney Hill Associates, LLC