CX16 HEAP MANAGER for BANKED RAM and VERA VRAM

All aspects of programming on the Commander X16.
BruceMcF
Posts: 1336
Joined: Fri Jul 03, 2020 4:27 am

CX16 HEAP MANAGER for BANKED RAM and VERA VRAM

Post by BruceMcF »



On 7/28/2022 at 1:36 PM, rje said:




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.



 



An allocation unit of 256 bytes is going to sound very weird to an old-school 8bit system programmer!

Of course, optimum depend on application. A lot depends on how large a pool of text you are likely to have.

One approach for strings when the strings are not the main target for the application is to have a chunk of 16 bytes as the smallest unit. If you know that your underlying text pool is going to end up being 4KB or smaller (as chunks), you can allocate 4KB of space for a text pool and have the "address" be a byte that is shifted left by four to get a 12bit offset into the pool. If strings are always going to be 240 characters or less, you can have an exact byte count for the string length and a byte reference to location, used by the routines that access the text of the string, while the record of the allocation can work with chunk offset and number of chunks allocated, from 0-15, with four bits available for additional information storage.

Then a rope approach can fit on top of that if you need either longer strings or a bigger string pool, since the rope approach works fine with a lower length limit, by just having more stringlets in the rope ... you can, for instance, bump up to an 8KB text pool by pulling the char limit down to 127 bytes and using the top bit of the length byte for bit 13 of the text pool offset.



Using chunks already filters out the smallest string allocation "bubbles", and if it is still an issue, you can experiment with making a minimum allocation unit of 2 or 4 chunks.

 

 

User avatar
svenvandevelde
Posts: 488
Joined: Wed Dec 23, 2020 6:30 am
Location: Belgium, Antwerpen

CX16 HEAP MANAGER for BANKED RAM and VERA VRAM

Post by svenvandevelde »


I'm still around... just very busy at work at the moment and can't concentrate for now on the cx16.

KICKC home page by Jesper Gravgaard.
My KICKC alpha with Commander X16 extensions.
Post Reply