Hidden Costs of Freedom: Understanding Heap Performance

Exploring the Realm of Dynamic Memory Management

Published in

ILLUMINATION

8 min readApr 16, 2024

It’s true that the stack’s extraordinarily quick speed because of its LIFO structure and stack pointer is a significant benefit, as we previously discussed. Below image shows how LIFO works

But there are trade-offs with everything in life, I suppose, with the possible exception of the ideal cup of coffee in the morning. Let’s examine the three primary restrictions associated with using the stack that you mentioned in more detail:

1. Large Data and Stack Overflow:

Limited Size: The stack has a predetermined size, which can vary depending on the system and programming language. This fixed size becomes a critical constraint when dealing with large data sets.
Overflow Risk: If you attempt to store data exceeding the stack’s capacity, a stack overflow occurs. This is a runtime error that often leads to program crashes and data corruption.
Example: Imagine you’re working with image processing and need to store a high-resolution image in memory. Due to its size, the image might exceed the stack’s limit, causing a stack overflow and crashing your program.

2. No Dynamic Size Types:

Static Allocation: The stack requires knowing the exact memory size needed for data at compile time. This means it’s unsuitable for data structures with dynamic sizes, like dynamically allocated arrays or linked lists, where the size is unknown beforehand or can change during program execution.
Restriction on Flexibility: This limitation restricts the flexibility and adaptability of your program, particularly when dealing with data structures that grow or shrink dynamically.

Above code snippet in C++ illustrates the inability to dynamically add elements to an array allocated on the stack due to its fixed size

Explanation:

Array Initialization: We declare an integer array arr with a size of 5 and initialize it with values 1 to 5.
Count Variable: We introduce a variable count to track the number of elements currently in the array.
Adding Elements: Here’s where the problem arises. We attempt to add the values 6 and 7 to the array by accessing arr[count] and then incrementing count. However, since arr is allocated on the stack with a fixed size of 5, accessing elements beyond index 4 leads to undefined behavior.
Potential Consequences: The program might appear to work in some cases, but this is unreliable and dangerous. Accessing memory outside the allocated space can lead to:
Data Corruption: Overwriting data in other variables or memory regions.
Program Crashes: Segmentation faults or other runtime errors.
Unpredictable Results: The program may produce incorrect output or behave unexpectedly.

The main lesson is that we cannot dynamically change the size of arrays allocated on the stack due to its fixed-size nature. Due to this fundamental limitation, situations requiring dynamic data structures must use other memory management strategies, like the heap.

3. Single-Threaded Operation:

Concurrency Challenges: The stack operates in a single-threaded manner, meaning it cannot handle multiple operations concurrently. This can become a bottleneck in multi-threaded applications where tasks need to be executed simultaneously.
Limited Parallelism: This limitation restricts the ability to take full advantage of modern multi-core processors and can hinder the performance of applications that require parallelism.
Example: Suppose you’re building a web server that needs to handle multiple client requests concurrently. The single-threaded nature of the stack would make it difficult to efficiently manage these requests, potentially leading to performance issues and delays.

With a clear understanding of stack constraints, we can now introduce heaps, a memory management approach that overcomes these limitations and provides the flexibility of dynamic memory allocation within our system.

Understanding Heap Memory Allocation

Consider the heap to be an enormous public park, an area of memory that is under the control of the operating system. The heap is similar to a free-flowing area where you can claim and release memory chunks as needed during the execution of your program, in contrast to the stack, which has a fixed size and structure. Because of its dynamic nature, the heap is perfect for scenarios in which you need to store data that changes in size over time or in which you are unsure of the precise amount of memory needed.

Timing is Everything

Timing is the primary distinction between heap and stack allocation:

Stack Allocation (Compile-Time): Think of a cleanwarehouse where each item has a specific location. In a similar vein, the stack allocates memory for variables at compile time, which means that the compiler calculates the precise amount of memory required before the program even launches. Stack allocation is quick and effective with this static approach, but it is rigid.
Heap Allocation (Runtime): Envision a busy marketplace where you are able to hire different-sized stalls as needed. Runtime heap allocation enables your program to request and acquire memory as needed. This adaptability is useful when handling dynamic data structures or erratic memory requirements.

The Keys to the Heap Kingdom

Pointers are specialized tools that we need to access and manage memory on the heap. A pointer is comparable to an address or a reference to a particular memory location. You can store and retrieve data when you allocate memory on the heap because you get a pointer that serves as your key to that memory space.

