Help

Treating a slice as a stack is surprisingly expensive

D's dynamic arrays (slices) aren't containers; they don't own the data they refer to. A random char[] that contains "hello" may point right into a random other char[] that contains "hello world". So what happens when you append a '!' to the first slice, when it doesn't own the ' ' in the next byte of memory? It must reallocate in this case, and copy "hello" to new memory with room for the new byte, or it'd be stomping over someone else's memory. Of course if appending always reallocated slices that'd be terrible for performance, so this doesn't happen, and slices have a .capacity in addition to .length to prevent that.

There's a lot to say about slices, but they mostly "just work". They just have one pitfall: treating them like a stack causes that "hello"-needs-to-reallocate-to-not-stomp-over-unowned-memory condition to trigger on every single stack-push following a stack-pop.

Consider: 

struct Badstack {
    int[] stack;
    uint reallocs;

    void push(int n) {
        int* p = stack.ptr;
        stack ~= n;
        if (stack.ptr != p)
            reallocs++;
    }

    int pop() {
        stack.length--;
        return stack.ptr[stack.length];
    }
}

void main() {
    import std.stdio : writeln;

    Badstack one, two;
    foreach (n; 0 .. 100) {
        one.push(n);
    }
    writeln(one.reallocs); // output: 10

    foreach (n; 0 .. 100) {
        two.push(n);
        two.pop;
    }
    writeln(two); // output: Badstack([], 100)
}

Badstack updates a counter every time it notices a realloc (based on stack.ptr not remaining constant during a push). The first loop pushes a hundred elements onto one stack, and counts only 10 reallocs as the stack grows to contain all 100 elements. The second loop also pushes 100 elements, but it pops them each time. That loop results in 100 reallocs.

Simple fix: let the slice always cover all the stack memory, and track depth separately. The following program only has a single realloc in the second loop. 

struct Goodstack {
    int[] stack;
    size_t length;
    uint reallocs;

    void push(int n) {
        int* p = stack.ptr;
        if (length < stack.length) {
            stack[length++] = n;
        } else {
            stack ~= n;
            length++;
        }
        if (stack.ptr != p)
            reallocs++;
    }

    int pop() {
        return stack[--length];
    }
}

void main() {
    import std.stdio : writeln;

    Goodstack one, two;
    foreach (n; 0 .. 100) {
        one.push(n);
    }
    writeln(one.reallocs); // output: 10

    foreach (n; 0 .. 100) {
        two.push(n);
        two.pop;
    }
    writeln(two); // output: Goodstack([99], 0, 1)
}

Other discussion: