The Assignment

To hand-optimize part of the Insertion Sort algorithm for the SPARC architecture.

The Analysis

First thing I did was compare the output from gcc -S and gcc -S -O3 to see how they stacked up. Without optimizations there are 57 lines and with -O3 there are 31, already quite an improvement. It does not use save/restore, as required. Additionally, -O3 never calls the seperate insert() function, but instead inlines it directly into isort(). Then I tried running CPU and architecture specific optimizations with gcc -S -O3 -mcpu=ultrasparc, but that only changed the instruction names a bit without changing the instruction count or speed at all.

Analyzing isort() for unused registers was fairly simple. It uses %o0-o3 and none of %g. It loads its own data into the registers both before and after calling insert(), so practically nothing insert() does can affect isort()'s correct behavior. I did a quick test to prove this by throwing in -O3's insert() into the unoptimized assembly, and it worked without any complaints. -O3's output is in Source Listing 2.

The completely unoptimized insert() is quite horrible. The main loop, consisting of .LL7 and .LL9, uses 8 load and 2 store operators, totalling 10 memory accesses. A rolling analysis follows...

insert:

!#PROLOGUE# 0

save %sp, -112, %sp

!#PROLOGUE# 1

Here it saves the input variables, i and key, for later use.

st %i0, [%fp+68]

st %i1, [%fp+72]

Start of the main loop. LL7 handles the conditions.

.LL7:

Now load the previously saved input variable, i.

ld [%fp+68], %o0

Compare if i is <0, and branch to the end if so.

cmp %o0, 0

bl .LL10

nop

Create an offset to num[i], then load it.

sethi %hi(num), %o1

or %o1, %lo(num), %o0

ld [%fp+68], %o1

mov %o1, %o2

sll %o2, 2, %o1

ld [%o0+%o1], %o0

Load key, and compare to num[i]. If num[i]>key, branch to .LL9, else go to end.

ld [%fp+72], %o1

cmp %o0, %o1

bg .LL9

nop

b .LL10

nop

Welcome to Superfluous Branch Tags. This week's special:

.LL10:

b .LL8

nop

Continuation of the main loop. LL9 handles the assignments.

.LL9:

Create an offset to num[i+1], then create an offset to num[i], then load num[i] and store in num[i+1].

sethi %hi(num), %o1

or %o1, %lo(num), %o0

ld [%fp+68], %o2

add %o2, 1, %o1

mov %o1, %o2

sll %o2, 2, %o1

sethi %hi(num), %o3

or %o3, %lo(num), %o2

ld [%fp+68], %o3

mov %o3, %o4

sll %o4, 2, %o3

ld [%o2+%o3], %o2

st %o2, [%o0+%o1]

Reload i, decrement i, save i.

ld [%fp+68], %o0

add %o0, -1, %o1

st %o1, [%fp+68]

Branch back to loop condition checks.

b .LL7

nop

Post-loop actions are done in LL8.

.LL8:

Create an offset to num[i+1]

sethi %hi(num), %o1

or %o1, %lo(num), %o0

ld [%fp+68], %o2

add %o2, 1, %o1

mov %o1, %o2

sll %o2, 2, %o1

Load key, save key in num[i+1].

ld [%fp+72], %o2

st %o2, [%o0+%o1]

Done, so return and restore.

.LL6:

ret

restore

All in all, this is a by-the-numbers what needs to be done and how can it be explicitly done step by step implementation. Nothing is incorrect or dangerous, but it is very slow. In contrast, -O3's main loop uses only 1 load and 1 store, but even that is not as sleek as possible.

The Implementation (see: Source Listing 1)

Looking at -O3 to see what can be optimized, not much really stands out as being unnecessary. The only thing I noticed was that it builds an offset from i by i<<2 (same as i*4), and then uses that offset for all subsequent loads and saves. Even so, it is still keeping i itself up to date. So, first thing was to only use i once to create the initial offset, then work with that. This shaved 1 instruction (addcc %o0, -1, %o0) off the main loop (.LL53).

