Don't Use Arrays As Stacks


EDIT 2011.10.27: I'll cut to the chase: You can do it in D, it'll work, but it will be slow because whenever you pop and then push, it will reallocate and copy. And stacks do that frequently. For more details and a solution, read on:

The D programming language has fantastic array features. The ease of using D's arrays makes it very tempting to use them as stacks:

int[] stack = [1, 2, 3]; stack ~= 7; // Push auto x = stack[$-1]; // Peek stack = stack[0..$-1]; // Pop (Uses slicing, so it *doesn't* copy any data)

Brilliant! Right? It is, as long as you want an array. But if what you really want is a stack (that is, whenever you'll be doing a lot of pushing and popping), then this is unnecessarily slow. Why? Because of excess allocations.

"Poppycock! Arrays have a reserve capacity which prevents excess allocations."

Yes, but slicing can get in the way of that. Consider this example of using an array as a stack:

import std.stdio; void info(ref int[] stack) { writefln("length %s, capacity %s", stack.length, stack.capacity); } void push(ref int[] stack) { stack ~= 7; write("Push: "); stack.info(); } void pop(ref int[] stack) { stack = stack[0..$-1]; write("Pop: "); stack.info(); } void main() { int[] stack = [1, 2, 3]; stack.info(); stack.push(); stack.push(); stack.pop(); stack.push(); stack.pop(); stack.pop(); stack.push(); }

That produces the following output with DMD 2.055 Windows:

length 3, capacity 3 Push: length 4, capacity 7 Push: length 5, capacity 7 Pop: length 4, capacity 0 Push: length 5, capacity 7 Pop: length 4, capacity 0 Pop: length 3, capacity 0 Push: length 4, capacity 7

The first three lines look ok: The stack starts with three elements and no extra reserve space. A fourth element is added, but there isn't enough room, so it bumps the capacity up to 7. So there's four elements, with room for three more. Then, when a fifth element is added (sans Bruce Willis, unfortunately), there's already enough space for it, so we get that fifth element without another allocation. Joy!

Then we pop an element off...and the capacity plummets to zero?! WTF?! The reason for this is aliasing. For all the array knows, we might still have a reference somewhere to the full original array, including that fifth element:

int[] stack = [1, 2, 3, 7, 7]; auto stackOriginal = stack; stack = stack[0..$-1]; // Pop assert(stack == [1, 2, 3, 7]); assert(stackOriginal == [1, 2, 3, 7, 7]);

Suppose we now append another value to the stack:

stack ~= 20; assert(stack == [1, 2, 3, 7, 20]); assert(stackOriginal == [1, 2, 3, 7, 7]);

In this case, the append must allocate new memory and copy the old data into it. Otherwise, it would clobber the last value of stackOriginal with 20. In other words: After being popped, the stack can no longer guarantee it will still be able to accommodate up to 7 elements without allocating, so its capacity is set to zero [1].

The end result is: Slicing an array is fast, and appending is usually fast [2], but slicing the end off and then appending is slow. But since that's how a stack is normally used, arrays make for slow stacks.

How can you have a fast stack? By handling an array's length and capacity manually. The basic principle works like this:

int[] stack = new int[100]; stack[0..3] = [1, 2, 3]; size_t stackLength = 3; // Push stackLength++; stack[stackLength-1] = 7; // Peek auto x = stack[stackLength-1]; // Pop stackLength--;

That's not as nice, but fortunately those details can be hidden in a templated struct that provides the same syntax as arrays. I've already written such a struct, available in my SemiTwist D Tools project. It's perhaps not as fully-featured as it could be, but it should work in most cases as a drop-in replacement for an array. When I dropped it into the parsing engine for my Goldie Parsing System I got an instant 5x-6x boost in parsing speed [3].

So don't use a plain old array when you want a stack. A proper stack will give you far better performance and memory usage.

One caveat about this method: If you save a slice of the stack, pop elements off the stack, and then push new values back on, the old slice you took will likely [4] reflect the new values, not the original ones.

Note that Phobos's development has been accelerating for the past year or so, so I wouldn't be surprised to see a superior stack implementation in std.container sometime in the not-so-distant future.

For more information about D's arrays and slicing, see Steven Schveighoffer's award-winning article, D Slices.


[1] Why is the capacity set to zero instead of the actual length of four? I'm not certain, but my guess is that zeroing the value is slightly faster than copying the length. Either that, or perhaps it has to do with the fact that the slice doesn't actually "own" the data. Update 2011.09.26: Steven has explained why it's zero.

[2] If you're doing a lot of appending, you may be better off using D's Appender.

[3] This figure is parsing speed alone, not lexing and parsing combined. Your mileage may vary.

[4] I say "likely" instead of "definitely" because of an unfortunate indeterminism inherent in D's array/slice system. This quirk is explained in the "Determinism" section of Steven Schveighoffer's article mentioned above.

7 comments for "Don't Use Arrays As Stacks"

  1. (Guest) Borask
    2011-09-25 04:45

    You do the pop operation with

    stack = stack[0..$-1];

    Why dont' you do it like this?

    stack.length = stack.length - 1;

    which reduces the current stack without creating another one.

    (not sure if stack.length--; would work)

  2. (Guest) jmdavis
    2011-09-25 05:11

    stack = stack[0 .. $-1] and --stack.length are identical operations. No new memory is allocated in either case.

  3. 2011-09-25 05:16

    Because of the magic of D's slices ;)

    In D, the first example doesn't create a new stack. It's just a slice, ie, a different view, of the exact same memory addresses. So it's literally equivalent to decreasing the length. In fact, if change that line as you suggest in the second code block above, you'll get the exact same output.

    D's arrays can be thought of like this:

    struct Array(T) {
    T* ptr;
    size_t length;
    }

    So when you do that slice, you're really just doing:

    stack = Array!int(stack.ptr, stack.length-1);

    And since you're just assigning it back to the same variable, the compiler should even be able to optimize away that temporary literal.

  4. 2011-09-25 09:43

    This is first time I heard about D programming language ,my ignorant. but my java experience says that Stack are implemented using Vector which internally backed by array. So ultimately it goes to array.

  5. (Guest) acehreli
    2011-09-25 21:36

    As an aside, the std.array module provides the popBack() range primite:

    import std.array;

    void main()
    {
    int[] stack = [1, 2, 3];
    stack.popBack();
    assert(stack.length == 2);
    }

    Ali

  6. (Guest) Steven Schveighoffer
    2011-09-26 07:43

    Borask:

    Why dont' you do it like this?

    stack.length = stack.length - 1;

    Setting the length is actually a runtime function call, taking a [0..$-1] slice is a single instruction. The compiler may optimize it into the same thing, but is not guaranteed to. My guess is that dmd does *not* optimize this, unless -O is passed, but I haven't tested.

  7. (Guest) Aatch
    2012-02-20 17:59

    I know this is a little old, but using assumeSafeAppend(stack) stops the problem of allocating on append. Basically you tell the GC that there will only every be one reference to this array, and its your own damn fault if you corrupt data.

    Of course, if you need a proper stack, use a proper stack, but if you quickly need some stack-like semantics, then stack.makestack(), stack.push('a'), and stack.pop() will get you acceptable performance.

Leave a comment

Captcha