Garbage Collector for CC65

Discuss technical or other issues relating to programming the Nintendo Entertainment System, Famicom, or compatible systems. See the NESdev wiki for more information.

Moderator: Moderators

JohnDoom
Posts: 20
Joined: Sun Sep 11, 2011 1:00 am

Garbage Collector for CC65

Post by JohnDoom »

:D Hi there, it's been a while! I've succesfully programmed a garbage collector in C for CC65 and thought of sharing my work with you.

It's very easy to use:
- include "memory.c" and "memory.h" in your project;
- call "MemoryStart" in "main" to initialize the GC;
- use "MemoryAlloc" instead of "malloc" to get memory (you don't need to use "free" anymore).

Makes use of most of the 8KB RAM area (the rest is for global variables as usual) and calls "MemoryClean", a "mark & sweep" algorithm, when memory is full. I won't claim this is "zero-overhead", in fact there's a slight lag when the algorithm is called, but it does work for CC65 and the NES, compared to other libraries on the internet. You can also manually call MemoryClean whenever you want, for example during scene change, to manually free unused memory.

I've attached the testing example I worked on, so you can give it a shot too!

memory.h:

Code: Select all

#ifndef MEMORY_H
#define MEMORY_H

#include "stdfx.h"

void MemoryStart();
void* MemoryAlloc(size_t size);
void MemoryClean();

#endif
memory.c:

Code: Select all

#include "memory.h"

#define STACK_MIN 0x0500
#define STACK_MAX 0x0800
#define RAM_MIN 0x6000
#define MEMORY_MIN 0x6100
#define MEMORY_MAX 0x8000

typedef struct
{
	void* ptr;
	size_t size;
	void* next;
	bool marked;
} MemoryObject;

MemoryObject* memoryList = NULL;

void MemoryDeleteByPrevious(MemoryObject* previous)
{
	MemoryObject* current;

	if(previous != NULL)
	{
		current = previous->next;
		previous->next = current->next;
	}
	else
	{
		current = memoryList;
		memoryList = current->next;
	}

	free(current->ptr);
	free(current);
}

void MemoryMarkArea(void* start, void* finish)
{
	void** ptr;
	MemoryObject* object;

	for(ptr = start; ptr < finish; ptr++)
	{
		if(*ptr < (void*)MEMORY_MIN || *ptr >= (void*)MEMORY_MAX) continue;

		object = memoryList;
		while(object != NULL)
		{
			if(object->marked == false && *ptr == object->ptr)
			{
				object->marked = true;
				MemoryMarkArea(object->ptr, (void*)((size_t)object->ptr + object->size));
				break;
			}

			object = object->next;
		}
	}
}

void MemoryMark()
{
	MemoryMarkArea((void*)STACK_MIN, (void*)STACK_MAX);
	MemoryMarkArea((void*)RAM_MIN, (void*)MEMORY_MIN);
}

void MemorySweep()
{
	MemoryObject* previous;
	MemoryObject* current;

	previous = NULL;
	current = memoryList;
	while(current != NULL)
	{
		if(current->marked == false)
		{
			MemoryDeleteByPrevious(previous);

			current = (previous != NULL) ? previous->next : memoryList;
		}
		else
		{
			current->marked = false;

			previous = current;
			current = current->next;
		}
	}
}

void MemoryClean()
{
	MemoryMark();
	MemorySweep();
}

void MemoryAdd(MemoryObject* object, MemoryObject* previous, MemoryObject* current)
{
	if(current != NULL)
	{
		MemoryAdd(object, current, current->next);
	}
	else
	{
		current = object;
		current->next = NULL;
		current->marked = false;

		if(previous != NULL) previous->next = current;
		else memoryList = current;
	}
}

void* MemoryAlloc(size_t size)
{
	void* ptr = NULL;
	MemoryObject* object = NULL;
	MemoryObject* previous = NULL;
	MemoryObject* current = NULL;

	while(true)
	{
		ptr = malloc(size);
		if(ptr == NULL) MemoryClean();
		else break;
	}

	while(true)
	{
		object = malloc(sizeof(MemoryObject));
		if(object == NULL) MemoryClean();
		else break;
	}

	current = memoryList;
	while(current != NULL)
	{
		previous = current;
		current = current->next;
	}
	current = object;
	current->ptr = ptr;
	current->size = size;
	current->next = NULL;
	current->marked = false;

	if(previous != NULL) previous->next = current;
	else memoryList = current;

	return ptr;
}

void MemoryStart()
{
	_heapadd ((void*)MEMORY_MIN, MEMORY_MAX - MEMORY_MIN);
}
Attachments
memory.zip
(8.76 KiB) Downloaded 48 times
Oziphantom
Posts: 1565
Joined: Tue Feb 07, 2017 2:03 am

Re: Garbage Collector for CC65

Post by Oziphantom »

I have to ask... why?
JohnDoom
Posts: 20
Joined: Sun Sep 11, 2011 1:00 am

Re: Garbage Collector for CC65

Post by JohnDoom »

Oziphantom wrote: Sun Mar 05, 2023 7:15 am I have to ask... why?
Safer and more efficient memory usage to develop bigger games?
Oziphantom
Posts: 1565
Joined: Tue Feb 07, 2017 2:03 am

Re: Garbage Collector for CC65

Post by Oziphantom »

I suppose if you are making a KOEI simulation style game, then maybe you could get away with it.
User avatar
Jarhmander
Formerly ~J-@D!~
Posts: 569
Joined: Sun Mar 12, 2006 12:36 am
Location: Rive nord de Montréal

Re: Garbage Collector for CC65

Post by Jarhmander »

It can make sense if one makes a game with a somewhat lightweight scripting engine. Ideally, the garbage collector should run frequently with small collection steps so it is quick to run in the general case that the scripting engine doesn't generate more garbage than the collector can collect. The scripting engine's VM itself could be made to run a certain maximum number of opcodes per frame to limit its cost in CPU time, so the rest of the game engine (in native code!) could run reliably.

The thing is, what kind of game would benefit more for using such a scripting engine vs what it costs? Maybe RPGs, but with the limited memory of the NES would limit severely what one could achieve with such otherwise powerful tools. SNES games on the other hand would be an excellent target IMHO. The segmented RAM is a pain to work with, and the scripting engine could abstract nicely the RAM memory layout, and there's plenty of it.
((λ (x) (x x)) (λ (x) (x x)))
User avatar
Quietust
Posts: 1920
Joined: Sun Sep 19, 2004 10:59 pm
Contact:

Re: Garbage Collector for CC65

Post by Quietust »

I have to wonder, though - how much CPU/RAM overhead is taken up merely by supporting dynamic allocation in the first place, let alone supporting garbage collection on top of that? I suppose this might be useful on a Commodore 64, but on an NES where you've only got 2KB of builtin RAM (minus the zeropage, stack, and another page for sprites) and maybe an extra 8KB on the cartridge, a few bytes here and there can add up to quite a lot, and when all you've got is ~1.8MHz you might quickly find yourself running out of time to finish running your game logic.
Last edited by Quietust on Sun Mar 05, 2023 1:56 pm, edited 1 time in total.
Quietust, QMT Productions
P.S. If you don't get this note, let me know and I'll write you another.
Drag
Posts: 1615
Joined: Mon Sep 27, 2004 2:57 pm
Contact:

Re: Garbage Collector for CC65

Post by Drag »

I'll bet something like this would be very useful on something like the C64, like if you wanted to make an adventure game that relied more heavily on a scripting engine, and that's something a computer-like platform is perfect for. :D

It could work on the NES too, because we have games like Maniac Mansion, Princess Tomato in Salad Kingdom, and Famicom Detective Club, all of which are adventure games which don't entirely need to be action oriented, so they can spare more resources towards a scripting engine's features (such as a GC). Though admittedly, those games are more niche on the NES compared to more actiony games. :P

Just-before-posting-edit: Quietust ninja'd me on mentioning the C64. :P
creaothceann
Posts: 611
Joined: Mon Jan 23, 2006 7:47 am
Location: Germany
Contact:

Re: Garbage Collector for CC65

Post by creaothceann »

Genesis too.
My current setup:
Super Famicom ("2/1/3" SNS-CPU-GPM-02) → SCART → OSSC → StarTech USB3HDCAP → AmaRecTV 3.10
JohnDoom
Posts: 20
Joined: Sun Sep 11, 2011 1:00 am

Re: Garbage Collector for CC65

Post by JohnDoom »

I've coded all day long to make this new demo: almost everything is dynamically allocated and the game doesn't lag at all, in fact memory usage is under control thanks to pooling and the GC isn't called once. This proves you can make action games with GC without performance hits. If I were to add another scene to the game, I would then free the memory by calling the GC and reuse it for whatever comes next, in a safe way and without being constricted by static variables :D
P.S.: I've removed the extra 8KB RAM, the GC is currently using only the $0500-$0800 memory area!
Attachments
memory.zip
(40.75 KiB) Downloaded 26 times
User avatar
jeffythedragonslayer
Posts: 344
Joined: Thu Dec 09, 2021 12:29 pm

Re: Garbage Collector for CC65

Post by jeffythedragonslayer »

Oziphantom wrote: Sun Mar 05, 2023 7:15 am I have to ask... why?
To encourage Java developers to pick up NES dev. :p
vbc
Posts: 72
Joined: Sun Jun 21, 2020 5:03 pm

Re: Garbage Collector for CC65

Post by vbc »

JohnDoom wrote: Sun Mar 05, 2023 5:12 am It's very easy to use:
- include "memory.c" and "memory.h" in your project;
- call "MemoryStart" in "main" to initialize the GC;
- use "MemoryAlloc" instead of "malloc" to get memory (you don't need to use "free" anymore).
I only had a very short look at the code, but I would have some concerns:
  1. I think your alloc code does not account for the case that the memory object structure cannot be allocated.
  2. Your mark algorithm seems to assume that you always keep a pointer to the start of each allocated block. A pointer with an offset will not suffice.
  3. Your mark algorithm seems to assume pointers are 16bit aligned which on the 6502 they usually are not.
  4. Any data that happens to match an object pointer will keep an unused block from ever being freed.
1. is an easy fix. 2. can be avoided if the user is told about it. 3. can be fixed but will increase the likelihood of 4. which is the biggest problem. It may work in some cases, but it does not seem to be reliable and predictable.
JohnDoom
Posts: 20
Joined: Sun Sep 11, 2011 1:00 am

Re: Garbage Collector for CC65

Post by JohnDoom »

vbc wrote: Mon Mar 06, 2023 7:10 am I only had a very short look at the code, but I would have some concerns:
  1. I think your alloc code does not account for the case that the memory object structure cannot be allocated.
  2. Your mark algorithm seems to assume that you always keep a pointer to the start of each allocated block. A pointer with an offset will not suffice.
  3. Your mark algorithm seems to assume pointers are 16bit aligned which on the 6502 they usually are not.
  4. Any data that happens to match an object pointer will keep an unused block from ever being freed.
1. is an easy fix. 2. can be avoided if the user is told about it. 3. can be fixed but will increase the likelihood of 4. which is the biggest problem. It may work in some cases, but it does not seem to be reliable and predictable.
1) it does by calling the GC and retrying;
2) why not? That's what GC usually do;
3) nope, it searches the memory moving 1 by 1 rather than 2 by two;
4) improbable because stack is always changing its values. I've run the program on fceux at turbo speed for minutes and it never hanged.
vbc
Posts: 72
Joined: Sun Jun 21, 2020 5:03 pm

