Elysian Shadows

I know what the difference between the heap and the stack is when you code. All the stuff about how a stack is a stack and the heap is for dynamically allocated objects and so on.

For some time now, i have wondered about why the designers of C/C++ (and pretty much every other language too, but often hidden from the user) made this distinction.

All i know about how computers work on the hardware level is from the book called "Code - the hidden language of computer hardware and software"(a book more about hardware than the title suggests). Since all my knowledge about the subject comes from this book, it can be hard to judge how accurate it is, but I'm under the assumption that it gives a very detailed description of a very simple/basic computer. (where very is very relative :P)

But from what i gather, RAM works by you giving it an address through some pins (32 on a 32bit computer i think) and it will give you a value through some other pins. If you want to write to it, you can give it some data through a third set of pins and send it a "write" signal through another pin.

Now, if i where to design a way of setting and getting variable values in a language. I would probably have ended up with something like this. One symbol for denoting if you are talking about the value x or the address x (could for instance be x and &x). And then only letting a single address be on the left side of an = sign. Then in a moment of enlightenment i might have had the idea of putting some alias system on top of it, so i didn't need to bother with all those numbers. (Then i would try to implement it and fail epicly)

I'm no C++ expert, but what I've just described seems to me, to look a little like pointers in C++. A way to throw something on the heap and retrieve it again. I think that functions like malloc and free even could be written on top of that!

I realize that I at this point might be talking complete nonsense......

So, as far is i know, "the stack" is not a hardware thing, it is something some software guy came up with, right? My question is, WHY would he do that? Why bother with pushing and popping and pushing again, when you have random access??

------
The good, but also very annoying, thing about writing long question, is that you sometime end up with the answer. As i was writing this, I began to think that i had actually read something about PUSH and POP assembly instructions in Code, so i looked stack up in the register(in the back of the book, not the CPU register).

It seems, that the reason is functions. When you call a function, everything gets pushed to the stack, and when the function returns everything is pop'ed back. In some way this makes sense to me, but i still wonder where it gets pushed from and pop'ed too? Registers? What if you have more variables on the stack than registers? I think code describes it so that only the registers gets pushed to the stack. This makes sense. But why can you declare variables on the stack yourself then? Why would you do it, except to avoid dealing with pointers (and what comes with them in terms of memory leaks and stuff)? Isn't all that pushing and popping slow? Something tells me that it might have something to do with scope, even though I'm not sure how. If that is the case, is scope really that important?

I will also like to know where the stack is implemented. In hardware (Code talks about push and pop instructions, some tutorials talk about "area in memory"), in the OS, in the application(through the std library) or somewhere else?

Okay, maybe more questions than answers...

P.S. Sorry of all of this is nonsense :S

I *think* that working on the stack is MUCH faster then accessing heap memory, as the entire stack is copied to cpu cache memory upon access. When you follow a pointer, it points to some other part of the memory that the processor must retrieve.

One could make a (quite large) benchmark to find out if this is so...

Oh my... Heeeeeeeeere we go... !

ismetteren wrote:For some time now, i have wondered about why the designers of C/C++ (and pretty much every other language too, but often hidden from the user) made this distinction.

If there were no stack, every single variable ever used in the program would either have to be manually dynamically allocated and deallocated on the heap, or every variable would have to persist at global scope. The stack exists to automatically handle the lifetime of temporary data. That's where the "auto" keyword that C inherited from B came from. All variables defaulted to global in B. They could be forced to the stack with the "auto" keyword, which meant that the memory was "automatically" allocated and deallocated.

ismetteren wrote:Now, if i where to design a way of setting and getting variable values in a language. I would probably have ended up with something like this. One symbol for denoting if you are talking about the value x or the address x (could for instance be x and &x). And then only letting a single address be on the left side of an = sign. Then in a moment of enlightenment i might have had the idea of putting some alias system on top of it, so i didn't need to bother with all those numbers. (Then i would try to implement it and fail epicly)

If I understand what you're trying to say, that's already exactly how C works. A variable "x" referenced as "x" is the value at that address. Using the '&' operator in "&x" gives the memory address of the variable x.

