Преимущества массивов структур по сравнению с параллельными массивами в ассемблере 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(монстр), который будет работать только с

 txa
 clc
 adc #sizeof(Monster)
 tax

Это на 3 инструкции больше, чем версия для параллельных массивов.

Кажется, что параллельные массивы - это объективный выигрыш для языка ассемблера 6502, но есть этот неясный комментарий Джона Кармака из его файла плана

... фактически, вплоть до понимания достоинств структур над параллельными массивами на языке ассемблера 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

Вы можете избавиться от умножения, создав параллельный массив указателей на каждый элемент. У вас все еще есть две строки установки, которые не нужны для параллельных массивов, и вы все равно будете делать оставшуюся часть кода медленнее и больше. 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 монстров (и много бесплатных адресов zero page, это не должно быть большой проблемой)

в каждой новой ситуации (например, когда вы добираетесь до новой карты, входите в новое подземелье и т. д.), указатели нулевой страницы могут обновляться, чтобы указывать на монстров нового уровня.