It is currently Sun Dec 09, 2018 5:05 pm

All times are UTC - 7 hours





Post new topic Reply to topic  [ 18 posts ]  Go to page 1, 2  Next
Author Message
PostPosted: Fri Jun 22, 2018 8:00 pm 
Offline
User avatar

Joined: Tue Jun 24, 2008 8:38 pm
Posts: 2118
Location: Fukuoka, Japan
I remember reading somewhere that using an array of structures is not a good idea but don't remember why it was such a case. Is it really that bad?

For example, let say that I want to keep in a structure all the information about a specific animation. I could be something like this (code may contain mistakes since it is written in the post without testing):
Code:
typedef struct {
   const unsigned char someAttribute1;     // example of extra data
   const unsgined char someAttribute2;
   const unsigned char frameCount[];        // list for how long are each frame, 0 is end of list
   const unsigned char* const frameList[]; // list of frames
} animInfo_t;

...

animInfo_t heroAnimList[] = { .. some list here ... };

This way I could retrieve a pointer to this group of information like this:
Code:
if ( state == STANDING) {
    hero.anim = &heroAnimList[STANDING];
... // will continue next "code" tag

Then once the state change, I would retrieve from that struct the pointers for the animList, value from frameCount at proper index and save them to avoid accessing that structure many time:
Code:
     // retrieve first frame
     hero.frame.maxCount = hero.anim->frameCount[0];
     hero.frame.current = hero.anim->frameList[0];
}

So I do not access the array of structure on every frame change but just when the state change. And I keep a reference to the current frame to avoid accessing the other list in anim on every frame to reduce access to arrays of arrays.

I'm aware that right now that structure is maybe complicated. Since I'm experimenting on how I can write code (and enjoying it) the final result may be quite different based on the hurdle I will encounter when using it. Still, any new nes code I write is time I was able to spent on it and learn it so I'm more than happy with that. This is how I was able to make my makeFile that automatically takes any files in any folder in your target without the need to define them one by one and automatically set the include path on all the files so you don't need to write the relative path on every include, which is quite useful. I learned a lot from it.


Top
 Profile  
 
PostPosted: Fri Jun 22, 2018 8:28 pm 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 7005
Location: Canada
The parallel alternative to an array of structures is the "structure of arrays" paradigm.
Code:
struct
{
   char a[50];
   char b[50];
} object_t;

object_t objects;

// accessing:
return objects.a[5];

Accessing syntax is almost the same, you've just moved the braces a little bit.

Why is array of structures bad? To resolve an index to an actual pointer, you need to multiply that index by the size of the structure. On x86 this isn't that bad, there's a lot of instruction modifiers that do this very easily, but on 6502 not so much. (There are a lot of modern cases where this applies too, e.g. cache coherence.)

In cc65... well, arrays in general do not perform that well. Part of the problem is that it doesn't usually try to use 8-bit indices, which is usually the ideal way to access arrays on 6502. Array of structures just adds one more step in the chain of inefficiencies here.

Ideally you would want to break up arrays of 16 bit integers into two stripes of 8 bit arrays, too, but this becomes really inconvenient to implement in C. Macros might help a little with this, but you'd have to do a bit of work to figure out how to make it play nicely with the compiler.

Of course, an array of structures often has convenience. Mostly because it's the more prevalent paradigm elsewhere, and maybe feels more "natural" especially with object oriented thinking, or in cases where you do serial access of the data. (Your thought about creating a temporary pointer to the currently indexed structure could help a lot, you'd only do the indexing once.) If you don't have a performance issue with the data, you might not need to optimize your structures anyway.


Top
 Profile  
 
PostPosted: Sat Jun 23, 2018 3:49 am 
Offline
User avatar

Joined: Sat Sep 07, 2013 2:59 pm
Posts: 1764
As a little simplification, think about this:

If you have an array of a struct and you do this:
Code:
structVar[i].Data = 5;

then the compiler needs to do this:

1. Get the address of structVar.

2. Multiply i * sizeof(MyStruct).
(Unless the size of the struct is exactly 2, 4, 8, 16, 32 etc., a multiplication is expensive.)

3. Add this value to the address.

4. Add Offset_Data to this new address value.


But if you have a struct with a bunch of arrays and you do this:
Code:
structVar.Data[i] = 5;

then the compiler just needs to do this:

1. Get the address of structVar + Offset_Data.
(The offset is known at compile time, so the sum of the addition is calculated at compile time as well, so this is just one value here and takes exactly as much CPU time and ROM space as point 1 from above and is not like point 4.)

2. Add i to this address.
(Actually, i * sizeof(Data), but if Data is a normal variable like int, long or double, it will be multiplied by 2, 4 or 8 which is just a shift left of 1, 2 or 3 which is cheap and not like a full blown multiplication).


As you see, the second version is much shorter and has no expensive multiplication in it.

_________________
Available now: My game "City Trouble".
Website: https://megacatstudios.com/products/city-trouble
Trailer: https://youtu.be/IYXpP59qSxA
Gameplay: https://youtu.be/Eee0yurkIW4
German Retro Gamer article: http://i67.tinypic.com/345o108.jpg


Top
 Profile  
 
PostPosted: Sat Jun 23, 2018 9:55 am 
Offline
User avatar

Joined: Tue Jun 24, 2008 8:38 pm
Posts: 2118
Location: Fukuoka, Japan
@rainwarrior

Regarding performance, I think it will depends how many times an animation state would change. If the animation change rarely then the array of structure is just a list which is more structured and as long that you don't do any indexing directly on it (keep a reference in another pointer) then it should reduce the performance hit.

If it is too heavy then I will just keep the original idea, which is an array per attribute (animation list, frame count, custom attribute) and based on the state retrieve all values at that index. This is what I had in mind first but I want to test how far I can structure it.

@DRW

This is the part that I was concerned about. If you do indexing directly on complex structure that are not of size of a power of 2, it would be an issue and it's not sure the compiler would be able to optimize on that case automatically.

I will keep you idea in mind for structuring data (a struct with arrays inside) and now my memory was refreshed on what could be common problem about struct of array.

Like mentioned above, I would like to keep a complex structure in a list and when needed, save a pointer about it to avoid indexing on each access. I guess I will need to judge how much convenience vs performance I'm ready to trade based on the needs of each project.


Top
 Profile  
 
PostPosted: Sat Jun 23, 2018 11:16 am 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 7005
Location: Canada
Banshaku wrote:
as long that you don't do any indexing directly on it (keep a reference in another pointer) then it should reduce the performance hit

Yes, like you suggested in your OP, if you make a pointer to the indexed structure once when you start using it and then just use that pointer it will mitigate most of the problem.

The structure of arrays really shines in assembly, moreso than in C. When you can guarantee the index is only 8-bit, and write code that uses absolute indexed addressing instead of indirection through a pointer, this is the optimal case. It's not very easy to get CC65's C to do this, though, often its array access will end up being through a pointer anyway. (In many cases the compiler will assume indices are 16-bit, unfortunately. Explicitly converting your index to an unsigned char can help.)

Banshaku wrote:
This is the part that I was concerned about. If you do indexing directly on complex structure that are not of size of a power of 2, it would be an issue and it's not sure the compiler would be able to optimize on that case automatically.

Power of 2 are better, but even if it is a power of 2 it creates a lot of extra work. Like a struct of size 32 will incur 5 16-bit shifts before it can add the index to the pointer. With structure of arrays the index just adds directly.


Edit: BTW C compilers are allowed to pad structures, and padding to a power of 2 is a common optimization they are allowed to do. Not sure if CC65 does this, but probably not.


Last edited by rainwarrior on Sat Jun 23, 2018 11:34 am, edited 2 times in total.

Top
 Profile  
 
PostPosted: Sat Jun 23, 2018 11:29 am 
Offline
User avatar