When you assign a value to 'x', it is called an lvalue. The compiler is technically referring to its memory address when you do x = 4. Not sure what you're trying to say with "aliasing," (C lets you have multiple pointers to the same address), but that's essentially how it works anyway...

ismetteren wrote:I'm no C++ expert, but what I've just described seems to me, to look a little like pointers in C++.

Because it is...

ismetteren wrote:A way to throw something on the heap and retrieve it again. I think that functions like malloc and free even could be written on top of that!

A pointer can point to either the stack or the heap. I think you have a misconception that "pointer" is associated with the heap. It isn't, it can point to any memory address. So no, pointers are not "ways of throwing something on the heap and retrieving it." They are ways of accessing or "pointing" to memory addresses. When you do: You are allocating two pieces of data. An integer pointer 'i' that resides on the stack, and an actual integer whose memory address is returned by the new operator. This integer resides on the heap.

...and about malloc() and free() being written ontop of that... I think you've partially begun to understand what a pointer is and how it works, and are mistakenly thinking this is in some manner groundbreaking. malloc() and free() DO operate on memory addresses. One allocates data and returns a heap address, and the other frees the data at the address of a given pointer...

ismetteren wrote:So, as far is i know, "the stack" is not a hardware thing, it is something some software guy came up with, right? My question is, WHY would he do that? Why bother with pushing and popping and pushing again, when you have random access??

I mean no offense, but if you have to ask this question, you DON'T understand how the stack works... at all. The stack is absolutely not a hardware thing. The hardware USUALLY offers assembly opcodes to facilitate a software stack (although these aren't even necessary). And I've already answered you as to the stack's purpose. How would you manage memory without it? Allocate every variable in the entire application as a persisting global or have to manually dynamically allocate and deallocate each variable?

ismetteren wrote:It seems, that the reason is functions. When you call a function, everything gets pushed to the stack, and when the function returns everything is pop'ed back.

HE GETS IT!!! That's all the stack is. It's the data/variables local to each function that are being allocated ("pushed") and deallocated ("popped") from memory.

ismetteren wrote:In some way this makes sense to me, but i still wonder where it gets pushed from and pop'ed too? Registers?

...maybe he doesn't get it. No, they get pushed and popped to your RAM.

ismetteren wrote:What if you have more variables on the stack than registers?

You have a dozen or so general-purpose registers that can hold either 32 or 64 bits each. You have GIGABYTES of RAM. Of COURSE you have more variables on the stack than registers... that's the whole point.

ismetteren wrote:I think code describes it so that only the registers gets pushed to the stack.

I think you have managed to thoroughly confuse the shit out of yourself by reading too many low level books before understand how the higher levels work... DATA is pushed onto the stack. That data can come from registers. That data can come from somewhere else in memory. When a function is called, it requires registers to operate. The previous function may need data that is still in these registers. So the previous function pushes the registers to the stack, calls the function (which clobbers the registers), then pops them back off to get their old value. You need to look up what a "stack frame" is and how it works.

ismetteren wrote: Why would you do it, except to avoid dealing with pointers (and what comes with them in terms of memory leaks and stuff)? Isn't all that pushing and popping slow?

Slow compared to requesting every byte of data dynamically from a runtime? Hell no. And also think about what a pain in the ass that would be. And what about the cache benefits of a structure like a stack? There's quite a bit you aren't factoring in.

ismetteren wrote:Something tells me that it might have something to do with scope, even though I'm not sure how.

Then you REALLY, REALLY should learn what the stack is...

ismetteren wrote:I will also like to know where the stack is implemented. In hardware (Code talks about push and pop instructions, some tutorials talk about "area in memory"), in the OS, in the application(through the std library) or somewhere else?

It's software, so no hardware support is required (but like I said, there are stack pointer registers and push and pop instructions, usually). Usually the operating system allocates or initializes the stack, although you can do it yourself at the software level (or in embedded systems where there is no OS).

I mean no offense, but your post shows that you clearly do NOT understand how the stack works. I recommend putting down whatever low-level architecture/organization book is talking about pushing registers onto a software stack, and start with the basics in a C/++ book. You've confused the hell out of yourself by going too low level before understanding the higher levels.

