DEFINITIONS4c1

An enfilade is a data structure in which the positions of data items in index space (i.e., the retrieval keys associated with those data items) are stored indirectly, as local positions relative to the data items’ neighborhoods in the data structure, rather than being stored directly, as absolute positions.

4c3Enfilades have traditionally been implemented as trees. Each node of the tree is called a crum (in order to disambiguate the term “node” — see footnote 4). Each crum contains, either explicitly or implicitly, two components of indexing information, called the wid and the disp. In addition, a crum may contain other structural information, such as pointers to descendent or sibling crums.

4c4A disp represents the relative offset, in index space, of its crum from its crum’s parent. The “sum” of a crum’s disp with those of all of its ancestors determines the crum’s absolute position in index space. A change in a crum’s disp therefore causes a corresponding change not only in the crum’s absolute position but in those of all of its descendents.

4c5A wid represents the extent, in index space, of its crum’s collective descendants, relative to its crum’s position (which is in turn derived from its crum’s disp). A change in a crum’s wid may result if the wid or disp of one of the crum’s children changes.

4c6An enfilade’s disps are interpreted in a top-down fashion, telling the relationship of crums to their ancestors, while the wids are interpreted from the bottom-up, indicating the relationship of crums to their descendents.

A group of sibling crums, all descended from the same parent crum, is collectively referred to as a loaf or crum-block. The single crum which forms the root of the tree and from which all other crums are descended is called the fulcrum. The disp of the fulcrum is offset relative to the origin of the index space. The crums which form the leaves of the tree are called bottom crums. The tree is maintained at a constant depth, so all bottom crums are the same number of levels below the fulcrum. Bottom crums may contain actual data in addition to structural and indexing information and therefore may have a different structure or form than their ancestors do. Non-bottom crums are referred to as upper crums. When enumerating the levels of an enfilade, it is conventional to number from the bottom up so that the level number of a crum will not change as the enfilade grows or shrinks (levels are added or deleted at the top).

4c8An index space may be multi-dimensional, and not all dimensions need participate in enfiladic operations, as described below.

4c9An enfilade is similar in many ways to a conventional B-tree. This is especially so when considering the set of primitive operations that are defined. However, an enfilade is not a B-tree. Enfilades possess two properties that distinguish them from B-trees (properties that were, in fact, the motivation for the invention of the first enfilades). These properties are rearrangability and the capacity for sub-tree sharing. These derive from the nature of wids and disps as local abstractions independent of the overall frame of reference of the full data structure.

4c10While enfilades have traditionally been implemented as trees, we do not feel that this is essential. Generalization of the theory of enfilades to other types of data structures, for example hash tables, has been considered but not yet examined in depth.

OPERATIONS4d1

4d2The fundamental operations on an enfilade are retrieve, rearrange and append. These are augmented by the useful, though not strictly necessary, operations insert and delete. All of these are supported by the “housekeeping” operations cut, recombine, level push and level pop.

4d3The retrieve operation obtains a data item associated with a particular location in index space. Such a data item may be stored in an enfilade either directly, by actually storing it in the bottom crum associated with the desired position in index space, or indirectly, as a function of the wids and disps of the crums traversed while descending the tree to that bottom crum. The latter alternative is fairly unusual and deserves elaboration. For example, enfilades in index spaces with multiple independent dimensions could store data by indexing with some dimensions and not others and then return the positions of bottom crums along the other dimensions. A single enfilade may contain several collections of data at once, some stored one way and some another.

4d4The general algorithm for retrieve is:

retrieve (indexSpacePosition)
  result ← recursiveRetrieve (indexSpacePosition, fulcrum, .0.)
end retrieve

recursiveRetrieve (index, aCrum, cumulativeIndex)
  if (index .==. cumulativelndex)
    result ← data (aCrum)
  else 
    for each child of aCrum
      if (disp(child) .<=. index) and (index .<. (disp(child) .+. wid(child)))
        result ← recursiveRetrieve (index, child, cumulativeIndex .+. disp(chlld))
      end if
    end for
  end if
end recursiveRetrieve

4d5where disp(crum) extracts a crum’s disp, wid(crum) extracts its wid, and data(crum) extracts the datum from a bottom crum. The symbols .==., .<. and .<=. represent comparison operators in index space. The symbol .+. represents “addition” in index space. The symbol .0. represents the origin of the index space. If less than the full number of possible dimensions is being used for indexing, the index space operators must be specified to take this into account. The symbol ← is an assignment operator. result is assigned to return a value. The control constructs are what they appear to be.

4d6Note that this algorithm retrieves exactly one data item stored directly in a bottom crum. If data are stored indirectly in the wids and disps, as described above, the algorithm must be modified accordingly. To implement the case described previously (where some dimensions are used for indexing and others for indirect data storage), the operators .==., .<., and .<=. should be defined only to compare along the indexing dimensions, while .+. should be defined on all dimensions. The result returned should not be the extraction of data from the bottom crum but the extraction of the data dimension components of cumulativeIndex.

4d8This algorithm also does not take into account the possibility that the desired data item might not be present at all. Once again, the generalization of collecting the results in a set would correct this (the result in such a case would be an empty set) and the omission is for clarity.

4d9In cases where multiple hits are excluded, retrieval time is logarithmic with the number of data items stored. Where multiple hits are permitted, non-logarithmic elements are introduced and the analysis is not so straightforward, but depends upon the specific nature of the enfilade in question. In the case of multi-dimensional index spaces, retrieval times depend on the splitting and regrouping algorithms used to balance the tree. There are tradeoffs that depend on the number of dimensions that are typically to be used to retrieve with and the performance in atypical retrievals. If the enfilade is totally optimized along one dimension, retrievals will be of logarithmic order along that dimension and linear along the others. If it is optimized along D dimensions collectively and retrievals are performed along K of those dimensions, the retrieval time will be on the order of N^(D-K)/D·log(N), K≤D, where N is the number of data items stored in the enfilade.

4d10The rearrange operation alters the index space positions of clusters of data items by selective alteration or transposition of disps. Rearrangability is one of the two essential properties of enfilades which distinguish them from other sorts of data structures (the other, sub-tree sharability, is discussed below). Rearrange changes the relative ordering of crums in index space.

4d11Rearrange operations are specified in terms of cuts. There are two “flavors” of rearrange, called three-cut rearrange and four-cut rearrange. A cut delineates a boundary for the rearrange operation. A cut is a separation between two regions of interest, defined by a position in index space, C, such that there exists a pair of sibling crums (i.e., crums descended from the same parent), A1 and A2, such that:

indexSpacePosition(A1) .<=. C .<. indexSpacePosition(A2)
                and
(indexSpacePosition(A1) .+. disp(A1)) .<=. C

indexSpacePosition(Q) .<=. C implies that either
        indexSpacePosition(Q) .<. indexSpacePosition(A1)
                or
        Q is a descendant of A1
and
C .<. indexSpacePosition(Q) implies that
           indexSpacePosition(A2) .<=. indexspacePosition(Q)

4d12Cuts are generally used in groups (in the case of rearrange, in groups of three or four). When multiple cuts are used together they are constrained to propagate upward until all cuts reach a common ancestor. In other words, if cut C1 is bounded by crums A1 and A2, as described above, and cut C2 is similarly bounded by crums A3 and A4, then crums A1, A2, A3 and A4 should all have the same parent.

4d13A three-cut rearrange performed with cuts C1, C2 and C3 moves the material between C2 and C3 to the position defined by C1 (or, equivalently, moves the material between C1 and C2 to the position defined by C3). This is accomplished at the level of the sibling crums at the top of the three cuts by adjusting some of the crums’ disps, as follows, where P is the parent to all of the crums at the top of the cuts:

for each crum that is a child of P
        pos ← indexSpacePosition(crum)
        if (C1 .<. pos) and (pos .<=. C2)
                disp(crum) ← disp(crum) .+. (C3 .-. C2)
        else  if (C2 .<. pos) and (pos .<=. C3)
                disp(crum) ← disp(crum) .-. (C2 .-. C1)
        end if
end for

4d14A four-cut rearrange performed with cuts C1, C2, C3 and C4 transposes the material between cuts C1 and C2 and the material between cuts C3 and C4. As with the three-cut rearrange, this is performed by manipulating the disps of the crums at the top of the cuts:

