At some point in your programming career, you've probably written a growable list.  It might've been to implement a dynamic array or it might've been for a hash table, but I bet you've written one.  After all, while you can usually find a library that has already implemented your application for the growable list, using that library isn't always an option.  In the past I've sometimes had to reimplement standard data structures because the library available to me had bugs I wasn't able to work around.

An introductory data structures class will teach you that the "correct" way of implementing a growable list is by using a doubling strategy.  The analysis goes as follows:  say I start out with a list large enough to hold a single element, and I grow the array by a single element each time.  Every grow operation requires me to allocate new memory and copy the content of the array over -- this takes time proportional to the size of the array.  Adding n elements requires takes time proportional to

                     1 + 2 + 3 + .... + n = 1/2 * n * (n+1) = O(n^2)

It should be obvious that growing the array by any constant amount will still leave you with O(n^2) time for n inserts.  On the other hand if we double the array length each time, we only have to copy the entire array about lg(n) times for n inserts.  If we assume that n = 2^l + r, this then requires time proportional to

                  n + 1 + 2 + ...  2^l = n + 2^(l+1) - 1 < n + 2n -1 < 3n = O(n)

One gotcha to look out for is shrinking the list.  If you halve the length of the list whenever possible, then a loop that alternately adds and removes a single element will run very slowly indeed.  A little care must be taken to not shrink too early. 

End of story, right?  The math works, out so we know what to do.  Of course the real world is never so pretty.  Sometimes we have some knowledge of the data set which tells us that doubling is overkill.  If I know that I'll rarely overrun the list by more than a few elements and the list is likely to never grow very large, I might decide to use the constant-grow mechanism.  After all asymptotic analysis only applies if my data can grow large, and I know that's not the case;  of course if my data changes at some future date, the maintainer of the code will probably curse my name for using constant grows. 

There's one major problem with the above strategy of doubling the array, and that is latency.  When you amortize the cost out over a length of time it's fairly cheap, however if you graph the performance of this list as you add elements you'll see spikes whenever the array is doubled.  This spikes might be acceptable in a batch system, but cause usability issues in whenever the array is doubled.  A laudable goal is to find a growable array class that is both efficient and that maintains steady performance without spikes.

One trick that I learned for Alan Cox of Rice University is to programmatically amortize the cost of the doubling operation.  What does this mean?  Well the above operation worked by having most adds be extremely cheap with the rare (lg n times) occurance of an extremely-expensive add.  If you're willing to take a slight performance hit on every add, you can completely eliminate the expensive add operation.  Consider the following C++ class for an integer array (untested code):

    // assume memory allocations always succeed
    class Array    {
    private:
        int* oldList;
        int* currentList;
        size_t size, maxSize;
        size_t elementsCopied;
    public:
        Array() : oldList(NULL), newList(NULL), size(0), maxSize(1), elementsCopied(0)
        {  currentList = new int[1]; }     

        ~Array()
        { delete[] oldList;  delete[] currentList; }    

        void Add(int item)
        {
            if (size == maxSize)  {
                delete[] oldList;
                oldList = currentList;
                maxSize *= 2;
                currentList = new int[maxSize];
                elementsCopied = 0;
            }   
 
            currentList[size++] = item;        
            if (oldList != NULL)  {
                currentList[elementsCopied] = oldList[elementsCopied];
                ++elementsCopied;
            }
        }

        void Get(size_t index)
        {
            if (oldList != NULL && index <= elementsCopied)
                return oldList[index];
            else
                return currentList[index];
        }
    };       

Notice that when we fill up the array we allocate a new memory buffer of double the size, but we don't actually copy anything.  We keep the old memory around though, and every time an element is added to the the end of the array we copy one more element into the new buffer.  Since the new buffer is double the size, by the time we've filled it up we've also finished copying from the old buffer (notice that this works for any multiple > 1).  We've slowed down each Add operation by replacing one write with a read and two writes, but we no longer hav latency jags when we double the array.  (we assume that allocating the new memory is a constant-time operation;  this isn't a bad assumption, and the fact that we allocate memory in powers of 2 actually helps for many head allocators).  The other tradeoff is memory.  We use 1.5 times as much memory as with the previous scheme to allow us to do the copying lazily.

Starting tomorrow, I'll start focusing on interesting trasformations done by compilers.