A fast storage bookkeeping method is described which is particularly appropriate for list-structure operations and other situations involving many sizes of blocks that are fixed in size and location. This scheme, used in the LLLLLL or L6 (BelL Telephone Laboratories Low-Level List Language), makes available blocks of computer registers in several different sizes: the smaller blocks are obtained by successively splitting larger ones in half, and the larger blocks are reconstituted if and when their parts are simultaneously free.
A storage allocating and bookkeeping mechanism is described which makes available blocks of computer registers in several different sizes, the smaller blocks being obtained by successively splitting larger ones in half, and the larger blocks being reconstituted if and when their parts are simultaneously free. Each block contains a few bits of information indicating its size and whether it is presently free or in use; the rest of the block may be formatted as the user wishes. The operations involved in obtaining blocks from and returning them to the free storage lists are very fast, making this scheme particularly appropriate for list structure operations and for other situations involving many sizes of blocks which are fixed in size and location. This is in fact the storage bookkeeping method used in the BelL Telephone Laboratories Low Level List Language [1] (LLLLLL or L6 pronounced L sixth).
The method to be described is illustrated by an example in which block sizes are one, two, four and eight machine words [2]. Figure 1a depicts the original layout of storage, with the storage area divided into blocks of the largest sizes. These blocks are initially arranged in a doubly connected loop of which one element is the system register. The register's pointers point to the beginning and end of the list of blocks, as shown in Figure 1b. Pointers for such purposes could be either addresses of the first words of blocks pointed to or the 2's complements of these addresses. In this example addresses will be assumed.
There is a free storage list for each size of block. Since the lists of smaller blocks are initially null the pointers of each of these lists point to each other, that is to the same register in which both are located. As is customary with this arrangement of pointers a block is removed from its list by making its predecessor and successor point to each other; a block is inserted at the beginning of the list by appropriate setting of the four pointers involved. (Special cases, such as removing the only remaining block or inserting a block when none is there, do not require special treatment because the system pointers occupy the same locations within their words as do the other pointers.)
The storage bookkeeper being illustrated has the following points of entry from the outside: one for setting up in a prescribed region the initial list of largest-size blocks, four for obtaining blocks of the four different sizes and one for returning a block to free storage. (The bookkeeper looks at the block's size indicator to determine what to do with it.
It may frequently happen that a block of the desired size not available from the list for blocks of that size. This would be noted by system pointers pointing to each other or by a zero count in an optional counter for the current number of blocks of this size. In this case a block of the next larger size is obtained and split in two; one of its halves is returned to free storage and the other half is presented as the requested block. The process works recursively up to the largest size of block. Thus given the situation depicted in Figure 1a for a one-word block, the resulting free storage lists would contain three eight-word blocks, and one block each of sizes one, two and four words. A number of additional operations for obtaining and returning blocks of different sizes could, for example, lead to the condition illustrated in Figure 2.
The procedure is clearly one which divides available storage into blocks of different sizes exactly in proportion to the requirements of the current computer run. One difficulty not discussed is the possibility that many small blocks are required early in the run and are subsequently returned and that later many larger blocks are requested, thus requiring the reconstitution of large blocks from their individually used and freed parts.
The system under discussion does in fact recombine blocks according to these rules: When a block is being returned to free storage, a check is made to determine whether its mate (the block of the same size from which it was previously split) is presently in free storage and not further subdivided. If so the mate is removed from its list (this is why backward as well as forward pointers are required in the free storage lists), the two blocks are combined and the resulting block is placed on the list for blocks of this next larger size. This operation can be done quickly since a block's mate can be found quickly (it is immediately above or below - the question is which). One way to do this is simply to complement the nth order hit of the 2n block's address relative to the beginning of the storage region. Thus if the relative address of the beginning of a two-block ends in binary ...011001, then the relative address of the beginning of its mate ends in ...011011. Similarly if the relative address of a four-word block ends in ...010110 then the relative address of its mate ends in ...010010.
It is worth noting that a similar procedure can be used, for whatever purpose, to find the beginning of the block above a certain block in storage in the sense implied by Figure 2a. (Finding the block below it is trivial.) The method depends again upon the regular way in which the original blocks have been subdivided and upon the information as to size always found within each block.
Recombination, like splitting, is recursive. Thus in Figure 2a if the lowest. two-word block in use (lowest shaded block) is returned to free storage, not only will it be combined with the two-word block below it but the resulting four-word block will also be combined with the free four-word block above it, thus reconstituting one of the original eight-word blocks.
In the interest of further improving the speed of the system it may not be desired to recombine free blocks every time recombination is possible. The system may be designed to use a simple strategy to decide when to try to recombine: e.g., when there are already a certain number of blocks of the size being returned, or when there are fewer than the desired minimum number of blocks of the largest size or when some other simple function of these numbers is satisfied. The precise form of the heuristic used to govern recombination will depend upon how early the system should begin to anticipate trouble which could result from a proportionally increased demand for the larger blocks.
[1] KNOWLTON, K. C. A programmer's description ot LLLLLL, Bell Telephone Laboratories low-level list language. Bell Telephone Laboratories, Inc., Mar. 1965. This language provides for blocks of the following lengths: 1, 2, 4, 8, 16, 32, 64 and 128 words.
[2] Upon completing this paper the author has learned that a similar storage handling system is used in SIMscRIPT where block sizes are in fact one, two, four and eight words. For a description of the language, see MARKOWITZ, H. M., HAUSNER, B., and KARN, H. W. SIMSCRIPT - A Simulation Programming Language. Prentice-Hall, Englewood Cliffs, N. J., 1963.