A case of premature optimization

I had a case of premature optimization recently. I need to learn more self-control: to take it easy and let the compiler does what it does best.

I had a few tests I needed to write and they had to be super tight because they would run in gate level simulation (GLS) where time is a luxury the verification team do not have.

My other more normal test programs make use of the newlib library and I have implemented system clock and console to make writing test programs more palatable. However adding newlib makes test programs big and slow to complete in a simulation environment. So, for the GLS, I decided to make the test programs as lean as possible. This means not using newlib, or any of the libraries for that matter. Which also means no standard C library and the math emulation (because ARM7 do not have math coprocessor and does not have divide instruction.)

As an alternative to using printf and friends, I wrote a function to write to a GPIO port instead:

static void lean_vout(char *s, ...) {
 va_list ap;
 va_start(ap, s);
 lean_out(s);
 while ( (s=va_arg(ap,char*)) != 0 )
   lean_out(s);
 va_end(ap);
}

Where lean_out prints each character in the string to the GPIO port. Printing to GPIO is fast and the verification team can easily see the characters in the simulation signal viewer.

Beside, the ability to see what is happening in a test program, the ability to do assertions is important too. I cannot use the facility in the <assert.h> because it makes use of printf. So, I have this macro for my lean-and-mean assertion:

#define lean_assert(cond) if (!(cond)) lean_do_assert(__FILE__, __LINE__);

Basically, when the assertion fails, the filename and the line number would scuttle through the GPIO port. But there is a small problem: I need to convert the line number into its ASCII representation. Because, recently, I had a program failing to compile because I use division with -nostdlib, I thought I needed to use an algorithm to divide by 10 without actually using the division operator. And find I did: Section 10 to the "Hacker's Delight" book which talks about division by constant in great depth. Based on the information in this section, I came up with my version of itoa for converting integer to base-10 ASCII representation:

/* taken straight from "Hacker's Delight" */

static int remu10(unsigned n) {
 static char table[16] =
   {0, 1, 2, 2, 3, 3, 4, 5,
    5, 6, 7, 7, 8, 8, 9, 0};
 n = (0x19999999*n + (n >> 1) + (n >> 3)) >> 28;
 return table[n];
}

char *lean_itoa(int n, char *s, int len) {
 int r;
 s += len;
 *--s = '\0';
 while (n && len > 0) {
   r = remu10(n);
   n = ((n - r) >> 1)*0xCCCCCCCD; /* also from "Hacker's Delight" */
   *--s = '0' + r;
   --len;
 }
 return s;
}

Basically, the remainder is computed and the divide-by-10 is done using the remainder. The generated code from arm-elf-gcc (with optimization -O2):