for each crum that is a child of P
        pos ← indexSpacePosition(crum)
        if (C1 .<. pos) and (pos .<=. C2)
                disp(crum) ← disp(crum) .+. (C4 .-. C2)
        else  if (C2 .<. pos) and (pos .<=. C3)
                disp(crum) ← disp(crum) .-. (C2 .-. C1) .+. (C4 .-. C3)
        else  if (C3 .<. pos) and (pos .<=. C4)
                disp(crum) ← disp(crum) .-. (C3 .-. C1)
        end if
end for

4d15It can be seen that the three-cut rearrange is equivalent to a four-cut rearrange in which two adjacent cuts are identical.

4d16The cut operation itself is accomplished by splitting crums which straddle the cut location. The two new crums correspond to the two sides of the cut. The children of the old crum are assigned to the new crums according to which side of the cut they fall on — any children which themselves straddle the cut are split using the same procedure recursively. Cuts are usually made in groups, with the cutting process terminating when a single crum spans all of the cut location (this crum corresponds to the crum P in the algorithms above). The following is the algorithm for cut:

cut (cutSet)
        recursiveCut (cutSet, fulcrum)
end cut

recursiveCut (cutSet, parentCrum)
        dontDiveDeeperFlag ← TRUE
        for each child of parentCrum
                if (disp(child) .<. firstCut(cutSet)) and (lastCut(cutSet) .<=. (disp(child) .+. wid(child)))
                        dontDiveDeeperFlag ← FALSE
                        for each cut in cutSet
                                cut ← cut .-. disp(child)
                        end for
                        recursiveCut (cutSet, child)
                end if
        end for
        if (dontDiveDeeperFlag)
                chopUp (cutSet, parentCrum)
        end if
end recursiveCut

chopOp (cutSet, parentCrum)
        for each cut in cutSet
                for each child of parentCrum
                        if (disp(child) .<. cut) and (cut .<=. (disp(child) .+. wid(child)))
                                neWChildSet ← split(cut, child)
                                disown(parentCrum, child)
                                adopt (parentCrum, leftChild(newChildSet))
                                adopt (parentCrum, rightChild(newChildSet))
                                break out of inner loop
                        end if
                end for
        end for
end chopUp

split (cut, crum)
        leftCrum ← createNewCrum ()
        rightCrum ← createNewCrum ()
        disp(leftCrum) ← disp(crum)
        wid(leftCrum) ← cut .-. disp(crum)
        disp(rightCrum) ← cut
        wid(rightCrum) ← wid(crum) .+. disp(crum) .-. cut
        for each child of crum
                if ((disp(child) .+. wid(child)) .<. cut)
                        adopt (leftCrum, child)
                else  if (cut .<=. disp(child))
                        adopt (rightCrum, child)
                else 
                        newChildSet ← split(cut .-. disp(child), child)
                        adopt (leftCrum, leftChild(newChildSet))
                        adopt (rightCrum, rightChild(newChildSet))
                end if
        end for
        result ← makeChildSet(leftCrum, rightCrum)
end split

4d18The general algorithm to append a single new element to an enfilade is:

append (newThing, beyond, where)
        potentialNewCrum ← recursiveAppend (newThing, fulcrum, beyond, where)
        if (notNull(potentialNewCrum))
                levelPush (potentialNewCrum)
        end if
end append

recursiveAppend (newThing, parent, beyond, where)
    if (where .==. .0.)
        newCrum ← createNewBottomCrum ()
        data(newCrum) ← newThing
        wid(newCrum) ← naturalWid(newThing)
        disp(newCrum) ← disp(parent) .+. beyond
        result ← newCrum
    else 
        for each child of parent
            if (disp(child) .<=. where) and (where .<. (disp(child) .+. wid(child)))
                potentialNewCrum ← recursiveAppend(newThing, child, beyond,
                                                         where .-. disp(child))
                break
            end if
        end for
        if (notNull(potentialNewCrum))
            if (numberOfChildren(parent) >= MaximumNumberOfCrumsInALoaf)
                newCrum ← createNewCrum ()
                disp(newCrum) ← disp(potentialNewCrum)
                disp(potentialNewCrum) ← .0.
                wid (newCrum) ← wid(potentialNewCrum)
                result ← newCrum
            else 
                wid(parent) ← enwidify(children(parent), potentialNewCrum)
                adopt(parent, potentialNewCrum)
                result ← NULL
            end if
        else 
            result ← NULL
        end if
    end if
end recursiveAppend

4d19Enfiladic trees are generally balanced by maintaining the requirement that the number of children of anyone crum (i.e., the number of crums in a loaf) may not exceed a given threshold. In practice, since the structure of bottom crums and upper crums may differ, it is often the case that this threshold will differ between bottom loaves and upper loaves. The actual values chosen for these thresholds depend upon the actual enfilade in question, and are typically selected to optimize retrieval speed, disk space efficiency, or some other empirically determined, implementation dependent criteria.

4d20The level push operation adds an additional level to the tree when an append or insert operation causes the number of children of the fulcrum to grow too large. It simply creates a new fulcrum from which is descended the old one. The algorithm is:

levelPush (newCrum)
        newFulcrum ← createNewCrum ()
        disp(newFulcrum) ← .0.
        wid(newFulcrum) ← enwidify(fulcrum, newCrum)
        adopt (newFulcrum, fulcrum)
        adopt (newFulcrum, newCrum)
        fulcrum ← newFulcrum
end levelPush

4d21where the argument newCrum represents the new sibling to the old fulcrum from which is descended the branch of the tree which caused the old fulcrum to overflow.

4d22The insert operation adds a new data element at a random position in the enfilade. Insert is not a strictly necessary operation, since it is functionally equivalent to an append operation followed by a rearrange operation. The append adds the new item to the data structure and then the rearrange relocates it to the desired location. In practice, insert is often implemented as a separate operation, for reasons of efficiency or convenience. An insertion is accomplished by making a cut at the desired insertion point, extending this cut upwards to a crum whose wid is large enough to encompass the data to be inserted, and then plugging the new material in. The disps of crums .>. the new material at this level are then incremented accordingly. The algorithm to accomplish this is left as an exercise for the reader in order not to overly extend this paper. The delete operation removes things from an enfilade. Delete, like insert, is also not strictly necessary, since undesired material can be relocated to any arbitrary “purgatory” by the rearrange operation. In actual use, however, it often desirable to actually delete things in order to be able to reclaim the storage that they occupy. The delete operation is quite simple: two cuts are made on the boundaries of the unwanted region of index space and propagated up to a common ancestor. The child crums of this ancestor which lie between the cuts are then disowned and the disps of greater siblings reduced accordingly. The disowned crums and all of their descendants may then be deallocated or left for garbage collection.

4d23Deletes and rearranges can result in an enfilade that is a badly fragmented, unbalanced tree and in which many crums have fewer than the optimum number of children. This in turn can result in a tree which has more levels than necessary, with a potentially adverse affect upon performance. The recombine operation is used to tidy things up by merging sibling crums. The algorithm to merge two siblings is:

primitiveRecombine (parent, sibling1, sibling2)
        newCrum ← createNewCrum ()
        disp(newCrum) ← disp(sibling1)
        for each child of sibling1
                disown(sibling1, child)
                adopt (newCrum, child)
        end for
        dispCorrection ← disp(sibling2) .-. disp(sibling1)
        for each child of sibling2
                disown(sibling2, child)
                disp(child) ← disp(child) .+. dispCorrection
                adopt (newCrum, child)
        end for
        wid(newCrum) ← enwidify(children(newCrum))
        disown(parent, sibling1)
        disown(parent, sibling2)
        adopt(parent, newCrum)
end primitiveRecombine

4d24The term recombine is commonly used to refer to the process of climbing around the enfiladic tree and selectively applying the above operation in order to perform some general housecleaning. Such a process may also include cut operations to split up recombined crums which have too many children, perhaps interleaving cuts with primitiveRecombines in order to “shuffle” crums around in the tree. The methods for doing this are heuristic rather than algorithmic, and depend both on the nature of the particular enfilade in question and the data with which it is being used. Certain applications may not, in fact, require any recombines to be performed at all. A recombine may also invoke a level pop operation to remove an excess level from the tree. This can be performed when the fulcrum has but a single child. The algorithm is simply:

