Threaded code

Not to be confused with multi-threaded programming.

In computer science, the term threaded code refers to a compiler implementation technique where the generated code has a form that essentially consists entirely of calls to subroutines. The code may be processed by an interpreter, or may simply be a sequence of machine code call instructions.

Threaded code has better code density than code generated by alternative code generation techniques and alternative calling conventions, sometimes at the expense of slightly slower execution speed. However, a program small enough to fit fully in a computer processor's cache may run faster than a larger program that suffers many cache misses.^[1]

Threaded code is best known as the implementation technique commonly used in some programming languages, such as Forth, many implementations of BASIC, some implementations of COBOL, early versions of B,^[2] and other languages for small minicomputers and amateur radio satellites.

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, which 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 of the first Apple II computers had only 4 KB 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".

Development

To save space, programmers squeezed the lists of subroutine calls into simple lists of subroutine addresses, and used a small loop to call each subroutine in turn. For example:

start:
  ip = &thread
top:
  jump *ip++
thread:
  &pushA
  &pushB
  &add
  ...
pushA:
  *sp++ = A
  jump top
pushB:
  *sp++ = B
  jump top
add:
  *sp++ = *--sp + *--sp
  jump top

In this case, decoding the bytecodes is performed once, during program compilation or program load, so it is not repeated each time an instruction is executed. This can save much time and space when decode and dispatch overhead is large compared to the execution cost.

Note, however, addresses in thread for &pushA, &pushB, etc., are two or more bytes, compared to one byte, typically, for the decode and dispatch interpreter described above. In general, instructions for a decode and dispatch interpreter may be any size. For example, a decode and dispatch interpreter to simulate an Intel Pentium decodes instructions that range from 1 to 16 bytes. However, bytecoded systems typically choose 1-byte codes for the most-common operations. Thus, the thread often has a higher space cost than bytecodes. In most uses, the reduction in decode cost outweighs the increase in space cost.

Note also that while bytecodes are nominally machine-independent, the format and value of the pointers in threads generally depend on the target machine which is executing the interpreter. Thus, an interpreter might load a portable bytecode program, decode the bytecodes to generate platform-dependent threaded code, then execute threaded code without further reference to the bytecodes.

The loop is simple, so is duplicated in each handler, removing jump top from the list of machine instructions needed to execute each interpreter instruction. For example:

start:
  ip = &thread
  jump *ip++
thread:
  &pushA
  &pushB
  &add
  ...
pushA:
  *sp++ = A
  jump *ip++
pushB:
  *sp++ = B
  jump *ip++
add:
  *sp++ = *--sp + *--sp
  jump *ip++

This is called direct threaded code (DTC). Although the technique is older, the first widely circulated use of the term "threaded code" is probably Bell's article "Threaded Code" from 1973.^[3]