Think of the heap as a quilt made of pieces rather than a neatly laid out grid. The heap may fragment as memory blocks are allocated and released, distributing available space amongst used blocks. Finding acceptable space for new allocations may become more difficult and inefficient as a result of this fragmentation.

Below is a simple C++ code snippet to illustrate heap allocation and the use of pointers.

We should use memory requests (new) cautiously! It creates a box on the heap (flexible memory) for age (integer). Use *age to access the value and delete age to clean up when done.

Heap Slowness: Exploring the Bottlenecks

While the heap offers valuable flexibility, it comes at a price: performance. Let’s understand the factors that contribute to the heap’s slower operation compared to the stack:

Free Space: A Quest for the Perfect Fit

Algorithms and Lists for Free: Consider the free space inside the heap as a collection of dispersed islands. The mechanism keeps a free list, which is essentially a map of available chunks, in order to identify an appropriate island (memory block) for a new allocation. There are several algorithms to use to navigate this map:

First-Fit: It seizes the first sufficiently-sized island it comes across, much like a hurried explorer.
Best-Fit: More exacting, it looks for the smallest island that satisfies the criteria with the goal of reducing wasted space.
Worst-Fit: Despite the name, it selects the largest island that is available in the hopes of saving larger portions for later distributions.

Time Complexity: Finding the best space can take a lot of time, particularly when there are broken heaps. The worst-case situation could require us to traverse the whole free list, in which case the time complexity could be O(n), where n is the total number of blocks allotted.

Allocation Overhead: The Hidden Costs

Although heap memory allocation is more flexible than stack allocation, it still has certain drawbacks for dynamic data structures. This is the reason why:

System Calls and Metadata: The heap, in contrast to the stack, uses system calls to ask the operating system for memory. The context switch to the kernel mode required by these system calls may be slower than internal stack operations. Metadata is also required for each block that is allocated in order to track its size and status. The overhead of heap allocation increases with the maintenance of this metadata.
Fragmentation: The heap may become fragmented over time as a result of memory allocations and deals. Picture an untidy room with a lot of empty space. Due to this fragmentation, it becomes more difficult to locate big, contiguous blocks for upcoming allocations, which could result in slower performance and inefficient memory usage.

In the above image, even though there’s enough free space, allocating a large block might be impossible due to the fragmentation.

Garbage Collection: Cleaning Up the Mess

Preventing memory leaks requires careful memory management following allocation. Just like when you return a rented item, deallocating memory blocks is necessary. Program performance may be hampered by forgetting to do this, which can trap usable memory. Automatic garbage collection, a resource-intensive but handy feature that locates and deallocates unused memory, is available in certain languages. However, because of their complexity, which increases with the number of objects in the program, garbage collection algorithms like mark-and-sweep can cause overhead and pauses.

Benchmarking: Heap vs. Stack Performance

Though theory is instructive, belief comes from experience. Let’s use benchmarks to pit the heap against the stack in a performance showdown.

We’ll compare the time taken to allocate and access a large number of integers using both stack and heap allocation.

Even though both arrays are on the heap, the heapAllocation function might involve more overhead in finding a suitable contiguous memory block, especially if the heap is fragmented from previous allocations and deallocations.

Stack allocation time: 37452 microseconds
Heap allocation time: 43614 microseconds

My name is Mohit Mishra, and I’m a blogger that creates intriguing content that leave readers wanting more. Anyone interested in machine learning and data science should check out my blog. My writing is designed to keep you engaged and intrigued with a regular publishing schedule of a new piece every two days. Follow along for in-depth information that will leave you wanting more!
If you liked the article, please clap and follow me since it will push me to write more and better content. I also cited my GitHub account and Portfolio at the bottom of the blog.

You can follow me on Twitter to learn more about this. Every day, I tweet about a variety of subjects here, such as software engineering, system design, deep learning, machine learning, and more.

Thank you for reading my blog post on Hidden Costs of Freedom: Understanding Heap Performance. I hope you find it informative and helpful. If you have any questions or feedback, please feel free to leave a comment below.

I also encourage you to check out my portfolio and GitHub. You can find links to both in the description below.

I am always working on new and exciting projects, so be sure to subscribe to my blog so you don’t miss a thing!

Thanks again for reading, and I hope to see you next time!

[Portfolio Link] [Github Link]