nesdev.org

Do any of you veterans out there use dynamic memory allocation techniques when storing/creating/freeing objects/entities? Or do you primarily just use fixed memory tables with a set position.

What do you call it when you have a big object table at a fixed location in RAM, then allocate objects at different places within that table?

That's allocation from a pool, and NES games have been doing that all the way back to Balloon Fight.

I am unaware of any games that use a traditional "heap". I think that the overhead (cpu time + bytes of memory used for heap metadata, block pointers, etc...) would be a big negative.

For objects, I have several arrays of X bytes, where X is the number of slots for objects (i.e. maximum number of active objects).

Something like this: With this code I can have up to 24 objects, each with 28 bytes. Inside the object routines I use better names for the individual bytes, like this:
This makes the code more readable.

When processing the objects, X holds the index of the current object, so all manipulation of the object's memory has to be done with indexed addressing.

I also have a linked list of free object slots, where a variable indicates the first free slot and a specific byte in each slot indicates the next free slot, with a negative index indicating the end of the list. I do this so that it's easy for new objects to get free slots, because I don't have to loop through all the slots looking for a free one, I can just grab the first one in the list and make the second one the new first. When an object is deleted, it returns the slot to the beginning of the linked list.

The way I do it is DMA sprites to the sprite table every frame, then calculate the new sprite positions every frame and run the engine and stuff. Alot faster then doing it one-by-one I would think.

tokumaru wrote: I also have a linked list of free object slots, where a variable indicates the first free slot and a specific byte in each slot indicates the next free slot, with a negative index indicating the end of the list. I do this so that it's easy for new objects to get free slots, because I don't have to loop through all the slots looking for a free one, I can just grab the first one in the list and make the second one the new first. When an object is deleted, it returns the slot to the beginning of the linked list.

Sounds more like a stack than a linked list. Otherwise I kind of like the fixed object list like that. Sounds pretty fast for something where overhead would kill it.

3gengames wrote:The way I do it is DMA sprites to the sprite table every frame, then calculate the new sprite positions every frame and run the engine and stuff. Alot faster then doing it one-by-one I would think.

Not referring to Sprite data. Referring to data that matters more to physics calculations, etc.

ManicGenius wrote:Sounds more like a stack than a linked list.

No, it really is a linked list, but it's singly-linked, so you can only read it one way. It may even look like a stack at first, because the slots are used one after the other, but they are not returned in the same order as they are used (it's not LIFO, like an stack), because objects at any position can be unloaded at any time.

There's something I though of doing, but I don't because of the way I do sprite cycling (which involves calling the objects in random order): also maintain a linked list of used slots. That way, when it was time to process the objects, you'd only look at the slots that actually had something. As objects were loaded and unloaded, the slots would constantly jump from one list to the other.

See... this is what's funny about dicking around with 6502 ASM compared to my day job as a programmer.

Day job as a programmer: Don't care 'bout what kind of structure I use, just as long as I'm storing data somehow (usually). Stuff I write for really doesn't matter *cough* business app *cough*. Keep note that the app I write for doesn't give a damn about speed. At all. That and I have the wonders of garbage collection and don't give a damn about memory unless there's a leak.

6502 ASM: Vital to the performance of the app due to severe memory and speed restrictions.

When handling things like objects or animations, I set aside a fixed number of memory "slots". I can have, for example, up to 8 active enemies in my game at one time. As the player scrolls through the level, enemies will fall out of range, and new ones will spawn in. When an enemy falls out of range, it releases its memory slot which can then be taken by a new enemy when it spawns. The size of this RAM is fixed for each object, but each object can do what it wants with its own RAM.

Each object accesses its own bytes with indirect addressing through a single pointer variable that gets updated after each object is done being processed. I'm not sure what sort of other techniques are used in other projects. I do speed a lot of things up by copying object coordinates and velocity values into ZP before handling those objects. This not only saves time, but it also saves space (about 3 bytes for every time I access one of those values). For about 50 or so enemies (which I haven't yet programmed), that's about 150 bytes save just for accessing that one variable one time. So I would recommend just as a side note doing something like that to free up some space taken by AI code.

ManicGenius wrote:Day job as a programmer: Don't care 'bout what kind of structure I use, just as long as I'm storing data somehow (usually).
[...]
6502 ASM: Vital to the performance of the app due to severe memory and speed restrictions.