Joined: Sat Sep 07, 2013 2:59 pm
Posts: 1764
Banshaku wrote:
Like mentioned above, I would like to keep a complex structure in a list and when needed, save a pointer about it to avoid indexing on each access.

This wouldn't really help you that much because the pointer access itself already has a bunch of overhead every time you use it:

Code:
pMyStruct = &ListOfStructs[i];
...
pMyStruct->Value = Something;
...
pMyStruct->OtherValue = SomethingElse;

Don't think just because you use a pointer, this is now as performant as if you accessed a single struct object directly. Pointers have their own overhead:

- Read the value (which is an address) that is stored in the pointer.
- Put the offset for "Value" to the Y register.
- Use indirect access to (value of pointer) + Y.

- Read the value (which is an address) that is stored in the pointer.
- Put the offset for "OtherValue" to the Y register.
- Use indirect access to (value of pointer) + Y.

If I'm not mistaken, this happens for every single access of every variable from that struct. Pointer access basically means dynamically calculating an address every single time you need it.

In comparison to a struct of arrays:
Code:
MyStruct.Values[i] = Something;
...
MyStruct.OtherValues[i] = SomethingElse;

- Put the offset for "Values" to the Y register.
- Use direct access to (Address of "Values") + Y.

- Put the offset for "OtherValues" to the Y register.
- Use direct access to (Address of OtherValues) + Y.

If you cannot access data statically (like in: Player character always has index 0, opponent A always has index 1 etc.), your best bet is to use an array that is as big as the largest amount that the array can have. And then simply access this array directly, with an index.
(Whether you put a bunch of arrays into a struct or whether you declare them separately is just coding style.)
Every kind of access through a pointer is really the worst version.

_________________
Available now: My game "City Trouble".
Website: https://megacatstudios.com/products/city-trouble
Trailer: https://youtu.be/IYXpP59qSxA
Gameplay: https://youtu.be/Eee0yurkIW4
German Retro Gamer article: http://i67.tinypic.com/345o108.jpg


Top
 Profile  
 
PostPosted: Sat Jun 23, 2018 2:33 pm 
Offline

Joined: Mon May 27, 2013 9:40 am
Posts: 499
Slightly off topic and ugly, but whenever I need to use a lot of arrays a lot (for example, when handling enemies) I usually begin each loop by copying the current element of each array to a set of equivalent variables in ZP using inline assembly, do all my fiddling using the temporal variables, and end up updating the arrays with the new data using inline assembly too. The gain in space and speed is huge, specially if you are doing lots of stuff with the arrays. It saves literally hundreds of bytes in most cases, as most of my arrays are of 8 bit data indexed by 8 bit indexes.

For example, check enems_load and enems_move here https://github.com/mojontwins/MK1_NES/b ... enengine.h

_________________
http://www.mojontwins.com


Top
 Profile  
 
PostPosted: Sat Jun 23, 2018 2:39 pm 
Offline
User avatar

Joined: Sat Sep 07, 2013 2:59 pm
Posts: 1764
That's what I'm doing in the moment as well, for variables that are often used, like x and y position etc.
But you shouldn't do this for everything. If you only read and write the array entry once or twice per frame, it might not pay off.
But in general, yes: Cache your character's variables to temporary global zeropage variables and write them back later. This saves ROM space and CPU time.

_________________
Available now: My game "City Trouble".
Website: https://megacatstudios.com/products/city-trouble
Trailer: https://youtu.be/IYXpP59qSxA
Gameplay: https://youtu.be/Eee0yurkIW4
German Retro Gamer article: http://i67.tinypic.com/345o108.jpg


Top
 Profile  
 
PostPosted: Sat Jun 23, 2018 3:29 pm 
Offline

Joined: Mon May 27, 2013 9:40 am
Posts: 499
I do a lot of trial and error and try to find the situations when this is an advantage, of course. It's not an "always do" trick from the hat.

_________________
http://www.mojontwins.com