levelPop ()
        newFulcrum ← theOneChildOf(fulcrum)
        disp(newFulcrum) ← disp(newFulcrum) .+. disp(fulcrum)
        disown(fulcrum, newFulcrum)
        fulcrum ← newFulcrum
end levelPop

OBSERVATIONS4e1

4e2The use of wids and disps means that each crum in an enfilade is located relative to its parent rather than to any absolute coordinate space. This in turn means that enfilades may engage in sub-tree sharing. Multiple crums on a given level of one or more enfilades may point to a single lower crum as one of their children. This has the effect of making virtual copies of the sub-tree represented by that crum and all of its descendents. The index space position of the bottom crums of such a sub-tree depends upon the particular parent crum through which they are accessed. Sub-tree sharability and rearrangability, both the result of the localizing action of wids and disps, are the two properties which most significantly distinguish enfilades from other sorts of data structures.

4e3One of the problems with multi-dimensional data is that, unlike one dimensional data, there is, in general, no single well-defined ordering of the data. K-ary trees solve this problem using projection onto a single dimension. Enfilades use the locality of wids and disps to eliminate the need for ordering.

4e4One of the many useful applications of sub-tree sharing is versioning — the creation enfilades which represent alternate organizations of a given body of data. Often, alternate versions of some set of material will have significant portions in common (insert reference on Reps’ subtree sharing here) (this, in fact, may be what we mean when we say two things are “versions” of each other, rather than saying that they are separate things). Common portions of two data sets can be represented by a single enfiladic sub-tree. Separate data structure is only required where they actually differ. If the differences between two versions are small relative to the total volume of data, the storage savings can be significant. In addition, alterations to the shared portions may also be shared, thus changing one data set can change the other correspondingly, if this is desired.

4e5The recombine operation must be reconsidered in the light of sub-tree sharing. Recombination is not always desirable, even when an enfilade is badly balanced, since it would be an error to recombine a shared crum with an unshared one. The recombine operation must be carefully constructed, if used at all, in applications where sub-tree sharing is expected.

4e6Another interesting (and pleasing) property of enfilades is that they naturally and automatically tend to adapt themselves to take advantage of any clustering of the data in index space. This is because crums are grouped together into loaves according to the volume of material stored, rather than according to the material’s indices. In addition, it is often the case that cuts will tend to occur in the less dense regions of the data structure. Over a period of time, the various manipulations performed will tend to bring about a helpful measure of correlation between patterns of sub-tree grouping in the enfilade and patterns of clumping in the data that it stores.

SUMMARY4f1

4f2An enfilade is a tree structure in which the nodes, called crums, do not directly store the indexing key, but rather a pair of localized abstractions of the key called the wid and the disp. These represent the extent and position relative to a parent in index space. Manipulation of an enfilade is supported by the operations retrieve, append, rearrange, insert, delete, recombine, cut, level push and level pop. Enfilades also allow sub-tree sharing.

TUMBLERS AND HUMBERS5e1

5e2A form of transfinitesimal number called a tumbler is used frequently throughout the system. Tumblers are like the numbers used to identify chapters, sections, sub-sections, pages, paragraphs and sub-paragraphs in many technical manuals. They are represented externally as a sequence of integer fields separated by periods (“.”) and internally as a string of integers. For example, 3.2 and 47.23.137.0.5 are tumblers (the period is a delimiter for the human reader and is not essential to the fundamental notion of what tumblers are).

5e3A non-commutative arithmetic operation called tumbler addition is defined. For example:

5e5This arithmetic gives different roles to the two tumblers: the first specifies a position — where something is — and the second specifies an offset — a distance to move forward. In this example, only the first field of the original position matters. A couple more examples are:

5e7The following rules describe the procedure for tumbler addition:

1. 5e8a1Evaluating from the most to the least significant fields (i.e., from left to right), the fields of the final result are equal to the corresponding fields of the initial position as long as the corresponding fields of the offset are zero.

2. 5e8b1The first non-zero offset field is added to the corresponding field of the initial position.

3. 5e8c1The remaining fields of the final result are equal to the remaining fields of the offset.

5e9Since tumbler addition is non-commutative, there are two possible forms of tumbler subtraction. We call these strong tumbler subtraction and weak tumbler subtraction. The Xanadu system makes use of a generalized tumbler difference operator defined as follows: when taking the difference of two tumblers A and B, if A is greater than B then the result is obtained by strongly subtracting B from A: otherwise the result is obtained by weakly subtracting A from B. As a result, no subtraction operation is ever performed that results in a negative tumbler. Like tumbler addition, tumbler subtraction involves two operands with different roles: a position and a negative offset. The difference between the two forms of tumbler subtraction is that strong subtraction results in a tumbler which may be added to the negative offset to get back to the original position, whereas weak subtraction involves simply applying the same essential procedure as tumbler addition with field subtraction substituted for field addition.

5e10Here are some examples of strong tumbler subtraction:

5e12Note that:

5e14The following rules describe the procedure for strong tumbler subtraction:

1. 5e15a1Evaluating form the most to the least Significant fields (i.e., from left to right), the fields of the final result are equal to zero as long as the corresponding fields of the initial position and the negative offset are equal to each other.

2. 5e15b1The first non-equal field of the negative offset is subtracted from the corresponding field of the initial pOSition.

3. 5e15c1The remaining fields of the final result are equal to the remaining fields of the initial position.

5e16Here are some examples of weak tumbler subtraction:

5e18The following rules describe the procedure for weak tumbler subtraction:

1. 5e19a1Evaluating from the most to the least significant fields (i.e., from left to right), the fields of the final result are equal to the corresponding fields of the initial position as long as the corresponding fields of the negative offset are zero.

2. 5e19b1The first non-zero negative offset field is subtracted from the corresponding field of the initial position.

5e20Tumblers are used in the Xanadu system because of their accordion-like extensibility. They have the property that, like both real and rational numbers, between any two numbers are infinitely many more. Tumbler-space has a porosity that allows any amount of new material to be inserted at any point.

5e21Tumblers are stored internally using Humbers. “Humber“ is short for ”Huffman encoded number“ or ”huge number”. A humber is a form of infinite precision integer used to represent the fields of tumblers. Use of infinite precision integers prevents constraints on the size of a tumbler’s field due to a restriction to, for example, 32-bit numbers.

5e22Humbers are constructed out of 8-bit bytes. If the high-order bit of the first byte is 0, then the remaining 7 bits encode the number itself, with possible values ranging from 0 to 127. It the aforementioned bit is 1, then the remaining 7 bits encode the number of bytes in the number, and that many bytes then follow which contain it. Should more than 127 bytes be required to represent the number, the length zero (i.e., a high order bit of 1, followed by seven 0’s) indicates that what follows is a humber (applying this definitio recursively) that encodes the length, followed by the indicated number of bytes encoding the number.

5e23This representation never runs out of precision and can represent any non-negative integer whatsoever (and, in fact can represent negatives with minor modification). In addition, most tumbler fields in the Xanadu system are small (i.e., less than 127) and thus can be encoded in a single byte. Tumblers are represented in a floating-point like format, with a mantissa consisting of a field count humber followed by the indicated number of field humbers, and an exponent humber indicating the number of leading 0 fields (leading since tumblers are transfinitesimals).

5e24Tumblers are used in the Xanadu system as both V-stream addresses and I-stream addresses. We perform some tricks with these addresses by encoding some information about the thing addressed in parts of the tumbler itself. In particular we use fields with the value “0” as a delimiter to separate one part of a tumbler from another. For example, the “0” in 4.3.7.0.19.1 separates the tumbler into the two pieces 4.3.7 and 19.1. Of course, the pieces have to be constrained to not contain any “0”s themselves. Note also that the pieces are themselves tumblers.

5e25Using the 0-field-as-delimiter scheme, an invariant orgl identifier is represented as a tumbler of the form:

