CX16 HEAP MANAGER for BANKED RAM and VERA VRAM

[svenvandevelde]

 

i agree!

[svenvandevelde]

 

...

[svenvandevelde]

Been optimizing the API and also been working to optimize the internals of the code. The first posts in this thread have been updated to reflect those changes.

You can find the latest code here:

src/test/kc/examples/cx16/cx16-heap/cx16-heap-test.c · CX16_VERA · Sven Van de Velde / kickc · GitLab

Sven

[svenvandevelde]

This is a complete example of how I use the cx16 heap manager to setup memory segments in BRAM and VRAM for dynamic memory management.

    // Memory is managed as follows:

    // ------------------------------------------------------------------------

    //

    // HEAP SEGMENT                     VRAM                  BRAM

    // -------------------------        -----------------     -----------------

    // HEAP_SEGMENT_VRAM_PETSCII        01/B000 - 01/F800     01/A000 - 01/A400

    // HEAP_SEGMENT_VRAM_SPRITES        00/0000 - 01/B000     01/A400 - 01/C000

    // HEAP_SEGMENT_BRAM_SPRITES                              02/A000 - 20/C000

    // HEAP_SEGMENT_BRAM_PALETTE                              3F/A000 - 3F/C000

 

    // Handle the relocation of the CX16 petscii character set and map to the most upper corner in VERA VRAM.

    heap_segment segment_vram_petscii = heap_segment_vram(HEAP_SEGMENT_VRAM_PETSCII, 1, 0xF800, 1, (0xF800-VRAM_PETSCII_MAP_SIZE-VERA_PETSCII_TILE_SIZE), 1, 0xA000, 16);

    petscii(segment_vram_petscii);

 

    // Allocate the segment for the sprites in vram.

    heap_bank heap_vram_ceil_bank = heap_vram_floor_bank(segment_vram_petscii);

    heap_ptr heap_vram_ceil_ptr = heap_vram_floor_ptr(segment_vram_petscii);

    heap_segment segment_vram_sprites = heap_segment_vram(HEAP_SEGMENT_VRAM_SPRITES, heap_vram_ceil_bank, heap_vram_ceil_ptr, 0, 0x0000, 1, 0xA400, 0x02c0);

 

    // Load the palettes in main banked memory.

    heap_segment segment_bram_palettes = heap_segment_bram(HEAP_SEGMENT_BRAM_PALETTES, 63, 0xC000, 63, 0xA000);

    heap_handle handle_bram_palettes = heap_alloc(segment_bram_palettes, 8192);

    heap_ptr ptr_bram_palettes = heap_data_ptr(handle_bram_palettes);

    heap_bank bank_bram_palettes = heap_data_bank(handle_bram_palettes);

 

    // Initialize the bram heap for sprite loading.

    heap_segment segment_bram_sprites = heap_segment_bram(HEAP_SEGMENT_BRAM_SPRITES, 32, 0xC000, 2, 0xA000);

[svenvandevelde]

Just a note to let you all know that i'm still working on this. It is a lot of fun actually to play with the bits and the banking.

I'll need to contact Jesper to optimize is cx16 compiler, but i plan to make a similar implementation for the CC65.

I'll support both compilers.

[svenvandevelde]

Still working on my heap manager, although I had to park the development of the project due to my professional activities, which required all my attention the past months.

I've re-initiated the project during the Christmas holidays and New Year period, and have made great progress. It's now in a functional working condition and have been making test programs for it.

The attached is a prg that runs in an endless loop, stopping after a key press, which is allocating and freeing memory blocks with random sizes in banked ram. The white areas are newly allocated memory blocks and the red are "free" memory blocks in banked ram on the CX16. The black zone is completely unallocated.

On the top you see this white and red dotted line. This is the visual reflection of the index, which contains 3 lists:

• 
  The heap index list, containing the catalog of the allocated or free memory blocks on the heap. Both allocated and free memory blocks are contained in this list.
  


• 
  The free index list, containing the catalog of the heap indexes that point to free memory blocks on the heap. This index is used to speed up the searching for potentially free memory blocks for re-allocation.
  


• 
  The idle index list, containing the catalog of indexes that have become unallocated due to memory coalescing.
  

You can see the index being updated while memory is dynamically allocated or freed. Upon a new memory allocation request, free memory blocks are searched for on a first-fit basis, and re-allocated when a sufficiently large memory blocks are found, potentially splitting the free memory blocks into the new memory blocks and the remainders as free memory blocks. Although this first-fit re-allocation method is not the most efficient method to prevent fragmentation, it is the fastest method. And since the CX16 has more than sufficient memory, it shows that the fragmentation is not really an issue.

When an allocated memory block it freed, the heap memory manager performs coalescing of adjacent free blocks into one bigger free memory block. A free command will investigate if the allocated memory block lower than the current memory block and/or higher than the current memory block can be combined into one bigger free memory block. Coalescing means that previously free memory blocks become "idle", meaning, its previous indexes are of no relevance anymore, but take up space in the index memory area (we cannot just delete them, they are there...). The solution is that these idle indexes are added to the idle index list, for future re-use of index blocks, when processing sequent free or allocation commands.

Next week i'll clean the code of the heap manager, and also try to make the VERA heap working ... VERA? yes ... dynamic loading or unloading of tiles and sprites in vram during a game flow of pre-loaded graphic files in bram :-). But that is for the next chapter ...

Please run the following program (the prg file) in the x16emu, and hope it makes sense for you ...

 

 

Try it here ...


 
cx16-heap-test-fragmentation.prg
cx16-heap-test-fragmentation.c

[svenvandevelde]

After a long time, decided to improve this heap manager. I need such a memory manager to dynamically allocate and free from the VRAM on the vera tiles and sprites of various compositions like 32x32, 16x32, 16x64 etc. And this during raster interrupt logic.

The code that I had written for BRAM and VRAM had ended to to be bulky, slow and hard to understand.

So I decided yesterday to try again, with the focus on managing VRAM only.

So I took my code and have been reworking it. The major requirements for the design have stayed the same, but additionally, it should avoid internal fragmentation. Also, it should allow the heap to be compacted (not garbage collected), so I decided to keep the handle based approach. This memory manager won't give you pointers but references or handles to indirectly access the memory. The heap manager still uses an index in BRAM, which contains the dictionary of where VRAM is used, where it is free. 

I just finished today a new logic, with a code footprint of about 2000 bytes ... Tested the main allocation scenarios including coalescing. 

More on it later. Dinner is served.

[ZeroByte]

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

[rje]

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.

 

[theelkmechanic]

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.