Efficiency of using array as stack

[Jonathan M Davis]

On Saturday, March 23, 2013 13:10:56 Ivan Kazmenko wrote:
> Today, I had trouble using D built-in dynamic array as a stack:
> it timed out badly.  I have then tried to reduce the problem down
> to a minimal example.  I am using DMD 2.062.

You might want to check out this article where someone ran into similar 
issues:

https://www.semitwist.com/articles/article/view/don-t-use-arrays-as-stacks

And if you haven't read Steven's article on arrays, you should do so:

http://dlang.org/d-array-article.html

But basically, you need to either wrap an array and then either

1. Use it as a holder a chunk of pre-allocated chunk of memory for your stack 
rather than the stack itself. You then get something like

void push(T elem)
{
    if(_stackLen == _arr.length)
        _arr ~= elem;
    else
        _arr[stackLen++] = elem;
}

void pop()
{
    ++_stackLen;
}

2. Use the internal array as a stack, and use assumeSafeToAppend when you pop 
an element, but you have to guarantee that there are no other slices to the 
array for that to work, or you'll end up stomping on those other slices.

void push(T elem)
{
    _arr ~= elem;
}

void pop()
{
    --_arr.length;
    assumeSafeAppend(arr);
}

In either case, using an array directly as a staci and simply appending to it 
to push and decrementing its length to pop isn't going to be particularly 
efficient do to how slices work.

- Jonathan M Davis