MVM: Bubblesort

MVM: Minimal Virtual Machine | a project by Stefan Reich

Bubblesort

As a sample algorithm, a bubblesort was implemented in MVM. Here's some stats:

Code takes up 180 machine words (720 bytes, 60 instructions)
Sorting an array of 1000 integers requires 39,438,525 subleqs in worst case
The Java-based interpreter completes a sort in about 550 ms
This equates to roughly 70 MIPS
Fast enough for many tasks!
For the rest, we can still dream up a JIT compiler.

The code was produced from within Java using a somewhat ad-hoc utility class called CodeGen. CodeGen provides the typical macros you want when you program for MVM (copy, load, store, add). Handling labels is a bit messy (note how the forward-jump requires manual patching).

listStart and listEnd are constant addresses. ax, bx, i and j are variables or memory-mapped registers, however you like to perceive them.

Here's the Java source:

  gen.set(i, 1-(listEnd-listStart-1)); // i is a negative counter
  int lLoop = gen.getPC();

  gen.set(j, listStart);

  // load pair
  int lLoopJ = gen.getPC();
  gen.load(ax, j);
  gen.addC(j, 1);
  gen.load(bx, j);
  gen.subC(j, 1);
  int patchNoSwap = gen.getPC()+2;
  gen.subleq(ax, bx, PATCH);

  // swap
  gen.add(ax, bx); // restore ax
  gen.addC(j, 1);
  gen.store(j, ax);
  gen.subC(j, 1);
  gen.store(j, bx);

  // loop while j <= listEnd-2
  gen.patch(patchNoSwap, gen.getPC());
  gen.addC(j, 1);
  gen.copy(ax, j);
  gen.subleqC(ax, listEnd-2, lLoopJ);

  // loop while ++i <= 0
  gen.subleqC(i, -1, lLoop);

Alright, it's not a beauty, but at least we get 60 subleqs out of far less than 60 lines.

Disassembly

This disassembler dump shows symbols instead of addresses wherever possible and uses a new notation optimized for readability. Every line is still one subleq. The middle column shows the code's bit representation in memory.

  1016: 00000003 00000003 000003FB | clr i
  1019: FFFFFFFC 000003E6 000003FE | sub i #(998)
  1022: 00000004 00000004 00000401 | lLoopI: clr j
  1025: FFFFFFFB FFFFFFF0 00000404 | sub j #(-16)
  1028: 00000000 00000004 00000407 | lLoopJ: sub Z j
  1031: 00000411 00000411 0000040A | clr 1041
  1034: 00000411 00000000 0000040D | sub 1041 Z
  1037: 00000000 00000000 00000410 | clr Z
  1040: 00000000 7FFFFFFF 00000413 | sub Z *
  1043: 00000001 00000001 00000416 | clr ax
  1046: 00000001 00000000 00000419 | sub ax Z
  1049: 00000000 00000000 0000041C | clr Z
  1052: FFFFFFFB FFFFFFFF 0000041F | sub j #(-1)
  1055: 00000000 00000004 00000422 | sub Z j
  1058: 0000042C 0000042C 00000425 | clr 1068
  1061: 0000042C 00000000 00000428 | sub 1068 Z
  1064: 00000000 00000000 0000042B | clr Z
  1067: 00000000 7FFFFFFF 0000042E | sub Z *
  1070: 00000002 00000002 00000431 | clr bx
  1073: 00000002 00000000 00000434 | sub bx Z
  1076: 00000000 00000000 00000437 | clr Z
  1079: FFFFFFFB 00000001 0000043A | sub j #(1)
  1082: 00000001 00000002 00000494 | sub ax bx leq lNoSwap
  1085: 00000000 00000002 00000440 | sub Z bx
  1088: 00000001 00000000 00000443 | sub ax Z
  1091: 00000000 00000000 00000446 | clr Z
  1094: FFFFFFFB FFFFFFFF 00000449 | sub j #(-1)
  1097: 00000000 00000004 0000044C | sub Z j
  1100: 00000461 00000461 0000044F | clr 1121
  1103: 00000461 00000000 00000452 | sub 1121 Z
  1106: 00000462 00000462 00000455 | clr 1122
  1109: 00000462 00000000 00000458 | sub 1122 Z
  1112: 00000467 00000467 0000045B | clr 1127
  1115: 00000467 00000000 0000045E | sub 1127 Z
  1118: 00000000 00000000 00000461 | clr Z
  1121: 7FFFFFFF 7FFFFFFF 00000464 | sub * *
  1124: 00000000 00000001 00000467 | sub Z ax
  1127: 7FFFFFFF 00000000 0000046A | sub * Z
  1130: 00000000 00000000 0000046D | clr Z
  1133: FFFFFFFB 00000001 00000470 | sub j #(1)
  1136: 00000000 00000004 00000473 | sub Z j
  1139: 00000488 00000488 00000476 | clr 1160
  1142: 00000488 00000000 00000479 | sub 1160 Z
  1145: 00000489 00000489 0000047C | clr 1161
  1148: 00000489 00000000 0000047F | sub 1161 Z
  1151: 0000048E 0000048E 00000482 | clr 1166
  1154: 0000048E 00000000 00000485 | sub 1166 Z
  1157: 00000000 00000000 00000488 | clr Z
  1160: 7FFFFFFF 7FFFFFFF 0000048B | sub * *
  1163: 00000000 00000002 0000048E | sub Z bx
  1166: 7FFFFFFF 00000000 00000491 | sub * Z
  1169: 00000000 00000000 00000494 | clr Z
  1172: FFFFFFFB FFFFFFFF 00000497 | lNoSwap: sub j #(-1)
  1175: 00000000 00000004 0000049A | sub Z j
  1178: 00000001 00000001 0000049D | clr ax
  1181: 00000001 00000000 000004A0 | sub ax Z
  1184: 00000000 00000000 000004A3 | clr Z
  1187: FFFFFFFE 000003F6 00000404 | sub ax #(1014) leq lLoopJ
  1190: FFFFFFFC FFFFFFFF 000003FE | sub i #(-1) leq lLoopI
  1193: 00000000 00000000 FFFFFFFF | sub Z Z leq NIRVANA