6502 汇编语言中结构数组相对于并行数组的优点？

Question

我从当时写的大量 6502 中了解到，并行数组比存储数据的结构更好。

想象一下，您想要一个怪物统计数据表，在 C 中可以像这样定义

struct Monster {
  unsigned char hitPoints;
  unsigned char damage;
  unsigned char shieldLevel;
  char* name;
};

您可以将其存储为结构数组

static Monster s_monsters[] = {
  { 5,   1, 0, "orc", },
  { 50, 10, 5, "dragon", },
  { 10,  3, 1, "goblin", },
};

或者您可以将其存储为并行数组（通常使用宏或工具来生成）。注意：我用 C 语言显示代码，但请想象它是 6502 汇编。

unsigned char Monster_hitPoints[] = { 5, 50, 10, };
unsigned char Monster_damage[] = { 1, 10, 3, },
unsigned char Monster_sheildLevel[] = { 0, 5, 1, };
unsigned char Monster_nameLow[] = { 
   &m_orc_name & 0xFF, 
   &m_dragon_name & 0xFF,
   &m_goblin_name & 0xFF, 
};
unsigned char Monster_nameHigh[] = { 
   &m_orc_name >> 8 , 
   &m_dragon_name >> 8,
   &m_goblin_name >> 8, 
};

在 6502 中，给定一个 itemNdx，您可以使用并行数组访问所有字段，如下所示

ldx itemNdx
lda Monster_hitPoints,x   ; access hitpoints
...
lda Monster_damage,x      ; access damage
...
lda Monster_shieldLevel,x ; access shieldLevel
...
lda Monster_nameLow,x     ; access name
sta pageZeroStringPointer
lda Monster_nameHigh,x
sta pageZeroStringPointer + 1
ldy #0
lda (pageZeroStringPointer),y

就好像您使用结构而不是并行数组一样，它变成了

lda itemNdx
clc          ; have to compute offset
asl a        ; a = itemNdx * 2   
asl a        ; a = itemNdx * 4
adc itemNdx  ; a = itemNdx * 5
tax          ; x = itemNdx * 5 

lda s_monsters+Monster.hitPoints,x   ; access hitpoints
...
lda s_monsters+Monster.damage,x      ; access damage
...
lda s_monsters+Monster.shieldLevel,x ; access shieldLevel
...
lda s_monsters+Monster.name,x        ; access name
sta pageZeroStringPointer
lda s_monsters+Monster.name+1,x
sta pageZeroStringPointer + 1
ldy #0
lda (pageZeroStringPointer),y        ; a is now first char of name

结构版本必须计算每个结构的偏移量。在上面的例子中，与并行数组版本相比，多了 5 条指令。最重要的是，用于计算偏移量的数学是手动编码的，这意味着如果结构发生变化，则必须随时重写它。最重要的是你只能有一张256 / sizeof(Monster)大桌子。如果您有更多字段（20 到 30 个并不罕见），这意味着您的表只能有 8 到 12 个条目，而使用并行数组可以有 256 个条目。如果您想迭代表，还有一个优势。对于并行数组，您只需递增 x inx，一条指令即可。对于结构，您必须添加 sizeof(monster) ，它仅适用于 a

 txa
 clc
 adc #sizeof(Monster)
 tax

这比并行数组版本多了 3 条指令。

看起来并行数组是 6502 汇编语言的客观胜利，但是 John Carmack 在他的计划文件中给出了这个晦涩的评论

...实际上，一直回到理解 Apple II 汇编语言中结构相对于并行数组的优点... ...

有谁知道这些优点是什么？

我能立即想到的唯一优点是使用结构数组分配动态数组更容易，但大多数游戏在 6502 天里都没有分配任何东西。他们对固定大小的内存数组进行了硬编码，因此看起来不可能是这样。6502也没有缓存，所以没有缓存优势。

此外，如果您完全使用指针，则可以寻址超过 256 个项目，但完全使用指针比上面显示的任何一种方法要慢得多，并且需要更多的代码，因此它们通常是最后的选择。

; setup pointer
lda itemNdx
ldx #sizeof(Monster)
jsr multiplyAX       ; 8->16 bit multiply is around 70 cycles result in A(low), X(high)
clc
adc #s_monster && 0xFF
sta POINTER
txa
adc #s_monster >> 8
sta POINTER + 1

ldy #Monster.hitPoints   ; access hitpoints
lda (POINTER),y   
...
ldy #Monster.damage      ; access damage
lda (POINTER),y 
...
ldy #Monster.shieldLevel ; access shieldLevel
lda (POINTER),y 
...
ldy #Monster.name       ; access name
lda (POINTER),y
sta pageZeroStringPointer
ldy #Monster.name+1    
lda (POINTER),y
sta pageZeroStringPointer + 1
ldy #0
lda (pageZeroStringPointer),y        ; a is now first char of name

您可以通过创建指向每个项目的并行指针数组来消除乘法。您仍然有 2 行并行数组不需要的设置，并且您仍然会使其余代码变得更慢、更大。每次访问 8 个周期与每次访问 5 和 5 个字节与 3 个周期。

基本上，只有在绝对必要的情况下才会使用指针。如果您可以选择并行数组，那么似乎您应该始终选择它们。

Answer 1

并行数组使用绝对寻址在一组固定参数内工作得非常快。然而，一旦超出这个范围并且必须使用零页索引，情况就会发生逆转。

;  Assuming MONSTER_PTR is zp, set to the start of the current structure
ldy  #Monster.hitPoints
lda  (MONSTER_PTR),y
...
ldy  #Monster.damage
lda  (MONSTER_PTR),y

对于超出单页限制的并行数组，必须为每个数组重置指针。此外，一旦指针发挥作用，长索引计算可以用预先计算的指针的简单移动或对索引指针表的单移来代替。

考虑到这些优势（至少在他所使用的灵活性方面），动态分配项目的能力是免费的。他在文中并不清楚，但这似乎就是他的意思。