标签云

微信群

扫码加入我们

WeChat QR Code

什么是栈和堆?

Programming language books explain that value types are created on the stack, and reference types are created on the heap, without explaining what these two things are. I haven't read a clear explanation of this. I understand what a stack is, but where and what are they (physically in a real computer's memory)?

  • To what extent are they controlled by the OS or language runtime?
  • What is their scope?
  • What determines the size of each of them?
  • What makes one faster?


a really good explanation can be found here What’s the difference between a stack and a heap?

2018年05月23日38分21秒

Also (really) good: codeproject.com/Articles/76153/… (the stack/heap part)

2018年05月23日38分21秒

Good explanation can be found here

2018年05月23日38分21秒

youtube.com/watch?v=clOUdVDDzIM&spfreload=5

2018年05月23日38分21秒

Related, see Stack Clash. The Stack Clash remediations affected some aspects of system variables and behaviors like rlimit_stack. Also see Red Hat Issue 1463241

2018年05月23日38分21秒

Jeff - your answer was superb - I wanted to have this kind of question in a similar way to use as an interview question - then I realised I didn't exactly know the answer myself either! How bad is is that?! And FYI : bookkeeper is the ONLY English word with 3 consecutive double letters ;)

2018年05月23日38分21秒

Good answer - but I think you should add that while the stack is allocated by the OS when the process starts (assuming the existence of an OS), it is maintained inline by the program. This is another reason the stack is faster, as well - push and pop operations are typically one machine instruction, and modern machines can do at least 3 of them in one cycle, whereas allocating or freeing heap involves calling into OS code.

2018年05月23日38分21秒

I'm really confused by the diagram at the end. I thought I got it until I saw that image.

1970年01月01日00分03秒

Anarelle the processor runs instructions with or without an os. An example close to my heart is the SNES, which had no API calls, no OS as we know it today - but it had a stack. Allocating on a stack is addition and subtraction on these systems and that is fine for variables destroyed when they are popped by returning from the function that created them, but constrast that to, say, a constructor, of which the result can't just be thrown away. For that we need the heap, which is not tied to call and return. Most OS have APIs a heap, no reason to do it on your own

2018年05月23日38分21秒

Lee James - Is it? I can count at least 3 of them: bookkeeper, bookkeeping and bookkeep :-)

2018年05月23日38分21秒

The pointer pBuffer and the value of b are located on the stack, and are mostly likely allocated at the entrance to the function. Depending on the compiler, buffer may be allocated at the function entrance, as well.

2018年05月23日38分21秒

It is a common misconception that the C language, as defined by the C99 language standard (available at open-std.org/JTC1/SC22/WG14/www/docs/n1256.pdf ), requires a "stack". In fact, the word 'stack' does not even appear in the standard. This answers statements wrt/ to C's stack usage are true in general, but is in no way required by the language. See knosof.co.uk/cbook/cbook.html for more info, and in particular how C is implemented on odd-ball architectures such as en.wikipedia.org/wiki/Burroughs_large_systems

2018年05月23日38分21秒

Brian You should explain why buffer[] and the pBuffer pointer are created on the stack and why pBuffer's data is created on the heap. I think some ppl might be confused by your answer as they might think the program is specifically instructing that memory be allocated on the stack vs heap but this is not the case. Is it because Buffer is a value type whereas pBuffer is a reference type?

2018年05月23日38分21秒

Remover: No a pointer holds an address and it can point to something on the heap or the stack equally. new, malloc, and some other functions similar to malloc allocate on the heap and return the address of the memory that was allocated. Why would you want to allocate on the heap? So that your memory won't go out of scope and get released until you want it to.

2018年05月23日38分21秒

"Responsible for memory leaks" - Heaps are not responsible for memory leaks! Lazy/Forgetful/ex-java coders/coders who dont give a crap are!

2018年05月23日38分21秒

David I don't agree that that is a good image or that "push-down stack" is a good term to illustrate the concept. When you add something to a stack, the other contents of the stack aren't pushed down, they remain where they are.

2018年05月23日38分21秒

This answer includes a big mistake. Static variables are not allocated on the stack. See my answer [link] stackoverflow.com/a/13326916/1763801 for clarification. you are equating "automatic" variables with "static" variables, but they are not at all the same

2018年05月23日38分21秒

Specifically, you say "statically allocated local variables" are allocated on the stack. Actually they are allocated in the data segment. Only automatically allocated variables (which includes most but not all local variables and also things like function parameters passed in by value rather than by reference) are allocated on the stack.

2018年05月23日38分21秒

I've just realised you're right - in C, static allocation is its own separate thing rather than a term for anything that's not dynamic. I've edited my answer, thanks.

1970年01月01日00分03秒

It's not just C. Java, Pascal, Python and many others all have the notions of static versus automatic versus dynamic allocation. Saying "static allocation" means the same thing just about everywhere. In no language does static allocation mean "not dynamic". You want the term "automatic" allocation for what you are describing (i.e. the things on the stack).

2018年05月23日38分21秒

Martin - A very good answer/explanation than the more abstract accepted answer. A sample assembly program showing stack pointers/registers being used vis a vis function calls would be more illustrative.

2018年05月23日38分21秒

Every reference type is composition of value types(int, string etc). As it is said, that value types are stored in stack than how does it work when they are part of reference type.

2018年05月23日38分21秒

This answer was the best in my opinion, because it helped me understand what a return statement really is and how it relates to this "return address" that I come across every now and then, what it means to push a function onto the stack, and why functions are pushed onto stacks. Great answer!

2018年05月23日38分21秒

