4

我从那天写了很多 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 个条目。如果您想遍历表，还有一个优势。使用并行数组，您只需增加inx一条指令 x 。对于结构，您必须添加 sizeof(monster) ，其中添加仅适用于 a 将是

 txa
 clc
 adc #sizeof(Monster)
 tax

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

这似乎是并行数组是 6502 汇编语言的客观胜利，但是 John Carmack 从他的计划文件中有这个晦涩的评论

......实际上，一直回到理解苹果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 个周期 vs 5 和每次访问 5 个字节 vs 3。

基本上，如果绝对必须，您只会使用指针。如果您可以选择并行阵列，那么您似乎应该始终选择它们。

4

2 回答 2

2

并行数组使用绝对寻址在一组固定的参数中工作得非常快。但是，当您超出此范围并不得不使用零页索引时，表格就会翻转。

;  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

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

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

于 2017-08-14T05:50:21.173 回答
1

唯一的一点，并行数组比结构访问更好（这需要在每次访问时计算当前怪物的地址），如果你有指向零页中每个数组的准备好的指针：

; 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 个怪物（还有很多免费的零页地址，这应该不是什么大问题）

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

于 2017-08-14T07:59:54.780 回答