Next thing I noticed was that the registers %o2, %o3, and %o4 served much of the same purpose in building offsets, but was being maintained seperately. The instructions “add %o2, -4, %o2” and “add %o3, -4, %o3” in .LL53 had to be redundant. Then I got stuck trying to clean it all up, and instead I looked around for a later version of gcc to see how that would do it.

Source Listing 3 has the insert() from v3.3.3 of gcc -O3 -mcpu=i686, which has a simple and clean 6 instruction main loop (.L58). One instruction better than what I had so far. It is different from SPARC in that i686 doesn't need to pre-calculate the offset into num[], so it can keep its i variable around in %edx for accessing the num[] array directly. Whether it actually is a single instruction behind the scenes I don't know, but it looks much cleaner.

Then I combined my single offset calculation with the i686 main loop ported to SPARC Assembly, and then had what you can see in Source Listing 1.

Runtimes:

Best case of i=0: 6 instructions

Better case of num[i]<=key: 12 instructions

All other cases: (i*6)+13 instructions

Used registers:

I also looked at isort() to see if I could reuse something from it's environment to speed things up, but there's only %o2 holding offset to num[j] and %o3 holding j. They might be useful for initialization, but I truly doubt the 6 instruction main loop can be any faster, regardless of how many registers are available or can be inherited from the caller.

The Testing

Not really sure what can be tested here except showing it gives the right output:

bash-2.03$ gcc insertion_sort.normal.s

bash-2.03$ ./a.out

Input:

10, 18,-19, 18, 12, 8, 3, 42, 15, 20, 3, 17, 25, 11, 23, 12, 0, -8,-13, 9,

Output:

-19,-13, -8, 0, 3, 3, 8, 9, 10, 11, 12, 12, 15, 17, 18, 18, 20, 23, 25, 42,

The Conclusion

Beat gcc -O3's main loop by 2 instructions (a whopping 25%), which is as good as it gets.

- Tino Didriksen

Source Listing 1: The hand-optimized SPARC Assembly insert()

insert:

!#PROLOGUE# 0

!#PROLOGUE# 1

cmp %o0, 0

bl .LL9

sethi %hi(num), %o3

or %o3, %lo(num), %o3

sll %o0, 2, %o2

ld [%o3+%o2], %g2

cmp %g2, %o1

ble .LL9

add %o3, 4, %o4

.LL53:

st %g2, [%o4+%o2]

addcc %o2, -4, %o2

bneg .LL9

ld [%o3+%o2], %g2

cmp %g2, %o1

bg .LL53

.LL9:

nop
add %o2, 4, %o2
retl
st %o1, [%o3+%o2]

Source Listing 2: The insert() by gcc -O3

insert:
!#PROLOGUE# 0
!#PROLOGUE# 1
cmp %o0, 0
bl .LL9
sethi %hi(num), %g3
or %g3, %lo(num), %o3
sll %o0, 2, %o2
ld [%o3+%o2], %g2
cmp %g2, %o1
ble .LL9
add %o2, 4, %g2
mov %o3, %o4
add %g2, %o4, %o3
ld [%o2+%o4], %g2
addcc %o0, -1, %o0
.LL53:
st %g2, [%o3]
add %o2, -4, %o2
bneg .LL9
add %o3, -4, %o3
ld [%o2+%o4], %g2
cmp %g2, %o1
bg,a .LL53
addcc %o0, -1, %o0
.LL9:
add %o0, 1, %g2
or %g3, %lo(num), %g3
sll %g2, 2, %g2
retl
st %o1, [%g3+%g2]

Source Listing 3: The insert() by v3.3.3 gcc -O3 -mcpu=i686

insert:
pushl %ebp
movl %esp, %ebp
movl 8(%ebp), %edx
movl 12(%ebp), %ecx
testl %edx, %edx
js .L55
movl num(,%edx,4), %eax
cmpl %ecx, %eax
jle .L55
.p2align 4,,15
.L58:
movl %eax, num+4(,%edx,4)
decl %edx
js .L55
movl num(,%edx,4), %eax
cmpl %ecx, %eax
jg .L58
.L55:
popl %ebp
movl %ecx, num+4(,%edx,4)
ret