This is the best in my opinion, namely for mentioning that the heap/stack are very implementation specific. The other answers assume a lot of things about the language and the environment/OS. +1

2018年05月23日38分21秒

What do you mean "The code in the function is then able to navigate up the stack from the current stack pointer to locate these values." ? Can you elaborate on this please?

2018年05月23日38分21秒

This is incorrect. i and cls are not "static" variables. they are called "local" or "automatic" variables. It is a very important distinction. See [link] stackoverflow.com/a/13326916/1763801 for clarification

2018年05月23日38分21秒

I did not say they were static variables. I said that int and cls1 are static items. Their memory is statically allocated and therefore they go on the stack. This is in contrast to an object which requires dynamic memory allocation which therefore goes on the heap.

2018年05月23日38分21秒

I quote "Static items... go on the stack". This is just flat out wrong. Static items go in the data segment, automatic items go on the stack.

2018年05月23日38分21秒

Also whoever wrote that codeproject article doesn't know what he is talking about. For instance, he says "primitive ones needs static type memory" which is completely untrue. Nothing stops you from allocating primitives in the heap dynamically, just write something like "int array[] = new int[num]" and voila, primitives allocated dynamically in .NET. That is just one of several inaccuracies.

2018年05月23日38分21秒

I edited your post because you have made serious technical mistakes about what goes in the stack and heap.

2018年05月23日38分21秒

A recommendation to avoid using the heap is pretty strong. Modern systems have good heap managers, and modern dynamic languages use the heap extensively (without the programmer really worrying about it). I'd say use the heap, but with a manual allocator, don't forget to free!

2018年05月23日38分21秒

If you can use the stack or the heap, use the stack. If you can't use the stack, really no choice. I use both a lot, and of course using std::vector or similar hits the heap. For a novice, you avoid the heap because the stack is simply so easy!!

2018年05月24日38分21秒

If your language doesn't implement garbage collection, Smart pointers (Seporately allocated objects that wrap around a pointer which do reference counting for dynamically allocated chunks of memory) are closely related to garbage collection and are a decent way of managing the heap in a safe and leak free manner. They are implemented in various frameworks, but are also not that tough to implement for your own programs as well.

2018年05月24日38分21秒

I would refer to a static variable declared within a function as having only local accessibility, but would generally not use the term "scope" with it. Also, it may be worth noting that the one stack/heap aspect with which languages have essentially zero flexibility: a language which saves execution context on a stack cannot use that same stack to hold things which will need to outlive the contexts wherein they are created. Some languages like PostScript have multiple stacks, but have a "heap" that behaves more like a stack.

2018年05月23日38分21秒

supercat That all makes sense. I defined scope as "what parts of the code can access a variable" (and feel this is the most standard definition) so I think we agree :)

2018年05月23日38分21秒

I would regard the "scope" of a variable as being bounded by time as well as space. A variable at class-object scope is required to hold its value as long as the object exists. A variable within an execution-context scope is required to hold its value as long as execution remains in that context. A static variable declaration creates an identifier whose scope is bounded to the current block, which is attached to a variable whose scope is unbounded.

2018年05月23日38分21秒

supercat This is why I use the word lifetime, which is how I term what you call time scope. It reduces the need to overload the word "scope" with so many meanings. As far as I can tell, there doesn't seem to be total consensus on exact definitions though, even among canonical sources. My terminology is drawn partially from K&R and partially from the prevailing usage at the first CS department I studied/taught at. Always good to hear another informed view.

2018年05月23日38分21秒

you must be kidding. can you really define static variable inside a function ?

2018年05月23日38分21秒

Re "as opposed to alloc": Do you mean "as opposed to malloc"?

2018年05月23日38分21秒

How portable is alloca?

2018年05月23日38分21秒

PeterMortensen it's not POSIX, portability not guaranteed.

2018年05月23日38分21秒

Another nitpick- most of the answers (lightly) imply that the use of a "stack" is required by the C language. This is a common misconception, though it is the (by far) dominate paradigm for implementing C99 6.2.4 automatic storage duration objects (variables). In fact, the word "stack" does not even appear in the C99 language standard: open-std.org/JTC1/SC22/WG14/www/docs/n1256.pdf

2018年05月23日38分21秒

[Heath] I have a small comment on your answer. Take a look at the accepted answer to this question. It says that the free store most probably is the same as the heap, though not necessarily is.

2018年05月23日38分21秒

Also worth mentioning here that intel heavily optimizes stack accesses, especially things such as predicting where you return from a function.

2018年05月23日38分21秒

How portable is alloca? For instance, does it work on Windows? Is it only for Unix-like operating systems?

2018年05月23日38分21秒

[T.E.D.] Why did you say "sometimes the parameters get pushed on the stack"? What I know is that they always are. Could you please elaborate more?

2018年05月23日38分21秒

OmarOthman - I say that because it is entirely up to the writer of your compiler/interpreter what happens when a subroutine is called. Classic Fortran behavior is to not use a stack at all. Some languages support exotic things like pass-by-name, which is effectively a textual substitution.

2018年05月23日38分21秒

"I like the accepted answer better since it's even more low level." That's a bad thing, not a good thing.

2018年05月23日38分21秒

Could you please translate this answer to English?

2018年05月23日38分21秒

What is OPP? Do you mean OOP (object-oriented_programming)?

2018年05月23日38分21秒

Do you mean to say that malloc is a kernel call?

2018年05月24日38分21秒

1) yes, sorry.. OOP... 2) malloc: I write shortly, sorry ... malloc is in user space.. but can trigger down other calls.... the point is that using heap CAN be very slow...

2018年05月24日38分21秒