Q
16 local karma · 13 contributions here · active since May 2026
Can on demand paging be used to implement dynamic arrays?
Dynamic arrays, for instance std::vector in c++ are implemented based on the idea that if their size exceeds their capacity, the underlying array is reallocated to one that is twice the current capacity.
My question is, would this even be necessary given that at least in Linux, pages are allocated to a process on demand?
For instance, with a simple program like this:
#include <stdio.h>
#include <stdlib.h>
int main()
{
long size = (long)(64 * 4096 * 64) * 8;
long *arr = malloc(size);
for(long i=0; i < (size/32); i++)
{
arr[i] = i;
printf("%d\n", arr[i]);
}
printf("--->%p\n", arr);
while(1)
;
}
if size were equal to 64 * 4096 * 64, we can see via /proc/[PID]/maps that the heap section is about 4M(despite the malloc being for 16M) and with the size given in the program it is about 32M(despite the malloc being for 128M), illustrating on demand paging.
Considering that this implementation is probably not used widely, why is that? I figured one explanation would be the assumption of the system having on demand paging at all, which simply might not be the case, thus reducing portability, but what am I missing otherwise?
Join the discussion
You must be a member of /c/programming to comment.
C
7 local karma · 7 contributions here · active since May 2026
If we think for a moment about writing assembly and calling syscalls directly:
With functions like mmap (mremap etc., the whole group), madvise, faultfd/signalfd, ebpf, etc., ... you're right, actual reallocations (that might include moving the data etc.) can mostly be avoided, and there are many other nice things possible.
Where it gets problematic are the language specs of C and C++, that are much more limiting and ambiguous.
Like, in a simple case and ignoring the ideas above, surely you know that you can't allocate 10 ints with malloc and the access [12] in that array - it's past the end of the allocation, therefore UB. This is true even if, right after that first array, another allocated array happens to be, with no gap between them. Ie. C happens to define that one malloc call will always give you a single array, that you can legally access from the first to last element (independent of what happens within malloc), but you can't really view two mallocs as mergeable even if the addresses it gave you would make this possible.
If you now start doing some syscall magic to make your self-allocated array larger, you're a) firmly outside the C standard (it doesn't even know mmap), b) you have to know how much your C implementation (compiler optimizations, glibc allocator system, ...) will forgive you, or if you're introducing code that might cause problems in some way.
▲
1
▼
16 local karma · 13 contributions here · active since May 2026
> you can't really view two mallocs as mergeable even if the addresses it gave you would make this possible.
I don't understand why this would be a problem in my case, considering the example I have given above uses only a single, big malloc. Nor am I talking about the use of syscalls like mmap here.
> If you now start doing some syscall magic to make your self-allocated array larger,
The whole idea is that you don't. You just malloc a large amount(essentially an upper limit) of memory and use it without worrying about reallocation is what I proposed.
C
7 local karma · 7 contributions here · active since May 2026
So, maybe I was going to fast with my thoughts/explanations.
You just malloc a large amount(essentially an upper limit) of memory
a) Quite often, you won't be able to guarantee a upper limit that always hold for all users, therefore there still needs to be some reallocation logic
b) Even with with you call "on-demand paging" (mmu page table stub entries, or whatever name fits better), you can't just allocate a few huge arrays that you maybe won't fully use, because the OS prevents it. Linux has some config knobs regarding that matter, but unless you change it yourself you won't find a no-limits environment.
c) And even then, there's still the question how the allocators (kernel and glibc) decides on a virtual memory layout etc.
14 local karma · 8 contributions here · active since May 2026
And since you are putting each vector on its own page, a vector with one element takes 4KB of memory, and that’s real memory, not just virtual address space. You committed 4KB of memory but are using only 8 bytes of it, wasting 99.8%. Your program allocated 500x more memory than it needs. (A doubling reallocator allocates only 2x as much memory that it needs, worst case.)