5e27where 〈node〉, 〈account〉 and 〈orgl〉 are tumblers that don’t contain “0” as one of their constituent fields. The 〈node〉 component is there in anticipation of future implementations which store orgls in a distributed network, and represents the particular node of that network with which the orgl is associated. 〈account〉 similarly anticipates future multi-user systems, and represents the particular user or account (i.e., user associated with node number 〈node〉) which owns the orgl. 〈orgl〉 indicates which particular one of that user’s orgls is desired. For example, 5.0.3.2.0.17 indicates the 17th orgl belonging to the 3.2nd user on the 5th node. In the present single-node single-user system, addresses all resemble 0.0.〈orgl〉 with the 〈node〉 and 〈account〉 components being empty. Both V-stream and I-stream addresses are tumblers of the form: 〈invariant orgl id〉.0.〈v-space〉.〈position〉 where 〈invariant orgl id〉 is the tumbler representing an invariant orgl identifier of the form described above and 〈v-space〉 and 〈position〉 are inteqer fields. 〈v-space〉 specifies which virtual space of the orgl in question is desired, and 〈position〉 indicates a particular atom within that v-space. Thus 5.0.3.2.0.17.0.47.23 denotes the 23rd atom of the 47th v-space of the orgl specified in the previous example.

5e28Use of the “0” field as a delimiter to concatenate the various components of addressing information into a single tumbler allows a single tumbler-space to contain all possible V-stream or I-stream addresses. This in turn simplifies the construction of data structures that use V-stream or I-stream space as their index space by eliminating any need for dealing with the various components separately.

5e29Future plans may include support for an extended indirect V-stream address of the form:

5e31where 〈v-stream address〉 is a V-stream address of either this form or the previous one. This notation allows the immediate specification of atoms via orgls which are themselves within other orgls. For example, 5.0.3.2.0.17.0.47.23.2.1 would indicate the 1st atom of the 2nd v-space of the orgl addressed in the previous example (assuming, of course, that it was in fact an orgl and not a character atom).

5e32The porosity of tumbler space enables new addresses to be created easily without conflict with previously created ones. For example, node 5 from the past few examples could create a new node 5.1 without requiring knowledge of whether, say, node 6 existed or not. Orgl ids for new versions of previously existing orgls are created this way. For example, the first new version of orgl 1.0.2.0.3 would be 1.0.2.0.3.1 and the next would be 1.0.2.0.3.2. Physical storage locations are not, in general, represented using tumblers. Instead they have a form which is entirely dependent upon the nature and quantity of the underlying storage hardware and the dictates of the operating system software which interfaces with that hardware.

THE GRANFILADE5f1

5f3The index space used by the granfilade is I-stream tumbler space. The wid of a granfilade crum is a tumbler specifying the span of I-space beneath the crum (i.e., the distance, in tumbler space, from the first to the last bottom crum descended from it). The widdative function is tumbler addition, therefore a crum’s wid is simply the tumbler sum of its children’s wids. Bottom crums have an implicit wid of 0.0.0.0.1 (i.e., spanning no nodes, no accounts, no orgls, no V-spaces and spanning a single atom). Granfilade disps are tumbler offsets in I-space from the parent crum.

5f4Bottom crums in the granfilade represent atoms. Atoms come in two varieties: characters and orgls. Character bottom crums are stored as spans of characters, rather than individual bytes. These consist of a pointer to a block of physical storage, either in core or on disk, containing the bytes themselves, and an (integer) length, telling the number of bytes in the block. Since each of these bytes has an implicit wid of 0.0.0.0.1, the character span has a wid of 0.0.0.0.〈number of characters in the span〉. Orgl bottom crums are stored in a similar fashion, but instead of literal data bytes, pointers to the fulcrums of orgls (poomfilades) are stored.

5f5To obtain the atom associated with a particular I-stream address, an enfilade retrieve operation is performed (see accompanying paper on enfilade theory). Starting with the fulcrum, the wid is subtracted from the desired I-stream address, and the child crum is selected whose disp comes closest to the modified I-stream address without going over it. The process is then repeated with this child crum and the modified I-stream address as the target. At the bottom, the (by now much reduced) target address is used as an index into the appropriate character or orgl span to select the desired atom. It is quite possible to find that there is no bottom crum associated with a given I-stream address, since tumbler space is porous (i.e., between any two tumblers are infinitely more tumblers).

5f6Although the grandmap is said to simply map from I-stream addresses to physical storage locations, a retrieval operation on the grandmap may involve looking up the disk locations of the atoms in the granfilade, bringing the atoms themselves from those locations into core, and then returning the core addresses. This is something more than a simple lookup operation.

5f7In practice, retrieves are performed upon a whole span at once, returning a number of atoms (which is specified in the retrieve request) starting at the given index space location. The length of the span to be retrieved is also a tumbler, due to the porosity of tumbler space.

5f8The only operations performed upon the granfilade are retrieve and append, although there are an infinite number of potential places to append to (one such place for each possible V-space or each possible invariant orgl id). The granfilade is never cut, deleted from or rearranged. It simply accretes data monotonically, and then allows it to be quickly regurgitated. For this reason, it is quite reasonable to store the bottom and interior crums of the granfilade on an unchangeable medium, such as write-once optical disks.

THE POOMFILADE5g1

5g2The second major data structure inside the system is the poomfilade. The poomfilade is used to implement orgls. POOM stands for Permutations On Ordering Matrix. The poomfilade represents something functionally similar, though not identical, to a permutation matrix: a sparse binary matrix in tumbler space, one axis of which represents the V-stream and the other the I-stream. A “1” at a given coordinate indicates that the orgl realized by the matrix maps that coordinate’s V-stream axis location to and from its I-stream axis location. A “0” indicates that no such mapping exists. This would be a permutation matrix but for virtual copies, which result in a mapping between a single I-stream location and a number of V-stream locations, allowing a given I-stream “column” of this matrix to have more than one “1” entry. In addition, the previously mentioned porosity of tumbler space results in an infinite number of “rows” and “columns” which are all “0”s.

5g3The index space used in the poomfilade is two-dimensional cartesian tumbler space. The disps and wids of poomfilade crums are ordered pairs of tumblers representing the positions and extents, respectively, of rectangles in this space. The positions (disps) draw their origin relative to the parent crum. The widdative function is construction of the minimum enclosing rectangle of the rectangles represented by all the children in a loaf.

5g4Bottom crums in the poomfilade are identity matrices, representing V-spans that map without internal alteration onto I-spans. These are stored as a position (disp) along with a single value for extent (since identity matrices are, by definition, square). It is not necessary to actually store the “1”s and “0”s themselves.

5g5Retrievals are performed on the poomfilade using one axis as the indexing axis and the other as the data axis. Extracting information consists of recursively delving into the boxes represented by the rectangles crossing the rows or columns of interest. A rearrange performed along the V-stream axis implements the corresponding primitive orgl edit operation (see the accompanying paper on the Xanadu system architecture) on the V-stream order of the orgl that the poomfilade represents. The other edit operations are implemented by manipulating the poomfilade in a similar fashion. Virtual copies are implemented using sub-tree sharing.

THE DIV POOM5h1

5h2The DIV poom is an extended design for the poomfilade that is planned but not yet implemented. The DIV poom is similar to the poom, but adds a third dimension to enable the determination of the orgl of origin of material that has been virtually copied. The third dimension is orgl (or “document”, for historical reasons, hence the “D”) of origin of the I-span. Bottom crums are still planar identity matrices, but associated with each is a position on the I-stream corresponding to orgl of origin for the span represented. Upper crums represent three-dimensional bounding rectangular prisms, although the enfilade is otherwise the same as the basic poomfilade.

THE SPANFILADE5i1

5i2The Xanadu system’s third major data structure is the spanfilade. The spanfilade is used to implement the spanmap, a mapping from the I-stream to the O-stream (the subset of the I-stream whose atoms are orgls).

5i3The spanfilade is similar to the poomfilade in its higher level structure — crums represent recursively nested boxes, and the widdative function is still the minimum enclosing rectangle. The bottom crums are different, however, as is the interpretation of the axes.

5i4The two axes represent the I-stream and the O-stream. In addition, the data structure is partitioned along the O-stream axis into independent segments, each of which spans the entire O-stream but represents the spans referenced from a particular V-space (this partioning is like having a set of parallel spanfilades, one for each V-space). Such a partitioning enables retrievals to be readily restricted to orgls from particular V-spaces.

5i5Bottom crums represent I-spans referenced by a particular orgl in a particular V-space. A Bottom crum contains an O-stream position (relative to its parent crum), representing the I-stream address of a referencing orgl, an I-stream position (also relative to the parent crum), representing the start of an I-span, and an I-span length. The first two of these together constitute the bottom crum’s disp, while the third is the crum’s wid.

