# ARM: Efficient C for ARM: Sentinels

by on

## Sentinels

When searching through a list we normally do two comparisons:

1. Compare loop index against maximum.
2. 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.

## Example

The original code:

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

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

return -1;
}
```

Compiles to:

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

If we rewrite it as follows:

```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;
}
```

It compiles to:

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

## Remarks

Sentinel: Computers. a symbol, mark, or other labelling device indicating the beginning or end of a unit of information.

This is from http://www.azillionmonkeys.com/qed/case4.html.

Obviously you need to ensure that `list[N]` is both available and writable.

This can be improved further by replacing array indexing with pointers.