I'd like some outside opinions on something. I was thinking of utilizing a type of rope in one of my projects. The biggest problem I foresee, just because I would like to use a memory arena, is that the character strings will be constantly changing, I'll be adding and removing nodes as people type in content and the arena would have a lot of fragmentation and dead strings around (At least how I'm thinking of utilizing the arena). Does anyone have any thoughts to fix fragmentation rather than keeping track of each string pointer in the arena? Everytime I think about it or draw it out I think this is the best way, let me know.
Oh and Happy New Year!
Oh and Happy New Year!
I'm not sure I understand exactly what you want to do, more precise informations would help.
If you are have an general idea of the maximum length of the strings, you can push blocs of that size only and keep a list of blocs that are no longer in use so you can use them again before allocating more blocs (free list). But there would be some unused space after each string.
If you are have an general idea of the maximum length of the strings, you can push blocs of that size only and keep a list of blocs that are no longer in use so you can use them again before allocating more blocs (free list). But there would be some unused space after each string.
Yeah I thought about doing that, I just think that isn't very efficient, but it would definitively work... I would rather have the block size be dynamic :/...
I did just have an idea though. If I had a header before each string that said the string length, and if the string was viable to use jumping from one header to another would be easy then... And reconstruct the rope by iterating over the old one... Seems inefficient still, taking up a lot of memory over time as there could be a lot of strings, so a lot of headers.
Think on the scale of textbook or long novels, where each each word is a separate node. Someone can add to that word, I'll probably move that node's address at the end of the arena, then there's fragmentation... Should I do a memory copy to close the gap? If they remove the string or lessen it, then memory copy again? Or do I just leave the gap? I could do as you said, have uniform sizes for allocated blocks for each string with no header... Then of course what if a string becomes larger than that size.
I'm not sure if anyone knew any clever tricks to this problem, I'm sure people have encountered it on their projects on handmade network.
I did just have an idea though. If I had a header before each string that said the string length, and if the string was viable to use jumping from one header to another would be easy then... And reconstruct the rope by iterating over the old one... Seems inefficient still, taking up a lot of memory over time as there could be a lot of strings, so a lot of headers.
Think on the scale of textbook or long novels, where each each word is a separate node. Someone can add to that word, I'll probably move that node's address at the end of the arena, then there's fragmentation... Should I do a memory copy to close the gap? If they remove the string or lessen it, then memory copy again? Or do I just leave the gap? I could do as you said, have uniform sizes for allocated blocks for each string with no header... Then of course what if a string becomes larger than that size.
I'm not sure if anyone knew any clever tricks to this problem, I'm sure people have encountered it on their projects on handmade network.
Edited by Jesse Coyle
on
If you have varying sizes for your allocations, and aren't willing to trade off on anything else, then you're pretty much into the territory of general purpose allocators. Casey did do some work on that (starting day 160).
One other technique is to not just have one free list allocator with blocks of a certain size, but to use a number of allocators of varying size (e.g. 8 bytes, 16 bytes, .. 2 kb, ..) to waste less memory.
One other technique is to not just have one free list allocator with blocks of a certain size, but to use a number of allocators of varying size (e.g. 8 bytes, 16 bytes, .. 2 kb, ..) to waste less memory.
you can also do work to reduce fragmentation. It will require copying the strings around to pack them together again.
Depending on how the allocations and accesses happen this can be very easy or impossible.
For example a string is a struct which points into an offset of a memory block and if the block is marked for deletion (because there are too many holes in it) then if code wants to access it it will copy the string to a new block and free the old memory. If it is the last allocation in that block the block can be reused.
Depending on how the allocations and accesses happen this can be very easy or impossible.
For example a string is a struct which points into an offset of a memory block and if the block is marked for deletion (because there are too many holes in it) then if code wants to access it it will copy the string to a new block and free the old memory. If it is the last allocation in that block the block can be reused.
Huh, seems interesting ratchet. I'll have to try out a few things like that, the strings might be changed so much though that an entire deletion of a whole node would indicate the whole tree has to be copied, or maybe I do that but wait until the memory used will be over the size of the arena and then we copy the whole tree into a new allocated arena.
And it looks like I should re-watch the allocator parts, I thought I knew all the techniques he talked about but I don't remember the different allocator portions. Well, I think I'll start getting to work on trying out some of this stuff. I'll come back when I have time and talk about it and what I chose if I remember.
And it looks like I should re-watch the allocator parts, I thought I knew all the techniques he talked about but I don't remember the different allocator portions. Well, I think I'll start getting to work on trying out some of this stuff. I'll come back when I have time and talk about it and what I chose if I remember.