What is “the stack”?

The x87 FPU "stack" is not truly a stack though: it's rather a ring buffer of 8 registers.

And you can model it pretty well even without a "head pointer", just with moves between all registers, e.g. push(x) is ST(7) = ST(6), ST(6) = ST(5), ..., ST(1) = ST(0), ST(0) = x.

I've implemented it as such in a lifter from x86 machine code and all the redundant moves just disappear, if the uses of the pseudo-stack are balanced, and you're left with traditional registers.

Some microcontrollers (e.g. some PICs) even have a hardware stack for storing return addresses. This stack is on the processor die like the registers and not in the RAM which makes it even more fundamental.

Regarding BM mainframes don't have a dedicated stack pointer; the stack is a software construct., Gene Ahmdahl, when asked why the 360 architecture didn't have a stack, he said "Too expensive". One might suspect that wasn't the whole story, as the 8085 (back when $5 retail quantity one) did have a stack.

The Burroughs 5000 and the rest of their line was quite interesting architecture. Arthur Sale once told me that he would use the B6700 architecture as a "universal counterexample" when talking about language conventions, such as C using zero as NULL.

I think it's entirely appropriate that the article just scratches the surface; as you say, going into all the crazy details just makes the topic scary to a newcomer.

In college I met a guy that had co-authored Marathon, the first big hit for Bungie Studios. (This was Ryan Martell, not Jason Jones.) Ryan taught me how my C code compiled to assembly, and we were using 68K Macs back in that day, so it was pretty straightforward to understand once you had somebody to show you the basics.

Oh man, that was a revelation. Stepping through compiled code made concepts like pointers, stack/heap, registers, etc. just as clear as day. Those handful of hours with Ryan did more for my understanding of computing than the whole rest of my college courses. (Well, excepting my operating systems class, that one was good.)

Funny enough, my first job was working on an embedded operating system that didn't have source-level debugging, I had to debug in 68K assembly. So I'll just shout this out to the ether: thanks again, Ryan.

Conversely, I often think how lucky I am to have entered the industry at this point.

I learnt HTML by initially downloading websites using ctrl-s, and then editing them in notepad. I learnt HTML/CSS, and then JavaScript, and then other languages.

I had the advantage that I had a GUI text editor. While I'm now quite comfortable using VIM and command-line editors, I sometimes think if I had tried to become a developer before the advent of GUI editors the learning curve would have been too steep.

Perhaps under the hood things are more complex, but the interfaces have improved.

One of the really nice things about Julia and her writing style, is she makes quite complicated subjects fairly easy to grasp from a high level.

For beginners, or those who work much higher up the technology chain it provides a nice launching off point for further investigation.

I find her style quite fun and engaging.

I believe Go, however, uses its own stack rather than the C stack.

I think Rust used to do the same thing and use segmented stacks (rather than the C stack) until late 2013 or early 2014, point at which the language's base was drastically lowered (in the abstraction stack) away from builtin GC, green threads and the like.

In turn, isn't LLVM's stack management and argument passing dictated by the hardware's ABI? ARM, for one, publishes its calling convention in AAPCS (ARM Architecture Procedure Call Standard) which establishes the calling convention on the C stack.

I always just drew the stack downwards in school. Makes it easier to for that assignment to diagram the stack at level of deepest recursion, at least.

There are. Parallax Propeller has no stack, no interrupts.

> `push` decrements the stack pointer on x86 architecture, unlike on ARM.

