Threaded Code - Preparatory History

Preparatory History

The common way to make computer programs is to 'translate' a computer program written in some symbolic language to machine code using a compiler. The code is typically fast but nonportable since the binary code is designed for a specific computer hardware platform. A different approach uses a virtual machine instruction set — that has no particular target hardware. An interpreter executes it on each new target hardware.

Early computers had relatively little memory. For example, most Data General Nova, IBM 1130, and many Apple II computers had only 4 K words of RAM installed. Consequently a lot of time was spent trying to find ways to reduce the size of programs so they would fit in the memory available. At the same time, computers were relatively slow, so simple interpretation was very noticeably slower than executing machine code.

Instead of writing out every step of an operation in every part of the program where it was needed, programmers saved memory by writing each step of such operations once (see "Don't repeat yourself") and placing it in a subroutine.

This process — code refactoring — is used today, although for different reasons. The top-level application in these programs may consist of nothing but subroutine calls. Many of these subroutines, in turn, also consist of nothing but lower level subroutine calls.

Mainframes and some early microprocessors such as the RCA 1802 required several instructions to call a subroutine. In the top-level application and in many subroutines, that sequence is constantly repeated, only the subroutine address changing from one call to the next. Using memory to store the same instructions repeatedly is wasteful.

To save space, programmers squeezed that series of subroutine calls into a list containing only contiguous addresses of the sub-routines, and used a tiny "interpreter" to call each subroutine in turn.

This is identical to the way other programmers squeezed a series of jumps in a branch table, dispatch table, or virtual method table into a list containing only the destination addresses, and used a small selector to branch to the selected destination. In threaded code and these other techniques, the program becomes a list of entry points to the actual code to be executed.

Over the years, programmers have created many variations on that "interpreter" or "small selector". The particular address in the list of addresses may be extracted using an index, general purpose register or pointer. The addresses may be direct or indirect, contiguous or non-contiguous (linked by pointers), relative or absolute, resolved at compile time or dynamically built. No one variation is "best".