5i6Retrievals are performed on the spanfilade using I-spans as the indexing elements. The result of such a retrieval is a set of I-stream addresses corresponding to the orgls which map some segment of the V-stream onto the I-span used as the key.

THE DREXFILADE5j1

5j2The drexfilade is a much improved design for the spanmap which will replace the current one as soon as possible. The drexfilade is also similar in flavor to the spanfilade, the poomfilade and the DIV poom (in fact, these are all part of a family which we call N-dimensional enfilades, where, in this case, N is 2 or 3). It is a three dimensional binary matrix, with the three dimensions representing the O-stream and the starting and ending I-stream addresses of I-spans. Bottom crums are single points (the “1”s of the matrix). The interpretation of this matrix is as follows; a point is “1” (i.e., present in the data structure) if and only if the I-span it denotes on the two I-stream axes is present in (i.e., mapped to in full by) the orgl denoted by its O-stream axis position.

5j3The drexfilade avoids some unfortunate combinatorial problems with the spanfilade. It also allows queries about arbitrary patterns of overlap between particular I-spans and the spans mapped to by the orgls, in addition to queries about simple enclosures.

THE HISTORICAL TRACE ENFILADE5k1

5k2The historical trace enfilade is certainly the most complex Xanadu data structure. Implementation has therefore been deferred until the more basic portions of the system are fully functional.

5k3The underlying representation of an orgl is a sparse binary mapping matrix. Each of the primitive editing operations which the system supports — rearrange, append, insert and delete — is expressed as a transformation matrix that the poom is multiplied by to obtain the new, edited orgl. Note that the initial state of an orgl is a single identity matrix. When an edit operation is applied to this identity matrix, the resulting orgl is the transformation matrix for that edit itself. From this it may be seen that each edit transformation matrix is in some sense an orgl itself, mapping from the old V-stream order of the orgl to the new V-stream order.

5k4The matrix product of several of these transformation matrices is itself a transformation matrix for a single transformation that is equivalent to the constituent transformations applied individually. The product of all the transformations in the history of an orgl (not including alternate versions) is in fact the orgl itself.

5k5The history of a phylum consists of the sequence of changes which have been made to its orgls over time. In the case of a phylum for which no versioning has taken place, this is a linear series of operations. Whenever a new version is introduced, the sequence of changes branches and becomes a tree. One way of visualizing this is as a wire frame tree with beads strung along the wires. Each bead represents a single primitive change to an orgl. It is this tree which forms the index space of the historical trace enfilade. There are thus two trees to keep in mind: the enfiladic tree — the data structure itself — and the tree-shaped index space in which the enfilade resides.

5k6Locations in the index space — points in the history of a the phylum — are expressed as a path through the history tree. The tree is structured so that there are only binary branches. A path can be represented by distances (in units of single edit operations) interspersed with direction changes. If, with a binary tree, we follow the convention of always taking, say, the right branch unless otherwise directed, a path can be represented as a series of distances, between which are implicit left turns.

5k7An enfilade is constructed in this space by grouping crums over regions of the tree (see the attached diagram). Each of these regions has a single entrance and zero or more exits. A crum’s index wid is the set of paths through it to farther siblings. Its index disp is the path to its entrance relative to the entrance to its parent. The index widdative function is path concatenation.

5k8The bottom crums of the historical trace enfilade are transformation matrices for the individual edit operations. These are quite simple. The index wid of a bottom crum is a single step along the historical trace.

5k9In addition to its index wid, each crum also has a data wid. In the case of a bottom crum, this is the primitive transformation matrix that it stores. In the case of an upper crum, the data wid is the matrix product of the data wids of its children. The data wid of a crum is thus the full transformation achieved by traversing the segment of the tree which it covers. This is in turn a poomfilade, constructed using sub-trees which are shared with the historical trace crum’s children’s data wids. The historical trace is thus an enfilade constructed from enfilades! Note that, because of branching in the historical trace tree, a crum may have a number of matrices in its data wid — one for each path across the it. There is a one-to-one correspondence between the matrices in the data wid and the paths in the index wid. The data disp of an historical trace crum is implicitly the matrix product of the data wids of the crum’s siblings along the path between the crum and the entrance to its parent.

5k10A retrieval on the historical trace is accomplished by multiplying together the data disps of the crums descended through on the way to the bottom crum located at a particular point on the history tree. The result is a poom for the orgl that existed at that point in the phylum’s history. In practice it is not necessary to actually multiply whole matrices together, since the object of interest is not the final matrix itself but the mapping which it represents. It is sufficient to simply map whatever V-spans are desired through each of the disp matrices. This is equivalent to multiplying the matrices, but only requires dealing with the particular spans of interest, rather than the whole product orgl.

THE CURRENT IMPLEMENTATION (AS OF APRIL 1, 1984)6c1

6c2The system currently operates in a dedicated single-user mode. Support for multiple users/processes is anticipated as soon as funding permits. Multi-user Xanadu will be implemented as a transaction based system.

6c3The present system supports an older interface paradigm in which orgls are separated into two classes called documents and links. Support for orgls in the sense that they are described in these documents will entail a change to the interface layer but not to the system proper.

6c4The present implementation uses the older spanfilade and poomfilade designs (described above) rather than the newer drexfilade and DIV poom. In addition, as was mentioned earlier, historical trace has not yet been implemented.

6c5Tumblers are currently stored internally using a fixed-size structure, rather than using the variable-length humber representation described here. This results in a substantial storage use inefficiency.

6c6The single-user backend is written in C and runs under the Unix family of operating systems. The code, however, uses a minimum of operating system services and was written with portability in mind, so transfer to other systems is relatively straightforward. Multi-user will by necessity be somewhat more system dependent, but that limitation has not yet arrived.

THE FRONTEND/BACKEND INTERFACE6d1

6d2The Xanadu system makes a strong distinction between the data storage, retrieval and organizational functions and the user interface, display management and data formating functions. The latter are the responsibility of a separate frontend. The frontend is a program that runs as a separate process, possibly on a separate computer, and accesses the capabilities of the backend via some sort of data communications line or I/O channel. The backend implements the functions described in this set of documents in as application independent a fashion as possible.

6d3The backend and the frontend interact via an interface language called Phoebe. This language allows programs to express requests to the backend to perform any of the functions described in these documents. The backend then responds with the requested data, or by performing the requested manipulation and returning an indication of whether or not it was able to do what was asked. The full interface language specification is not yet complete since our conception of the virtuality of the system has recently changed and the interface is being redesigned to take advantage of this. The interface protocol for the older virtuality is the one recognized by the current implementation. This protocol is described in one of the attached documents. Phoebe will be described in detail in a future document5.

THE CORE/DISK MEMORY MODEL6e1

6e2The present design assumes a two-level memory model: the hardware upon which the system is running has a limited quantity of high speed, random access memory which is immediately accessible, which we call core, and a much larger quantity of slower, less immediately accessible memory, called disk. The terms “core” and “disk” are chosen for convenience, and do not necessarily reflect the technology used to realize them.

6e3Core is assumed to be a limited resource, restricted to a relatively small amount (e.g., a few megabytes per active process). Disk is not so constrained, and the model assumes that the amount of disk storage available is effectively unlimited. This is not to say that the system requires an infinite amount of disk space, but merely enough to contain all of the data that it is being asked to manage.

6e4The contents of all of the system’s data structures are stored permanently on disk. As used, they are also moved into core. All reading into core and writing out to disk is under the system’s direct control. Swapping occurs at the data structure level, therefore use of a traditional demand-paged virtual memory system is not advantageous. The general rules for managing core storage are

1. 6e5a1all alterations to data structures must be performed in core,

2. 6e5b1if a crum is in core, then all of its ancestors must also be there,

3. 6e5c1within the above two constraints, try to keep as much material in core as possible.

6e6Core is assumed to be less than totally reliable, in the sense that a system crash may cause any information stored there to be lost. Disk is assumed to be more reliable, and care is taken to ensure that the sequencing of transfers between core and disk preserves the integrity of data stored on disk. This in turn helps ensure that system failures leave the disk in a consistent state so that recovery is possible. The procedure for changing data stored on disk is: first, bring the data into core; second, perform the actual change; third, write a new copy out to disk; and finally, after verifying that what was written to disk was correct, write out to disk some indication that the new copy is now the active one.

