CX16 HEAP MANAGER for BANKED RAM and VERA VRAM

[svenvandevelde]

On 5/9/2022 at 5:23 PM, ZeroByte said:

The test programs are written in C - is the manager itself also written in C or is that assembly?

In C using kickc. Note however that the kickc produces an asm file that can be compiled with kickass assembler. Once I've properly documented I'll post it.  I also have a bram memory manager using a heap approach and a bram fixed block memory manager. The latter however results in internal memory fragmentation but is blazing fast.

[svenvandevelde]

On 5/9/2022 at 6:48 PM, theelkmechanic said:

I ended up writing a banked RAM heap manager for the Unicode library I'm working on (https://github.com/theelkmechanic/unilib) for those same reasons. Once you start dealing with dynamic/unpredictable memory needs, it really becomes necessary.

Exactly. Note that for a VRAM memory manager, the complexity is that the memory manager cannot be implemented using header and/or footer blocks as this would pollute the video objects!

[svenvandevelde]

On 5/9/2022 at 6:01 PM, rje said:

A heap manager for banked RAM is nice and helpful if, for example, you want to implement a hashtable using banked RAM.



And that's useful if, for example, you're writing a parser/interpreter and need a symbol table.



Etc.



 

Yes. Building memory managers is a fascinating subject. How to make it fast, achieve requirements, small code base, use memory efficient, avoid long loops, easy to use etc ...

There are tons of "examples" on the internet and github using C on 32/64 bit machines and using the operating system brk on unix or memory allocation using win 32 api. However, on a naked cx16 in 8 bits architecture this topic gets a whole other dimension. You need to manage the addressing in memory yourself without operating system support! Then add to that the VRAM and BRAM banking and segmentation, and you have a problem domain that is extremely interesting to solve. 

[svenvandevelde]

Here a few test programs that I've written to test the mechanisms and performance of the vera heap manager. It is coming together:

- best fit algorithm for finding the optimal free block.

- coalescing free blocks

- statistics for debug

- byte-level indexing, so no word size and very fast

- no vram pollution, so everything is managed in RAM or BRAM

- no direct pointers of offsets returned after an alloc, it returns a handle, which is an indirect reference!



Feel free to run the following attached prgs in an cx16 emulator and observe the workings.

I'll post a more detailed description of it later! (It"s a very long story).

My last challenge is how to optimize memory location placement, to avoid fragmentation.

But this is a common problem that is not easy to fix.

I think I will further design a compactor that can be triggered from within a game logic to  compact memory when needed (for example between levels).



cx16-veraheap_test_stress.prgcx16-veraheap_test_graphical.prg

[rje]

I'm running up against main memory limits with my "Traveller Space Trader" program. 

That's a good thing, because artists must work within constraints.  Otherwise I'll never finish.  It uses 30K of main RAM, and it's "not done yet"... but for practical purposes it is indeed darn close to "done", whether it's complete or not.

But, I shove a lot of constant data into banked RAM, and this lets main RAM focus on game logic.  That's a good thing too.

So naturally, I was thinking about that neat heap manager of yours, and how it might be useful for storing tokens in a symbol table.  For my purposes, a "token" is probably just a string, but it's just a pile of bytes, so a pointer to it could be cast to any struct.  The neat part is the symbol table angle -- it's a generic solution that I could use for all sorts of runtime data.

 

 

[svenvandevelde]

You see... more ram brings more complexity to manage that ram, as it allows for more complex software or games. More video ram requires a capability to manage that ram and to use that ram effectively. Because it's very limited although 128k seems like a lot. It all depends what is the game you're trying to create. Some people may put this statement at question, as written in other forum posts. Those people should do what we do, and then they will see ?.

Once I get the vram heap manager in the most optimised state, I'll share the METHOD of how it was done and how it works, so you can potentially reimplement in an other language like prog8. Just a few more days patience please.

Once the VRAM is working I'll make the BRAM manager again but now with a different method than how the VRAM manager is implemented.

The two have distinct properties that really require a different approach.

 

 

 

[Travis Bryant moore]

Anything like a memory management unit in there somewhere? 

[DigitalMonk]

On 5/16/2022 at 2:55 PM, svenvandevelde said:

Here a few test programs that I've written to test the mechanisms and performance of the vera heap manager. It is coming together:



- best fit algorithm for finding the optimal free block.



 

 

Just a comment from an ancient ComSci memory:  Have you considered "worst fit" allocation?  It sounds stupid on the face of it, but is used by some allocators because it causes less heap fragmentation than "best fit".  "Best fit" tends to leave little tiny unallocated pieces all over the heap.  Finding the block is also easy/fast, 'coz it's at the top of the heap.

And there's always "first fit", which might be the fastest, with fragmentation performance somewhere in between, but that tends to be a compromise solution that no one likes (it isn't that much faster, at best)

I've always wondered about a "perfect or worst fit" allocator that would allocate a perfectly-sized block if one was available, and allocate from the worst-fit otherwise.  That should truly provide minimal fragmentation for any given workload.  I just haven't sat down and worked out the actual space and performance hit of having to maintain a block-size hash table for the perfect-fit step...  And, on small computers, this is a fairly serious tradeoff decision, because both space and time are tightly constrained.

On a side note, I strongly suspect that any text-heavy application would benefit more from the implementation of a "rope" variable type (structure, whatever -- don't get too hung up on the word "type", I'm just an old C++ programmer and think that way) that could be used instead of strings.  Cutting apart and reassembling strings is one of the fastest ways to fill and fragment your heap.  A rope is made of multiple strings (get it? ? ), and either each piece contains a pointer to the next piece (which precludes re-using any piece in multiple ropes, so it's less useful) or a separate list of pointers to all of the strings.  Concatenation then only requires allocation of the pointer-list and doesn't involve copying text at all.  This means that string literals inside your code are used directly in place, even when combined into larger ropes, saving even more memory.  Of course, you can't use any of the underlying OS I/O routines directly with these (although that would be a cool Kernal extension, to my mind), but it should be a relatively small wrapper to walk through a pointer-list calling the OS routine for each string.

(I wish I could take any credit whatsoever for the rope idea, but it's been an extended C++ "type" for a very long time.  Hmmm...  Just looked this up, and they're a bit fancier than I described, with the benefit of being faster for more operations because of binary tree optimizations:  https://www.geeksforgeeks.org/stl-ropes-in-c/  )

[DigitalMonk]

(was a duplicate, 'coz it wasn't clear that the Submit had worked the first time)

[rje]

I betcha "perfect fit" would be a waste of time almost all the time, leaving "worst fit" as the thing of choice.

Heap-of-Ropes is the way I thought of things.  Your smallest Every allocation unit is 256 bytes or something like that.