[boost] circular_buffer and unused space overhead

From: Pavel Vozenilek (pavel_vozenilek_at_[hidden])
Date: 2003-07-27 16:16:31

Right now circular_buffer allocates array sufficient to keep max allowed
number of elements. There are many situations where this is useful and OK.

But there may be different use case:

Think data gathering system with sensor continually delivering data in 1kB
blocks. Circular buffer will be used to keep them before futher processing.
It imposes limit max 5000 blocks.

Typically, the processing application keeps up with sensor and there are no
more than few blocks in buffer. But the memory consumption will be always
5MB.

The unused memory won't get swapped away - new data are inserted
sequentially - and the container will have worse CPU cache friendliness.

Wouldn't it be better to use smaller internal memory block initially and
resize it only when demand goes up?

For example circular_buffer<> constructor can have additional parameter,
number of elements initially allocated. If this count is exceeded, internal
array is resized, if usage goes down the array could shrink. If this number
is equal to capacity (by default), array will be fully allocated and
circular_buffer<> behavior will be exactly the same as now.

Something like:

  // internal array is fully allocated, no resize/shrink allowed
  circular_buffer(
      size_type capacity,
      const allocator_type& a = allocator_type());

  // size of internal array may vary between <minimal_capacity, capacity>
  circular_buffer(
      const std::pair<size_type, size_type>& capacities // capacity +
minimal_capacity
      const allocator_type& a = allocator_type());

  // minimal_capacity will be equal to new_capacity
  void set_capacity(size_type new_capacity);

  // size of internal array may vary between <minimal_capacity,
new_capacity>
  void set_capacity(const std::pair<size_type, size_type>& capacities);  //
new_capacity + minimal_capacity

  size_type get_minimal_capacity();
  void set_minimal_capacity(size_type minimal_capacity);

The library would need to employ some heuristic how and when to
shrink/resize internal array.

/Pavel