35.4. Memory Models

There are 6 memory models. Which one is used, depends on the operating system and is determined at build time.

Memory Models

SPVW_MIXED_BLOCKS_OPPOSITE

The heap consists of one block of fixed length (allocated at startup). The variable-length objects are allocated from the left, the 2-pointer objects are allocated from the right. There is a hole between them. When the hole shrinks to 0, garbage-collect is invoked. garbage-collect slides the variable-length objects to the left and concentrates the 2-pointer objects at the right end of the block again. When no more room is available, some reserve area beyond the right end of the block is halved, and the 2-pointer objects are moved to the right accordingly.

Advantages and Disadvantages

(+)

Simple management.

(+)

No fragmentation at all.

(-)

The total heap size is limited.

SPVW_MIXED_BLOCKS_OPPOSITE & TRIVIALMAP_MEMORY

The heap consists of two big blocks, one for variable-length objects and one for 2-pointer objects. The former one has a hole to the right and is extensible to the right, the latter one has a hole to the left and is extensible to the left. Similar to the previous model, except that the hole is unmapped.

Advantages and Disadvantages

(+)

Total heap size grows depending on the application's needs.

(+)

No fragmentation at all.

(*)

Works only when SINGLEMAP_MEMORY is possible as well.

SPVW_MIXED_BLOCKS_STAGGERED & TRIVIALMAP_MEMORY

The heap consists of two big blocks, one for variable-length objects and one for 2-pointer objects. Both have a hole to the right, but are extensible to the right.

Advantages and Disadvantages

(+)

Total heap size grows depending on the application's needs.

(+)

No fragmentation at all.

(*)

Works only when SINGLEMAP_MEMORY is possible as well.

SPVW_MIXED_PAGES

The heap consists of many small pages (usually around 8 KB). There are two kinds of pages: one for 2-pointer objects, one for variable-length objects. The set of all pages of a fixed kind is called a "Heap". Each page has its hole (free space) at its end. For every heap, the pages are kept sorted according to the size of their hole, using AVL trees. The garbage-collection is invoked when the used space has grown by 25% since the last GC; until that point new pages are allocated from the OS. The GC compacts the data in each page separately: data is moved to the left. Emptied pages are given back to the OS. If the holes then make up more than 25% of the occupied storage, a second GC turn moves objects across pages, from nearly empty ones to nearly full ones, with the aim to free as many pages as possible.

Advantages and Disadvantages

(-)

Every allocation requires AVL tree operations, thus slower

(+)

Total heap size grows depending on the application's needs.

(+)

Works on operating systems which do not provide large contiguous areas.

SPVW_PURE_PAGES

Just like SPVW_MIXED_PAGES, except that every page contains data of only a single type tag, i.e. there is a Heap for every type tag.

Advantages and Disadvantages

(-)

Every allocation requires AVL tree operations, thus slower

(+)

Total heap size grows depending on the application's needs.

(+)

Works on operating systems which do not provide large contiguous areas.

(-)

More fragmentation because objects of different type never fit into the same page.
SPVW_PURE_BLOCKS

There is a big block of storage for each type tag. Each of these blocks has its data to the left and the hole to the right, but these blocks are extensible to the right (because there is enough room between them). A garbage-collection is triggered when the allocation amount since the last GC reaches 50% of the amount of used space at the last GC, but at least 512 KB. The garbage-collection cleans up each block separately: data is moved left.

Advantages and Disadvantages

(+)

Total heap size grows depending on the application's needs.

(+)

No 16 MB total size limit.

(*)

Works only in combination with SINGLEMAP_MEMORY.

In page based memory models, an object larger than a page is the only object carried by its pages. There are no small objects in pages belonging to a big object.

The following combinations of memory model and mmap tricks are possible (the number indicates the order in which the respective models have been developed):

Table 35.1. Memory models with TYPECODES

 ABCD
SPVW_MIXED_BLOCKS_OPPOSITE19 8
SPVW_MIXED_BLOCKS_STAGGERED 6 7
SPVW_PURE_BLOCKS  45
SPVW_MIXED_PAGES2   
SPVW_PURE_PAGES3   

Table 35.2. Memory models with HEAPCODES

 ABD
SPVW_MIXED_BLOCKS_OPPOSITE***
SPVW_MIXED_BLOCKS_STAGGERED **
SPVW_MIXED_PAGES*  

Legend to Table 35.1, “Memory models with TYPECODES and Table 35.2, “Memory models with HEAPCODES

  1. no MAP_MEMORY
  2. TRIVIALMAP_MEMORY
  3. SINGLEMAP_MEMORY
  4. GENERATIONAL_GC

These notes document CLISP version 2.49Last modified: 2010-07-07