Heap Fragmentation

[mikep]

What happens as variable length strings (or for that matter my own data) keep getting allocated and freed in the heap? Presumably when a block is freed, ajoining free space is collapsed into one free item on the free list. But if the heap is full but fragmented, there is not much that can be done except to free things and then reallocate them?

The motivation for this question is the best way to store up to 50 strings (or byte arrays) that can be added or deleted on the fly. There are 4 options:
1. Use vector of 50 strings which can lead to fragmentation of the heap
2. Use fixed length strings in an array which wastes space.
3. Use variable length character arrays that are allocated and deallocated in the heap.
4. Use a fixed length vector of bytes that I suballocate to each character string as needed and I collapse the gaps whenever a string is deleted. A separate unsigned integer vector of offsets into the one large vector of bytes is used to mark the beginning and each string. Another byte vector keeps the lengths.

[dkinzer]

Presumably when a block is freed, ajoining free space is collapsed into one free item on the free list.

That is true. Adjacent free blocks are combined to form the largest possbile free block. Moreover, when the block at the end of the heap is freed, the heap is shrunk so that it ends with an allocated block. This helps maximize the space that is usable by the main task stack.

There are 4 options

Another option is a variation of #4 wherein a string is represented by a "handle". All access to the string is via the handle.

[mikep]

There are 4 options

Another option is a variation of #4 wherein a string is represented by a "handle". All access to the string is via the handle.

Any suggestions for the "best" approach given an application that will do a large number of string creation and deletions over a period of time? The strings (or character arrays) are usually between 20 and 60 characters long and there could be up to 50. I need to know if there memory is exhausted as well. I have my own idea of what will probably work best but I'm looking to see what other people think.

[dkinzer]

I need to know if the memory is exhausted as well.

Currently, the only way to determine if string allocation has failed is to check the length of the string. If it should not be zero length but it is, the most likely cause is that space could not be found for the string.

For native mode devices, you can set a hard limit on the heap. A heap allocation will fail if the allocation would cause the heap to grow past the heap limit. In the current VM versions, there is no such limit and the heap will be grown to accommodate a new allocation even though it causes the heap to encroach on the main task stack. The VM version that we are currently testing implements the same type of hard heap limit.