| |
Hoogo
Registered: Jun 2002 Posts: 105 |
Strings of variable size
I'm thinking about a good way to store strings of variable size. I don't have the time for a garbage collection because it should be used in a demo. The correct numbers may differ a little, but the strings have to fit to this:
-Always the same number of strings, it's an array of 700 strings
-Size is between 32 and 64 Bytes
-Usually they will be read AND changed, usually they will become bigger.
-Normally about 2 to 20 folowing strings are read/rewritten.
-A "char" has 11 bits, any combination may occur.
-This all runs until I run out of memory.
Now I tried to find a good solution for this. My favorite aproach so far, though I did not think it to the end:
-700*32 Bytes fixed strings (Its mimimum size or little above)
-A map of a few hundred 32Byte-chunks as an overflow-area. These chunks might be divided into 2. The last 3 Bits of the 32byte-chunk can tell if a half is free or used and if the whole chunk is divided or not.
-For every of the 700 strings I need a link to its overflow-area.
I hope that I waste only half of the overflow-memory, less than a quarter overall.
The most expensive thing that can happen is that a 16byte-chunk overflows and that I have to find 1 more lonely 16byte-chunk, move and relink one of them.
Anyone some suggestions about all this?
Frank/Hoogo |
|
| |
Stryyker
Registered: Dec 2001 Posts: 468 |
Tried messing with fixed sized arrays? Maybe use (0) as size or another array for the size tables. No idea about speed but if you have space you can create some assembly that will copy over old values. That way the same memory is used and you reduce chances of running out of memory because of the bad memory management of variables. |
| |
Hoogo
Registered: Jun 2002 Posts: 105 |
Oh, I was talking about assembler anyway, sorry that I did not mention that.
I do not have enough memory to give every string the maximum size. But with a variable size it will go fine for a while. Now my problem is how to store them without wasting to much room or needing a garbage collection. I'm looking for a memory management that fits my purposes.
Writing over old values will not work. My strings become longer, so normally they have to be stored at the end, leaving a big hole of unused memory. And how do I manage these holes? Keeping they adress an lenght in a list? That list will suck up my memory and will also need a kind of collection (following holes can/have to be reduced to one bigger hole).
I also thought about storing a new string always at the end and having a permanent garbage collection. When I store one string at the end, I might move 2 string as far to the beginning as possible, but that was a really bad idea and does not work at all. |
| |
Stryyker
Registered: Dec 2001 Posts: 468 |
how about making tables of 32 bytes each. If you want more then link 2. Have a table for first and 2nd. entry used. Can be limiting but may be quicker. |
| |
Hoogo
Registered: Jun 2002 Posts: 105 |
Hm, sounds much easier than my variation :-) I'll have some tests with that |