Efficiency of using array as stack

[H. S. Teoh]

On Sat, Mar 23, 2013 at 01:10:56PM +0100, Ivan Kazmenko wrote:
> Hello again!
> 
> Today, I had trouble using D built-in dynamic array as a stack: it
> timed out badly.

Using arrays as stack *can* be efficient -- but you should not be
appending/shrinking it constantly. Here's why.  Consider this code:

	int[] arr = [1,2,3];
	int[] barr = arr[0..1];
	barr ~= 4;
	writeln(arr[2]);	// what should this print?

In D, arrays are actually views into runtime-managed memory blocks. When
you shrink an array, the underlying memory block remains the same
(because the runtime system doesn't know immediately whether another
slice points to the data past the end). If you immediately append to the
array again, the system doesn't know whether it's safe to overwrite what
was there before (because another slice might be pointing to that data).
So, to be safe, it will reallocate the array.

To tell the runtime system that it's OK to overwrite what was there, you
should call assumeSafeAppend before appending to the array again.

Alternatively, you should not shrink the array, but keep another counter
on how much of the array is being used, so that you can reuse the space
immediately without risking reallocation. Here's an example array-based
stack implementation that does this:

	struct Stack(E)
	{
	    private E[] impl;
	    private size_t curSize = 0;

	    /**
	     * Returns: true if the stack contains no elements, false
	     * otherwise.
	     */
	    @property bool empty() { return (curSize == 0); }

	    /**
	     * Access the top element of the stack without popping it.
	     * Precondition: The stack must not be empty.
	     * Returns: The element at the top of the stack, by reference.
	     */
	    @property ref E top()
	    {
		assert(curSize > 0);
		return impl[curSize-1];
	    }

	    /**
	     * Pops an element off the stack.
	     * Precondition: The stack must not be empty.
	     * Returns: The popped element.
	     */
	    E pop()
	    {
		assert(curSize > 0);
		auto elem = top();
		curSize--;
		return elem;
	    }

	    /// Pushes an element onto the stack.
	    void push(E elem)
	    {
		if (curSize == impl.length)
		{
		    // Array not big enough to fit element; increase capacity.
		    impl.length = (curSize + 1)*2;
		}
		assert(curSize < impl.length);
		impl[curSize] = elem;
		curSize++;
	    }
	}


T

-- 
Answer: Because it breaks the logical sequence of discussion.
Question: Why is top posting bad?