Why C isn't a good fit for 6502

You can talk about almost anything that you want to on this board.

Moderator: Moderators

Post Reply
CrowleyBluegrass
Posts: 42
Joined: Sun Jun 30, 2013 7:59 am

Why C isn't a good fit for 6502

Post by CrowleyBluegrass »

Hi! Hope this is the right place. I'm not sure it's quite NES-specific enough to belong in general. If it is, apologies for requiring the move!

Why is it that (I'm speaking with no experience here, just from what I've remembered reading here and there) C is not a good fit for 6502 programming? People often praise C for how "close to the metal" it is, but I suppose that's just one kind of metal? :) (https://queue.acm.org/detail.cfm?id=3212479)

Is it related to how C (and most other procedural languages, higher or lower level) deal with the stack? is the 6502 stack insufficient? I remember reading something regarding a "virtual stack" on the 6502, but admittedly the majority went over my head.

Or is it related to the fact that, relatively speaking, there really isn't a "market" for an optimized C-to-6502 compiler?

I'm not a systems programmer, nor an assembly programmer, and I'm only a passable C programmer! So please forgive my ignorance, but I am for some reason particularly curious in regards to this topic. Hopefully you knowledgeable folks on here are prepared to humor me and give me your thoughts.

Those are the two things that popped into my mind, but I'm very curious to know the thoughts of you on here.

Thank you! :)
User avatar
Bregalad
Posts: 8056
Joined: Fri Nov 12, 2004 2:49 pm
Location: Divonne-les-bains, France

Re: Why C isn't a good fit for 6502

Post by Bregalad »

There's many reasons, one of those is that in standard ANSI C "int" is at least 16-bits by default, and even when working with 8-bit variables (declared "unisgned char" or similar) they are promoted to "int" for mathematical and logical operations.
So even if you have code as simple as.

Code: Select all

unsigned char a, b, c;
a = b+c;         // This is a 16-bit operation, the result will be truncated in 8 bits
Theoretically ANSI C reuqires promoting b and c to 16-bit, then doing a 16-bit addition, then taking the lower 8 bits and putting the result in a. Of course in this case the addition of the upper 16 bits can be optimized out by the compier, but it shows just how complex a simple operation is.

Another huge problem is that all variables are, by default, on the stack. The 6502 has very weak access to hardware stack : only PHA/PLA instructions, or combined TSX and normal operations on $100,X. Reserving 1/3 of the processor's register for stack access isn't very optimal, and is never going to produce optimal code.
You can implement a software stack, and that's what CC65 does, but the problem is exactly the same; 1/3 of the registers are eaten by the stack, and this will hardly ever produce optimal or even sufficiently fast/short code.
User avatar
Dwedit
Posts: 4924
Joined: Fri Nov 19, 2004 7:35 pm
Contact:

Re: Why C isn't a good fit for 6502

Post by Dwedit »

You really need a pass where you generate a call graph, and come up with fixed memory addresses for all variables in the functions. Recursive functions still need a stack.
Here come the fortune cookies! Here come the fortune cookies! They're wearing paper hats!
User avatar
Bregalad
Posts: 8056
Joined: Fri Nov 12, 2004 2:49 pm
Location: Divonne-les-bains, France

Re: Why C isn't a good fit for 6502

Post by Bregalad »

Dwedit wrote:You really need a pass where you generate a call graph, and come up with fixed memory addresses for all variables in the functions. Recursive functions still need a stack.
And compilers that have provisions for such a pass are sparse. There's also function pointers which basically defeats this optimization entirely (or at least, greatly).
User avatar
rainwarrior
Posts: 8732
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: Why C isn't a good fit for 6502

Post by rainwarrior »

Another problem:

The only "fast" way to index an array on the 6502 is if the index is 8-bit (fits in a register) and the data is also 8-bit. i.e. the machine is only capable of efficiently looking up a byte that is less than 256 bytes away from the start of the array.

16-bit or larger types are hard to access efficiently at all, since even an 8-bit integer has to be multiplied by 2, promoting it to at least 9 bits wide. This means we can't use efficient indexing instructions, and have to instead calculate a pointer and use indirection (see: 6502 addressing modes).

In assembly, what you'd probably want to do is split a 16-bit array into two 8-bit arrays, but C doesn't really have any natural way to specify that in data types. It's allowed to pad, but not really allowed to drastically rearrange the memory layout like this. Inline functions to access the array might help you do it manually, if your compiler can optimize the access effectively, but there isn't really a way to directly specify this behaviour in natural C.


In theory I think you could get around this if you defined your C language variant with a new 7-bit type, that you could multiply by 2 once before breaking the index size restriction (...and/or 6-bit type for 32-bit access, etc.) which could limit the size of the efffective index enough to fit in the 1 byte index register. These of course would limit your array length to 128 or 64 entries, or fewer.

Alternatively you could come up with an extension to specify striped arrays. This would be more ideal, and always allow up to 256 entries to be accessed efficiently. (Consider arrays of structures as well, though this could get very complex.)

Both of these theoretical extensions would probably be difficult to reconcile with most other C implementations though. You'd have custom types or specifiers peculiar to this implementation.
tepples
Posts: 22708
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Why C isn't a good fit for 6502

Post by tepples »

