Is this a reasonable way to implement a stack ?

[Harovan]

Originally posted by loinburger
It unnecessarily bounds the size of your stack and introduces a lot of internal fragmentation.

A linked list of small (say, 4-12 elements) arrays reduces memory overhead, has minimal internal fragmentation, improves cache performance, and lets you do some loop transformations that aren't possible with a simple linked list (e.g., loop unrolling). Implementing the stack as one massive array doesn't gain you much over the linked list of arrays, and its disadvantages greatly outweigh its negligible advantages.

Yes, it's a simple way to code a stack. No, you should never code a stack this way.

That depends a bit where you're coming from.

If you implement the stack for an application on a PC with 1 or more gigs of memory, a swap file and a powerful OS for the memory management, which reboots at least once a day, so that memory leaks aren't all that dangerous, you can make your stack open-ended with dynamic allocation.

If however you implement the stack as part of the firmware of an embedded system with merely a few KB or MB RAM, without mass storage for a swap file, and which is supposed to run several months or even years without reboot, you'd better implement it the way UR said, avoiding per-element dynamic allocation. And you'll make yourself carefully sure, that this hard limit is never exceeded.

[Harovan]

Originally posted by loinburger
Is private the default?

Yes for classes, no for structs. That's btw the only difference between them in C++.

[loinburger]

Originally posted by Sir Ralph
If however you implement the stack as part of the firmware of an embedded system

That's true, I just usually don't associate C++ with embedded or hard real-time systems -- you pretty much aren't allowed to use any of the features that distinguish C++ from C.

[Harovan]

You can write firmware or software for embedded systems in C++ and take advantage of type safety, data encapsulation, property derivation and all that, what C++ grants. There are of course some differences. You won't likely use streams, they're useless for this purpose, your I/O devices are hardly streamable. You won't use dynamic memory allocation during runtime, but maybe only once during initialization. And most importantly, you will either not use exceptions at all, or make damn sure, that every single one of them is appropriately caught. Remember you mostly won't have a display, where a window pops up with an error message. You'll for the most part have only a red LED to show an error state - if at all.

[Urban Ranger]

Originally posted by loinburger
It unnecessarily bounds the size of your stack and introduces a lot of internal fragmentation.

Well, the size of the stack is always bounded. For example, a hypothetical machine may have a 128-entry stack that is 32-bit wide.

[Harovan]

No UR, it's not. In most implementations, which use containers and dynamic memory allocation (take the STL for an example), stack sizes are open and limited only by the capacity of the particular computer.

[loinburger]

And even if you're talking about the call stack, most (all?) compilers have an option to increase its size. Or you can do a CPS transformation, and then you've effectively got a call stack with an unlimited size.

[Fve Crathva]

I think what UR means is that the stack should take up all available memory, so that you can have all the benefits of dynamic allocation, without having to worry all the extra crap that makes things so complicated.

SP

[Provost Harrison]

Can we talk about MBTs please? It was so much more stimulating...

[loinburger]

Originally posted by Fve Crathva
I think what UR means is that the stack should take up all available memory, so that you can have all the benefits of dynamic allocation, without having to worry all the extra crap that makes things so complicated.

SP

Better yet, if the stack is external then you'd only be limited by the capacity of your hard drive(s) rather than by the capacity of your RAM. With enough hard drives, you could allocate multiple terabytes of storage for your stack! Try overflowing that stack, hackers!!!

Originally posted by Provost Harrison
Can we talk about MBTs please? It was so much more stimulating...

I'll get the ball rolling. My favorite MBT is the one that's got a main cannon and also has a mounted machine gun. I forget its name.

[Skanky Burns]

Hello code tags

[Fve Crathva]

Originally posted by loinburger
I'll get the ball rolling. My favorite MBT is the one that's got a main cannon and also has a mounted machine gun. I forget its name.

Sheila?

SP

[metalhead]

I should probably leave forever again.

[Urban Ranger]

Originally posted by Sir Ralph
No UR, it's not. In most implementations, which use containers and dynamic memory allocation (take the STL for an example), stack sizes are open and limited only by the capacity of the particular computer.

For a general purpose CPU with a hardware stack pointer, the size of the stack is bound by the size of the stack pointer. Microcontrollers are more interesting since the available RAM is usually much more limited.

[Harovan]

Originally posted by Skanky Burns

Hello code tags

What's interesting is, that I used them (try quoting my post), but they didn't do squat other than changing the font to Courier.