Charles H. Moore invented a more compact notation in 1970 for his Forth virtual machine: indirect threaded code (ITC). Originally, Moore invented this because it was easy and fast on Nova minicomputers, which have an indirection bit in every address. He said (in published remarks, Byte Magazine's Forth Issue) that he found it so convenient that he propagated it into all later Forth designs.

Some Forth compilers compile Forth programs into direct-threaded code, while others make indirect-threaded code. The programs act the same either way.

Threading models

Practically all executable threaded code uses one or another of these methods for invoking subroutines (each method is called a "threading model").

Direct threading

Addresses in the thread are the addresses of machine language. This form is simple, but may have overheads because the thread consists only of machine addresses, so all further parameters must be loaded indirectly from memory. Some Forth systems produce direct-threaded code. On many machines direct-threading is faster than subroutine threading (see reference below).

An example of a stack machine might execute the sequence "push A, push B, add". That might be translated to the following thread and routines, where ip is initialized to the address &thread.

thread:
  &pushA
  &pushB
  &add
  ...
pushA:
  *sp++ = A
  jump *ip++
pushB:
  *sp++ = B
  jump *ip++
add:
  addend = *--sp
  *--sp = *sp + addend
  jump *ip++

Alternatively, operands may be included in the thread. This can remove some indirection needed above, but makes the thread larger:

thread:
  &push
  &A
  &push
  &B
  &add
push:
  *sp++ = *ip++
  jump *ip++
add:
  addend = *--sp
  *--sp = *sp + addend
  jump *ip++

Indirect threading

Indirect threading uses pointers to locations that in turn point to machine code. The indirect pointer may be followed by operands which are stored in the indirect "block" rather than storing them repeatedly in the thread. Thus, indirect code is often more compact than direct-threaded code, but the indirection also typically makes it slower, though still usually faster than bytecode interpreters. Where the handler operands include both values and types, the space savings over direct-threaded code may be significant. Older FORTH systems typically produce indirect-threaded code.

For example, if the goal is to execute "push A, push B, add", the following might be used. Here, ip is initialized to address &thread, each code fragment (push, add) is found by double-indirecting through ip; and operands to each code fragment are found in the first-level indirection following the address of the fragment.

thread:
  &i_pushA
  &i_pushB
  &i_add
i_pushA:
  &push
  &A
i_pushB:
  &push
  &B
i_add:
  &add
push:
  *sp++ = *(*ip + 1)
  jump *(*ip++)
add:
  addend = *--sp
  *--sp = *sp + addend
  jump *(*ip++)

Subroutine threading

So-called "subroutine-threaded code" (also "call-threaded code") consists of a series of machine-language "call" instructions (or addresses of functions to "call", as opposed to direct threading's use of "jump"). Early compilers for ALGOL, Fortran, Cobol and some Forth systems often produced subroutine-threaded code. The code in many of these systems operated on a last-in-first-out (LIFO) stack of operands, which had well-developed compiler theory. Most modern processors have special hardware support for subroutine "call" and "return" instructions, so the overhead of one extra machine instruction per dispatch is somewhat diminished. Anton Ertl has stated "that, in contrast to popular myths, subroutine threading is usually slower than direct threading."^[4] However, Ertl's most recent tests^[1] show that subroutine threading is faster than direct threading in 15 out of 25 test cases. Ertl's most recent tests show that direct threading is the fastest threading model on Xeon, Opteron, and Athlon processors; indirect threading is the fastest threading model on Pentium M processors; and subroutine threading is the fastest threading model on Pentium 4, Pentium III, and PPC processors.

As an example of call threading "push A, push B, add":

thread:
  call pushA
  call pushB
  call add
  ret
pushA:
  *sp++ = A
  ret
pushB:
  *sp++ = B
  ret
add:
  addend = *--sp
  *sp = *sp + addend
  ret

Token threading

Token threaded code uses lists of 8 or 12-bit indexes to a table of pointers. Token threaded code is notably compact, without much special effort by a programmer. It is usually half to three-fourths the size of other threaded-codes, which are themselves a quarter to an eighth the size of compiled code. The table's pointers can either be indirect or direct. Some Forth compilers produce token threaded code. Some programmers consider the "p-code" generated by some Pascal compilers, as well as the bytecodes used by .NET, Java, BASIC and some C compilers, to be token-threading.

A common approach historically is bytecode, which uses 8-bit opcodes and, often, a stack-based virtual machine. A typical interpreter is known as a "decode and dispatch interpreter", and follows the form

bytecode:
  0 /*pushA*/
  1 /*pushB*/
  2 /*add*/
top:
  i = decode(vpc++)
  addr = table[i]
  jump *addr
pushA:
  *sp++ = A
  jump top
pushB:
  *sp++ = B
  jump top
add:
  addend = *--sp
  *sp = *sp + addend
  jump top

If the virtual machine uses only byte-size instructions, decode() is simply a fetch from bytecode, but often there are commonly used 1-byte instructions plus some less-common multibyte instructions, in which case decode() is more complex. The decoding of single byte opcodes can be very simply and efficiently handled by a branch table using the opcode directly as an index.

For instructions where the individual operations are simple, such as "push" and "add", the overhead involved in deciding what to execute is larger than the cost of actually executing it, so such interpreters are often much slower than machine code. However, for more complex ("compound") instructions, the overhead percentage is proportionally less significant.

Huffman threading

Huffman threaded code consists of lists of tokens stored as Huffman codes. A Huffman code is a variable length bit string used to identify a unique token. A Huffman-threaded interpreter locates subroutines using an index table or tree of pointers that can be navigated by the Huffman code. Huffman threaded code is one of the most compact representations known for a computer program. Basically the index and codes are organized by measuring the frequency that each subroutine occurs in the code. Frequent calls are given the shortest codes. Operations with approximately equal frequencies are given codes with nearly equal bit-lengths. Most Huffman-threaded systems have been implemented as direct-threaded Forth systems, and used to pack large amounts of slow-running code into small, cheap microcontrollers. Most published^[5] uses have been in smart cards, toys, calculators, and watches. The bit-oriented tokenized code used in PBASIC can be seen as a kind of Huffman threaded code.

Lesser-used threading

An example is string threading, in which operations are identified by strings, usually looked-up by a hash table. This was used in Charles H. Moore's earliest Forth implementations and in the University of Illinois's experimental hardware-interpreted computer language. It is also used in Bashforth.

Branches

Examples above show no branches. For all interpreters, a branch changes the thread pointer (ip above). As example, a conditional branch when the top-of-stack value is zero might be encoded as follows. Note that &thread[123] is the location to jump to, not the address of a handler, and so must be skipped (ip++) whether or not the branch is taken.

thread:
  ...
  &brz
  &thread[123]
  ...
brz:
  tmp = *ip++
  if (*sp++ == 0)
    ip = tmp
  jump *ip++

Common amenities

Separating the data and return stacks in a machine eliminates a great deal of stack management code, substantially reducing the size of the threaded code. The dual-stack principle was originated three times independently: for Burroughs large systems, Forth and PostScript, and is used in some Java virtual machines.

Three registers are often present in a threaded virtual machine. Another one exists for passing data between subroutines ('words'). These are:

ip or i (instruction pointer) of the virtual machine (not to be confused with the program counter of the underlying hardware implementing the VM)
w (work pointer)
rp or r (return stack pointer)
sp or s (parameter stack pointer for passing parameters between words)

Often, threaded virtual machines such as implementations of Forth have a simple virtual machine at heart, consisting of three primitives. Those are:

nest, also called docol
unnest, or semi_s (;s)
next

In an indirect-threaded virtual machine, the one given here, the operations are:

next:
  *ip++ -> w
  jump **w++
nest:
  ip -> *rp++
  w -> ip
  next
unnest:
  *--rp -> ip
  next

This is perhaps the simplest and fastest interpreter or virtual machine.

References

1 2 "Speed of various interpreter dispatch techniques V2".
↑ Dennis M. Ritchie. "The Development of the C Language". 1993. quote: "The B compiler on the PDP-7 did not generate machine instructions, but instead 'threaded code' ..."
↑ Bell, James R. (1973). "Threaded code". Communications of the ACM 16 (6): 370–372. doi:10.1145/362248.362270.
↑ Ertl, Anton. "What is Threaded Code?".
↑ Latendresse, Mario; Feeley, Marc. "Generation of Fast Interpreters for Huffman-Compressed Bytecode". Elsevier. CiteSeerX: 10.1.1.156.2546.