Efficiency of using array as stack

[Jonathan M Davis]

On Sunday, March 24, 2013 00:45:21 Ivan Kazmenko wrote:
> So, what is the exact strategy of growing an array?  Maybe you
> could just kindly point me to some more interesting reading in
> druntime source?

I'd start by looking in src/Object_.d, but it looks like the information that 
you'd be looking for is probably in src/rt/lifetime.d, but I'd have to go 
digging through the code to figure out what druntime currently does. 
Regardless, remember that all of that is implementation-dependent, so if 
you're relying on a particular behavior with regards to how much druntime 
allocates when reallocating an array or anything like that, it could change on 
you at any time. It probably doesn't get changed much, but there's zero 
guarantee that it won't be, and if someone comes up with a way to improve how 
that works, its implementation would change. So, relying on how that works is 
probably not a good idea. You should be able to reliably know _when_ a 
reallocation is going to occur by paying attention to capacity, but stuff like 
how much memory gets allocated could change at any time.

> And, well, now how do I implement a generally
> efficient array-based queue in D?

By not removing elements from the front like that. You're just guaranteeing 
that you're going to have to reallocate the array at some point, even if 
you're always dealing with a small number of elements. I'd suggest making it a 
circular queue and keeping track of where in the array the first element is as 
well as the length. You'd have to reallocate if you ever reach the point that 
the queue is full, and the first element in the queue was not the first element 
in the array, but if you're queue size never had to grow, you'd never have to 
reallocate, whereas with the scheme that you proposed, you'll have to 
reallocate every time that you've queued as many items as the original 
capacity of the array.

If you're going to try and use an array to implement another data structure, I 
would strongly suggest that you use a wrapper struct, and that you generally 
try and treat the array as a block of memory that you need to manage rather 
than relying a lot of array magic. The array magic is cool, but it's likely to 
have performance characteristics which conflict with what you need for other 
data structures (like stacks or queues).

- Jonathan M Davis