Why do you say "unlike on ARM"? In 25 years I've never seen anything but a full, descending stack used as the program stack. You can have ascending stacks, but that's more an artifact of the fact that `pop` and `push` (which didn't exist in the assembly language until Thumb) are just specific uses of the general multiple load/store instructions `LDM` and `STM`, which can "write back" an incremented or decremented base register.

At some point I was messing around with writing a toy VM and the choice of co-mingling return addresses and what where the functions arguments felt weird to me so I split them into two different stacks. It actually worked out. I mean it meant I diverged from the book I was using to do this but that was part of the fun to see which parts were simpler and which parts were more complicated in my design.

This was the book I used in case folks are curious http://www.springer.com/us/book/9783642149085.

Separate call/local stacks is not really a property of Harvard architectures, which are distinguished by having different address spaces for code and data. The split is really orthogonal to the architecture type.

IA64 is Von Neumann architecture, but still has separate stacks. In fact, at least with clang with SafeStack enabled, you can have separate stacks independently from architecture.

A heap is a data structure used by the malloc() and free() functions to find appropriately-sized chunks of RAM to give to the rest of the program.

The defining feature of heap-allocated memory is that it's persistent up the call stack; a common newbie error in C is to return a pointer to something allocated on the stack, which will become invalid the instant the other function sees it: If a() calls b(), everything in b()'s section of the call stack is cleaned up when b() returns to a(), so if a() tries to dereference a pointer to something b() allocated on the stack, the program will die.

The flip side is that programmers have to manage this by hand, which is the cause of memory leaks. Garbage collection is used to mitigate this; to, at the very least, turn a program from one with quickly-growing memory usage into one with slow-growing memory usage.

The heap is basically the memory that isn't your program code, your stack, or the space reserved by the compiler for your global variables (speaking of C, here). The heap memory traditionally gets allocated from a unix kernel with a syscall called sbrk(), which adds on to one end of the heap so that it stays one big contiguous chunk of memory. Traditionally, the heap begins at the opposite end of memory from the stack and grows towards it (some CPU's stacks grow up and some grow down). This may not be the case any more on 64 bit machines, since 64 bit address space is so big.

Technically it's up to your app to use that memory as it pleases. Of course, 99.9999% of programs use the standard C library functions malloc() and free() (or "new" and "delete") which handle all this for you, and keep track of which chunks of memory are in use. They're also cross platform so you don't have to worry about what the system API in Windows is for low level memory allocation. But you don't have to use them if you really don't want to (though in that case be careful calling shared library functions that might call malloc() behind your back).

This is a good comment because lots of folks confuse the heap and the stack.

Let's say you assign a variable in c, like so int i = 0; No matter where you do this, you're assigning a variable on the stack. A location on the stack is set aside and your variable goes in there.

This works great for small-ish things that you keep around to work on, but sometimes you want a big thing -- or you want something that lives on after the function dies.

In this case, you create something on the heap. In this case, you tell the computer to set aside a chunk of memory somewhere else -- the heap -- and let you store things there. You can continue using this location after your function is completed.

For an integer, it'd look like this.

int* j = malloc(sizeof(int));

So if you have a function creating bitmaps, you might have a lot of local (stack) variables, and you'd probably either create or use a pointer to a big hunk of memory where you kept all the bits for the bitmap (heap)

One way of thinking about it is if you're using a stack variable, only one piece of information gets stored in the computer -- the value. If you're using a heap variable, you're actually creating and storing two pieces of information, the value (on the heap), and a pointer to the value (on the stack). (hat tip to StackOverlow for the nice example http://stackoverflow.com/questions/6770596/memory-allocation... )

Things like the stack and heap and many other things (like memory mapped I/O, interrupts, etc) are often taught in first year university courses under a name like "introduction to computer organization". There are many online courses you can do for free, or you can simply go to a book store and pick up a text book. Although none of it is something that you desperately need in order to work as a programmer these days, it's one of those things that will undoubtedly be useful almost every day, so I highly recommend it.

As for the heap, I noticed another description, but I'll have a go at describing it in a slightly different way. Back in the old days you had a big chunk of contiguous memory. It started at address 0 and ended at address 65535 (if you were lucky enough to have 64K of RAM!).

As you saw in the article, you need to set aside some of that memory for the stack. In most languages that are compiled to machine language, the stack holds storage for variables local to a function as well as the function return address (the object that holds all the information for one function is called a "stack frame"). As others have said, other organizations are possible, but this is the most common.

Allocating memory on the stack is ideal because it is really easy to allocate and deallocate. When you enter a new function, you look at how big each of the local variables are and you simply move the "stack pointer" that many bytes (either up or down, depending on the architecture of the machine). When the function is finished, you simply move the stack pointer back to the start of that stack frame. Super easy and super fast.

