Coding in C using the 65C02 CPU - Structure of Arrays versus Array of Structures

[svenvandevelde]

Hello all,

In this article I would like to spend some time with you on some C coding techniques, so that your C program uses the 65C02 CPU most efficiently. The principles outlined below also apply to other languages (probably). The subject of this thread is about how to combine arrays and structure C language constructs.

There are two distinguished ways how arrays and structures can be combined, which are known in the software world as Arrays of Structures (AoS) compared to Structure of Arrays (SoA) .

Please see below the following example:

Dia6.PNG (79.72 KiB) Viewed 4209 times

The above compares two different ways of how Arrays and Structures can be combined. On the left, the AoS variable is an Array of Structures.

The type definition struct_t only contains scalar data types, while in the variable declaration, AoS is dimensioned as an Array (of Structures). On the right side, you see the other alternative, where the SoA variable is a Structure of Arrays.

The type definition struct_t contains the arrays inside the struct (thus, a Structure of Arrays), with the variable declation of SoA being a simple structure declaration.

The initialization of the data contents between AoS and SoA is different, the AoS fills out the structure completely one by one, while the SoA fills out the field array completely within the structure.

As a result, observe the memory layout in the ligher boxes on the picture, how different the memory is arranged between AoS and SoA. Both variables have the same total size, but the bytes have a different order.

And this is very important regarding the 6502 CPU addressing modes. The 6502 supports various addressing modes, which you can find documentation on the X16 forums, and all over the internet, just google.

Since structures are addressed in a linear mode in memory, the most optimal addressing mode to be used are the absolute,x or absolute,y addressing modes (if possible). Of course, absolute,x or y addressing can only be used if the location of the structure is fixed in memory, otherwise indirect indexed addressing or other types of addressing could be used (indexed indirect or self modifying?).

However, indirect indexed addressing modes should be avoided as much as possible to my experience, as these constructs clutter code and also consume much more cycles, but more on that in an other post when we discuss pointers and further deep dive into this subject of AoS versus SoA.
Let us first compare how the C compiler generates the assembler, utilizing the AoS versus SoA variables, in a simple example below.

Dia7.PNG (87.46 KiB) Viewed 4209 times

The examples speak for itself, so let us focus on the resulting assembler, because there is a clear distinction! Note that in this example, both variables are addressed using the index variable, which is an 8-bit value (char).

This is important, since the 6502 absolute,x and absolute,y addressing modes require the x or y register to be populated with an 8-bit value. Using 16-bit index values to address arrays is possible, but through completely other assembler contructs (see in later post).

In the AoS case, the C compiler has chosen to use the x register for the absolute indexed addressing. Although this solution looks elegant, one can observe that the total assembler code required is a bit longer than the SoA variation. But more importantly, the "reach" of the x register to address the AoS array is far more limited than in the SoA case. The AoS variable can only address 51 elements  (256 divided by 5 bytes, floored), while the SoA variable is able to address each field individually,

- 128 elements, in case the field has a type containing 2 bytes, like pointers, int,

- 256 elements for 8 bit data types like char!

- 64 elements if your variable is a 4 bytes in size, like the type long ... (not recommended on 8bit computers).

This is a major distrinction. To create data structures for C programs using the 6502 CPU, the Structure of Arrays technique is a preferred technique, compared to Arrays of Structures.

Hopefully this topic is useful for others. Please leave your comments or remarks regarding this subject. If you have other ideas or other experiences you want to share about this topic, by all means, feel free to do so for others to pick this up and make better software for the X16.

I might edit this first post, and update the text here with your reference if the addition is very useful and adds to the subject.

Thanks,

Sven 

[rje]

If I understand correctly, then, software design on these 8-bit machines really does need to be "closer to the metal".

I've been programming C in a rather "normal" way -- if I need a structure, I define it, and if I've got an array of them in memory then I declare that as either a pointer or an array. So, an array of structures.

One thing I do not do is allocate or deallocate memory, unless I have absolutely no choice. Thus my structures are typically prebuilt, loaded into banked RAM, and I point a pointer to the starting element. I don't know if this improves my code's situation -- I suspect that it does not.

It sounds like the most effective way I can speed up code that must run fast, is to store data in single-type arrays; i.e. a structure of arrays.

I immediately think of my Core Wars implementation, which currently represents the core memory as an array of 5-byte structures. If changing this to a structure of arrays can speed up execution then that would be a good thing.

[kelli217]

If I understand correctly, then, software design on these 8-bit machines really does need to be "closer to the metal".

Absolutely. You can use high-level languages a bit more easily with some of the other major 8-bit CPUs of the day, since they have larger stacks and larger/more registers; the 6502 architecture is somewhat more limited. And the 65816 architecture has concessions to these considerations, as well.

[rje]

If I understand correctly, then, software design on these 8-bit machines really does need to be "closer to the metal".

Absolutely. You can use high-level languages a bit more easily with some of the other major 8-bit CPUs of the day, since they have larger stacks and larger/more registers; the 6502 architecture is somewhat more limited. And the 65816 architecture has concessions to these considerations, as well.

Yes. I already refrain from passing parameters when possible, relying on global data, and use unsigned chars all over the place. I admit I do still pass pointers, but you know.

[kelli217]

I admit I do still pass pointers, but you know.

One can hardly avoid that in C.