The performance issue does not lie in the C code or the assembly. You'll note that if you look at the un-optimized assembly from any decent compiler, between stack and heap access there is hardly any difference. To a high level language, memory is memory is memory is memory. Doesn't matter if it comes from the disk, DRAM, L3, L2, L1...wherever.

What DOES matter is how the OS deals with distributing this.

Now its not easy enough to say that stack always outperforms heap because it does not. With small data sets with very sequential access patterns, heap can actually be a LITTLE faster. Where you'll run into problems is when you start swapping pages. Now since your allowable stack size is very small and the default page size on most OS's is 4096 bytes (~4kb), its MOST likely that for any access pattern across a stack allocated array, that the memory we are requesting is likely to be in L2 or L1, which is extremely fast.

When you request memory to be read, the processor will actually fetch the pages immediately near the memory being requested because subsequent fetches are likely to be spatially local. This is called "prefetching". So its clear that with a small set, whether it be heap or stack allocated is likely to be present in L1/L2 if you're dealing with only several pages of data.

However, the WORST case is that you have large data sets that extend beyond many many pages of memory. (A page is the smallest memory that will ever be returned to the program by the OS). The worst case is that lets say you have 32 pages of memory. So if you have a heap or stack allocation, the worst you can do is access memory as follows: 0, 31, 1, 30, 2, 29, 3, 28....etc. This is completely random and at this point the processor is loading and unloading pages and pages of data at high frequency. The difference is that depending on where the memory actually IS, the processor may have to go out further for the memory fetch.

This is why it is not always the case that stack > heap. In many cases you'll be working with data sets that are sufficiently large as to out-grow the capacity of a stack. "The quadratic problems of today are the n-problems of tomorrow". So then its generally acceptable to say that, yes the stack outperforms the heap but you're not likely to be working with such small allocations so frequently, and in the cases where you ARE going to be working with such small allocations the difference is negligible unless you're accessing the memory in an unpredictable fashion or a poor fashion. You simply have to be aware that the access patterns that you use to query into heap allocated memory GREATLY affect your overall execution time simply because the memory you're requesting should be as temporally local as absolutely possible. The penalty for this is also severe for stack allocation as well....(see: striding the cache, data alignment). Depending on the system, the penalty may be significantly more severe or less severe. There are many implications here and its not something many beginning programmers really think about but there is alot more to writing good programs than being able "to code".

TL;DR Be judicious about your data structures and algorithms as to be as sequential as possible because whether you're using the stack OR the heap, poor algorithms will bite you in the ass every single time.

Just a note.

Shouldn't this stuff be flagged in the education index?

/derail

wtf is an education index?

/underail

GyroVorbis wrote: I mean no offense, but your post shows that you clearly do NOT understand how the stack works. I recommend putting down whatever low-level architecture/organization book is talking about pushing registers onto a software stack, and start with the basics in a C/++ book. You've confused the hell out of yourself by going too low level before understanding the higher levels.

I see..

I meant that i had read some short explanations and that I was more interested in the reason why you would use a stack. But I see now that i knew/know a lot less than i thought. I also shouldn't have made the post so long, since I'm not a very good writer and even worse when I Have to use english, so it became kind of clumsy, i think.

IIRC, the first thing that puzzled me, was that you would restrict yourself to LIFO access when you had random access. But is it right that if you in a function declare first "int a;" (and it gets pushed to the stack) and then "int b;" (which is now on top of the stack), you can actually assign a value directly to a without first popping b, as opposed to the kind of stack you use as a data structure inside of your program? If so that would make a lot of sense to me.

Anyways this was way more complicated than i first thought and a really appreciate the the time you have taken to write the answers :D

ismetteren wrote:But is it right that if you in a function declare first "int a;" (and it gets pushed to the stack) and then "int b;" (which is now on top of the stack), you can actually assign a value directly to a without first popping b, as opposed to the kind of stack you use as a data structure inside of your program? If so that would make a lot of sense to me.

You're confusing yourself again... OF COURSE this is valid: I just set the value of 'a' with 'b' being last on the stack... From a software perspective, the only implication of the stack is the LIFETIME/SCOPE of variables. Of course you can access them however you want. For all you know, it might not even be a stack in the background (although any other implementation would be stupid).

It appears to me that you are confusing what is relevant to C/++ and what is relevant to assembly. Don't go too low level too fast.