Managed Tables

ManagedTables was a storage management technique used in GordonLetwin's 8080 Basic interpreter. It also was a standard library component in the Purdue Mace OS and used in many utilities.

These days software generally relies on large amounts of real or virtual memory and usually manages all dynamic storage out of a single heap. Managed tables may still be suitable where

Memory is fixed and limited
It is impossible or impractical to stage data to disk
Dynamic data can be classified into a small number of homogeneous items

Where it makes sense, managed tables have a lot less storage overhead, as the overhead is constant per table rather than per item.

Managed Tables are implemented in a contiguous section of RAM. Typically all the spare RAM after loading your program is allocated to managed tables. Within that, each of the tables (data types) to be managed are assigned a fixed relative order. The table manager maintains a pointer or index to the start of each individual table. When a table grows in size, all the following tables are block-moved down to make room. Usually, the moved tables move down so that all the available free space is now part of the table which most recently grew.

The table manager provides functions for

adding a new item to a table
deleting an item to a table
accessing the ith item in a table

Fancy implementations additionally provide

creating and removing a table
maintaining sort order of elements in a table
managing tables consisting of variable length items (of a known format)

GregMansfield wrote a managed table package for the CDC6000 series. It's hard these days to think of managed tables as an achievement. You have to remember that back then machine words were long and scarce. A UniversalDataStructure? had to deal with BitPacking? and do so quickly with word addressing.

I suspect Gordon picked up the ideas from Greg's package, possibly through RossGarmoe? who was a DualMace heavy. Gordon later brought Ross into the os group at Microsoft.

-- WardCunningham

The SinclairZX81 and SinclairSpectrum Basic's also managed memory in this way. The SinclairZX81 even used ManagedTables for its display file. If there was nothing on the screen, the machine would store just one newline for each screen line. When text was added to the screen, it would expand the ManagedTables character by character.

-- JamesNoble

Venn implemented, as part of their set-theoretic database software for the PC, a library called Space Manager. Space Manager used a couple of dedicated pages of PC memory to provide access to a very large collection of tables. Tables could grow and shrink, and could be added and removed. Space Manager was basically ManagedTables with disk-based virtual memory.

The reason you never heard of this is that we only had a very small number of very happy customers. Next time I'll partner with a sales guy, not another techie. --RonJeffries