6e7The optimum procedure for managing core use in an environment that already has an underlying virtual memory mechanism is unclear. We feel that the Xanadu system itself can anticipate its own storage requirements and decide what to swap and when to swap it better than the algorithms used in typical demand-paged virtual memory systems. In some systems, however, it may not be practical to “turn off” the virtual memory. The best course in such a case is a matter for further study.

Fix the various known bugs in the present system:8c1

8c2There are a few things that are just plain wrong and need to be corrected. In particular: links currently do not follow through to versions; there are some garbage collection glitches, especially when things get complicated; there used to be a persistent off-by-one error deep inside the code which was fixed and several places that worked by compensating for it themselves are now broken. At this time, none of these bugs are serious, in the sense that they interfere with the current capabilities of our demonstration system. They will become more important as work on the system proceeds. We estimate that these will be fixed in the course of debugging the system as a whole.

Modify to use variable-length tumblers:8d1

8d2The current fixed-size representation requires 40 bytes for each and every tumbler used in the system. Conversion to variable length will reduce this considerably. Most tumblers are quite small and in the variable-length format will require as few as 3 bytes. This will tremendously increase disk and memory efficiency. It will also speed things up because the amount of processing that may be performed in-core without swapping to disk will be increased. Also, any given operation on the data structures will have fewer bytes to shuffle. We have devised a plan for making the transition to variable-length tumblers in several independent steps. The first step involves modification of the low-level tumbler routines to handle tumblers in either format. Next, the various higher-level routines get converted one-by-one to use the variable-length format. Once the correctness of these modifications is verified, the fixed-length capabilities are finally removed from the low-level tumbler routines. This is a fairly involved process and may take a couple of man-months.

Install the drexfilade and the DIV poom:8e1

8e2These improved data structures are needed to permit realization of the full virtuality of our design. Fortunately, the higher level routines for N-dimensional enfilades, which the current spanfilade and poomfilade share, can also be used with little or no modification for the drexfilade and DIV poom. The lower level routines, which deal with bottom crums, and the routines which actually use the data structures to respond to requests will, of course, need to be modified. Conversion will be a two step process. The first step involves installing the new data structures and getting the system to work as it did with the old data structures. The second step involves adding the functionality which the new data structures provide that the old did not. These two steps together will probably require several man-months.

Specify and implement the new frontend/backend interface protocol (“Phoebe”):8f1

8f2A new protocol is required to reflect recent important changes in the system virtuality. Before the beginning of this year the notions of document and link were deeply embedded in the system design. In particular, the current frontend/backend interface protocol reflects the restricted functionality provided by documents and links rather than the more generalized functionality provided by unconstrained use of orgls. The recent generalization to orgls somewhat reduces the range of possible requests that the frontend can give to the backend, but the remaining requests become much more complex. In addition, the conversion from the spanfilade to the drexfilade greatly increases the number of different kinds of restrictions that may be applied to retrieval operations.

8f3Specification of a new protocol will involve an in-depth examination of the capabilities of the new virtuality in order to determine a set of requests that provides access to all of the system’s capabilities without undue complication. Once the request set is determined, the format of the requests themselves and the grammar for the interface language will have to be designed.

8f4Implementation of the new protocol will involve the construction of a new input parser for the backend and a nearly complete rewrite of those high-level routines directly responsible for fielding requests.

8f5Both the specification and the implementation will be fairly large undertakings. We estimate a month for specification: a week to get the ideas sorted out, a week to figure out the request set, a week to design the grammar and a week to write it all down. Specification of the interface is a necessary precursor to much frontend work. Implementation will take somewhat longer: a few weeks to code and debug the parser and a month or more to rewrite the request handling routines. Implementation of the new protocol need not follow immediately upon completion of specification.

Optimize code around bottlenecks:8g1

8g2The system was implemented with a greater emphasis placed on things that could be readily made to work with the proper algorithmic efficiency, rather than on things that were efficient at a low level. As a consequence there are some pieces of code that are clear, correct and understandable and horribly slow. Some performance studies need to be done in order to find out where the real bottlenecks are. We have been hampered in conducting such studies by the state of the current release of Unix on our computers, in which the performance analysis and profiling tools do not work correctly. Performance studies have therefore been deferred until a newer release of the operating system software becomes available. The actual work of streamlining our system is an ongoing task. As with any complex system, there is a bottomless list of things that can be done to speed it up.

Implement the historical trace facility and design the protocol to use it:8h1

8h2Historical trace is a separable piece of the system, in the sense that the system will work without it. Implementation was therefore deferred until the rest of the system worked. Historical trace can be accomplished in two stages. In the first stage we build the historical trace tree with the individual reversible edit changes at the bottom of the data structure but without the higher level aggregate matrices. This results in a simple branching edit log allowing retrieval of any version by tracing the individual edits in sequence from the current orgl. This works, albeit very slowly. In the second stage we erect the higher level data structure and speed things up, at the price of greater complication. The first stage, called slow historical trace, is relatively straightforward and can probably be accomplished in a month or two. The second stage, fast historical trace, is a major project and may require several months. Once slow historical trace is in place and the interface protocol is designed to use it, implementation of fast historical trace will be transparent to the user (except that it will be faster, of course). It is likely, however, to be somewhat challenging to implement.

Develop version archiving and “garbage collection” facilities:8i1

8i2Material stored in the xanadu system accretes monotonically. Mechanisms must be developed to identify unreferenced or little used material and reuse the space it occupies while archiving it in some sort of low-cost long-term storage. Mechanisms to allow material to be permanently discarded may also be desirable. In addition, storage and time inefficiencies are introduced by orgl fragmentation as a result of substantial numbers of edit changes. One way of dealing with such fragmentation ist make a “clean copy” of the material in the orgl at some time “t” and then provide an orgl mapping from V to V(t) (the V-stream order at time “t”) in addition to the mapping from V to I. The major unresolved issue is the mechanism for deciding when a “clean copy” of some orgl should be made. Facilities such as these need to be both designed and implemented. For the first pass, we estimate a month to analyze the underlying problems and design solutions. The length of time required to realize the resulting design is unclear, but we guess that it would be on the order of a few months.

Implement multi-dimensional orgls:8j1

8j2In the present design, orgls represent linear (i.e., one-dimensional) collections of atoms. The generalization of the underlying data structures to higher dimensions is straightforward, but the implications of doing this are not clear. Further study is required to determine the desired virtuality for such a system and the protocols for controlling it. We estimate a few months of study and design work, and an unknown (but certainly greater) amount of implementation work.

Implement support for multiple-users:8k1

8k2This is essential. It is also the biggest single task in the list of tasks so far. The implementation of multi-user Xanadu will involve a greater degree of operating system dependence than is found in the present system. Our present notions of how to proceed are based upon 4.2BSD Unix as the anticipated host operating system. Current plans call for multi-user Xanadu to be implemented as a transaction-based system. The idea is to split backend requests into series of the simplest possible primitive transactions which involve in-core data structure operations. These operations don’t involve interaction with disk storage. Disk accesses are handled by Xanadu’s virtual memory manager. A number of host dependent design issues are partially unresolved, and will remain so until the host environment is determined. These include:

• 8k3a1What is the most appropriate memory management scheme for the backend, given the host system’s own underlying memory management? In particular, how do we go about sharing memory between processes?

• 8k3b1What is the most appropriate way to deal with multi-processing in the backend? In particular, should the backend be split into several separate processes, and if so, how?

• 8k3c1The complete mechanisms to handle berts must be designed.

• 8k3d1Access protection and authority control mechanisms must be designed.

8k4Once the complete multi-user system is designed, it must then of course be implemented. We estimate a month to study the host system, two months to design and specify the multi-user backend work, and six months to implement it. However, such time estimates are, at best, educated guesses at this stage.

Various design improvements and corrections:8l1

8l2There are a few things which we would like the system to do that the present design cannot. We have ideas as to how these various problems can be solved, but the ideas need to be refined. For example:

• 8l3a1It cannot distinguish between the “original” of some material and a virtual copy if both the original and the copy are in the same orgl. This problem derives from the fact that virtual copies are made of I-spans, whereas they are referred to externally in terms of V-spans. The DIV Poom was the first step to solving this problem: in the original design, there was no way to distinguish between the original and the copy at all, even if they were in different orgls. The third axis of the DIV poom encodes the orgl of origin of a V-span (as opposed to the orgl of appearance). However, this does not enable us to determine where in that orgl the span came from, since this is potentially variable. Two possible ways of solving this problem are to change the way I-stream space is structured to embody a difference between copies of things, or to somehow dynamically keep track of how the V-stream address of a span shifts over time. Neither of these solutions is very well defined right now.

