Efficient C for ARM

Sentinels

When searching through a list we normally do two comparisons:

Compare loop index against maximum.
Compare current key against desired key.

That’s two flow conditions inside a tight loop, which is bad on modern pipelined CPUs.

Solution:

Augment the array with the desired value at the end.

This allows both comparisons to be merged.
But it requires one extra element.

Examples

int search1(int *list, int N, int want)
{
  int i;

  for (i = 0; i < N; i++)
    if (list[i] == want)
      return i;

  return -1;
}

search1
     MOV   r3,#0     ; i = 0
     B     loop
test LDR   r12,[r0,r3,LSL #2]
     CMP   r12,r2    ; key
     ADDNE r3,r3,#1  ; i++
     BNE   loop
     MOV   r0,r3     ; i
     MOV   pc,lr
loop CMP   r3,r1     ; i < N
     BLT   test
     MVN   r0,#0     ; -1
     MOV   pc,lr

int search2(int *list, int N, int want)
{
  int i;

  list[N] = want;

  i = 0;
  while (list[i] != want)
    i++;

  if (i == N)
    return -1;

  return i;
}

search2
     STR   r2,[r0,r1,LSL #2]
     MOV   r3,#0     ; i = 0
loop LDR   r12,[r0,r3,LSL #2]
     CMP   r12,r2
     ADDNE r3,r3,#1  ; i++
     BNE   loop
     CMP   r3,r1     ; i == N
     MOVNE r0,r3
     MVNEQ r0,#0     ; -1
     MOV   pc,lr