This “huge VM” approach works great and I am using it extensively in production (though not with a dynamic array interface). For 32-bit systems or other contexts in which allocating large virtual address ranges is not possible, another alternative that preserves pointer stability (but does not guarantee contiguity of elements in virtual memory) is the “segment array”: a small fixed-size array stores pointers to “segments” of exponentially increasing size (except the initial size is repeated once). The total memory doubles each time a segment is added to the array: 8, 8 + 8 = 16, 8 + 8 + 16 = 32, etc.
I first encountered the “segment array” idea in “The Design and Implementation of Dynamic Hashing for Sets and Tables in Icon” but have seen it in many other places since. The “huge VM” paradigm shows up in many, many places as well; one of the most interesting is the “virtual span” idea in scalloc. I use a similar approach to nearly eliminate the need for compaction due to virtual memory fragmentation in a compacting GC for an MVCC database (compaction is generally required only for physical memory fragmentation, i.e., sparse allocations within a single page).
It was actually just after implementing a segment array that I thought of doing this. I’d been using the virtual memory ring buffer trick at work a few weeks before so it was fresh in my head, and I thought “wait, the page table could just put all my segments beside each other…”
You can exploit demand paging in so many applications. Another “huge VM” trick I found was to adapt linear hashing to a predetermined layout of page-size buckets in a single VM segment, so buckets can be split in any order (rather than strictly in order per standard linear hashing). It doesn’t matter how sparse allocated pages are, as long as 1) allocations within the pages themselves are dense, and 2) you can spare enough virtual memory (which you nearly always can).
This “huge VM” approach works great and I am using it extensively in production (though not with a dynamic array interface). For 32-bit systems or other contexts in which allocating large virtual address ranges is not possible, another alternative that preserves pointer stability (but does not guarantee contiguity of elements in virtual memory) is the “segment array”: a small fixed-size array stores pointers to “segments” of exponentially increasing size (except the initial size is repeated once). The total memory doubles each time a segment is added to the array: 8, 8 + 8 = 16, 8 + 8 + 16 = 32, etc.
I first encountered the “segment array” idea in “The Design and Implementation of Dynamic Hashing for Sets and Tables in Icon” but have seen it in many other places since. The “huge VM” paradigm shows up in many, many places as well; one of the most interesting is the “virtual span” idea in scalloc. I use a similar approach to nearly eliminate the need for compaction due to virtual memory fragmentation in a compacting GC for an MVCC database (compaction is generally required only for physical memory fragmentation, i.e., sparse allocations within a single page).
It was actually just after implementing a segment array that I thought of doing this. I’d been using the virtual memory ring buffer trick at work a few weeks before so it was fresh in my head, and I thought “wait, the page table could just put all my segments beside each other…”
You can exploit demand paging in so many applications. Another “huge VM” trick I found was to adapt linear hashing to a predetermined layout of page-size buckets in a single VM segment, so buckets can be split in any order (rather than strictly in order per standard linear hashing). It doesn’t matter how sparse allocated pages are, as long as 1) allocations within the pages themselves are dense, and 2) you can spare enough virtual memory (which you nearly always can).