Hacker News new | comments | show | ask | jobs | submit login

Why would you favour a AOS (Array of Structures) or the SOA (Structure of Arrays), for the different architectures?



The basic operation for accessing a value from a structure is to take the address of the structure, add a compile-time constant offset to it, and use that address. There's an addressing mode specifically for this in the Z80: you put the struct address in a register, and have the constant offset as part of the instruction. So you can do stuff like this: (numbers in comments are: <bytes for this instruction> <bytes total> / <cycles for this instruction> <cycles total>)

    <<put address in IX>>
    LD A,(IX+0)            ; A=SELF.X              3 3  / 19 19
    ADD A,(IX+2)           ; A=SELF.X+SELF.DX      3 6  / 19 38
    LD (IX+0),A            ; SELF.X=SELF.X+SELF.DX 3 9  / 19 57
    XOR A                  ; A=0                   1 10 / 4  61
    LD (IX+2),A            ; SELF.DX=0             3 13 / 19 80
The 6502 doesn't have anything exactly like this. You do have an indirect addressing mode, but the offset goes in a register. So for every access, you need to have the offset into the index register. (There's no point adding the offset to the address; the offset is mandatory, so you'd then just have to load zero into the index register every time.) So the above in 6502:

    <<put address in $70>>
    LDY #2                                         2 2  / 2 2
    LDA ($70),Y            ; A=SELF.DX             2 4  / 5 7
    LDY #0                                         2 6  / 2 9
    CLC                                            1 7  / 2 11
    ADC ($70),Y            ; A=SELF.DX+SELF.X      2 9  / 5 16
    STA ($70),Y            ; SELF.X=SELF.X+SELF.DX 2 11 / 6 22
    TYA                                            1 12 / 2 24
    LDY #2                                         2 14 / 2 26
    STA ($70),Y            ; SELF.DX=0             2 16 / 6 32
Which is rather unwieldy, takes up more space, and is a bit slow (the 4:1 ratio I mentioned in my original past is here closer to 2:1) - even after I rearranged the code a bit so the Y value didn't need reloading so much. You also have the issue that the struct address is a 16-bit quantity, something that is inconvenient to handle on the 6502. There are no instructions that operate on 16-bit data.

One thing the 6502 does have though is an addressing mode where the operand's address is a fixed 16-bit value (from the instruction) plus an 8-bit index register. So, with this in mind, what you could do is have a separate table for each struct field. So this switches things around, and instead of a runtime 16-bit address (of the struct) and a compile-time 8-bit offset (of the field), you have a compile-time 16-bit address (of the field table) and a runtime 8-bit offset (for the row in the table). Which is a perfect fit. Best of all, the indexing is free if you arrange things correctly, which is not that hard to do. Then the code would look more like this:

    <<put row in X>>
    CLC                     ;                        1 1  / 2 2
    LDA XS,X                ; A = SELF.X             3 4  / 4 6
    ADC DXS,X               ; A = SELF.X+SELF.DX     3 7  / 4 10
    STA XS,X                ; SELF.X=SELF.X+SELF.DX  3 10 / 4 14
    LDA #0                  ;                        2 12 / 2 16
    STA DXS,X               ; SELF.DX=0              3 15 / 4 20
And there's that 4:1 ratio again...

Each object's "address" is now an 8-bit quantity (it's just an index into the tables), so much easier to deal with. And moving from one object to the next is very quick, since it's just incrementing a register.

There doesn't appear to be anything analogous to this alternative approach on the Z80.




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: