[nhaehnle]

The libc memory allocator does not simply hand out memory contiguously. In your example, the 256K block will end up being 4K aligned.

In fact, that's what the article already explains: the large alloc will just end up being passed through to the kernel, which only deals at page granularity.

[whoopdedo]

What the article revealed to me is that there is no guarantee a contiguous block of allocated virtual memory will be backed by contiguous physical memory. In hindsight, that should be obvious.

But what does this mean for locality? Will I be thrashing the cache if I use realloc frequently? Do I even have the promise that malloc will return unfragmented memory?

[nhaehnle]

Do I even have the promise that malloc will return unfragmented memory?

What do you mean by this? malloc returns memory that is contiguous in the virtual address space. It may not be contiguous in the physical address space, but that should be irrelevant for cache behavior.

Will I be thrashing the cache if I use realloc frequently?

I suppose. But if you use realloc, you should anyway ensure that you realloc geometrically growing chunks of memory (e.g., whenever you need a new buffer, you multiply its size by a constant factor like 1.2 instead of just adding an element at a time). As a result, realloc() should be infrequent enough that it normally doesn't matter.