Skip to content

Latest commit

 

History

History
141 lines (111 loc) · 7.12 KB

0008-faster-memory-allocation.md

File metadata and controls

141 lines (111 loc) · 7.12 KB
Raw

(IE-0008) Faster memory allocation

  • Proposal: IE-0008
  • Discussion PR link: #8
  • Authors: Dannii Willis
  • Status: Draft
  • Related proposals: None
  • Implementation: None

Summary

Faster runtime access to flexibly-sized data like texts and lists.

Motivation

In code generated by Inform, the contents of flexibly-sized data structures such as texts and lists are stored in blocks. Such data typically has a lifetime shorter than that of the program as a whole: for example, it may exist only while a function is being executed. Moreover, the data can change in extent during that lifetime.

All this is invisible to the user. The compiler generates function calls which create and destroy such data structures when their lifetimes begin and end. Those calls are to functions in BasicInformKit which allocate and deallocate memory on a heap at runtime. The present implementation of those functions was conservative in what it assumed about the runtime environment. For code running on the Z-machine VM, where nothing resembling malloc or free exists, there was no alternative to managing memory by hand. Code running on the Glulx VM used the same approach until running out of memory, and only then employing Glulx's malloc opcode as a last resort.

But now it is a decade later. Glulx is very reliably implemented and we can have confidence that its malloc opcode will be efficient. This proposal, then, is to make two related changes:

  1. Replace the current runtime memory management code with use of Glulx malloc/free, when running on Glulx. Continue to use the current Flex allocation code within a fixed-sized heap when running on Z.

  2. Oblige all "long blocks" of data (see below) to occupy single contiguous regions of the heap rather than spreading such data across a linked list of sub-regions scattered across the heap.

Change (1) is straightforwardly a win on Glulx: we gain speed and lose no functionality, at least if we can assume our VM always provides malloc and free.

Change (2) offers equally clear benefits on Glulx. Data can be accessed faster and more simply, and we can imagine future benefits from being able to use Glulx's built-in binary search opcode on long block data, for example.

On Z, the position is less clear-cut. The current practice attempts to reduce problems with fragmentation in a fixed-size heap as data grows and reduces in size. The nightmare scenario is where just enough little regions are used, scattered across the heap, that no large allocation of memory is possible any longer even though the total amount of free memory is sufficient for it. After change (2), therefore, there will be some degenerate cases where an Inform program running on the Z-machine runs out of heap memory earlier than it would before. As a trade-off for that, however, access to the heap will be faster, the heap will involve less memory overhead (since the linked lists of multiple blocks won't need to be stored), and some of BasicInformKit's functions will be smaller in size. Our current belief is that (2) is unlikely to cause real problems for users running programs on the Z-machine. In the end, very heavy users of memory allocation and deallocation are likely to be using Glulx anyway.

Components affected

  • No change to the natural-language syntax.
  • No change to inbuild.
  • Minor changes to inform7.
  • No change to inter.
  • No change to the Inter specification.
  • Major changes to BasicInformKit; no change to other runtime kits.
  • Major changes to Basic Inform; no change to the Standard Rules.
  • No change to documentation.
  • No change to the GUI apps.

Impact on existing projects

Unless users are running their projects on very old or buggy Glulx implementations, there should be no adverse impact on users compiling to Glulx or C.

For users compiling to Z, the memory environment is likely to be different in its behaviour when memory is close to running out: see above. Different does not necessarily mean worse, but if it is, then this can be mitigated by using a larger heap size.

In the event of the Flex API changing, that could conceivably affect projects which are calling Flex directly from their own Inter, but we are not aware of any extensions which do so. (And nor should they.)

Current implementation

BasicInformKit provides a three-level stack of functions for dealing with memory management:

(1) Each block-valued kind (or constructor), such as text (or list of K), has an API for dealing in a natural way with its values. For example, Text.i6t contains functions for fetching characters from a text. These APIs call down to:

(2) The BlockValues.i6t API, which can create, read/write, extend, contract or destroy block data, and provides functions such as BlkValueCreate or BlkValueRead. This in turn uses:

(3) The Flex.i6t API, which manages a heap of memory and provides functions such as FlexAllocate, FlexResize and FlexFree.

The Inform compiler generates calls to (1) and (2), but not (3), and makes no assumptions about the internal organisation of the heap. Moreover, (3) Flex is called only from (2) BlockValues.

Values which cannot be stored in single words are called "block values". Here a value such as a text is a pointer to a "short block", fixed in size and sometimes in static memory, sometimes on the heap, and sometimes on the stack. This short block in turn contains a pointer to a "long block", which is always on the heap. (Strictly speaking, a few block values use only a short block and can therefore exist without the heap: stored actions, for example. But texts, lists and relations all do.)

This double-indirection system protects the value. For example, suppose T is a text: T is the address of (i.e., a pointer to) a short block. This in turn contains a pointer to a long block containing the text "orange". Now the text is changed, by, say, replacing every vowel in it with the word "(vowel)". That ought to make "(vowel)r(vowel)ng(vowel)". But suppose this new text is too large to fit in the existing long block, and the long block cannot be extended because the memory immediately after it is in use. The only way out is to move the long block to some larger area elsewhere in memory: that means changing the pointer from the short block, but it does not change T. This is important: the assumption that the short block never moves in the lifetime of a block value is very deep-seated in the compiler and in BasicInformKit.

A further complication is that two different text short blocks can share the same long block, where they both refer to the same actual text. A system of reference-counting is used to make sure this does not lead to complications. Again, this is all deep-seated and means that the current division between short and long blocks cannot at all easily change.

Roughly speaking, BlockValues creates and manages short blocks. Flex creates and manages long blocks.

Proposed change

The proposal here, then, is to make the cleanest replacement: switching out Flex.i6t for a more efficient implementation of the same, or a similar, API. The new Flex implementation is likely to be much smaller and simpler.