Re: Garbage Collector for CC65

Post by vbc »

JohnDoom wrote: Mon Mar 06, 2023 9:20 am 1) it does by calling the GC and retrying;
So what if the GC does not free the required memory?
2) why not? That's what GC usually do;
But it's not how malloc/free works in C. You can perfectly do:

Code: Select all

int *mystack=malloc(..);
*mystack++=old_value;
do_something(mystack);
myvalue=*--mystack;
free(mystack);
With your system, the memory might be reused after mystack++. As I said, if you know about it, it can be avoided. But it's not as simple as just replacing malloc/free unless additional requirements are met.
3) nope, it searches the memory moving 1 by 1 rather than 2 by two;
Your code contains:

Code: Select all

void MemoryMarkArea(void* start, void* finish)
{
        void** ptr;
        MemoryObject* object;

        for(ptr = start; ptr < finish; ptr++)
        {
           ...
As ptr is a pointer to void *, it is incremented by two bytes (the size of a void*) each iteration.
4) improbable because stack is always changing its values. I've run the program on fceux at turbo speed for minutes and it never hanged.
That is not very convincing. It may never fail with one program and immediately with another, depending if there is some data that resembles a valid pointer. This may change when you add or remove a variable somewhere, and it may depend on dynamic values like timers, scores etc.
JohnDoom
Posts: 20
Joined: Sun Sep 11, 2011 1:00 am

Re: Garbage Collector for CC65

Post by JohnDoom »

vbc wrote: Mon Mar 06, 2023 10:04 am
JohnDoom wrote: Mon Mar 06, 2023 9:20 am 1) it does by calling the GC and retrying;
So what if the GC does not free the required memory?
2) why not? That's what GC usually do;
But it's not how malloc/free works in C. You can perfectly do:

