assembly - 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 来自 his plan file 的这个晦涩难懂的评论。

... actually, all the way back to understanding the virtues of structures over parallel arrays in apple II assembly language.. ...

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

我能想到的唯一优点是用结构数组分配动态数组更容易，但大多数游戏在 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 个周期 vs 5 个，每次访问 5 个字节 vs 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

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

鉴于优势(至少在他使用的灵活性方面)，动态分配项目的能力是免费赠品。他在写作中并不清楚，但这似乎就是他的意思。