• 8l3b1The system does not deal with the time dimension of material very well. In particular, we would like to be able to perform restricted retrievals using time as one of the dimensions of restriction. It seems like it would be relatively straightforward to time-stamp orgls as to their time of origin and most recent time of change. Adding time-wids to granfilade crums would also aid in filtering retrievals. As with the previous example. there appear to be things that we can do, but they need much more thought. Dealing effectively with the time dimension is something that we feel will be essential to many applications of the system.

• 8l3c1There is undoubtedly a lot of tuning and refining that can be done to make things more efficient. We do not assume that our architecture is optimum. These tasks are, by their very nature, rather vague and open-ended. Much of the work to be done in this category involves solving unsolved design problems. It is difficult to estimate how long this will take when the result is, by definition, not known. We do, however, have some ideas about how to proceed on some of these problems and feel that they are not insoluble. The design work listed here is perhaps best categorized as “ongoing”.

Memory/CPU Overhead9c1

9c2The current design for a multi-user Xanadu system calls for multiple processes in the backend processor to share a common segment of core memory which will contain the in-core portions of the enfiladic data structures. Modifications to these data structures are permitted only under the umbrella of serializing transactions. Each transaction represents a single primitive operation on the data structures and is executed in an uninterruptable block of computation during which time the other processes are excluded from looking at or themselves modifying the system enfilades. Reading from disk is performed by Xanadu’s underlying virtual memory manager when a process attempts to read a piece of some data structure which is not in core. Writing to disk is also the job of the virtual memory manager, and occurs when unused portions of the data structures are swapped out of core to make room for things being read in or when a process requests the virtual memory system to checkpoint its state.

9c3The data structures required in-core for system operation are the granfilade (including the atoms), its bottom crums date, the spanfilade and some number of poomfilades. However, only certain parts of these data structures need be core-resident at any given time. An operation performed on the data structure reads or modifies certain bottom crums and their ancestors, and only those branches of the trees which are are currently being used need be kept in core.

9c4Enfilades are, in general, said to be logarithmic with the number of data items stored, in terms of both time to perform the various primitive operations and in terms of data structural storage overhead. Like many generalizations, this one is not completely correct. Storage overhead is logarithmic. However, certain multi-dimensional enfilades have non-logarithmic factors in the times required for certain useful retrieve and edit operations. These are discussed in more detail in the companion paper on enfilade theory. The worst case involves a term varying as the square root of a measure of orgl size, but we are not sure of the consequences of such non-logarithmicities in terms of system performance on typical documents. We believe that they are not a significant source of inefficiency.

9c5Our memory management scheme requires that crums in core (i.e., the “active” crums) be accompanied by all their ancestors. The volume of the ancestor crums, as mentioned above, grows as the logarithm of the number of bottom crums in the whole system. Thus, core requirements vary as the product of the number of bottom crums in use with the logarithm of the total number of bottom crums in the corresponding enfilade(s). The amount of disk swapping over time will be directly proportional to the amount of change in the set of active bottom crums, which is effectively constant for a given number of users.

9c6The regularities of enfilades and their associated algorithms invite the design of a memory management system that takes explicit account both of disk blocks and of the (somewhat different) tree-structures in core. Thus, we think that Xanadu’s virtual memory manager can make more astute judgements about what to swap to disk than can a more general page-oriented virtual memory scheme. If Xanadu is installed on a system with such a virtual memory mechanism underneath, then it will need to know how much core it really has to work with. We are not sure how our virtual memory scheme would interact with those of list-oriented systems, since we are not current in our knowledge of list-oriented virtual memory techniques. We will undoubtedly learn about these if we work with such systems to any significant extent.

9c7Subtree sharing is used in multi-versioning orgls so that the common portions of different versions are stored in common. We believe that different versions of a given piece of material will have significant commonality and thus that subtree sharing will substantially reduce memory consumption. The exact degree of savings realized depends on the degree of commonality between versions which in turn depends upon the data being stored and on how the versions differ. Tradeoffs involving subtree sharing can better be studied when a fully operational system is available, since we can then see how people actually use it.

I/O Overhead9d1

9d2The Xanadu system makes use of two types of input/output (I/O). These are disk-block I/O, for data retrieval and long-term storage (via the virtual memory mechanism), and character I/O, for interaction with the frontend.

9d3The frontend/backend interface is designed to minimize backend character I/O. The backend transmits requested data to the frontend in a terse format and does not concern itself with screen management or data display functions, since these typically require substantial computational overhead and I/O bandwidth.

The Current Implementation9e1

9e2Although the present system implementation has the basic algorithmic efficiency described above, it is inefficient in many low-level ways. We believe that, in general, optimization is best left until one has a working system to optimize. Many of the data structures now contain data which is redundant or stored in a wasteful manner. For example, it is common to use a full-word integer — four bytes — to store a one-bit flag. This would be changed in a production system, but makes sense in a development system because it simplifies the code by eliminating the need to twiddle individual bits. This in turn makes it easier to get the system working in the first place. Many data objects which are inherently variable in size are now stored in fixed-size chunks of memory which are typically much larger than required for the average object. For example, all tumblers are now 40 bytes long, but a typical tumbler will only occupy a fraction of this space in a variable-length implementation.

9e3A single C struct is used to represent the upper crums of all three types of enfilades. This struct occupies 220 bytes in core and 164 bytes on disk. For storage on disk, the crums are packed into a struct which represents an entire loaf. The disk loaf struct is 1004 bytes long and contains 6 crums. The packing factor was chosen to enable a loaf to be stored in a single 1024-byte disk block. A crum is read into memory together with its sibling crums, since disk blocks are read as wholes. To read in a bottom crum thus requires up to 6×220=1320 bytes times the depth of the enfilade. This in turn is the base-6 logarithm of the number of bottom crums in the whole enfilade.

9e4Granfilade bottom crums contain either characters or orgls. A character bottom crum may contain up to 800 characters. An orgl bottom crum contains a single orgl pointer. This is in turn a struct which can hold both a core address and a disk address. The disk address is the permanent location of the fullcrum of an orgl on disk. The core address is the location in core of the core-resident fullcrum, if one exists (i.e., if the orgl is in core). The core location is null if the orgl has not been brought in from disk. Although up to 800 characters may be packed into a granfilade character bottom crum, no effort has been made to similarly pack orgl bottom crums. This is another source of inefficiency that can be easily corrected when appropriate.

9e5Spanfilade and poomfilade bottom crums differ little from upper crums, but (like granfilade orgl bottom crums) are not tightly packed when on disk.

Miscellaneous Issues9f1

9f2The present prototype implementation spends a significant fraction of its CPU time in a few low-level routines that perform tumbler comparison and tumbler arithmetic: these account for between 30% and 50% of the system’s total CPU usage. Though simple, these operations are heavily used. Further, they require a procedure call and return each time they are invoked, and involve data types which are not supported by the underlying hardware. These characteristics make the tumbler operations good candidates for implementation in microcode.

9f3Another support function that consumes a lot of computational overhead is storage allocation and free-space management (involving both core and disk space). The present scheme is modeled on Unix’s storage allocation facilities, but was implemented from scratch since the Unix facilities try to gobble up all of the available core in the system and then blow up when they run out of space. The Unix storage allocation mechanism also requires an excessive amount of storage overhead when, as in our system, very large numbers of small pieces (i.e., a few bytes each) are being allocated and freed with great frequency. Our present storage manager is modelled after Unix’s, so it is not an improvement over the Unix storage manager in this respect. There are many possible techniques for dealing with storage allocation that are better adapted to dealing with small pieces. For larger pieces, a scheme using a doubly-indirect index through a table to ease compaction of storage may be most appropriate. This would resemble the system used in Smalltalk-80 (insert reference [“Smalltalk-80: The Language and Its Implementation”, Adele Goldberg and David Robson, ISBN 0-201-11371-6 — Ed.]).

CODING CONVENTIONS11c1

