arrays, mmu, addressing choices

[LaTeigne via Digitalmars-d-learn]

On Monday, 8 August 2016 at 21:45:06 UTC, Charles Hixson wrote:
> I have a rather large array that I intend to build. but much of 
> it will only occasionally be used.  Will the unused sections 
> automatically be paged out?  If it matters my system is Debian 
> Linux.
>
> This array will be indexed by a ulong.  Is there any reasonable 
> maximum size?  I've considered segmented addressing anyway, in 
> case that's needed to allow paging, and it will definitely be 
> needed when I get around to concurrent processing, with 
> different sections resident in different threads.  But if 
> appropriate I could do that from the start.
>
> The questions above are really for a normal array, but I'd also 
> be interested in how using an associative array would affect 
> them.
>
> I expect to eventually be using more memory than I have RAM in 
> my system, so designing for paging is going to be important.  
> (Before then I'll be adding more RAM and a larger disk drive, 
> but if I complete the full design even a large disk is going to 
> be small.)

- maximum size relies on the memory fragmentation. With a system 
with 8Gb DRAM you might be able to allocate a 6Gb array just 
after boot, but after 1 week up time only 4Gb.

- sectors won't be automatically swapped. After reading your Q I 
was thinking to mmap() (in D: MMapAllocator + makeArray) but what 
actually happens is that nothing is allocated until it's used 
(allocation on comitment). Once it's there: it's there. Also mmap 
doesn't allow to allocate more than what's physically available.

- If you want a really big array you could design your own 
container with an array interface. The whole thing would reside 
on the HDD but a sector would be dynamically/lazily cached to 
DRAM on access, and a sector cache freed either explictly or 
according to several rules such as max usage, thread out of 
scope, these kind of stuff.

- your Q also makes me think to this data structure: 
https://en.wikipedia.org/wiki/Unrolled_linked_list. But I know 
nothing about it (seen a Delphi implementation years ago, that's 
all). The idea would be to create a custom allocator for the 
nodes (each linked sector) with disk "swap-ability".