Simple question about stack and heap
Author
In many, if not all, programming languages, there's a distinction between declaring things on the stack and on the heap. I know the differences between the two and how they work, but yet have a question about it:
Is this distinction between the stack and the heap created by the programming language (or its compiler), or by the underlying architecture, operating system or hardware?
I can imagine why they're both needed, you need some pool of memory, and something that works like a stack to handle nested function calls. But has this distinction always been there, has it historically grown, and there alternatives that have been tried out and died or that may pop up later? Stacks and heaps are both very simple data structures, could more complex ones have uses here?
Quote:Original post by Lode
Is this distinction between the stack and the heap created by the programming language (or its compiler), or by the underlying architecture, operating system or hardware?
Every architecture that I know has the call stack implemented in hardware. There's a special register that stores the top of the stack (for example esp on x86 and %sp on Sparc), and there either special push and pop instructions (CISC) or you use normal arithmetic on the stack pointer (RISC). So doing function calls and parameter passing are possible in assembly language without further support from anything else.
Native languages need support by the operating system and/or some runtime system to manage the heap, and despite its name, it's rarely actually implemented with the data structure that is known as a "heap". In modern languages that use compacting garbage collectors, the heap is a simple linear data structure, and allocating memory is just adding an offset to a "top of heap" pointer.
Quote:Original post by LodeA bit of both I suppose, they did grow up together after all.
Is this distinction between the stack and the heap created by the programming language (or its compiler), or by the underlying architecture, operating system or hardware?
As for alternatives there isn't much I can think of off hand. There's plenty of radically different non-imperative languages I suppose, a number of older imperative languages without a heap at all, and quite a few languages where the distinction between the stack and the heap can grow somewhat fuzzy (consider the implementation of continuations for instance.)
Forth might be one example of a language with an unorthodox concept of stacks. It's interesting in the sense that it's got two separate stacks in the form of an implicit call stack and an explicit data stack.
Quote:Original post by DevFredI rather think the OP was referring to the (conceptually) simple abstract data structure commonly called heaps, rather than the concrete priority queue data structure by the same name. Those crazy computer "scientists" keep overloading names.
Native languages need support by the operating system and/or some runtime system to manage the heap, and despite its name, it's rarely actually implemented with the data structure that is known as a "heap".
Author
Quote:Original post by implicit
I rather think the OP was referring to the (conceptually) simple abstract data structure commonly called heaps, rather than the concrete priority queue data structure by the same name. Those crazy computer "scientists" keep overloading names.
Confirmed...
It's only a guess, but I suppose it's just a matter of optimization: a stack is much more efficient to work with than a heap, but it has its limitations, so the heap is available as a general-purpose backup solution. If you're wondering who was first, i.e. did the CPU have the specialized registers first and did language designer decide to use them, or vice versa, I don't know, but as far as I know, influences in both directions have happened in the past.
Also, the stack is not always "just a stack", but sometimes also doubles as a linked list. Some compilers implement closures this way (either as an optimization where possible, or because functions are second-class values (i.e. they can be passed as arguments, but cannot be returned as function call results) in the language (e.g. Pascal?)). IIRC, dynamic scope also works this way. Perhaps I should look it up.
I don't think that if language designers had the freedom not to have to keep efficiency in mind, languages would look quite differently and stacks and heaps would be considered very low level stuff. Look at Oz: the language promotes the usage of thousands of threads and is designed in such a way that race conditions and deadlocks rarely happen. (If you think about it, a deadlock is rather a problem of not enough threads than too few :-)) But it certainly isn't as efficient as C++.
Also, the stack is not always "just a stack", but sometimes also doubles as a linked list. Some compilers implement closures this way (either as an optimization where possible, or because functions are second-class values (i.e. they can be passed as arguments, but cannot be returned as function call results) in the language (e.g. Pascal?)). IIRC, dynamic scope also works this way. Perhaps I should look it up.
I don't think that if language designers had the freedom not to have to keep efficiency in mind, languages would look quite differently and stacks and heaps would be considered very low level stuff. Look at Oz: the language promotes the usage of thousands of threads and is designed in such a way that race conditions and deadlocks rarely happen. (If you think about it, a deadlock is rather a problem of not enough threads than too few :-)) But it certainly isn't as efficient as C++.
Quote:Original post by Lode
Stacks and heaps are both very simple data structures, could more complex ones have uses here?
The problem with this question is that it means you believe that current implementations of heaps are simple. Try browsing the source code to MSVC's malloc() functionality. It does different things based on the size of the allocation, the status of global variables, the operating system the program is currently being run on, the state of environment variables, whether or not the program is being run from a debugger and probably the phase of the moon and which house mercury is in. Sometimes a memory allocation is handled by the CRT and sometimes it punts the entire allocation to operating system function calls. And that's just C's malloc(). Different allocation methods can be used for situation when the size is known at deallocation time, which gives rise to different forms of pooled allocation, binary buddy systems and so on.
Author
Quote:Original post by SiCraneQuote:Original post by Lode
Stacks and heaps are both very simple data structures, could more complex ones have uses here?
The problem with this question is that it means you believe that current implementations of heaps are simple. Try browsing the source code to MSVC's malloc() functionality. It does different things based on the size of the allocation, the status of global variables, the operating system the program is currently being run on, the state of environment variables, whether or not the program is being run from a debugger and probably the phase of the moon and which house mercury is in. Sometimes a memory allocation is handled by the CRT and sometimes it punts the entire allocation to operating system function calls. And that's just C's malloc(). Different allocation methods can be used for situation when the size is known at deallocation time, which gives rise to different forms of pooled allocation, binary buddy systems and so on.
Interesting: so the heap is managed by the programming environment here (since it's in the source of malloc()), not the operating system...
Windows provides heap functions. See HeapAlloc et al.
If you really want to dig into the guts of how Windows manages memory, check out: Memory Management: What Every Driver Writer Needs to Know. That's all kernel mode, but kernel mode is where Windows interfaces with the hardware. Along with many other things, that white paper describes how Windows creates a virtual address space and how device memory and registers are mapped into user space. See also Windows Memory Management.
DevFred -- esp isn't the stack, it's the stack pointer. 32 bit Windows assigns each thread a stack, typically 1 mb in size. The stack is a section of virtual memory just like the heap. Esp holds the address to the top of the stack. The Intel IA-32 manuals describe this in greater detail.
Another helpful reference for what goes on beneath the hood of 32 bit Windows is "Inside Microsoft Windows 2000" by David Solomon and Marc Russinovich.
If you really want to dig into the guts of how Windows manages memory, check out: Memory Management: What Every Driver Writer Needs to Know. That's all kernel mode, but kernel mode is where Windows interfaces with the hardware. Along with many other things, that white paper describes how Windows creates a virtual address space and how device memory and registers are mapped into user space. See also Windows Memory Management.
DevFred -- esp isn't the stack, it's the stack pointer. 32 bit Windows assigns each thread a stack, typically 1 mb in size. The stack is a section of virtual memory just like the heap. Esp holds the address to the top of the stack. The Intel IA-32 manuals describe this in greater detail.
Another helpful reference for what goes on beneath the hood of 32 bit Windows is "Inside Microsoft Windows 2000" by David Solomon and Marc Russinovich.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
