A debugger is a wonderful tool for understanding what actually happens in a piece of code. Donald Knuth’s coding in TAOCP is archaic enough that I do not understand it just by reading through. This is due to a combination of my unfamiliarity with MIXAL, as well as some of the coding conventions he’s chosen. So, I’m going to step through the MIXAL code in mixvm, and annotate what I find.
To initiate the run:
$ mixvm insertion.mix Program loaded. Start address: 3000 MIX> strace on MIX> next 3000: [OUT 0,0(2:3) ] START OUT INPUT(TERM) ZZZZZYYYYYXXXXXWWWWWVVVVVUUUUUTTTTTSSSSSRRRRRQQQQQPPPPPOOOOONNNNN Elapsed time: 1 /Total program time: 1 (Total uptime: 1) MIX> next 3001: [OUT 14,0(2:3) ] OUT INPUT+14(TERM) MMMMMLLLLLKKKKKJJJJJIIIIIHHHHHGGGGGFFFFFEEEEEDDDDDCCCCCBBBBBAAAAA Elapsed time: 1 /Total program time: 2 (Total uptime: 2) |
This skips over the lines that perform the output of the buffer in its pre-sorted state. Lets look at the first line of code from the sort example:
MIX> next 3002: [ENT1 -24,0 ] ENT1 2-N MIX> preg I1 rI1: - 00 24 (0024) MIX> psym N + 00 00 00 00 26 (0000000026) |
This line has the compiler perform the math 2-N and stores the value in Register I1. This is the number negative 24. Knuth’s convention is to use negative indexes, and then to check that they are no longer negative to end loop. We should see this check later on.
MIX> next 3003: [LDA 26,1 ] 2H LDA INPUT+N,1 MIX> preg A rA: + 28 28 28 28 28 (0477218588) |
Before we pull apart the command, lets see how Knuth describes commands in general.
To discuss instructions in a readable manner, we will use the notation
OP Address,I(F)
to denote an instruction…Here OP is a symbolic name given to the operation code (the C part) of the instructhin; ADDRESS is the +AA portion I and F represent the – and F fields, respectively.
TAOCP Vol 1. Page 126
So, for our command above, the OP is LDA, the Address is INPUTE+N, and the I value is 1. There is no explicit F value specified.
LDA is the command to Load the accumulator. From the Text:
LDA (load A), C = 8, F = field
The specified field of CONTENTS(M) replaces the previous contents of Register A…. If F is the normal field specific (0:5) everything in location M is copied into rA.
TAOCP Vol 1, Page 128
What about the 1 in the I field?
If I=0, the address +/-AA is used without change; otherwise I should contain a number between 1 and 6, and the contents of in register Ii are added to the address.
TAOCP Vol 1. Page 126
So the address we want to load into the accumulator is calculated by adding INPUT+N, and then adding the value of Index Register 1, which we calculated in the previous operation as 2-N.
INPUT + N + 2 – N
This might be the most convoluted way to say INPUT+2. WHy is it so complicated? Note the 2H before the operator. This line is going to be a target for a jump operation later on, and will be used in a loop. Thus, we should expect to see the I1 register get incremented later on. On line 11 and 12 of the original version:
INC1 1
J1NP 2B |
The value in the Accumulator is now 28 28 28 28 28.
Code 01-29 are for the letters A through Z with a few Greek letters thrown in.
TAOCP Vol 1 Page 136
This is the MIX representation for the Latin character stored ad INPUT + 2. The way I set up the sample data means this should be the second element in the Array, or the repeated character ‘Y’. The Value a INPUT + 1 should be ZZZZZ. We can inspect with PMEM
INPUT+26 should be the Letter A.
MIX> psym INPUT + 00 00 00 00 00 (0000000000) MIX> pmem 0 0000: + 00 00 00 00 00 (0000000000) MIX> pmem 1 0001: + 29 29 29 29 29 (0494262109) MIX> pmem 2 0002: + 28 28 28 28 28 (0477218588) MIX> pmem 26 0026: + 01 01 01 01 01 (0017043521) |
Now that we have a good idea of what has happened thus far, lets move on to the next command.
MIX> next 3004: [ENT2 25,1 ] ENT2 N-1,1 MIX> preg I2 rI2: + 00 01 (0001) MIX> preg I1 rI1: - 00 24 (0024) |
Looking at the original code, we can see this was originally written as.
ENT2 N-1,1 |
Address transfer operators. In the following operations, the (possibly indexed) “address” M is used as a signed number, not as the address of a cell in memory.
> ENT A (enter A)….The quantity M is loaded into rA…If M = 0, the sign of the instruction is loaded….
“ENT 0,1” sets rA to the current contents of index register 1, except that -0 is changed to +0.
TAOCP Vol 1. P 133
The OP code ENT2 means to ENTER the value from the value passed in M, which is 1 in this case. What is the the ,1 at the end doing? rI1 is set to 24, and that seems to have no impact on the eventual value of 1 assigned to rI2.
The MIXAL Docs do not shed any light on this mystery.
If I understand the intention of the approach, M should = N-1 (25) plus the value of rI1 (-24). This is, in fact, 1 as we have seen. Thus, we can expect to use the value of rI2 as one of the two index counters (i,j) from the algorithm. If rI1 is analogous to j (2) then rI2 is i (which starts the loop as j-1. We’ll have to see on additional steps if this is the case. The next two operations are a comparison and a jump. I executed three commands to see the result of the jump command.
MIX> next 3005: [CMPA 0,2 ] 3H CMPA INPUT,2 MIX> next 3006: [JGE 3011,0 ] JGE 5F MIX> next 3007: [LDX 0,2 ] 4H LDX INPUT,2 |
Lets start with the CMPA command.
CMPA (compare A) The specified field of rA is compared with the same field of CONTENTS(M).
TAOCP Vol 1. P 134
Again, we have a modifying value specified in the I field: 2. I take that to mean that the value of the accumulator register is compared with the memory location INPUT+I2. The comparison field is set to EQUAL and the JGE operation should not induce a jump. Thus we end on the line labeled 4H. This line was entered as:
4H LDX INPUT,2 |
We are thus loading in the value at INPUT + i into the X register. This is the start of the sequence annotated as S4. Move Ri decrease i.
If I2 = 1, then the value of the X register should be the same as INPUT + 1, or the first element of our array 29,29,29,29,29.
MIX> preg X rX: + 29 29 29 29 29 (0494262109) MIX> preg I2 rI2: + 00 01 (0001) |
Let’s continue:
MIX> next 3008: [STX 1,2 ] STX INPUT+1,2 |
The original code was
STX INPUT+1,2 |
We store this value from the previous operation into the memory location 1 indexed by the I2 Register, or one higher than it was before. This is where we start shuffling each of the values up one cell to make space for the insertion.
Here is a visualization of what has happened so far. I am going to elide the input to just a single letter. The first few element of the input were
[ ][Z][Y][X][W]…
INPUT points to that first block, which is blank, and not considered part of the data. We Start by treating the first element as a sorted array, so [Z] is sorted. We then do our first comparison, which was between Z and Y. Since Y is < than Z, we know we need to insert Y before Z, and thus shuffle the Array up to make space.
So we have: rX = Z and rA = Y.
Thus A is the current element we are looking to insert, and X is the value we are shuffling.
MIX> next 3009: [DEC2 1,0 ] DEC2 1 Elapsed time: 1 /Total program time: 14 (Total uptime: 14) |
We decrement the I2 Register by 1. If we were inserting a value near the beginning of a long sorted collection, this operation would get executed many times, but, since we are only shuffling on value up, it should only get executed once. The result
MIX> preg I2 rI2: - 00 00 (0000) |
I2 (i) is now 0 and thus at the start of the sorted list.
MIX> next 3010: [J2P 3005,0 ] J2P 3B |
J2P is the Jump command that looks at the i2 regsiter and jumps if it is positive. Since it is 0, we would expect not to jump. This can be thought of as a break statement in C, it exits the loop.
MIX> next 3011: [STA 1,2 ] 5H STA INPUT+1,2 |
We’ve found the location where we want to insert the value, and we’ve made space for it. This operation inserts it into the list. The first two elements of the list are now in sorted order, as shown here:
MIX> pmem 1 0001: + 28 28 28 28 28 (0477218588) MIX> pmem 2 0002: + 29 29 29 29 29 (0494262109) |
Since we have more elements in the unsorted portion of the list, we would expect to continue. These are the last two commands of the original algorithm code:
INC1 1
J1NP 2B |
And we see that they are executed:
MIX> next 3012: [INC1 1,0 ] INC1 1 MIX> next 3013: [J1NP 3003,0 ] J1NP 2B |
We jump back to 2B.
Here’s the short form ow the start of the array:
[Y][Z][X][W][V]
At this point, we should expect to pull the third element out of the list (27,27,27,27,27) and insert it at the front of the list. The shuffled portion should happen twice, first to move the Zs to block 3, second to move the Ys to block 2. After that, the X should be stuck in the start of the array.
[X][Y][Z][W][V]
Lets go back to the current line and run once through, step by step until we get to the J1NP at address 3013 one more time. I’ll remove the extraneous text so you can see just the trace:
MIX> pline Line 38: 2H LDA INPUT+N,1 MIX> next 3003: [LDA 26,1 ] 2H LDA INPUT+N,1 3004: [ENT2 25,1 ] ENT2 N-1,1 3005: [CMPA 0,2 ] 3H CMPA INPUT,2 3006: [JGE 3011,0 ] JGE 5F 3007: [LDX 0,2 ] 4H LDX INPUT,2 3008: [STX 1,2 ] STX INPUT+1,2 3009: [DEC2 1,0 ] DEC2 1 3010: [J2P 3005,0 ] J2P 3B 3005: [CMPA 0,2 ] 3H CMPA INPUT,2 3006: [JGE 3011,0 ] JGE 5F 3007: [LDX 0,2 ] 4H LDX INPUT,2 3008: [STX 1,2 ] STX INPUT+1,2 3009: [DEC2 1,0 ] DEC2 1 3010: [J2P 3005,0 ] J2P 3B 3011: [STA 1,2 ] 5H STA INPUT+1,2 3012: [INC1 1,0 ] INC1 1 3013: [J1NP 3003,0 ] J1NP 2B MIX> preg rA: + 27 27 27 27 27 (0460175067) rX: + 28 28 28 28 28 (0477218588) rJ: + 47 06 (3014) rI1: - 00 22 (0022) rI2: - 00 00 (0000) rI3: + 00 00 (0000) rI4: + 00 00 (0000) rI5: + 00 00 (0000) rI6: + 00 00 (0000) MIX> pmem 1 0001: + 27 27 27 27 27 (0460175067) MIX> pmem 2 0002: + 28 28 28 28 28 (0477218588) MIX> pmem 3 0003: + 29 29 29 29 29 (0494262109) MIX> pmem 4 0004: + 26 26 26 26 26 (0443131546) MIX> pmem 5 0005: + 25 25 25 25 25 (0426088025) |
Starting with the INC1 at address 3012, we can see that the I1 register is getting increased. This is the i value from the original algorithm. We can see at the end of the loop that this value is 27s, and we never change the rA during the execution of the loop. This is the value stored at the operation with label 5H: STA 1,2. We see that the i2 is still set to 0, so it goes into the front of the array as well.
Obviously, having the data in reverse sorted order makes for a poor demonstration; Ideally, we would see values inserted at the start, in the middle, and at the end of the sorted data.
Let’s continue to the last loop. I’ll set a break point on the line after the last jump.
MIX> sbp 49 Breakpoint set at line 49 MIX> run .... MIX> preg rA: + 01 01 01 01 01 (0017043521) rX: + 02 02 02 02 02 (0034087042) rJ: + 47 03 (3011) rI1: + 00 01 (0001) rI2: - 00 00 (0000) rI3: + 00 00 (0000) rI4: + 00 00 (0000) rI5: + 00 00 (0000) rI6: + 00 00 (0000) MIX> pmem 26 0026: + 29 29 29 29 29 (0494262109) |
On our last time through the loop, we see that the Accumulator was looking at 01s or the letter A. The rX register had 02s, or the letter B. Memory location 26 has 29s, or the letter Z. We can let the run finish:
Running ... 3014: [OUT 0,0(2:3) ] OUT INPUT(TERM) AAAAABBBBBCCCCCDDDDDEEEEEFFFFFGGGGGHHHHHIIIIIJJJJJKKKKKLLLLLMMMMM 3015: [OUT 14,0(2:3) ] OUT INPUT+14(TERM) NNNNNOOOOOPPPPPQQQQQRRRRRSSSSSTTTTTUUUUUVVVVVWWWWWXXXXXYYYYYZZZZZ 3016: [HLT 0,0 ] HLT ... done |
We have a sorted array.
What became apparent to me in this exercise is that MIXAL is very much OP code optimized to work with data in place in memory. This is not the norm for the X86_64 or AARCH64 instruction set; you need to explicitly fetch a value out of memory and then compare it. Fetching from memory is actually one of the longer operations you can anticipate, especially if the value you need is not in L1 or L2 cache. This might have an impact on the running time of algorithms, especially if the data is pre-ordered to avoid cache look ups.