Don't use arrays as stacks

[Nick Sabalausky]

"Steven Schveighoffer" <schveiguy at yahoo.com> wrote in message 
news:op.v2e19fkieav7ka at localhost.localdomain...
> On Sun, 25 Sep 2011 02:37:25 -0400, Nick Sabalausky <a at a.a> wrote:
>
>> If anyone cares, I've put up a little thing about why it's best not to 
>> use
>> D's arrays as stacks. This is drawn from a direct experience a few months
>> ago. Figured if I fell into that trap then others might too, so this 
>> could
>> be helpful for some people. There's a no-login-needed comments section
>> already there.
>>
>> https://www.semitwist.com/articles/article/view/don-t-use-arrays-as-stacks
>>
>>
>
> Nice article!
>

Thanks! Means a lot coming from people like you and Andrei. :)

>> [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.
>
> It was an arbitrary decision, but actually serves as an important 
> differentiator.  0 simply means "any append to this array will 
> reallocate".  capacity == length would mean the same thing, but has the 
> distinction of knowing that the length is the actual block length.

Or rather that the *end* of the array is the *end* of the actual block, 
right? (Since the array could also have some of first X elements sliced 
off.)

> This  might not seem like much, but you may want to know this difference, 
> for  example, if you wanted to call assumeSafeAppend.  The stack example 
> is a  good example.  If you wrote a generic "popStack" function, which 
> takes an  array, knowing before popping that you have control of the block 
> is  important (you may not call assumeSafeAppend if your pre-pop capacity 
> was  0).
>
>> 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.
> ...
>> [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.
>
> Actually, with the new functions capacity, assumeSafeAppend, and reserve, 
> most of the "non-determinism" is mitigated.  In your case, however, you 
> know you have control of the stack, and all its data, popping and pushing 
> will *definitely* overwrite the old value.
>

But when the stack grows past its currently-allocated size and it needs to 
expand (ex: from 1024 to 1500, in order to accomodate that 1025th element), 
there's still a chance it would get moved to a different memory location, 
right? In which case, if you then pop all the way back to 900, and then push 
100 or so back again, *now* any slice that *had* been pointing to the 
original, say, [920..970] will no longer be pointing to the new values, 
they'll still be pointing to the old values, right?

So, for instance, you can't take an instance on my Stack struct, do "foo = 
stack[0..10]", and then say "foo is guaranteed to always point to the bottom 
10 elements of stack (at least until you change foo)". Right? That's what I 
was referring to with that footnote [4]. To make that kind of guarantee, 
you'd have to specifically code the Stack class so that all slices of the 
Stack get updated whenever the Stack's data gets moved.

Not that slicing a stack would be all that common, but if it were done for 
whatever reason...