The problem is that as soon as your function finishes, the variable is deallocated. So let's say you have a function that loads a picture from disk. You make a big array in your picture loading function, put the picture data in it and return it from the function... uh oh... As soon as the function ends, the memory is deallocated :-(. That data is "gone" (what's worse is that the data is still there, so it will appear to work until the stack grows big enough to overwrite that data -- at which point your picture will be corrupted). So we need a way to allocate memory that will stick around until we tell the system that it is not needed any more.

That's what the heap is. I can call a system function (usually called "malloc", which stands for "memory allocate") and say "I want 4K of memory". It finds a contiguous chunk of 4K of memory, makes a note that the memory is in use and then gives me a pointer to it. I can then use that pointer to write into the memory. The system will not allocate any memory in that area unless I tell it to "free" the memory (usually with a call to something called "free"). After that it can be used again.

The place the system looks for in the memory for this kind of allocation is called the heap. So you can imagine the big block of memory in a computer is divided up into at least 2 sections: the stack and the heap. Often a computer system will put them at the opposite sides of the memory so that you can grow the stack as much as possible. So I might start the stack at 65535 and grow downward. And I might start allocating the heap from 0 upwards. In practice there are other things you need to reserve memory/addresses for, so this is not how it really works, but you get the idea.

Many programmers like allocating from the heap because it is easy. You don't have to worry about the scope of your program. You allocate a variable and it is there until you tell it to go away. But there are a couple of problems. First, if you forget to free the memory, it never goes away. This is called a "memory leak". Also, you might accidentally try to use the memory after you freed it, resulting in the same corruption noted earlier. But there is yet another problem.

Let's imagine that I allocated 1024 40 byte strings. That will take up 40K (almost all of my memory on this hypothetical old machine). Let's say that every second string is only needed at the beginning of the program, so let's free them all. That frees up 20K. However, the heap is now "fragmented". It has 40 bytes allocated, 40 bytes unallocated, 40 bytes allocated, 40 bytes unallocated... If I want to allocate 45 bytes, I will have to walk through 512 unallocated blocks, noting that each is too small, before I decide to allocate at the end. This is very slow. If there isn't a 45 byte chunk available, then my memory allocation will fail, even though I have 20K of free memory.

So, for many old timers like me, we favoured allocating on the stack. This leads to fast, efficient, safe code that is also surprisingly elegant. Unfortunately, it is also hard to design ;-)

These days, operating systems do a lot behind the scenes to make sure that you don't fragment your heap too much, etc, etc. Modern interpreted languages use garbage collection and allocate on the heap incrementally -- as if it were stack allocation. Occasionally they wander through and deallocate unused variables and compact the heap. Some of the algorithms used are very sophisticated and quick.

I keep thinking about designing a functional language with stack allocation, though... It appeals to my roots ;-).

Hope that description helps. Keep in mind that many details will be incorrect for any specific system. I mostly just tried to make the description simple, not accurate.

You might also like this https://www.youtube.com/watch?v=1S0aBV-Waeo

Although call stacks aren't the main topic, it gives a really nice outline of them

It's cool to see a bunch of really thorough, great answers here. The summary I use to keep them straight:

When a program starts, it asks the operating system for memory to store the program and all its initial data. The heap is the part of memory nothing is using yet -- it's just a heap of memory over in the corner for you to use later if you need it.

As well, I think about storing data in 2 ways:

A. When you only need the data as long as the current function is executing, you declare a variable in that function, and the OS includes it in the calculation for how big to make that function's stack. You use it then it gets cleared out when the function is done.

B. When you need the data to exist after the current function is done executing, but don't want to pass the data itself around as returns and arguments for other functions, you can ask the OS to give you part of that heap of memory to store the data in. But clearing heap data requires attention. Since we don't have the simplicity of clearing it when the function finishes, we generally have to keep track of what's been stored on the heap and make sure to free it up when we no longer need it.

Some languages implement a garbage control process to track and clear no-longer-needed heap memory for us, but really the more you have on the heap, the less memory available to other programs on the computer, which isn't cool.

