Go to the first, previous, next, last section, table of contents.


Muq Object Efficiency Considerations

Objects viewed a collections of named properties constitute one of the central Muq metaphors. In slightly mathematical terms, a Muq object implements an enumerated function: Given a key, it returns the corresponding value. I have tried to make this functionality as general as efficiently practical, by allowing use of arbitrary Muq data items as both keys and values.

Since objects and their properties are likely to dominate both the space and time efficiency of many Muq computations, I have attempted to make them reasonably efficient on both dimensions.

Since it is my understanding that human factors studies have shown that users prefer predictable to erratic response times, even at the cost of somewhat higher average response time if need be, I have tried to avoid algorithms which buy good performance for many cases at the cost of catastrophically bad performance for other cases.

Muq properties are implemented internally via a two-tiered mechanism in which built-in properties for a given class are stored in statically allocated slots within the object record itself (this avoids storing the property name for these properties on each object, and also allows C code to access these values via fast C pointer/structure operations) while user-defined properties are stored in separate propdir trees.

In the interests of presenting a simple, consistent programming model, these two classes of properties are, as far as practical, merged into a single set as far as the muf programmer is concerned. The difference emerges now and then, however: For example, built-in properties cannot be deleted from an object.

Niklaus Wirth has observed that, while binary trees are often not the top performer by a given measure, they are usually in the top three. In particular, they tend not to have catastrophically bad worst cases.

After studying the problem awhile, I concluded that array-based solutions such as hashtables are inappropriate due to abuse of the virtual memory subsystem: fetching one property from a hashtable holding a million or so can require reading in an arbitrarily large array, for example, yielding an arbitrarily bad worst case. Similarly, large-fanout trees suffer from needlessly slow lookup times when the tree fits entirely in memory. Finally, most trees suffer from the problem of excessive space wasted in null pointers: the typical binary tree has half its pointer field empty at any given time, which is not good if they are dominating our diskspace usage.

The Muq solution is a hybrid 2-3 tree with fat leaves containing approximately 6-12 key/val pairs. This has the following advantages:

The take-home lessons for the muf programmer are:

Note: In retrospect, I believe the 2-3 tree component was a mistake due to an analytical hallucination; A future release is likely to switch to more conventional B-trees.


Go to the first, previous, next, last section, table of contents.