Often we have a function of several inputs that we must frequently compute. Sometimes it is possible to divide the inputs into two categories, rapidly varying, and slowly varying. We will call them here the fast and slow inputs. Symbolically we must frequently evaluate g(f, s). It may be possible to find intermediate adapted data that depends on the slow inputs and that together with the fast input can be used to compute the original function quicker than starting from the slow inputs. In such cases it is necessary to keep the adapted data current.

Related Ideas

This is closely related to a circuit design principle used when computing a logical function of several inputs and some are available earlier than others. If I want to compute A∨B∨C and the value of C is a few pico second delayed, then compute A∨B during the wait. This saves time, not computation.

Modern computers typically have a memory map and a Translation Lookaside Buffer that in a few levels of logic translates virtual addresses into physical addresses. The memory map in RAM is the ultimate authority but the TLB holds adapted data to usually translate quicker. Change notification is required from the software that builds and updates the slowly varying memory map from which the TLB information is derived. There are many good programming tricks to be learned from the detailed hardware designs of TLB’s.

The caches for computer RAM and web caches duplicate data close to the user. Web caches are typically lax about ensuring currency.

Memoizing can be done automatically. It requires comparing argument values for each evaluation, a cost that may be avoided when change notification can be arranged. Memo functions in languages and scratchpad functions in database contexts are related ideas, I think. I have in mind more custom designs.

Partial Evaluation is another general technique. In computer science partial evaluation is usually presumed to occur before compilation. Partial evaluation is a generalization of constant folding, an old compiler optimization where sub-expresions such as “3+2” are replaced by 5 and the add instruction is omitted. In 1951 Alfred Tarski used a technique equivalent to partial evaluation in providing A Decision Method for Elementary Algebra and Geometry.

This idea is very near to adaptive formats where the same space is formatted according to recent use. The two ideas are closely connected in kernel code.

Adapted Data

Symbolically we want to find functions A and G so that
g(f, s) = G(f, A(s)).
To be useful G must be quicker to compute than g and the values of A must be economical to store. A(s) is the adapted form of s. It is also necessary to arrange for notification of changes to s so that stale values of A(s) can be expunged. We will generally assume code arrangement so that a time cluster of changes to s do not cause recomputations of A(s) until G is again evaluated. Our practice in the kernel typically requires having to recompute only part of A(s) when changing part of s. TLB hardware conforms to all of these principles. Indeed “Look Aside Data” might well serve in place of “Adapted Data”.

The Keykos kernel goes further and modifies node state indirectly by modifying adapted data. This is a bit like a store into cache, but of course the data formats are different.

Application

One significant application of this pattern is in symmetric crypto where the slowly varying input is the secret crypto key and the rapidly varying input is the plain text, or cipher text. Key preparation produces a data structure larger than the key, but derived only from the key, that makes encryption or decryption much quicker.

The real reason for this note is to introduce several instances of adapted data that are employed in the Keykos kernel. The slowly changing data structures are in each case a network of nodes connected together with keys. Three such structures are the three main primitive kernel objects, domains, segments and meters. For meters and domains, program actions are not only effected indirectly by node state, but also such actions effect node state.

It is first necessary to understand special tricks for handling keys. Keys may be prepared if they designate an object. This logic is otherwise oblivious to the meaning of the key. Depending on what sort of kernel implemented object some key helps to define, a key may be involved.

Meters are much more efficient than their external specs suggest.
Domains are adapted for quick starts and stops.
The prepared segment is the most complex of the data adaptations.