Understanding the MIXAL insertion sort.

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.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.