Re: Don't use arrays as stacks
"Nick Sabalausky" wrote in message news:j5vte2$3ql$1...@digitalmars.com... > > ...Although I'm not [*sure*] I like the implications... >
Re: Don't use arrays as stacks
"Steven Schveighoffer" wrote in message news:op.v2i2yv0beav7ka@localhost.localdomain... > On Wed, 28 Sep 2011 12:11:29 -0400, Nick Sabalausky wrote: > >> Of course, as it is now, the slice owner won't even know if >> the values it points to have been pooped off and *not* been pushed back >> on >> again. > > Freudian slip or simple typo? Either way, *hilarious* :) lmao. And it's surprisingly appropriate for the context. > Gives a new mental picture for a stack... Yea, and properly "upside-down" just like our trees. Although I'm not I like the implications that has for "push"...I guess that means the analogy would be better suited for a FIFO.
Re: Don't use arrays as stacks
On Wed, 28 Sep 2011 12:11:29 -0400, Nick Sabalausky wrote: Of course, as it is now, the slice owner won't even know if the values it points to have been pooped off and *not* been pushed back on again. Freudian slip or simple typo? Either way, *hilarious* :) Gives a new mental picture for a stack... -Steve
Re: Don't use arrays as stacks
"Steven Schveighoffer" wrote in message news:op.v2ita9hseav7ka@localhost.localdomain... > On Tue, 27 Sep 2011 00:22:02 -0400, Nick Sabalausky wrote: > > There's never a guarantee that a slice will always point at the current > values. There can't be, because you can never guarantee it will not be > reallocated on expansion. > Right. > But what I thought you were talking about is popping values off, and then > pushing values on, without exceeding the capacity. In fact, you would be > guaranteed the slice contains the newer values, even if a reallocation > occurs, since you have to push values into the slice before exceeding the > capacity. > > The situation you describe in this reply is, take a slice, push elements > on exceeding capacity, then pop elements back, then push elements on. > Quite different :) > Yes, but the slice "owner" won't necessarily know which of those scenarios has occurred. Of course, as it is now, the slice owner won't even know if the values it points to have been pooped off and *not* been pushed back on again. That said, I agree with you below: > You could create a "stack slice" which instead of pointing at the memory, > points at the stack aggregate itself (which would actually have to be > heap-allocated), and have the lower and upper bounds. Then a "slice" of > that type would continue to point at the current data. > I should definitely do something like that (or just eliminate the ability to take a slice, but I suspect that might be a little more limiting that it might initially seem). Or maybe I should just take a look at dcollections ;)
Re: Don't use arrays as stacks
On Tue, 27 Sep 2011 00:22:02 -0400, Nick Sabalausky wrote: "Steven Schveighoffer" wrote in message [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.) Yes, that's a better description. 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. There's never a guarantee that a slice will always point at the current values. There can't be, because you can never guarantee it will not be reallocated on expansion. But what I thought you were talking about is popping values off, and then pushing values on, without exceeding the capacity. In fact, you would be guaranteed the slice contains the newer values, even if a reallocation occurs, since you have to push values into the slice before exceeding the capacity. The situation you describe in this reply is, take a slice, push elements on exceeding capacity, then pop elements back, then push elements on. Quite different :) You could create a "stack slice" which instead of pointing at the memory, points at the stack aggregate itself (which would actually have to be heap-allocated), and have the lower and upper bounds. Then a "slice" of that type would continue to point at the current data. -Steve
Re: Don't use arrays as stacks
"bearophile" wrote in message
news:j5rn5o$1q0g$1...@digitalmars.com...
> Nick Sabalausky:
>
>> Not that slicing a stack would be all that common, but if it were done
>> for
>> whatever reason...
>
> Is it possible to write a function like:
>
> ForeachType!A unsafePop(A)(A)if(isDynamicArray!A) { /*...*/ }
>
> that contains both the popping (and something like assumeSafeAppend to
> mess with the druntime data structures) and use it to allow a stack-like
> usage of D dynamic arrays? (This function is not meant to replace the
> usage of a proper stack data structure based on a deque when you need a
> heavy-duty stack, but it's handy in other lighter cases).
>
Umm, maybe. Sounds like it should be feasable, though I haven't tried.
Although going by what Steve said about assumeSafeAppend, it might actually
end up slower than a wrapped Stack type that doesn't use assumeSafeAppend.
Re: Don't use arrays as stacks
Nick Sabalausky:
> Not that slicing a stack would be all that common, but if it were done for
> whatever reason...
Is it possible to write a function like:
ForeachType!A unsafePop(A)(A)if(isDynamicArray!A) { /*...*/ }
that contains both the popping (and something like assumeSafeAppend to mess
with the druntime data structures) and use it to allow a stack-like usage of D
dynamic arrays? (This function is not meant to replace the usage of a proper
stack data structure based on a deque when you need a heavy-duty stack, but
it's handy in other lighter cases).
Bye,
bearophile
Re: Don't use arrays as stacks
"Steven Schveighoffer" wrote in message news:op.v2e19fkieav7ka@localhost.localdomain... > On Sun, 25 Sep 2011 02:37:25 -0400, Nick Sabalausky 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...
Re: Don't use arrays as stacks
On Sun, 25 Sep 2011 07:05:34 -0400, Nick Sabalausky wrote: "Jonathan M Davis" wrote in message news:mailman.160.1316939358.26225.digitalmar...@puremagic.com... On Sunday, September 25, 2011 03:18:29 Andrew Wiley wrote: Isn't this exactly what assumeSafeAppend is for? Hmm, I didn't know about that. (Actually, I remember hearing it mentioned before, but then totally forgot about it.) and if you're using assumeSafeAppend, then you need to guarantee that nowhere else has a reference to that array (otherwise it's _not_ safe to assume that it's safe to append) Would the consequences of failing to do that be any worse (or any different at all?) than what I mentioned about: "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 reflect the new values, not the original ones." ...? The caveat is the same, however, you should continue doing it the way you are doing it. Using the runtime is somewhat magic, and there is a cost for being that magical -- too many runtime calls :) Every call to capacity and assumeSafeAppend *cannot* be inlined or optimized, since they end up calling extern(C) function prototypes. BTW, if you want to compare your performance with a stack implementation that uses assumeSafeAppend, try out dcollections' ArrayList, in which popBack does use assumeSafeAppend. -Steve
Re: Don't use arrays as stacks
On Sun, 25 Sep 2011 02:37:25 -0400, Nick Sabalausky 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! For more information about D's arrays and slicing, see Steven Schveighoffer's award-winning article, D Slices. :D [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. 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. -Steve
Re: Don't use arrays as stacks
Nick Sabalausky wrote: > "Jonathan M Davis" wrote in message > news:mailman.160.1316939358.26225.digitalmar...@puremagic.com... >> On Sunday, September 25, 2011 03:18:29 Andrew Wiley wrote: >>> >>> Isn't this exactly what assumeSafeAppend is for? > > Hmm, I didn't know about that. (Actually, I remember hearing it mentioned > before, but then totally forgot about it.) > >> >> and if you're using assumeSafeAppend, then you >> need to guarantee that nowhere else has a reference to that array >> (otherwise >> it's _not_ safe to assume that it's safe to append) >> > > Would the consequences of failing to do that be any worse (or any > different at all?) than what I mentioned about: > > "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 reflect the new values, not the original ones." > > ...? It looks like it behaves the same, but the docs mention this: 'Calling this function, and then using references to data located after the given array results in undefined behavior.' So it is not wise to depend on it. One thing that wasn't clear to me (but might be obvious): after modifying an array, the behavior is reset and you will need to call assumeSafeAppend again.
Re: Don't use arrays as stacks
Nick Sabalausky:
> https://www.semitwist.com/articles/article/view/don-t-use-arrays-as-stacks
Is it possible to write a function like:
ForeachType!A unsafePop(A)(A)if(isDynamicArray!A) { /*...*/ }
that contains both the popping (and something like assumeSafeAppend to mess
with the druntime data structures) and use it to allow a stack-like usage of D
dynamic arrays? (This function is not meant to replace the usage of a proper
stack data structure based on a deque when you need a heavy-duty stack, but
it's handy in other lighter cases).
Bye,
bearophile
Re: Don't use arrays as stacks
On Sunday, September 25, 2011 07:05:34 Nick Sabalausky wrote: > "Jonathan M Davis" wrote in message > news:mailman.160.1316939358.26225.digitalmar...@puremagic.com... > > > On Sunday, September 25, 2011 03:18:29 Andrew Wiley wrote: > >> Isn't this exactly what assumeSafeAppend is for? > > Hmm, I didn't know about that. (Actually, I remember hearing it mentioned > before, but then totally forgot about it.) > > > and if you're using assumeSafeAppend, then you > > need to guarantee that nowhere else has a reference to that array > > (otherwise > > it's _not_ safe to assume that it's safe to append) > > Would the consequences of failing to do that be any worse (or any different > at all?) than what I mentioned about: > > "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 reflect the new values, not the original ones." > > ...? I'm not sure. If you have 2 slices which point to the same memory, and one is longer than the other, and then you call assumeSafeAppend on the smaller one, then if you append to the smaller one, it will increase its size into the smaller one, which may or may not cause issues depending on what you're doing. The real potential issue though is what happens if you use the longer slice and append to it. I really don't know what happens at that point. It'll probably just adjust the information on that block such that the pointer (or length - I'm not sure which it is) that it keeps to the end of the longest slice may be adjusted accordingly, or it could cause issues, because the end of that slice is already beyond what the block thinks is the end of the longest slice. So, the problem is more or less the same as the situation that you gave, but I'm not sure that it's identical. Regardless, it's just safer to wrap the array in a stack struct and not give access to the array. Normally all you care about with a stack is pushing and popping elements on and off and possibly peeking at the top element - none of which require having access to the array - so wrapping the array and not giving external access to it should work just fine. - Jonathan M Davis
Re: Don't use arrays as stacks
"Jonathan M Davis" wrote in message news:mailman.160.1316939358.26225.digitalmar...@puremagic.com... > On Sunday, September 25, 2011 03:18:29 Andrew Wiley wrote: >> >> Isn't this exactly what assumeSafeAppend is for? Hmm, I didn't know about that. (Actually, I remember hearing it mentioned before, but then totally forgot about it.) > > and if you're using assumeSafeAppend, then you > need to guarantee that nowhere else has a reference to that array > (otherwise > it's _not_ safe to assume that it's safe to append) > Would the consequences of failing to do that be any worse (or any different at all?) than what I mentioned about: "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 reflect the new values, not the original ones." ...?
Re: Don't use arrays as stacks
On Sunday, September 25, 2011 03:18:29 Andrew Wiley wrote: > On Sun, Sep 25, 2011 at 1:45 AM, Jonathan M Davis wrote: > > On Sunday, September 25, 2011 02:37:25 Nick Sabalausky 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-st > >> acks> > > Yeah. If you want to use an array for a stack, it really needs to be > > wrapped in a struct or class like you'd do in C++. Expanding it when > > the size of the array needs to increase to accomodate items pushed onto > > the stack is certainly much easier in D, but trying to use the array as > > a stack directly is definitely going to cause issues as you show in the > > article. > > > > - Jonathan M Davis > > Isn't this exactly what assumeSafeAppend is for? Sure, you could do that, but simply concatenating to push and then slicing to pop doesn't work. You need to do something like use assumeSafeAppend or just treat the stack as being part of the array instead of the whole. And in either case, if the array isn't wrapped in a struct or class, you're asking for trouble. In the case where you're just using part of the array as a stack, you need something to keep track of which part of the array is currently the stack, so you need a wrapper, and if you're using assumeSafeAppend, then you need to guarantee that nowhere else has a reference to that array (otherwise it's _not_ safe to assume that it's safe to append), so you need a wrapper. In either case, you need a wrapper. - Jonathan M Davis
Re: Don't use arrays as stacks
On Sun, Sep 25, 2011 at 1:45 AM, Jonathan M Davis wrote: > On Sunday, September 25, 2011 02:37:25 Nick Sabalausky 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 > > Yeah. If you want to use an array for a stack, it really needs to be wrapped > in a struct or class like you'd do in C++. Expanding it when the size of the > array needs to increase to accomodate items pushed onto the stack is certainly > much easier in D, but trying to use the array as a stack directly is > definitely > going to cause issues as you show in the article. > > - Jonathan M Davis > Isn't this exactly what assumeSafeAppend is for?
Re: Don't use arrays as stacks
"Nick Sabalausky" wrote in message news:j5mi7l$1dtf$1...@digitalmars.com... > 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 And don't worry, it's not as long as my contest "article" was ;)
Re: Don't use arrays as stacks
On 9/25/11 1:37 AM, Nick Sabalausky 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 piece. http://www.reddit.com/r/programming/comments/kqoz2/dont_use_d_arrays_as_stacks/ Andrei
Re: Don't use arrays as stacks
On Sunday, September 25, 2011 02:37:25 Nick Sabalausky 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 Yeah. If you want to use an array for a stack, it really needs to be wrapped in a struct or class like you'd do in C++. Expanding it when the size of the array needs to increase to accomodate items pushed onto the stack is certainly much easier in D, but trying to use the array as a stack directly is definitely going to cause issues as you show in the article. - Jonathan M Davis
Don't use arrays as stacks
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