If you remember back to the days of needing to restart Firefox after half a day because that one open tab was somehow using 1.8GB of your RAM, it's an example of what happens when a lot of things are allocated to the heap and aren't freed.

Burroughs, IBM mainframes, Ada Machines (by Rational), Xerox Parc and ETHZ workstations are probably the best examples of more higher level friendly architectures.

Or at least the better documented ones.

I think you can had existing mainframe OSes to the exceptions list.

Left-to-right for me; vertical is confusing because I like to put address 0 at the top and address MAX at the bottom, but then the stack "grows down" and I get confused.

Left-to-right when I'm reasoning about general address spaces, but top-to-bottom when reasoning about the stack specifically.

> python is an interpreted language, and AFAIK it has no concept of a stack,

Here, I could say, "I find it pretty amazing that old-timey[1] 'programmers' fail to understand modern VM architecture". In fact, Python's interpreter (cpython) is partly based on the concept of a stack.

But instead, I'll just explain that most modern VM's are either stack-based or register-based. Stack-based VM's, like Python's, are (not surprisingly) based on a virtual machine that uses a stack as it interprets Python's bytecode. Yes, not the same level of abstraction as the call stack, but it's still a stack.

So instead of expressing dismay at how little modern programmers know about your little corner of the programming world (low-level systems programming), why not spend some time pondering about how so much programming has moved up the stack, and how abstractions have grown multifold.

In the 1970s and 1980s, it used to be that the typical self-taught programmer had to know all the details low-level C and assembly, because that was almost all there was to know, unless you were a high-level Lisp hacker.

I mean, I'm a little surprised at how little some C kernel hackers know about how the modern Web works (particularly regarding async programming patterns; eg, been asked by one why I didn't just use a mutex somewhere in JS program, wasn't trolling.). But then I realize that there's just too much for any but the most exceptional programmers to truly understand the full modern stack, from system architecture, to GPU, to networking, to Web, on so on.

Why not instead welcome how this particular web-focused programmer is interested in these low-level concepts? Is it that it wouldn't give you as much of a chance to show off your knowledge?

1. Said by another old-timey programmer.

> I find it pretty amazing how modern "programmers" are lacking in knowledge of basic computer science concepts.

IMO this is the natural evolution of programming. It has gotten remarkably easier to write complex programs that deliver real value to society. How fantastic is it that modern programmers don't need to understand the science of computers in order to be productive?

Yes, we will always need science and engineering and folks who understand the underlying technology. But the field is broadening into new places. Like it or not, when uncle Fred writes an excel macro, he's programming. And good for him!

wellll if you are going to nitpick you ought do it a little more cleanly: you are confusing machine language with assembly for starters, and even at the level of machine code, processors such as the x86 family were designed keeping support for higher level language conventions in mind, so it's difficult to pretend that there is no commonality of stack conventions baked into the microcoded x86 virtual machine.

Concepts you refer to such as "assembly language" exist a level up from bare metal, and at the same level as object libraries, linkers, and loaders and that implies full cooperation WRT calling conventions.

Your post has good technical information, but the attitude is not helpful. Please do not scold people for having less knowledge than you. It is not welcoming.

Same here. I guess this relates to why it is so difficult to hire people. Just a couple days ago, somebody crashed and burned in the interview by not knowing how to do bit manipulation. Why are these people allowed to graduate?

How does it work? Pass the return address in a register and have enough caller-saved registers that leaf functions can often do without spilling? Or is there a more sophisticated mechanism?

Sure. But I think it's fair to say that a structure that's part of the ABI is more distinguished/fundamental than an ordinary datastructure defined in the language.

Most modern FPGAs got two-port block rams. Ideal for stacks and FIFOs. Many non-trivial designs are using stacks one way or another.

That's a radically different design domain, though.

In case anyone is as confused as I was at first, agumonkey is referring to the fact that Functional Programming languages are capable of Tail Call Optimization, which allows functions to be composed without adding a new frame to the stack.

That hipstor buzzword hardly deserves "THE" in front of it.