feat: improve benchmark code

compare 3 alternatives:
1. Current avrInstruction() implementation
2. Map opcodes using a Javascript map
3. Map opcodes using a Uint16Array and big switch statement

4 files changed, 75 insertions, 19 deletions

diff --git a/benchmark/convert-instructions.ts b/benchmark/convert-instructions.ts
index 7e8e3fd..67a3f1f 100644
--- a/benchmark/convert-instructions.ts
+++ b/benchmark/convert-instructions.ts
@@ -2,15 +2,15 @@ import * as fs from 'fs';
 import * as prettier from 'prettier';
 
 const input = fs.readFileSync('src/instruction.ts', { encoding: 'utf-8' });
+let fnName = '';
 let fnBody = '';
 let openingBrace = false;
 let currentInstruction = '';
 let pattern = '';
 let output = `
 import { ICPU } from '../src/cpu';
-import { u16 } from '../src/types';
 
-function isTwoWordInstruction(opcode: u16) {
+function isTwoWordInstruction(opcode: number) {
   return (
     /* LDS */
     (opcode & 0xfe0f) === 0x9000 ||
@@ -23,6 +23,7 @@ function isTwoWordInstruction(opcode: u16) {
   );
 }
 `;
+const patternToFn: Array<[string, string]> = [];
 for (const line of input.split('\n')) {
   if (line.startsWith('  /* ')) {
     currentInstruction = line
@@ -33,11 +34,12 @@ for (const line of input.split('\n')) {
     openingBrace = false;
     pattern = line.split(',')[1].split('*')[0];
     console.log(currentInstruction);
-    currentInstruction = currentInstruction.replace(/[\(\)]/g, '');
+    fnName = 'inst' + currentInstruction.replace(/[\(\)]/g, '');
+    patternToFn.push([pattern.trim(), fnName]);
   }
   if (line.startsWith('  }')) {
     output += `
-      export function inst${currentInstruction}(cpu: ICPU, opcode: number) {
+      export function ${fnName}(cpu: ICPU, opcode: number) {
         /*${pattern}*/
         ${fnBody}
         cpu.cycles++;
@@ -54,6 +56,24 @@ for (const line of input.split('\n')) {
   }
 }
 
+let executeInstructionCases = ``;
+output += `\nexport const instructions = [`;
+let i = 1;
+for (const [fnPattern, fn] of patternToFn) {
+  output += `{pattern: '${fnPattern}', fn: ${fn}, idx: ${i}},`;
+  executeInstructionCases += `case ${i}: ${fn}(cpu, opcode); break;\n`;
+  i++;
+}
+output += ']';
+
+output += `\n
+export function executeInstruction(idx: number, cpu: ICPU, opcode: number) {
+  switch (idx) {
+    ${executeInstructionCases}
+    default: instNOP(cpu, opcode);
+  }
+}`;
+
 const formattedOutput = prettier.format(output, { singleQuote: true, parser: 'babel' });
 
 fs.writeFileSync('benchmark/instruction-fn.ts', formattedOutput, {
diff --git a/benchmark/index.ts b/benchmark/index.ts
index b90b6bd..02eee8d 100644
--- a/benchmark/index.ts
+++ b/benchmark/index.ts
@@ -1,31 +1,41 @@
-import { CPU } from '../src/cpu';
+import { CPU, ICPU } from '../src/cpu';
 import { avrInstruction } from '../src/instruction';
 import { createBenchmark } from './benchmark';
-import { instLDY } from './instruction-fn';
+import { permutations } from './permutations';
+import { instructions, executeInstruction } from './instruction-fn';
 
 /* Approach 1: use large Uint16Array with all possible opcodes */
-const instructionMap = new Uint16Array(65536);
-instructionMap[0x8088] = 0x5;
+const instructionArray = new Uint16Array(65536);
+for (let i = 0; i < instructions.length; i++) {
+  const { pattern } = instructions[i];
+  for (const opcode of permutations(pattern.replace(/ /g, '').substr(0, 16))) {
+    if (!instructionArray[opcode]) {
+      instructionArray[opcode] = i + 1;
+    }
+  }
+}
 
 function avrInstructionUintArray(cpu: CPU) {
   const opcode = cpu.progMem[cpu.pc];
-  const mapped = instructionMap[opcode];
-  switch (mapped) {
-    case 5:
-      instLDY(cpu, opcode);
-      break;
-  }
+  executeInstruction(instructionArray[opcode], cpu, opcode);
 }
 
-/* Approach 1: use Map() */
-const objMap = new Map<number, (cpu: CPU, opcode: number) => void>();
-objMap.set(0x8088, instLDY);
+/* Approach 2: use instMap */
+const instructionMap: { [key: number]: (cpu: ICPU, opcode: number) => void } = {};
+for (const { pattern, fn } of instructions) {
+  for (const opcode of permutations(pattern.replace(/ /g, '').substr(0, 16))) {
+    if (!instructionMap[opcode]) {
+      instructionMap[opcode] = fn;
+    }
+  }
+}
 
 function avrInstructionObjMap(cpu: CPU) {
   const opcode = cpu.progMem[cpu.pc];
-  objMap.get(cpu.progMem[cpu.pc])(cpu, opcode);
+  instructionMap[opcode](cpu, opcode);
 }
 
+/* Run the benchmark */
 function run() {
   const benchmark = createBenchmark('cpu-benchmark');
 
diff --git a/benchmark/permutations.ts b/benchmark/permutations.ts
new file mode 100644
index 0000000..4465557
--- /dev/null
+++ b/benchmark/permutations.ts
@@ -0,0 +1,23 @@
+export function* permutations(pattern: string) {
+  let totalPerms = 1;
+  for (const char of pattern) {
+    if (char !== '0' && char !== '1') {
+      totalPerms *= 2;
+    }
+  }
+
+  for (let permIndex = 0; permIndex < totalPerms; permIndex++) {
+    let varIndex = 0;
+    let value = 0;
+    for (const char of pattern) {
+      value *= 2;
+      if (char === '1') {
+        value++;
+      } else if (char !== '0') {
+        value += permIndex & (1 << varIndex) ? 1 : 0;
+        varIndex++;
+      }
+    }
+    yield value;
+  }
+}
diff --git a/tsconfig.benchmark.json b/tsconfig.benchmark.json
index 608b618..79f519c 100644
--- a/tsconfig.benchmark.json
+++ b/tsconfig.benchmark.json
@@ -1,5 +1,8 @@
 {
   "extends": "./tsconfig.json",
-  "compilerOptions": { "rootDir": "." },
+  "compilerOptions": {
+    "rootDir": ".",
+    "target": "es2018"
+  },
   "include": ["src/**/*.ts", "benchmark/**/*.ts"]
 }