Code: Select all

int *mystack=malloc(..);
*mystack++=old_value;
do_something(mystack);
myvalue=*--mystack;
free(mystack);
With your system, the memory might be reused after mystack++. As I said, if you know about it, it can be avoided. But it's not as simple as just replacing malloc/free unless additional requirements are met.
3) nope, it searches the memory moving 1 by 1 rather than 2 by two;
Your code contains:

Code: Select all

void MemoryMarkArea(void* start, void* finish)
{
        void** ptr;
        MemoryObject* object;

        for(ptr = start; ptr < finish; ptr++)
        {
           ...
As ptr is a pointer to void *, it is incremented by two bytes (the size of a void*) each iteration.
4) improbable because stack is always changing its values. I've run the program on fceux at turbo speed for minutes and it never hanged.
That is not very convincing. It may never fail with one program and immediately with another, depending if there is some data that resembles a valid pointer. This may change when you add or remove a variable somewhere, and it may depend on dynamic values like timers, scores etc.
1) I'd rather hang the game because it means I allocated too much, but I see your point: I could replace those "while" and return NULL;
2) it's not supposed to replace "free" too, I think this was obvious;
3) are you sure that's the case? If the pointer is pointing to 0x2000 and I add 1, shouldn't it now point to 0x2001? If I'm wrong, what can I do about it?

UPDATE: I've tried running this sample on https://www.onlinegdb.com/online_c_compiler...

Code: Select all

#include <stdio.h>

int main()
{
    void* ptr = 0x2000;
    printf("%x\n", ptr);
    
    ptr++;
    printf("%x\n", ptr);

    return 0;
}
... and it correctly returns 2000 and 2001, so that's it I guess.
Joe
Posts: 650
Joined: Mon Apr 01, 2013 11:17 pm

Re: Garbage Collector for CC65

Post by Joe »

JohnDoom wrote: Mon Mar 06, 2023 10:28 amUPDATE: I've tried running this sample
That sample is incorrect. Use void** instead of void* to see the problem.
Post Reply