0000820c <lean_itoa>:
   820c: e0821001  add r1, r2, r1
   8210: e3a03000  mov r3, #0 ; 0x0
   8214: e3500000  cmp r0, #0 ; 0x0
   8218: 13520000  cmpne r2, #0 ; 0x0
   821c: e92d4010  stmdb sp!, {r4, lr}
   8220: e1a0c002  mov ip, r2
   8224: e5413001  strb r3, [r1, #-1]
   8228: e2411001  sub r1, r1, #1 ; 0x1
   822c: da000018  ble 8294 <lean_itoa+0x88>
   8230: e59f4064  ldr r4, [pc, #100] ; 829c <.text+0x27c>
   8234: e1a0e001  mov lr, r1
   8238: e0803080  add r3, r0, r0, lsl #1
   823c: e0803103  add r3, r0, r3, lsl #2
   8240: e0633303  rsb r3, r3, r3, lsl #6
   8244: e0803103  add r3, r0, r3, lsl #2
   8248: e0633703  rsb r3, r3, r3, lsl #14
   824c: e0803183  add r3, r0, r3, lsl #3
   8250: e08330a0  add r3, r3, r0, lsr #1
   8254: e08331a0  add r3, r3, r0, lsr #3
   8258: e7d41e23  ldrb r1, [r4, r3, lsr #28]
   825c: e0612000  rsb r2, r1, r0
   8260: e1a020c2  mov r2, r2, asr #1
   8264: e0823082  add r3, r2, r2, lsl #1
   8268: e0833203  add r3, r3, r3, lsl #4
   826c: e0833403  add r3, r3, r3, lsl #8
   8270: e0833803  add r3, r3, r3, lsl #16
   8274: e0820103  add r0, r2, r3, lsl #2
   8278: e24cc001  sub ip, ip, #1 ; 0x1
   827c: e2811030  add r1, r1, #48 ; 0x30
   8280: e3500000  cmp r0, #0 ; 0x0
   8284: 135c0000  cmpne ip, #0 ; 0x0
   8288: e56e1001  strb r1, [lr, #-1]!
   828c: caffffe9  bgt 8238 <lean_itoa+0x2c>
   8290: e1a0100e  mov r1, lr
   8294: e1a00001  mov r0, r1
   8298: e8bd8010  ldmia sp!, {r4, pc}
   829c: 0001085b  andeq r0, r1, fp, asr r8

From the look of it, the compiler has tried very hard to use additions and shifts to perform the constant multiplications. This led me into thinking that, maybe, the compiler would be clever enough to avoid doing division in division by constants (of course, it is but it didn't occur to my thick head.) I tried this instead:

char *lean_itoa(int n, char *s, int len) {
 int r;
 s += len;
 *--s = '\0';
 while (n && len > 0) {
   r = n % 10;
   n = n / 10;
   *--s = '0' + r;
   --len;
 }
 return s;
}

And the generated assembly code:

0000820c <lean_itoa>:
   820c: e0821001  add r1, r2, r1
   8210: e3a03000  mov r3, #0 ; 0x0
   8214: e3500000  cmp r0, #0 ; 0x0
   8218: 13520000  cmpne r2, #0 ; 0x0
   821c: e92d4010  stmdb sp!, {r4, lr}
   8220: e5413001  strb r3, [r1, #-1]
   8224: e1a0e002  mov lr, r2
   8228: e2411001  sub r1, r1, #1 ; 0x1
   822c: da00000f  ble 8270 <lean_itoa+0x64>
   8230: e59f4040  ldr r4, [pc, #64] ; 8278 <.text+0x258>
   8234: e1a0c001  mov ip, r1
   8238: e0c13094  smull r3, r1, r4, r0
   823c: e1a03fc0  mov r3, r0, asr #31
   8240: e0633141  rsb r3, r3, r1, asr #2
   8244: e1a02003  mov r2, r3
   8248: e0833103  add r3, r3, r3, lsl #2
   824c: e0403083  sub r3, r0, r3, lsl #1
   8250: e24ee001  sub lr, lr, #1 ; 0x1
   8254: e2833030  add r3, r3, #48 ; 0x30
   8258: e3520000  cmp r2, #0 ; 0x0
   825c: 135e0000  cmpne lr, #0 ; 0x0
   8260: e1a00002  mov r0, r2
   8264: e56c3001  strb r3, [ip, #-1]!
   8268: cafffff2  bgt 8238 <lean_itoa+0x2c>
   826c: e1a0100c  mov r1, ip
   8270: e1a00001  mov r0, r1
   8274: e8bd8010  ldmia sp!, {r4, pc}
   8278: 66666667  strvsbt r6, [r6], -r7, ror #12

So, yes! The compiler avoids calling the division function. The previous generated code has 36 instructions with one load instruction for the table. The second one has 27 instructions with one load instruction used in the "signed multiply long" instruction. Which one is faster? I presume the compiler concluded that using the long multiplication is faster than additions-and-shifts (See also Re: Optimization question). But surely the second code is more compact.

This led me into digging further on how long divide-by-constant optimization has been around in GCC. Apparently, since 1994 when Torbjorn Granlund and Peter L. Montgomery wrote about it in their paper, "Division by Invariant Integers using Multiplication."

So there you have it. A case of trying to hard. I should've let GCC do its job. But I have learned a lot from the whole process.

Mind your struct's!

This should be elementary to seasoned C programmers but one rule of thumb is, in a struct, one should arrange the fields based on the size of their types in reverse order. This would typically lead to a more compact struct which can be crucial to an embedded system with limited memory. To illustrate, struct_a below is a struct similar to what I've found in a library provided by a partner of my company. One the other hand, struct_b is the same struct but with its fields "properly ordered". In addition, the array arr_a also appears in similar fashion in the partner's library.

#include 

struct struct_a {
  short f1;
  char  f2;
  int   f3;
  char  f4;
};

struct struct_b {
  int f3;
  short f1;
  char f2;
  char f4;
};

struct struct_a arr_a[32];
struct struct_b arr_b[32];

int main() {
  printf("sizeof(struct_a):%d\n", sizeof(struct struct_a));
  printf("sizeof(struct_b):%d\n", sizeof(struct struct_b));
  printf("   sizeof(arr_a):%d\n", sizeof(arr_a));
  printf("   sizeof(arr_b):%d\n", sizeof(arr_b));
  return 0;
}

Compiling the code above using the GNUARM toolchain and running it the ARM simulator in GDB, we get this output:

sizeof(struct_a):12
sizeof(struct_b):8
   sizeof(arr_a):384
   sizeof(arr_b):256

Simply by reordering the fields, we could save 4 bytes in the struct and 128 bytes from the array above. Another example is given below. Again struct_a is something found in the library and struct_b is an optimized version of the struct.

#include 

struct struct_a {
   short f1;
   int   f2;
   char  f3;
   char  f4;
   short f5;
   char  f6;
   short f7;
   short f8[3];
};

struct struct_b {
   int   f2;
   short f8[3];
   short f1;
   short f7;
   short f5;
   char  f3;
   char  f4;
   char  f6;
};

struct struct_a arr_a[32];
struct struct_b arr_b[32];

int main() {
  printf("sizeof(struct_a):%d\n", sizeof(struct struct_a));
  printf("sizeof(struct_b):%d\n", sizeof(struct struct_b));
  printf("   sizeof(arr_a):%d\n", sizeof(arr_a));
  printf("   sizeof(arr_b):%d\n", sizeof(arr_b));
  return 0;
}

The output of the program compiled through GNUARM toolchain is given below.

sizeof(struct_a):24
sizeof(struct_b):20
   sizeof(arr_a):768
   sizeof(arr_b):640

Again, we could save 4 bytes from the struct and 128 bytes from the array. Note that struct_b above has a short array with 3 elements as a field. Why it was not made the first field of struct_b? After all it is bigger than an int. It has something to do with int alignment on ARM. Try it out and see.