Buffer

Introduction

A buffer, like a linked list, is not an abstract data type, but an implementation type.

Essentially, a buffer is an array of object, in our case usually generic pointers so as to obtain uniform reference semantics. But buffers can also contain characters or arbitrary bytes of data.

Advantages of a buffer over linked lists

A buffer has several advantages over a linked list (simply or doubly).

For one thing, it takes up much less memory space. Assuming a system in which a pointer takes up 4 bytes, a cell for a simply linked list takes up 8 bytes for the two pointer fields, and another 4 or 8 bytes for the invisible header used by malloc. Thus, for each element that needs to be stored, a simply linked list uses 16 bytes, and a doubly linked list uses 24 bytes. A buffer, on the other hand, uses only 4 bytes per element stored, plus possibly some wasted empty space of at most 4 more bytes. On the average, a good buffer implementation should use around 6 bytes per elements stored.

Another great advantage of buffers is evident in systems with a garbage collector. A linked list will have another object (the cell) created for each element stored. That object must be traced, and perhaps copied by the garbage collector. Since no such extra objects are introduced by a buffer, the garbage collector runs much faster on buffers than on lists.

Finally, buffers are usually faster. Traversing linked lists requires more and costlier operations than the corresponding operations on a buffer.

Disadvantages of buffers compared to linked lists

Buffers are not better in all respects than liked lists. There are a few disadvantages as well.

It is costly and impractical to have the buffer be the exact size required to hold the number of elements. Thus, the buffer is most of the time slightly larger, the rest of the space being wasted.

Buffers have a fixed size at any point in time. When the buffer is full, it must be reallocated with a larger size and its elements must be moved. Similarly, when the number of valid elements in the buffer is significantly smaller than its size, the buffer must be reallocated with a smaller size and elements be moved, so as to avoid too much waste.

These disadvantages complicate programming a great deal compared to the equivalent programs with linked lists. However, if the abstract data types are to be reused in many different situations, it is well worth the effort.

Policies for changing size

Expanding and shrinking the buffer

As we mentioned above, if we are to use a buffer to implement some kind of container, we have to expand it when it is full, and shrink it when it has too few elements.

However, a block returned from malloc cannot just be expanded or shrunk. Instead one must

  1. Allocate a new block of the size that is required,
  2. Copy the objects from the old to the new block,
  3. Deallocate the old block.
The reader may object that one can use realloc to avoid such work, but realloc does exactly that, plus that it copies parts of the buffer that are not valid elements. Furthermore, realloc does not initialize the new memory. When we use a garbage collector, uninitialized memory can erroneously keep objects alive, causing memory leaks. For all these reasons, we are going to avoid realloc and use a combination of calloc, free, and memcpy.

When to expand the buffer, and by how much

Another important question is when the buffer should be expanded or shrunk. Suppose for instance that we use a buffer to implement a stack. Suppose further that we start with a single element in the buffer, and add another element whenever it overflows. Finally, suppose that we are executing a sequence of n push operations. What is the complexity of such a sequence of operations? Well, the first time we push an element, nothing happens with respect to changing the size, since there is one element in the buffer. The second time, we must expand the buffer, so we allocate a buffer with two elements, and copy them from the old one-element buffer to the new two-element buffer. The third time, we must copy two elements, and so on with three, four, etc. element. For n such operations, the cost will be proportional to the sum of all integers from 1 to n-1. This is an arithmetic series, whose sum is proportional to the square of n. The cost is thus quadratic, or if we divide it up per operation, each push operation is linear in cost, which is quite unacceptable.

One may perhaps do somewhat better if instead of adding a single element at a time, one adds (say) 20 elements or so. But the complexity remains the same, only with a different constant factor. What then can be done?

The solution to the problem is to expand not by a constant amount, but by a constant factor. Here, we are going to use a factor 2. So, if we start with a single element, we will get 2, 4, 8, etc. The reader can easily verify with the same type of reasoning as above, that the cost of copying elements is not proportional to the sum of a geometric series, and that sum is proportional to n. In other words, the cost is proportional to n for a sequence of n push operations, or constant per operation.

When to shrink the buffer, and by how much

As in the previous section, we can easily convince ourselves that the buffer should be shrunk by a constant factor as opposed to by a constant number of elements each time. We will again choose a factor 2 so that the buffer will be half its original size after being shrunk.

But when do we shrink the buffer? In the previous section, we decided to double the size of the buffer whenever it overflows. Thus, for a sequence of push operations, the buffer is at least half full. It may be tempting to shrink the buffer whenever it is less than half full, but that would be an error.

Consider a sequence of alternating push, and pop operations such that the first push overflows the buffer. With a policy of shrinking the buffer whenever it is half full, we will move n elements for every operation in the sequence. Similar sequences can be found for policies of shrinking when the buffer is half full minus some constant number of elements. Again, we have to go geometric. We are going to shrink the buffer whenever it is less than one fourth full. We shall also use a minimum size of the buffer, below which it is not worth the trouble to shrink anymore. We shall use 4 for that limit.