Adaptive Formats

This is an optimization idea that I want to record here for it is very old and simple, but many programmers are unaware of it. I have seen it applied in several fields.

I became aware of the idea when I heard the details of a machine simulator for the IBM 650 that ran on the IBM 704. The year was about 1957.

The 650 had 2000 words of memory; each comprised a one bit sign and 10 decimal digits. An instruction occupied a word formatted as CC AAAA BBBB, with a two digit op code, and two four digit addresses. An address was less than 2000. A 650 numeric operand was merely 10 decimal digits with a sign. The 704 was a binary machine with 36 bit words which included a sign. It was convenient and fast for 650 instructions to be held, one per 704 word as 7 bits for op code and 11 bits each for address; 29 bits all together. For data operands, however, it was fast and convenient to represent the 650 value in binary, the 704’s native radix. 34 bits plus a sign would suffice for this.

Neither the 650 nor the 704 were “Harvard” architectures which meant that the distinction between program and data was made only dynamically as the program ran. Thus how was one to decide how to code an individual 650 word? The insight was to decide dynamically. The sign of each 704 word indicated which format was in use for that word. As the simulator interpreted instructions it was necessary to test the sign each time. Likewise for accessing the simulated data. Early 650s had no index registers and it was common for a 650 program to modify addresses in itself. Simulation of some or the 650 instructions that were typically used for such modification tolerated the instruction format of their operands.

When such format conformance tests failed it was necessary to first convert the operand in the word to the other format before proceeding. Converting instruction format to data format was simple arithmetic. Converting the other way raised the question of what if one of the addresses fields exceeded the size of memory. The instruction format adopted by the simulator would not hold such an address. That was OK for then the simulation would report the same sort of error that the 650 hardware would have reported—invalid address.

The Keykos kernel uses a generalization of this scheme heavily. There are several uses that a capability may be put to such as designating a segment of memory, a place to send a message (gate), or a place to store other capabilities. A field in the storage place for a key (slot) coded the present format for the key. Particular bits in the key slot indicated that some of the information necessary to define the capability was stored outside the capability’s slot. In such cases an ordinary pointer within the slot would locate such data. This was a principled exception to the generally good DRY rule. When a capability is stored on disk it is always in its canonical form, and is the only copy of that information, modulo redundant (RAID like) disks.