Why mallocmemset is slower than calloc

Dynamic memory allocation is a cornerstone of C programming, offering flexibility in managing data structures. When it comes to allocating and initializing memory, developers often face the choice between malloc followed by memset versus calloc. While both achieve the goal of reserving memory, calloc frequently outperforms malloc + memset, especially for larger allocations. Understanding why involves delving into the underlying mechanics of these functions and the operating system’s role in memory management.

The Mechanics of malloc and memset

malloc reserves a block of memory of the specified size but doesn’t initialize it. This means the allocated memory contains whatever residual data was previously present. To ensure a clean slate, developers often use memset to set all bytes to zero. This two-step process involves two separate system calls, each with its own overhead.

For example:

include <stdlib.h> include <string.h> int main() { int ptr = (int ) malloc(1000  sizeof(int)); if (ptr == NULL) return 1; memset(ptr, 0, 1000  sizeof(int)); // ... use ptr ... free(ptr); return 0; }

The Efficiency of calloc

calloc allocates memory and initializes it to zero in a single step. This often translates to a single system call, reducing overhead. Furthermore, calloc can leverage optimized zeroing mechanisms provided by the operating system, such as using virtual memory tricks. This can significantly speed up the process, particularly for large memory blocks.

For example:

include <stdlib.h> int main() { int ptr = (int ) calloc(1000, sizeof(int)); if (ptr == NULL) return 1; // ... use ptr ... free(ptr); return 0; }

Operating System Optimization: The Role of Virtual Memory

Modern operating systems employ virtual memory, allowing programs to address more memory than physically available. When calloc requests a large block of zeroed memory, the OS can often optimize this by simply marking the corresponding pages in the virtual memory map as zeroed, without physically writing zeros to the RAM. This is known as demand-zero paging. When the program first accesses a page, the OS then allocates the physical RAM and fills it with zeros. This lazy initialization defers the cost of zeroing until necessary, resulting in significant performance gains.

Performance Benchmarks and Real-World Implications

Numerous benchmarks demonstrate calloc’s superior performance, especially for larger allocations. In applications requiring frequent allocation and initialization of large data structures, this difference can be substantial. For instance, in scientific computing or game development where large arrays are commonplace, using calloc can lead to noticeable performance improvements. Learn more about memory optimization techniques.

[Infographic placeholder: Comparing malloc+memset vs. calloc performance across various allocation sizes.]

Beyond Zeroing: When malloc + memset Might Be Preferable

While calloc generally shines, there are scenarios where malloc + memset might be a better choice. If you need to initialize the memory with a value other than zero, memset offers the flexibility to set any desired byte pattern. Additionally, for very small allocations, the overhead difference between the two approaches might be negligible, and the explicit initialization offered by memset could offer better control.

Key Considerations

Allocation size: For larger allocations, calloc often outperforms malloc + memset.
Initialization value: Use calloc for zero initialization; use malloc + memset for other values.

Steps for Efficient Memory Allocation

Analyze your application’s memory usage patterns.
Choose the appropriate allocation function based on size and initialization needs.
Profile your code to identify potential bottlenecks.

Understanding the nuances of malloc, memset, and calloc empowers developers to make informed decisions about memory management, ultimately leading to more efficient and performant C programs. Choosing the right tool for the job—zeroing versus initializing with specific data—can lead to noticeable improvements. While calloc often provides an efficient shortcut for zero-initialized memory, understanding the trade-offs with using malloc paired with memset allows developers to fine-tune memory allocation strategies. Explore further by checking out resources like the calloc man page and GNU libc memory allocation documentation.

For deeper insights into memory management, refer to this comprehensive guide on Memory Management.

FAQ

Q: Is calloc always faster than malloc + memset?

A: While generally true for larger allocations, the performance difference might be negligible for small allocations. The operating system’s implementation and specific hardware can also influence the results.

By considering these factors and choosing the appropriate method for memory allocation and initialization, developers can significantly improve the performance and efficiency of their C programs. This knowledge is particularly valuable when working with large datasets or performance-critical applications.

Question & Answer :
It’s known that calloc is different than malloc in that it initializes the memory allocated. With calloc, the memory is set to zero. With malloc, the memory is not cleared.

So in everyday work, I regard calloc as malloc+memset. Incidentally, for fun, I wrote the following code for a benchmark.

The result is confusing.

Code 1:

#include<stdio.h> #include<stdlib.h> #define BLOCK_SIZE 1024*1024*256 int main() { int i=0; char *buf[10]; while(i<10) { buf[i] = (char*)calloc(1,BLOCK_SIZE); i++; } }

Output of Code 1:

time ./a.out **real 0m0.287s** user 0m0.095s sys 0m0.192s

Code 2:

#include<stdio.h> #include<stdlib.h> #include<string.h> #define BLOCK_SIZE 1024*1024*256 int main() { int i=0; char *buf[10]; while(i<10) { buf[i] = (char*)malloc(BLOCK_SIZE); memset(buf[i],'\0',BLOCK_SIZE); i++; } }

Output of Code 2:

time ./a.out **real 0m2.693s** user 0m0.973s sys 0m1.721s

Replacing memset with bzero(buf[i],BLOCK_SIZE) in Code 2 produces the same result.

My question is: Why is malloc+memset so much slower than calloc? How can calloc do that?

The short version: Always use calloc() instead of malloc()+memset(). In most cases, they will be the same. In some cases, calloc() will do less work because it can skip memset() entirely. In other cases, calloc() can even cheat and not allocate any memory! However, malloc()+memset() will always do the full amount of work.

Understanding this requires a short tour of the memory system.

Quick tour of memory

There are four main parts here: your program, the standard library, the kernel, and the page tables. You already know your program, so…

Memory allocators like malloc() and calloc() are mostly there to take small allocations (anything from 1 byte to 100s of KB) and group them into larger pools of memory. For example, if you allocate 16 bytes, malloc() will first try to get 16 bytes out of one of its pools, and then ask for more memory from the kernel when the pool runs dry. However, since the program you’re asking about is allocating for a large amount of memory at once, malloc() and calloc() will just ask for that memory directly from the kernel. The threshold for this behavior depends on your system, but I’ve seen 1 MiB used as the threshold.

The kernel is responsible for allocating actual RAM to each process and making sure that processes don’t interfere with the memory of other processes. This is called memory protection, it has been dirt common since the 1990s, and it’s the reason why one program can crash without bringing down the whole system. So when a program needs more memory, it can’t just take the memory, but instead it asks for the memory from the kernel using a system call like mmap() or sbrk(). The kernel will give RAM to each process by modifying the page table.

The page table maps memory addresses to actual physical RAM. Your process’s addresses, 0x00000000 to 0xFFFFFFFF on a 32-bit system, aren’t real memory but instead are addresses in virtual memory. The processor divides these addresses into 4 KiB pages, and each page can be assigned to a different piece of physical RAM by modifying the page table. Only the kernel is permitted to modify the page table.

How it doesn’t work

Here’s how allocating 256 MiB does not work:

Your process calls calloc() and asks for 256 MiB.
The standard library calls mmap() and asks for 256 MiB.
The kernel finds 256 MiB of unused RAM and gives it to your process by modifying the page table.
The standard library zeroes the RAM with memset() and returns from calloc().
Your process eventually exits, and the kernel reclaims the RAM so it can be used by another process.

How it actually works

The above process would work, but it just doesn’t happen this way. There are three major differences.

When your process gets new memory from the kernel, that memory was probably used by some other process previously. This is a security risk. What if that memory has passwords, encryption keys, or secret salsa recipes? To keep sensitive data from leaking, the kernel always scrubs memory before giving it to a process. We might as well scrub the memory by zeroing it, and if new memory is zeroed we might as well make it a guarantee, so mmap() guarantees that the new memory it returns is always zeroed.
There are a lot of programs out there that allocate memory but don’t use the memory right away. Sometimes memory is allocated but never used. The kernel knows this and is lazy. When you allocate new memory, the kernel doesn’t touch the page table at all and doesn’t give any RAM to your process. Instead, it finds some address space in your process, makes a note of what is supposed to go there, and makes a promise that it will put RAM there if your program ever actually uses it. When your program tries to read or write from those addresses, the processor triggers a page fault and the kernel steps in to assign RAM to those addresses and resumes your program. If you never use the memory, the page fault never happens and your program never actually gets the RAM.
Some processes allocate memory and then read from it without modifying it. This means that a lot of pages in memory across different processes may be filled with pristine zeroes returned from mmap(). Since these pages are all the same, the kernel makes all these virtual addresses point to a single shared 4 KiB page of memory filled with zeroes. If you try to write to that memory, the processor triggers another page fault and the kernel steps in to give you a fresh page of zeroes that isn’t shared with any other programs.

The final process looks more like this:

Your process calls calloc() and asks for 256 MiB.
The standard library calls mmap() and asks for 256 MiB.
The kernel finds 256 MiB of unused address space, makes a note about what that address space is now used for, and returns.
The standard library knows that the result of mmap() is always filled with zeroes (or will be once it actually gets some RAM), so it doesn’t touch the memory, so there is no page fault, and the RAM is never given to your process.
Your process eventually exits, and the kernel doesn’t need to reclaim the RAM because it was never allocated in the first place.

If you use memset() to zero the page, memset() will trigger the page fault, cause the RAM to get allocated, and then zero it even though it is already filled with zeroes. This is an enormous amount of extra work, and explains why calloc() is faster than malloc() and memset(). If you end up using the memory anyway, calloc() is still faster than malloc() and memset() but the difference is not quite so ridiculous.

This doesn’t always work

Not all systems have paged virtual memory, so not all systems can use these optimizations. This applies to very old processors like the 80286 as well as embedded processors which are just too small for a sophisticated memory management unit.

This also won’t always work with smaller allocations. With smaller allocations, calloc() gets memory from a shared pool instead of going directly to the kernel. In general, the shared pool might have junk data stored in it from old memory that was used and freed with free(), so calloc() could take that memory and call memset() to clear it out. Common implementations will track which parts of the shared pool are pristine and still filled with zeroes, but not all implementations do this.

Dispelling some wrong answers

Depending on the operating system, the kernel may or may not zero memory in its free time, in case you need to get some zeroed memory later. Linux does not zero memory ahead of time, and Dragonfly BSD recently also removed this feature from their kernel. Some other kernels do zero memory ahead of time, however. Zeroing pages during idle isn’t enough to explain the large performance differences anyway.

The calloc() function is not using some special memory-aligned version of memset(), and that wouldn’t make it much faster anyway. Most memset() implementations for modern processors look kind of like this:

function memset(dest, c, len) // one byte at a time, until the dest is aligned... while (len > 0 && ((unsigned int)dest & 15)) *dest++ = c len -= 1 // now write big chunks at a time (processor-specific)... // block size might not be 16, it's just pseudocode while (len >= 16) // some optimized vector code goes here // glibc uses SSE2 when available dest += 16 len -= 16 // the end is not aligned, so one byte at a time while (len > 0) *dest++ = c len -= 1

So you can see, memset() is very fast and you’re not really going to get anything better for large blocks of memory.

The fact that memset() is zeroing memory that is already zeroed does mean that the memory gets zeroed twice, but that only explains a 2x performance difference. The performance difference here is much larger (I measured more than three orders of magnitude on my system between malloc()+memset() and calloc()).

Party trick

Instead of looping 10 times, write a program that allocates memory until malloc() or calloc() returns NULL.

What happens if you add memset()?