结构数组相对于 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 个条目。如果要遍历表，还有一个优势。使用并行数组，您只需递增 xinx，一条指令。对于结构，您必须添加 sizeof(monster(，该结构仅添加

适用于

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

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

考虑到这些优势(至少在他使用的灵活性方面(，动态分配物品的能力是免费赠品。他在写作中不清楚，但这似乎是他要表达的。

Answer 2

唯一一个点，其中并行数组比结构访问更好(这带来了在每次访问时计算当前怪物地址的需要(，如果你在零页中都有现成的设置指针到每个数组：

; set up zero page, done only once per level
; (per level, per stage, per dungeon, whatever)
lda #<monster_HP_list_for_this_level
sta $f0
lda #>monster_HP_list_for_this_level
sta $f1
lda #<monster_damage_list_for_this_level
sta $f2
lda #>monster_damage_list_for_this_level
sta $f3
lda #<monster_shield_list_for_this_level
sta $f4
lda #>monster_shield_list_for_this_level
sta $f5
...
; here you'd have instant access to the monster's values :
lda ($F0),y   ; monster Nr. y's HP
; or 
lda ($F4),y   ; monster Nr. y's Shield level

但： 你可能只有256个怪物(还有很多免费的零页地址，这应该不是什么大问题(

在每种新情况下(例如，您到达新地图，进入新地牢等(，零页指针都可以更新，以指向新关卡的怪物