One thing making idiomatic C not best suited for the 6502 is that the 6502's "absolute indexed" addressing mode prefers a structure of arrays rather than an array of structures. Another thing is a lack of a 24-bit data type, which can prove inconvenient in a scrolling game where you need both subpixel movement and a range larger than 256 pixels, though there are (sometimes complex) ways around this.

This is an array of structures:

Code: Select all

#define NUM_ACTORS 8
typedef struct Actor {
  unsigned char actor_y_subpixel;
  unsigned char actor_y_lo;
  unsigned char actor_y_hi;
  unsigned char actor_x_subpixel;
  unsigned char actor_x_lo;
  unsigned char actor_x_hi;
  signed short actor_dy;
  signed short actor_dx;
} Actor;
Actor actors[NUM_ACTORS];
This is the equivalent structure of arrays:

Code: Select all

#define NUM_ACTORS 8
unsigned char actor_y_subpixel[NUM_ACTORS];
unsigned char actor_y_lo[NUM_ACTORS];
unsigned char actor_y_hi[NUM_ACTORS];
unsigned char actor_x_subpixel[NUM_ACTORS];
unsigned char actor_x_lo[NUM_ACTORS];
unsigned char actor_x_hi[NUM_ACTORS];
unsigned char actor_dy_subpixel[NUM_ACTORS];
signed char actor_dy[NUM_ACTORS];
unsigned char actor_dx_subpixel[NUM_ACTORS];
signed char actor_dx[NUM_ACTORS];
Related reading: ISSOtm's article about why C isn't a good fit for the Game Boy and Game Boy Color either
User avatar
slembcke
Posts: 172
Joined: Fri Nov 24, 2017 2:40 pm
Location: Minnesota

Re: Why C isn't a good fit for 6502

Post by slembcke »

Counterpoint: cc65 can be "good enough" if you regularly read through the generated assembly and fix the worst inefficiencies. It still won't be optimal in speed or size, but it makes it pretty easy to see when your 8 bit values are being promoted to 16 bit. It's a lot easier to make progress with something higher level than assembly (few would argue that), and you can always rewrite and optimize after you know what you want to do.

Many games don't need all the CPU time or ROM space anyway, and it goes to waste if you aren't using it. I enjoy writing some fun bits in assembly, but implementing the layout/flow of the menus is tedium I barely want to do in C. ;)
User avatar
rainwarrior
Posts: 8732
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: Why C isn't a good fit for 6502

Post by rainwarrior »

I suppose, however, that if the size of the array is known to the translation unit, and the total array fits within 256 bytes, the compiler should be allowed to optimize this to an 8-bit index, since out of bounds is "undefined behaviour" anyway. That at least would require no extensions of the language.

Edit: Decided to make that suggestion on CC65's github.


One thing about this question is that a lot of the actual problems with C on the 6502 is just that the particular 6502 C compiler most people here are familiar with has very little optimization capability, and is an open source volunteer project with no active goal to improve that. The real world problems of CC65 are a bit broader in scope than the theoretical problems with C and the 6502.
Last edited by rainwarrior on Mon Dec 03, 2018 8:06 pm, edited 1 time in total.
User avatar
Banshaku
Posts: 2417
Joined: Tue Jun 24, 2008 8:38 pm
Location: Japan
Contact:

Re: Why C isn't a good fit for 6502

Post by Banshaku »

Depending what you do, it can be just fine. One have just to look at the games made by na_th_an and shiru to see that it's all possible if done in the limit of was is fine to do in 6502. As long that you are not using the standard library and write in ASM code that is time critical, I don't see why you shouldn't use it.

Like mentioned above, it was a time saver to write menu code (I wouldn't want to write such code in asm, waste of time!). As long you are aware that even though you use only the basics, some part of the runtime is still required then you are fine.
User avatar
dougeff
Posts: 3079
Joined: Fri May 08, 2015 7:17 pm

Re: Why C isn't a good fit for 6502

Post by dougeff »

the particular 6502 C compiler most people here are familiar with has very little optimization capability
A person skilled at 6502 asm should be able to optimize as needed.

Many of the mundane game states, like a title screen, or a menu, don't need to be optimized, and are twice as fast to program in C.
nesdoug.com -- blog/tutorial on programming for the NES
User avatar
gauauu
Posts: 779
Joined: Sat Jan 09, 2016 9:21 pm
Location: Central Illinois, USA
Contact:

Re: Why C isn't a good fit for 6502

Post by gauauu »

dougeff wrote:
the particular 6502 C compiler most people here are familiar with has very little optimization capability
A person skilled at 6502 asm should be able to optimize as needed.

Many of the mundane game states, like a title screen, or a menu, don't need to be optimized, and are twice as fast to program in C.
For a lot of games, even a lot of the less mundane parts are fine in C, as long as the tight inner loops or slower array accesses are assembly. And (in my opinion) more importantly than twice as fast to program, they're twice as easy to read and modify later.
User avatar
Banshaku
Posts: 2417
Joined: Tue Jun 24, 2008 8:38 pm
Location: Japan
Contact:

Re: Why C isn't a good fit for 6502

Post by Banshaku »

If only prototyping, start in C then later you can optimize in ASM. Depending of the game most of it can be done in C too.
Post Reply