Heap Allocation

The next important step in improving performance is to minimize heap allocation and reallocation. The Str class calls the realloc() function to resize a buffer when the current buffer is too small to store the result of a requested operation (such as an append()). In some cases / implementations, realloc() does a fairly good job of growing the buffer without moving it to a different place. If it is moved to a different place, however, realloc() will have to copy the data to the different place. If this happens a lot, performance will suffer.

In general, a good way to avoid getting into trouble with realloc() is to minimize its usage. This, in general, reduces heap fragmentation. Note that I say, in general because there are many implementations for heap memory and some do a fairly good job of avoiding fragmentation (usually by trading off a different desirable feature, such as allocation performance or memory efficiency).

There are several ways to reduce heap fragmentation, outlined below:

Avoid compact()

The built-in string functions do not reallocate smaller buffers when a string gets shorter for two reasons. One is to prevent a heap operation. The second is to prevent another heap operation if the string gets larger again in the near future. In most cases, this is the best approach.

Pre-allocate

If you have a set of string operations that grow a string and you can predict ahead-of-time how large the string will be, putting a resize(predicted_size + 1) call at the start of the operations will prevent a lot of heap realloc() calls. See section 5.5 for an example scenario.

Set Time Efficient

If you can not easily predict how large a string will become but know that it will probably grow in many small steps, calling setTimeEfficient(true) can save a lot of heap calls. When set to time efficient, all resize() calls (including those made internally) increase the string's buffer size to the next power of two (so a buffer will grow from $8 \rightarrow 16 \rightarrow 32 \rightarrow 64 \rightarrow 128 \rightarrow 256$, etc). This allows a string to grow large enough within $O(\log(n))$ buffer resizes. This typically pushes the cost of resizing into the noise of performance analysis.

Use The Stack

For generic processing routines that often deal with small amounts of data, starting a Str on the stack will avoid a lot of heap activity. The simple prototype is:

char buff[64];
Str x(buff, sizeof(buff));

Now the stack will be used to store string data unless the string grows beyond 64 characters in length. This has a number of nice properties:

• You are avoiding the allocation of a small block of data. The minimum requested size will be 64 bytes. As a general rule, smaller requests are bad news for heap implementations.

• In the cases where the string grows beyond 64, other operations in the routine are probably pushing the cost of the heap allocation into the noise.

Of course there are a lot of heuristics here to sort out. For example, why 64 and not 128 stack bytes? The real answer to these questions depends on your particular situation: Allocating a large amount of data on the stack without regard to program flow can lead to stack-overflow problems, but using the stack in a few strategic places can really help boost performance.