What exactly is/was threaded p-code?

Question

Quickbasic 4.0 added threaded p-code which at the time I remember thinking was magical. But I have no idea what it means. What exactly is/was threaded p-code (and is the p actually the Greek letter rho)?

Answer 1

You're in luck: Byte November 1987 introduces QuickBASIC 4.0 and has a feature on it, with a special box out specifically about threaded p-code which I've included below.

'p-code' is a letter P. I've found two articles by Steve Gibson that say it stands for pseudo-code (second), but Wikipedia claims it's 'Portable'. I looked through the MS QB 4.5 manual to see what they use and it doesn't mention it at all.

In something like Sinclair BASIC, the BASIC interpreter reads each token and acts on it in turn individually, with an implementation for each command or operator.

Threaded p-code is partially compiled BASIC (or Pascal, etc.) source code where lines are compiled into machine code chunks called 'executors', where the compiler embeds the connections between executors in the machine code itself. This step is faster than full compilation but allows some optimisations to take place (within expressions, for example (I think)), and also keeps enough of the program structure to allow breaking into the program and altering it quickly mid-execution. When you make the final EXE, it's fully compiled to machine code, not threaded p-code.

I believe it's somewhat analogous to compiling C code with no optimisation, with enough information for a debugger to step execution corresponding to the lines of the original source file, even though the source isn't rendered exactly in the executable.

The Threaded P-Code Interpreter

Two key ideas make QuickBASIC 4.0's threaded p-code interpreter workable: precompilation of BASIC source code lines into code that you can execute but still display and edit at the source level, and an efficient way to run this code.

Here's how QuickBASIC 4.0 uses these ideas:

First, QuickBASIC 4.0 precompiles each line of BASIC source code into a form that is 90 percent executable machine code, housekeeping code being the remaining 10 percent of the precompiled code. This code is called Parsed in the Microsoft hierarchy. Parsed code can be edited but contains no symbol information about the program's variables.

At this point in the program creation process, you can run the entered program. When you invoke the Start option, the interpreter changes the state of the code to Symbolic by adding a symbol table for variables. Immediately upon completion of the change to Symbolic code, QuickBASIC 4.0 changes the code state again, this time to what Microsoft calls the Threaded state. This state change adds type-checking code, binds procedure calls and control structures to actual memory locations, links COMMON data, and generates code and addresses for executors, the actual machine code fragments that perform operations like PRINT or * (multiply).

Now, QuickBASIC 4.0 can execute the code by jumping from executor address to executor address. The p-code interpreter consists of two lines of assembly language code:

LODSW ES

JMP AX

These two lines are appended to each BASIC operation's machine code fragment during the Threaded state change.

The interpreter code does just two things: First, LODSW ES simply loads the microprocessor's AX register with the address of the next executor in the code; JMP AX merely jumps to the address in AX, the next executor, and executes its code, whereupon it encounters another LODSW ES, JMP AX instruction pair that sends it on to another executor. In this way, the code fragments are threaded together, executing in a sequence determine by how they were entered and parsed.

The threaded p-code interpreter actually becomes part of the executing program. Because the interpreted execution of the program is part of the program, you can stop a program in the middle of its execution, change parts of the code and then resume execution. QuickBASIC 4.0 recompiles only the executor code that you changed and alters only the symbol table information affected by your changes.

The process of converting code from Parsed to Symbolic to Threaded happens at the rate of 60,000 lines per minute. When you stop and alter a running program, QuickBASIC 4.0 has to change the program's state from Threaded back to Symbolic to let the editor take over the microprocessor. This process happens at a rate of 150,000 lines per minute.

When you finally complete and debug your program, you can save it to disk as an executable file using QuickBASIC 4.0's Make .EXE option. Here, QuickBASIC 4.0 acts like a normal compiler. All the interpreter operation codes are discarded, and the compiler produces just executable machine code and symbol information.

The interpreter technology in QuickBASIC 4.0 is likely to appear in other products, according to a Microsoft spokesman, including language and application products.

Answer 2

What exactly is/was threaded p-code?

P-Code is Pseudo-Code

P-Code stands for Pseudo Code, as in code for a Pseudo-CPU. In contrast to code for a real CPU, as in Z80-Code or x86-Code. Like there are many different ways a CPU can be designed, there are as well many different types of P-Code. Some, like the UCSD-P-machine are rather close in design to more standard 16 bit CPU designs, others, like the one used by Quick BASIC, follow closely a target language.

Nowadays the equivalent term Byte-Code is more popular - made so by SUN to have their Java look all new. Likewise one would often call the interpreter executing this byte code a virtual machine instead.

P-Code is for Interpreters

Since there is no real CPU executing that code, an interpreter will be needed. It picks the next instruction to be performed, look up (find) the (real) code piece that will perform whatever that instruction asks for and loops back to repeat ad infinite.

Threading is for P-Code

An interpreter fetching instructions and looking them up before execution is an active component. As such it needs as well execution time to perform, slowing over all performance ... like all management does :))

One way to get rid of (most) management, beside just in time compilation, which wasn't a thing back then, is Threaded (P-)Code(*1). Here the to be interpreted code isn't represented by some arbitrary virtual OP-Code, but the direct address of the routine executing whatever the actual instruction needs. Essentially all threaded instructions form a back to back chain without any additional linking - much like a classic children Daisy-Chain.

Doing so most if not all of the core interpreter loop can be spared, minimizing the time spend for function calling/chaining. There are essentially two ways of doing so:

1. A minimal loop just fetching the next instruction's function address and jumping there to perform, which in turn are coded as regular subroutines, or
2. No loop, but each instruction fetching the address of the next one in sequence and jumping there.

While the later is the optimum version regarding performance, as each routine simply ends with an indirect jump, the first has that not only each function can still be used from other places as subroutine, but also debug code and over all management can be still added when needed. Doing so with variant#2 will bloat up each functions code, thus slowing it eventually more down that keeping the minimal loop of version#1 does.

Quick-BASIC is a threaded interpreter of the second kind.

In today's lingo Threaded P-Code is usually just called Threaded-Code.

Threading Isn't New At All

Threading is a well known technique since early days of programming. And while maybe not the first, Forth is since the 1970s the poster child of lightening fast execution of non native code, not at least due the use of threaded code.

Threading is Depending

It should not be ignored that switching from basic P-Code, that is using predefined OP-Codes, to threaded code is done at a cost: The code to be interpreted is now subject to version dependence, as it contains fixed addresses pointing into the interpreter runtime. Any new version would need to keep them constant(*2), relocate them according to version, or is simply unable to execute older programs, resulting in having multiple runtimes installed.

---

Addition from a comment by the OP

What is the relationship between this use of the term "threaded" and the modern one that refers to code you can run on multiple cores efficiently?

No, these two uses are complete unrelated.

• Threaded in case of interpreter code means that the instructions of a program are chained - forming a thread - for execution, while

• Threaded in case of parallel execution means that multiple execution paths happen simultaneous within the same code - like threads coexisting side by side in the same embroidery.

The only elation is that for both the same figure of speech was used. Much like thread is as well used to name a series of linked comments when it comes to social media. As well unrelated to either, but a good help to imagine.

---

*1 - Threaded code is always P-Code, as with native code it would be just program execution (via jumps/calls).

*2 - Which could be done by adding fixed entry points, thus turning threading into a third variant intermediate of a have the cake and eat it, by still eliminating the loop but using a table of secondary jumps that could not only be kept stable over several versions, but as well allow to hook debug functionality. Of course at cost of at least another Jump instruction.