title: Advantages of arrays of structures over parallel arrays in 6502 assembly language?
body: <p>My understanding from writing a lot of 6502 back in the day is that parallel arrays are better than structures for storing data.</p>
  
  <p>Imagine you want to have a table of monster stats that in C would be defined something like this</p>
  
  <pre class="lang-c prettyprint-override"><code>struct Monster {
    unsigned char hitPoints;
    unsigned char damage;
    unsigned char shieldLevel;
    char* name;
  };
  </code></pre>
  
  <p>You could store it as an array of structures</p>
  
  <pre class="lang-c prettyprint-override"><code>static Monster s_monsters[] = {
    { 5,   1, 0, "orc", },
    { 50, 10, 5, "dragon", },
    { 10,  3, 1, "goblin", },
  };
  </code></pre>
  
  <p>Or you could store it as parallel arrays (usually using macros or tools to generate). Note: I'm showing the code in C but please imagine it's 6502 assembly.</p>
  
  <pre class="lang-c prettyprint-override"><code>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[] = { 
     &amp;m_orc_name &amp; 0xFF, 
     &amp;m_dragon_name &amp; 0xFF,
     &amp;m_goblin_name &amp; 0xFF, 
  };
  unsigned char Monster_nameHigh[] = { 
     &amp;m_orc_name &gt;&gt; 8 , 
     &amp;m_dragon_name &gt;&gt; 8,
     &amp;m_goblin_name &gt;&gt; 8, 
  };
  </code></pre>
  
  <p>In 6502, given an itemNdx you can access all the fields with parallel arrays like this</p>
  
  <pre><code>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
  </code></pre>
  
  <p>Where as if you use a struct instead of parallel arrays it becomes</p>
  
  <pre><code>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
  </code></pre>
  
  <p>The structure version has to compute the offset to each structure. In the case above that's 5 more instructions vs the parallel array version. On top of which the math for computing the offset is hand coded, meaning it has to be re-written anytime the size if a structure changes. On top of that you can only have a table of <code>256 / sizeof(Monster)</code> large. If you have more fields (20 to 30 is not uncommon), that would mean your tables could only have 8 to 12 entries where as with parallel arrays you can have 256 entries. One more advantage if if you want to iterate over the table. With parallel arrays you just increment x <code>inx</code>, one instruction. With structures you'd have to add sizeof(monster) which add only works with a would be</p>
  
  <pre><code> txa
   clc
   adc #sizeof(Monster)
   tax
  </code></pre>
  
  <p>That's 3 more instructions than the parallel arrays version.</p>
  
  <p>That seems like parallel arrays are an objective win for 6502 assembly language but there's this obscure comment by John Carmack from <a href="https://raw.githubusercontent.com/ESWAT/john-carmack-plan-archive/master/by_day/johnc_plan_19980204.txt" rel="nofollow noreferrer">his plan file</a></p>
  
  <blockquote>
    <p>... actually, all the way back to understanding the virtues of structures over parallel arrays in apple II assembly language.. ...</p>
  </blockquote>
  
  <p>Does anyone know what those advantages are?</p>
  
  <p>The only advantages I can think of off the top of my head is that it's easier to allocate a dynamic array with arrays of structs but most games didn't allocate anything back in 6502 days. They hardcoded fixes sized arrays of memory so that doesn't seem like that can be it. 6502 didn't have a cache either so there's no cache advantage. </p>
  
  <p>Also you can address more than 256 items if you go full on pointers but full on pointers are <strong>much</strong> slower and require <strong>much</strong> more code than either of the methods shown above therefore they are usually options of last resort. </p>
  
  <pre><code>; setup pointer
  lda itemNdx
  ldx #sizeof(Monster)
  jsr multiplyAX       ; 8-&gt;16 bit multiply is around 70 cycles result in A(low), X(high)
  clc
  adc #s_monster &amp;&amp; 0xFF
  sta POINTER
  txa
  adc #s_monster &gt;&gt; 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
  </code></pre>
  
  <p>You could get rid of the multiply by making a parallel array of pointers to each item. You'd still have 2 lines of setup that are not needed for parallel arrays and you'd still be making the rest of the code slower and larger. 8 cycles per access vs 5 and 5 bytes per access vs 3.</p>
  
  <p>Basically you would only use pointers if you absolutely have to. If you can choose parallel arrays then it seems like you should always choose them.</p>