Virtual Memory for an Object-Oriented Language
--- Ted Kaehler, 1981


- overlays are large groups of subroutines that are moded to and from
  the disk under control of the user program;

- they have implemented a specific object-oriented virtual memory for
  the Smalltalk-76 system;

- the idea is that the basic unit of swapping is an object, instead of
  a page;

- Problems with paging:

	- if the program needs a particular byte, the entire page
	  surrounding that byte must be brought into memory;

	? it is common that the rest of the page has nothing to do
	? with the part currently wanted;

	- every pointer must be capable of reaching any word in the
	  entire virtual space;

- their rationale is that objects have more locality of reference
  than pages;

- object-oriented VM swaps individual objects instead of entire pages
  between disk and main memory;

- every object has an object pointer, used to locate it in memory or
  disk;

- a fixed correspondence between object pointers and locations in
  memory does not work (duhhh!);

- in OOZE, an object identifier (OID) has 16 bits, limiting the number
  of objects to 64K;

- their disk has 2-4MB! Today, with a 4GB of space and 200-byte
  objects, 24 bits would be needed to the object pointer;

- optimization: any object can be brought into memory by reading at
  most one place on the disk;

- a large hash table, called Resident Object Table (ROT), translated
  object pointer to memory location;

- they wrote the ROT code in microcode;

- a hash of an object pointer calculates a series of places to search
  in the ROT;

- avg number of entries examined to find an object was 1.8;

- to decrease the space needed to store the translation of an object
  pointer to a disk address, OOZE uses a "trick":

	- information is coded in each object pointer.  This is done
	  by dividing the set of object pointers into pseudoclasses 
	  (higher-order bits);

	- as all objects in a pseudoclass have the same Smalltalk
	  class, they have the same size;

	- the Pseudoclass Map is a table that is indexed with the
	  pseudoclass number, giving the Smalltalk class, object size, 
	  and disk address where pseudoclass starts;

	- objects of the same pseudoclass are stored consecutively on disk;

	- 512 words (1KB) is enough to save all the information;

- fields that point to the object need not change when the object moves;

- Store mgmt: each class keeps a list of free instances;

- they use a second-chance style for evicting objects from memory;

- after each round of purging, the degree of fragmentation is tested.
  If too big, the system performs compaction;


Results:
--------

- performance is equivalent to a paging system with several times the
  swapping space;

	- so what is the motivation? just use less swap?


Problems:
--------

- pointers have fixed length => limit on number of objects;

- OOZE has a limit of 245 classes!

- just useful with OO languages;

- I think memory is increasing faster than average object size, making
  external fragmentation a worse problem every day;

- naming problem appears again and again in system's design: 16 bits
  limits addressable space to 64K objects;

- they don't talk about how they handle the code segment;

- even if the objects are small, the smaller unit read from and
  written to disk is a disk block;