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 smallestEvery 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.