11c2The Xanadu backend is written in C and we try to follow a fairly small set of coding conventions. Identifiers — we use long identifiers for the names of functions and global variables. The purpose of long identifiers, in our estimation, is not merely to avoid the use of cryptic abbreviations but to enable an identifier to contain a complete phrase or sentence fragment describing the thing identified. Por example, a function to retrieve end-sets from the spanfilade would be named retrieveendsetsfromspanfilade in preference to, say, retspanfends. The purpose of this convention is to make the code more self-documenting. Long identifiers are used in preference to descriptive comments at the beginning of each function. There are two reasons for this: first, comments tend not to be updated in the frenzy of debugging and thus the comments and the actual code tend to drift away from each other; second, such comments are tied to the definitions of functions rather than to their use, thus making the purpose of a function call obscure if the function name is obscure.

11c3Unfortunately, the long identifier convention was not followed from the very beginning of implementation, and some older pieces of code contain functions with shorter, less descriptive names. Also, note that we do not use any contextual cues to indicate the separations between words in an identifier, such as underscores (retrieve_endsets_from_spanfilade) or capitalization (retrieveEndsetsFromSpanfilade). The original justification for this was that an identifier is a single unit, not a bunch of separate words. As a practical matter, if we had to do it over again we would probably follow the capitalization-of-interior-words convention. However, we feel that changing the convention in mid-implementation would result in confusion.

11c4Another side-issue is that in standard C in the Unix environment, only the first eight characters of an identifier are significant (and only the first seven for external symbols). To cope with this we use a preprocessor which prepends a unique sequence of characters to any long identifiers which disambiguates them within seven characters. Currently, this preprocessor is used in all the C software we write. Soon we will be converting to 4.2BSD Unix which supports long identifiers directly.

11c5Formating — we use a control-structure formating convention which is popularly called the “one true brace style”. The following examples are illustrative:

if (youdontcutthatout) {
        illtellyourmother();
}

if (itdoesntwork) {
        fix();
} else  if (itworksrealgood) {
        sell();
} else  {
        publish();
}

while (thecatsaway) {
        themicewillplay();
}

for (hesa(); jollygood; fellow()) {
        whicbnobodycandeny();
}

switch (swarlock) {

  case ofdynamite:
        goboom();
        break;

  case ofcoke:
        takea();
        break;

  default:
        thebankloses();
        break;
}

11c7Functions are formated according to the following pattern:

typeofreturneddata
functionname (firstargument, secondargument)
  typeoffirstargument   firstargument;
  typeofsecondargument  secondargument;
{
  typeoffirsttemporaryvariable firsttemporaryvariable;
  typeofsecondtemporaryvariable secondtemporaryvariable;

        bodyoffunction;
}

11c9Another formating convention we often follow is to keep very long lines “as is”, rather than splitting them up. This is partially due to the fact that nobody has been able to agree upon a consistent convention for splitting lines and partially to enable us to unambiguously locate things using “grep”. It does, however, result in some ugliness if the code is displayed or printed on a narrow (i.e., 80 columns or less) device.

11c10Use of types — We follow the practice of defining new data types for any structs that are used. In addition, types are defined for common uses of normal data types such as ints. Most type names begin with “type”, for example:

typedef struct foobarstruct typefoobarstruct;

11c12An historical artifact found in some of the code is that many types are defined using #define rather than typedef. These definitions date back to the initial phases of implementation in BDS C, a CP/M based C dialect which lacks the typedef construct.

11c13Comments — As a rule, we are sparing in our use of comments. It has been our experience that comments and the implementation have a tendency to drift away from each other (as mentioned above). Comments are reserved for explaining things that are difficult to make obvious from the structure of the code itself (i.e., things which can’t be made self-documenting). These are things such as efficiency hacks for optimization, kludges of any kind, obscure debugging fixes, and peculiar data structure use. Comments are also used to block out pieces of code for debugging purposes. If, when debugging, some function is found to require revisions which are either substantial or subtle, it is our practice to “comment out” the offending piece of code, make a copy, and then modify the copy. This enables us to recover the old version if we really mess up the new one. To aid in this, our preprocessor supports recursively nested comments. This enables us to comment out sections of code, which may themselves contain comments, with impunity.

COMMENTARY ON THE PRESENT SYSTEM SOURCE CODE11d1

11d2The present backend consists of slightly over 12,000 lines of C. Most (perhaps 75%) of this bulk is devoted to various support operations such as storage allocation and disk space management. This code is divided into approximately 500 C functions spread over approximately 50 files.

11d3The two versions of the system — We maintain two versions of the backend. One is called xumain and the other is called backend. Backend is the true backend program which interacts with a frontend. Xumain is a standalone version for debugging purposes which prompts the terminal directly for the input that it would ordinarily get from a frontend. The expected format of this input is the same as what a frontend would produce and xumain is therefore considered “user hostile”. We are gradually phasing xumain out as our frontend becomes more functional and sophisticated. Both versions share all of their code except for the very top level (main) and the interface protocol I/O routines.

11d4High-level structure — Both versions have the same structure. The main routine calls some initialization routines and then enters a loop. Inside this loop it repeatedly gets a request from the frontend (or the user terminal in the case of xumain) and processes it. The actual processing is done by a series of semantic routines, one for each request in the interface protocol. The selection of which semantic routine is to be used is determined by a table indexed by request number (the request number is, syntactically, the first thing in any request). Each of the semantic routines has the same basic structure. First, a “get” routine is called which reads and parses the parameters appropriate to the given request (there are two sets of “get” routines, one each for xumain and backend). The “get” routine builds the appropriate data structures to represent the information contained in the request. A “do” routine is then called which performs the actual request. There is also one “do” routine per request. Each of these do routines calls the appropriate high-level enfilade manipulation routines to accomplish the requested action. The “do” routine returns a data structure containing the appropriate information in response to the request. Finally, a “put” routine is called which packages the information in the appropriate format and sends it back to the frontend (as with the “get” routines, there are two sets of “put” routines).

11d5Storage management and virtual memory — The largest portion of the code is devoted to storage allocation and deallocation. We found it necessary to write our own storage allocator because the one Unix provides could not cope with our application. In particular, there is no way to tell when you have run out of space when using the Unix storage routines. We also must manage the allocation of disk space. The present implementation simulates a raw disk by storing everything in a single giant Unix file named “enf.enf”.

11d6The coredisk virtual memory mechanism uses a cyclical garbage collector called the grimreaper. All of the data structures resident in core at any particular time are linked together in a large circular list. Associated with each piece is an age. When something must be swapped out to make room for something being swapped in, grimreaper traverses this list. Things which are sufficiently old are swapped out or discarded (depending upon whether or not they have been altered since they were brought in from disk). Things which are not old enough to be reaped have their ages incremented. Grimreaper continues traversing this list until enough space is freed to meet the present demands.

11d7Another data structure used internally and which is not described elsewhere is typetask7. A task is simply a handle on a linked together collection of allocated temporary core storage associated with some function or task (hence the name) in the system. Temporary storage is allocated to a particular task. When finished with the activity to which the task structure belongs, the entire body of allocated temporary storage can be easily deallocated by traversing the allocation list in the task structure.

11d8Creeping abbreviationism — In spite of our long identifier convention, certain standard abbreviations have crept into some function names. The expansion of these is as follows:

• 11d9a1pm == poomfilade

• 11d9b1sp == spanfilade

• 11d9c1gr == granfilade

• 11d9d1cbc == core bottom crum

• 11d9e1cuc == core upper crum

• 11d9f1dbc == disk bottom crum

• 11d9g1duc == disk upper crum

• 11d9h1nd == n-dimensional enfilade (e.g. , the poomfilade or spanfilade)

• 11d9i1seq == sequential enfilade (e.g . , the granfilade)

• 11d9j1dsp == disp

• 11d9k1vsa == v-stream address

• 11d9l1isa == i-stream address

11d10Other dangling cruft — The present code contains a lot of ugliness due to debugging efforts. Often, pieces of code are commented out which are duplicate versions of troublesome routines. In addition, there are diagnostic print statements and calls to data structure dumping routines that clutter many places. These may sometimes obscure the true purpose of the code they are found in, especially if they are heavily used. There is also a whole file full of diagnostic routines which test various functions and allow complicated data structures to be dumped to the screen or to a file in a readable format. The routines are useful and important but add to the bulk of the code.