Space management and granularity

Explains how to manage space and granularity in dynamic buffers.

As the buffer expands, extra space must be allocated. As it contracts, space may be released. In order to tune the management of space, a granularity is specified to the buffer’s constructor. Space is always allocated and freed in multiples of this granularity.

The granularity should be carefully chosen. Too small a value will result in too many re-allocations with a cost in time and, due to fragmentation and segmentation overheads, some waste of space also. Too large a value will result in over-allocation of space: the extent of the waste of space depends on the type of data in the buffer: decisions must be made on a case-by-case basis.

For flat buffers, the buffer’s single alloc cell is guaranteed to be a multiple of the granularity in length. When the buffer must be extended, just sufficient space is allocated to cover the immediate space need (rounded up, if necessary, to the nearest multiple of the granularity). When data is deleted, no automatic space reclamation is performed. The Compress() function may be used to compress the allocation to the smallest possible multiple of the granularity necessary for the data currently held in the buffer.

For segmented buffers, the granularity is the number of data bytes in each segment. Segments additionally have a 16-byte overhead. Therefore, the granularity of segmented buffers should always be considerably greater than 16, to avoid significant space waste. When a segmented buffer is extended, enough extra segments are allocated to contain all the data. When data is deleted from a segmented buffer, segments are deleted if they contain no data. Segments whose content is partially deleted may be amalgamated with neighbouring segments, but usually they are left partially full. If the pattern of insertions and deletions into a segmented buffer is arbitrary, nothing can be said about the extent of data in each segment: it may range from a single byte up to the entire segment length — which is the granularity of the buffer. The Compress() function may be used with segmented buffers to cause a more efficient allocation of space to its segments.