Optimizing C array lookups for the 6502#
Most of the platforms in the IDE that are powerful enough to support a C compiler are Z80-based. The Z80 isn’t the easiest target for C, but at least it has a lot of registers.
While the 6502 only has three 8-bit registers, the 6502 has strengths the Z80 doesn’t, as we’ll see here.
Let’s compare the two dominant C compilers for these CPUs.
We’ll compile a function with the CC65 C compiler for the 6502, and then with the SDCC
(Small Device C Compiler) for the Z80.
We’ll call the function getValue():
int arr16[128];
int getValue(int index) {
return (arr16[index & 0x7f] & 0xff) >> 1;
}
This function just looks up a value in a array of 16-bit ints, truncates the result to 8 bits, then divides it by 2.
We’ll first compile it with the default flags for both compilers:
6502 VERSION (cc65) Z80 VERSION (sdcc)
jsr pushax push ix
ldy #$01 ld ix,#0
jsr ldaxysp add ix,sp
ldx #$00 ld bc, #_arr16+0
and #$7F ld l, 4 (ix)
jsr aslax1 res 7, l
clc ld h, #0x00
adc #<(_arr16) add hl, hl
tay add hl, bc
txa ld c, (hl)
adc #>(_arr16) ld h, #0x00
tax sra h
tya rr c
ldy #$01 ld l, c
jsr ldaxidx pop ix
ldx #$00
jsr asrax1
jmp L0004
L0004: jsr incsp2
rts
The 6502 version is a little more verbose here, compiling to 41 bytes vs. 31 bytes for Z80. One big difference: SDCC turns on most optimizations by default. That’s not fair, so let’s see what optimizations we can activate for CC65.
We’ll compile it again, but this time we’ll pass the -O flag to CC65.
We’ll try to get the Z80 version even smaller by passing --opt-code-size
to SDCC:
6502 VERSION (cc65 -O) Z80 VERSION (sdcc --opt-code-size)
jsr pushax call ___sdcc_enter_ix
ldy #$00 ld bc, #_arr16+0
lda (sp),y ld l, 4 (ix)
asl a res 7, l
tay ld h, #0x00
lda _arr16,y add hl, hl
ldx #$00 add hl, bc
lsr a ld c, (hl)
jmp incsp2 ld h, #0x00
sra h
rr c
ld l, c
pop ix
ret
The 6502 version is a lot smaller, down to 18 bytes! The Z80 version is only a little smaller due to the replacement of the stack frame setup with a function call.
What happened here to make the 6502 version so small?
The pedigree of CC65 goes back to 1980 and the Small C compiler. As a result, its optimization methods depend highly on peephole optimization. This is a method of scanning code linearly to look for patterns, then rewriting those patterns to be more efficient.
One such pattern is one I recently added in my own branch. It looks for 16-bit array lookups of the form:
array16[index & 0x7f] // or index < 0x7f
CC65 defers most optimization until after code generation. The pseudocode before optimization looks more-or-less like this:
AX = index
AX = AX & 0x7f
AX = AX << 1
AX = AX + address(arr16)
AX = read16(AX)
AX = AX >> 1
return AX
This may not look like a lot of code, but AX is a 16-bit value (actually
the AX register pair)
and manipulating 16-bit values is expensive on the 6502.
We need to find a way to reduce it to an 8-bit problem.
The key here is the index & 0x7f mask.
This guarantees that the array index will be less than 128.
Each array element takes two bytes, so we only have to index up to 256 bytes
of data – enough for 8 bits.
Instead of computing a 16-bit offset for the array, we can use the 6502’s
indexed addressing mode, i.e. LDA address,Y.
The pseudocode now looks like this:
// jsr pushax
// ldy #$00
A = index // lda (sp),y
A = A << 1 // asl a
Y = A // tay
A = arr16[Y] // lda _arr16,y
// ldx #$00
A = A >> 1 // lsr a
return A // jmp incsp2
Because we’re dealing mainly with 8-bit values, this code becomes much smaller and
faster. Note that we don’t even need the index & 0x7f mask anymore, because
the asl a instruction takes off that high bit for us.
Let’s compare the non-optimized 6502 output with the optimized version:
ORIGINAL VERSION OPTIMIZED VERSION
jsr pushax jsr pushax
ldy #$01 ldy #$00
jsr ldaxysp lda (sp),y
ldx #$00
and #$7F
jsr aslax1 asl a
clc
adc #<(_arr16)
tay
txa
adc #>(_arr16)
tax
tya
ldy #$01 tay
jsr ldaxidx lda _arr16,y
ldx #$00 ldx #$00
jsr asrax1 lsr a
jmp L0004
L0004: jsr incsp2 jmp incsp2
rts
The Z80 doesn’t have a equivalent addressing mode. To do a fast 8-bit table lookup, we have to align our table to a 256-byte page. Then we can stuff the index in the lower 8 bits of a 16-bit register pair. The result would look sort of like this:
ld h, #>(_arr16) ; H = MSB of table (constant)
ld a, 4 (ix) ; index parameter
sla a ; shift left
ld l, a ; L = LSB of table (computed)
ld a, (hl) ; look up 8-bit value in HL
The 6502 doesn’t require page alignment, so it has the edge here in
optimizing this case. The Z80 is better at other things, like dealing with
structs.
Thanks for reading! If you want to play with the CC65 C compiler, you can do so right now in the 8bitworkshop IDE using the venerable Apple II platform (with maybe more coming in the future!)