At my work, my Python code processes product listing changes for 100,000 different products in two minutes. It has to use the right data structure to look up the categories, calculate the brand based on the SKU prefix, calculate sale prices based on MSRP, minimum advertised price, and cost, and somehow chew through 80 MB of product descriptions without swapping. And then it has to do it all over again for each of several web sites on which we list products.

That and I have the wonders of garbage collection and don't give a damn about memory unless there's a leak.

In a garbage-collected environment, you still have to null out reference variables when you're done with an object. Otherwise, an object may remain reachable longer than you expect and cause a leak. The care needed for this is almost the care needed for an RAII environment with auto pointers like C++.

We were evaluating a vendor product for viewing a certain kind of data file (most 80-byte records of various types, but also includes variable length TIFF images embedded inside, all text is EBCDIC; yeah, it was designed by a committee too). These files are typically large (200MB to 1GB).

This vendor app was written in dot-net by a total fucking idiot. His code took 45 minutes to read a 800MB file over a network drive mount (client + server on same network segment). So I debugged it using tcpdump / wireshark, procexp and filemon. His code would issue a 4K read request to the kernel for EACH 1, 2 or 4 byte field within each record. Overlapping reads. Literally:
I filed a bug report. He didn't understand the problem. I sent in my data. He finally got it. They fixed the bug, but wanted to up their price by $2K for the fix. I said fuck this (if you haven't gathered, I was pissed at their sloppiness).

Over one weekend I wrote a win32 gui app in C++ using the pure win32 api (no mfc, no dot-crap, no winforms, gdi++ to read TIFFs from a memory stream). I mem-map the data file with a 256MB window that slides 64MB at a time. My app can process a 800MB file from local disk in 7 seconds (when its hot in the cache) and a 1G file over the network at near wire speed (12 seconds or so).

His app was a memory hog. Mine uses a bit of memory, but not a terrible amount. I designed a hybrid data structure (part tree, part linked-list) to hold the file's hierarchy in memory as I parsed it. The user can then search for records and the app displays the image and other record data.

I wanted to open-source the app and dump it on the Internet. As much as my bosses thought that would be funny, they did not permit me to.

My point is (other than a little bragging): Data structures and IO patterns _do_ matter. Even incredibly powerful modern computers and networks can be brought to their knees by bad coding practices.

clueless wrote:My point is (other than a little bragging): Data structures and IO patterns _do_ matter. Even incredibly powerful modern computers and networks can be brought to their knees by bad coding practices.

... I'm kinda not arguing against this, you do realize that. I'm just trying in a very poor way to explain that I have never had a need to reinvent the wheel in my day job. Our deadlines are too stringent to bother, so we usually use libraries. It's a crap practice for programmers who love doing everything by themselves in a really low level, but when you spend less than 1% of your time coding it kind've happens. (Most of my time is writing papers, not coding.)

The 6502 is a completely different beast to me compared to what I'm used to. That was the entire point about the beginning of this topic in the first place, I wanted to get a overview about how everyone else is doing things but it kind've got off-topic.

ManicGenius wrote:We usually end up having almost no time to code really. It's kind've sad since that's the fun part.

That sucks. Coding is the fun part.

ManicGenius wrote:Do any of you veterans out there use dynamic memory allocation techniques when storing/creating/freeing objects/entities? Or do you primarily just use fixed memory tables with a set position.

Back to your original post. I understood your question to ask if anyone was using a "heap" and implemented a generic mamory allocator, like malloc() / free() / realloc() / sbrk() / omgplzcrashmehardnow().

I know that cc65 has malloc/free as part of its library. I've used them on a Apple II project many years ago. But I can't imagine using them for a NES game. Possibly for doing A-star path finding, but I can imagine a more (speed) efficient implementation using memory slots and a linked list (in unused slots) to point to the next (like tokumaru described).

A huge problem with malloc/free on a system with limited memory would be memory fragmentation. One could use a SLAB allocator I suppose. But all of these things have CPU overhead and consume memory for heap mgmt.

I'm curious why you asked. Do you have a use-case for a generic memory allocator? If so, please share. I'm really curious now on how a NES game might benefit form one.