Jump to content

CX16 HEAP MANAGER for BANKED RAM and VERA VRAM


Recommended Posts

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.

 

 

 

  • Like 1
Link to comment
Share on other sites

  • 2 months later...
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/  )

Link to comment
Share on other sites

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.

 

Link to comment
Share on other sites

  • 2 weeks later...
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.

 

 

Edited by BruceMcF
Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

 Share

×
×
  • Create New...

Important Information

Please review our Terms of Use