Best way to implement a dynamic stack type? or Am i abusing realloc?

Question

I'm using an obscure language that doesn't have a native stack type so I've implemented my own. Now, reading on the net i've found a few different approaches to do this.

This is my implementation (psuedo code)

//push method
function Push(int)
{
    Increase (realloc) stack by 4 bytes;
    Push int into the new memory area;
}

//pop method
function Pop()
{
    collect int from the top of the stack;
    reallocate (realloc) the stack to shrink it by 4 bytes;
    return int;
}

Now some people say that using a realloc() call to resize the stack after popping a value is bad for performance so i have a few questions:

1. Is it best to just grow the stack using malloc then free it at program end?
2. To resize the stack (push) is it best to increase by 4 bytes or more?
3. Is it best practise to increase the stack by doubling the memory allocated when it's filled?
4. What are your thoughts of the above code?

Answer 1

The standard technique is to only grow the size by factor of 2, and to shrink it only when the effective memory use is less than quarter.

This way you can be sure that you never use more than O(the memory you need), and you can also prove that the stack is amortized constant time.

(look at it this way: You pay three cents for each item entering or exiting the stack. Two of them will be used during the next copying that will occur.)

Link to wikipedia article explaining in more details

Answer 2

Definitely don't grow and shrink 4 bytes at a time. Your heap will become very fragmented, and you'll spend too much time in the allocator. Even on a memory-limited architecture, you don't want to be micro-managing memory like that.

Choose a "page size", and increment by that amount. It's common to recommend doubling the size, but I'm not sure why that is. You probably know more about how the stack will be used to understand how best to increment the size.

Answer 3

Almost every variable-size structure implemented in popular libraries do some small optimisations to avoid reallocing all the time. Remember that it usually has to copy the data to make it bigger.

Usually it grows by bigger amounts. a common strategy is to double size until if reaches some limit, and then grow by a fixed amount over there. and for shrinking, don't worry to resize until it's wasting more than half the size.

OTOH, some realloc() implementations already do that for you behind curtains. alas, i doubt your 'obscure language' does it...