Top
 Profile  
 
PostPosted: Sat Jun 23, 2018 4:30 pm 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 20848
Location: NE Indiana, USA (NTSC)
I imagine that on an ISA that does all indexed addressing in software, such as 8080 or LR35902, copying a struct in and out of RAM is even more likely to pay off than on 6502.


Top
 Profile  
 
PostPosted: Sat Jun 23, 2018 8:47 pm 
Offline
User avatar

Joined: Tue Jun 24, 2008 8:38 pm
Posts: 2118
Location: Fukuoka, Japan
@rainwarrior

My guess too is that cc65 doesn't support the padding. For now with all the comments in this thread I may try to avoid pushing for array of structs because of the overhead.

@DRW

If the C compiler does have to prepare the address on every access then yes it would be an issue. I remember reading something on the cc65 site that based on the order you write your code, it may minimize those kind of issues but I'm not sure if it applied for struct though.

I think when in doubt, when like I was not sure for my struct that ended in DATA, the best thing is to look at the resulting .s file and see what is exactly done.

@na_th_an

I remember in my previous samples that I did put some specific variable in ZP to reduce the impact, especially when retrieving meta-meta tiles for the background but this was when I was doing it purely in assembler. For C, I will need to check how it works. I guess intensive data processing like for the map data should stay in assembler anyway since there it is just data processing, not real logic like for the entities.

@tepples

Interesting comment but I think we don't need to worry about those CPU when doing nes programming :)


Top
 Profile  
 
PostPosted: Sat Jun 23, 2018 8:59 pm 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 7005
Location: Canada
Banshaku wrote:
My guess too is that cc65 doesn't support the padding. For now with all the comments in this thread I may try to avoid pushing for array of structs because of the overhead.

Well, most compilers have a #pragma pack to use when you don't want the compiler to rearrange your structs.

I don't think CC65 makes any attempt to pad structs (when memory is more scarce than cycles and there's no alignment issues, there's not much reason to), but you can easily add padding variables of your own to meet a power of 2 if you think it's worth trading the space for. (Or maybe you can even use the padded space for a different array.)


Top
 Profile  
 
PostPosted: Sat Jun 23, 2018 9:46 pm 
Offline
User avatar

Joined: Tue Jun 24, 2008 8:38 pm
Posts: 2118
Location: Fukuoka, Japan
I did a quick check in the doc and cc65 doesn't seems to have such pragma so you would have to do it manually. I will keep that in mind. Thanks!


Top
 Profile  
 
PostPosted: Sun Jun 24, 2018 1:14 pm 
Offline

Joined: Mon May 27, 2013 9:40 am
Posts: 499
Banshaku wrote:
I remember in my previous samples that I did put some specific variable in ZP to reduce the impact, especially when retrieving meta-meta tiles for the background but this was when I was doing it purely in assembler. For C, I will need to check how it works. I guess intensive data processing like for the map data should stay in assembler anyway since there it is just data processing, not real logic like for the entities.


You are right. Now that I'm getting more fluent of assembly, I think it's time to move all my background data processing to assembly.

_________________
http://www.mojontwins.com


Top
 Profile  
 
PostPosted: Sun Jun 24, 2018 6:11 pm 
Offline
User avatar

Joined: Tue Jun 24, 2008 8:38 pm
Posts: 2118
Location: Fukuoka, Japan
Unless you have performance issues I think there is no rush to do so. Your games are already awesome the way they are :)

The more you move data processing on the asm side, the mode you will want to avoid parameter to the function, the more you will have to program with some compromise and it will look less like C. Still, I guess it is something that must be done on a project per project basic. I'm still trying to visualize how I would you some of the code I wrote 8 years ago without passing parameter from the C side and how much it would be worth it. I guess you need some specific extern from the ZP that will alows to set state that these functions will react to.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 18 posts ]  Go to page 1, 2  Next

All times are UTC - 7 hours


Who is online

Users browsing this forum: zeroone and 6 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group