I'm a computer science student, and this has been puzzling me. As I understand it, all memory used by a process is tracked by either the stack or the heap. I understand the stack very well, right down to the assembly level; I feel that I know how it works and why it works the way it does. The heap, however, I know much less about.

I understand how allocations and deallocations happen on the stack, so I understand their cost. I do not understand how allocations and deallocations happen on the heap. I know heap allocations are slower than stack allocations because I have been told so, and because it makes sense that the heap must be more complicated, but I do not know exactly why. Why is the heap called the heap? Is it a heap of addresses of free blocks of memory?

Take C. In C, you interact with the heap mainly through malloc (and calloc, etc) and free. I understand the effect of calling these methods, but I have no idea what they actually do internally; the heap is a black box to me, so I don't intuitively understand the cost of my actions.

I understand the possibility that the implementation of malloc (for example) might vary depending on any number of things, but I find it difficult to believe it could vary too wildly. The fundamentals of the heap have to be constant across most implementations, otherwise it wouldn't have such a specific name. Any pointers (ha)?

**Edit: This is not a duplicate of an earlier thread. I've read the thread in question and it does not answer my questions.**

"The size of the heap is set on application startup, but can grow as space is needed (the allocator requests more memory from the operating system)."

I have said that I know this in my question; I understand how to get memory from the heap, I want to know what the heap itself is doing to get that memory (beyond "it requests it". Does this mean that the heap is tracked entirely by the OS? If so, what's a basic outline of how the OS tracks it? I understand it varies, but the fundamentals have to be the same).

"The stack is faster because the access pattern makes it trivial to allocate and deallocate memory from it (a pointer/integer is simply incremented or decremented), while the heap has much more complex bookkeeping involved in an allocation or deallocation."

My entire question is about what that complex bookkeeping actually is.