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.