In the earliest days of digital computing, memory was the most-scarce resource.   (After all, magnetic doughnuts could be made only so small, and they had to be strung upon three tiny wires by hand.)   Thus, when external storage devices – disk and tape and drum – were developed, they were referred to as “mass” storage.   Most of us remember the bad old days, of MS-DOS and even earlier, when programs had to be separated into “overlays” in order to be made to fit into the one-and-only place from which instructions could be executed.

Well, fast-forward a few decades and “chips are cheap” now.   Gigabytes if not terabytes of semiconductor storage can fit into a space the size of a pencil eraser.   CPU architectures are especially designed to allow gigabytes of storage to be directly addressed.   Developers are eagerly taking advantage of this, because the days of “overlays” and then “virtual memory” (i.e. “paging”) appear to be long-ago and far-away.   After all, RAM has the unique advantage of being instantaneous.   If the data is available in RAM, disk-I/O does not occur.   (And, if the “disk” storage device is made of semiconductors, at least the “seek latency” and “rotational latency” does not happen, even though most semiconductor devices do have a certain form of “latency” of their own.)

There is a fly in that ointment, however.   RAM capacity is not yet so enormous that concerns about virtual memory can be dismissed outright, especially in production situations where many possibly memory-hungry applications are running on the same box at the same time.   Virtual memory is still with us, and therefore we must be mindful of how to work “with” it and not “against” it, just as we were very-obliged to do in the 1970’s.

When virtual memory is being used, “in-memory” data structures might involve disk I/O.   As you know, physical RAM is divided into equal-sized chunks called “pages,” and each page might be “resident” in memory or it might be “swapped out.”   When any virtual address is touched, a “page fault” might occur, and if so the process will be delayed until the necessary disk-I/O has been completed.   (And, in order to make room for the page, another page might have to be “stolen” from someone and written out to disk … thus, two or more disk-I/O’s must take place before the faulting process is allowed to proceed.)

Virtual memory’s success relies upon the assumption that, while page-faults will occur, they will not occur so frequently that the disk-I/O delays add up too much in practice.   The term is “locality of reference,” and it means that programs typically make memory-references in very concentrated groups.   Once a page-fault is satisfied, things should settle-down for a while as the processes continue to refer, again and again, to the page(s) that have most recently been faulted-in.   “Least Recently Used (LRU)” pages, by comparison, are presumed to be good candidates for page-stealing.   The total set of pages that any process requires in order to run without delay, at any instant in time, is referred to as its current “working set” at that instant.

There is, unfortunately, one data-structure mechanism in particular that flies in the face of “locality of reference,” and therefore of “small and tidy and predictable working-sets.”   That mechanism is:   the hash table.   Perl’s “hashref.”

Hash tables work by permuting a key across some smaller key-space in order to arrive at a single “bucket” that is searched for the target value.   Hash functions are designed to spread the key values more or less uniformly, but randomly, across the key space.   Thus, the hash structure itself can represent a large working-set (although hash algorithm designers, including Perl’s, do seek to constrain this).   But in any case, the hash buckets also refer, by reference, to outside blocks of memory that are obtained using memory allocation functions e.g. “malloc().”   The memory addresses pointed-to by the (already, large) hash table will, over time, become quite-widely distributed.   And so we have a “very random-access” data structure:   a large hash-table referencing an even larger set of memory blocks whose individual addresses are not predictable.   (A highly volatile very-active data structure becomes less and less predictable as the hours and days go by.   Working-set sizes increase quickly.)

(Perl’s designers know their stuff.   They know about these issues and carefully designed an industrial-strength system for all of us to enjoy.   We are well cared-for ... but the issues are still there, and, by definition, always will be.)

Working-set sizes become very large, then.   So, what actually happens when such an application enters service in a production machine that’s using virtual memory?   Unfortunately, it becomes a million-pound elephant … using, shall we say, far more than its fair share of RAM.   A disproportionately large amount relative to the others.   And therefore, both a source of virtual-memory pressure and(!) an especially vulnerable victim of it.   If such a program is to run efficiently (as it was specifically designed to do), it must have “all that RAM.”   But, if it gets what it wants (and must have), the other processes can’t get (and keep) theirs.   Paging activity begins to increase, as does the number of processes that are stuck in page-wait and the frequency that each process is stuck in page-wait.   At a certain point, the processing grinds to a halt.   It “hits the wall.”   It is “thrashing.”   The offending application is especially taking it in the shorts ... being especially big and especially vulnerable, it is “punch-drunk.”   But it’s not the only one.   (If there were any subtle timing-related bugs in this or any other application, this is the time when those kinds of problems will really start to show up.)

Given that, in a virtual memory setting, any “memory” reference can result in “disk” I/O, “memory” must in fact be treated as a “disk.”   Each memory-access, especially any access that might be widely-dispersed from other recent ones, must be considered as possibly taking several milliseconds to occur; not the microseconds or nanoseconds that are usually bantered-about by programmers who like to use the “time” command and discuss the third or fourth digit to the right of the decimal point.

Software developers usually don’t experience these things personally when designing their software:   their systems are the biggest, fastest, and especially the fattest of all.   They’ve got two or three large monitors.   Multiple processors.   Gigs of RAM.   As much as the motherboard will support.   In short, a situation altogether unlike the rack mounted boxes where their brainchildren will labor out their appointed business duties.

To run well, and to do so round-the-clock for days and weeks on end, all applications must be good virtual-memory citizens.   Whether their virtual memory allocations be large or small, their working-set sizes must be small … by design.   There are many possible ways to do that:   storing multiple entries in a single large structure rather than in many small ones; “batching” requests for even in-memory data stores; and, using disk-I/O directly instead of implicitly (as virtual-memory actually does).   All operating systems buffer disk-I/O operations, filling all available RAM with buffers but managing those buffers differently than they do VM page-frames.

Probably the very worst thing that can happen to your program’s design is for it to be very splendid on your machine, but unworkable in production … or even, “a pain in the asterisk in production.”   This requires thinking of RAM as being “a thing that is not without-delay,” from the very earliest stages of your designs.

HTH …