From ec512ea868d5df64a8a11ed27d5032337760ffde Mon Sep 17 00:00:00 2001 From: Uri Shaked Date: Sun, 1 Dec 2019 22:04:02 +0200 Subject: feat: add benchmarking code --- benchmark/.gitignore | 1 + benchmark/benchmark.ts | 127 ++++++++++++++++++++++++++++++++++++++ benchmark/convert-instructions.ts | 61 ++++++++++++++++++ benchmark/index.ts | 55 +++++++++++++++++ package-lock.json | 8 ++- package.json | 5 +- src/instruction.ts | 30 ++++----- tsconfig.benchmark.json | 5 ++ 8 files changed, 275 insertions(+), 17 deletions(-) create mode 100644 benchmark/.gitignore create mode 100644 benchmark/benchmark.ts create mode 100644 benchmark/convert-instructions.ts create mode 100644 benchmark/index.ts create mode 100644 tsconfig.benchmark.json diff --git a/benchmark/.gitignore b/benchmark/.gitignore new file mode 100644 index 0000000..f15e9f9 --- /dev/null +++ b/benchmark/.gitignore @@ -0,0 +1 @@ +instruction-fn.ts diff --git a/benchmark/benchmark.ts b/benchmark/benchmark.ts new file mode 100644 index 0000000..eecce31 --- /dev/null +++ b/benchmark/benchmark.ts @@ -0,0 +1,127 @@ +/** + * MIT License + * + * Copyright (c) 2019 Miško Hevery + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in all + * copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + * + * Source: https://github.com/mhevery/AngularConnect-2019 + */ + +// tslint:disable + +import { performance } from 'perf_hooks'; + +const MIN_SAMPLE_COUNT_NO_IMPROVEMENT = 100; +const MIN_SAMPLE_DURATION = 2; + +const UNITS = ['ms', 'us', 'ns', 'ps']; +export interface Benchmark { + (versionName: string): Profile; + report(fn?: (report: string) => void): void; +} +export interface Profile { + (): boolean; + profileName: string; + bestTime: number; + iterationCount: number; + sampleCount: number; + noImprovementCount: number; +} + +export function createBenchmark(benchmarkName: string): Benchmark { + const profiles: Profile[] = []; + + const benchmark = function Benchmark(profileName: string): Profile { + let iterationCounter: number = 0; + let timestamp: number = 0; + const profile: Profile = function Profile(): boolean { + if (iterationCounter === 0) { + let runAgain = false; + // if we reached the end of the iteration count than we should decide what to do next. + if (timestamp === 0) { + // this is the first time we are executing + iterationCounter = profile.iterationCount; + runAgain = true; + // console.log('profiling', profileName, '...'); + } else { + profile.sampleCount++; + // we came to an end of a sample, compute the time. + const durationMs = performance.now() - timestamp; + const iterationTimeMs = Math.max(durationMs / profile.iterationCount, 0); + if (profile.bestTime > iterationTimeMs) { + profile.bestTime = iterationTimeMs; + profile.noImprovementCount = 0; + runAgain = true; + } else { + runAgain = profile.noImprovementCount++ < MIN_SAMPLE_COUNT_NO_IMPROVEMENT; + } + if (durationMs < MIN_SAMPLE_DURATION) { + // we have not ran for long enough so increase the iteration count. + profile.iterationCount = Math.max( + // As a sanity if duration_ms is 0 just double the count. + profile.iterationCount << 1, + // Otherwise try to guess how many iterations we have to do to get the right time. + Math.round((MIN_SAMPLE_DURATION / durationMs) * profile.iterationCount) + ); + profile.noImprovementCount = 0; + runAgain = true; + } + } + iterationCounter = profile.iterationCount; + timestamp = performance.now(); + return runAgain; + } else { + // this is the common path and it needs te be quick! + iterationCounter--; + return true; + } + } as Profile; + profile.profileName = profileName; + profile.bestTime = Number.MAX_SAFE_INTEGER; + profile.iterationCount = 1; + profile.noImprovementCount = 0; + profile.sampleCount = 0; + profiles.push(profile); + return profile; + } as Benchmark; + + benchmark.report = function(fn?: (report: string) => void) { + const fastest = profiles.reduce((previous: Profile, current: Profile) => { + return previous.bestTime < current.bestTime ? previous : current; + }); + let unitOffset = 0; + let time = fastest.bestTime; + while (time < 1 && time !== 0) { + time = time * 1000; + unitOffset++; + } + const unit: string = UNITS[unitOffset]; + (fn || console.log)( + `Benchmark: ${benchmarkName}\n${profiles + .map((profile: Profile) => { + const time = (profile.bestTime * Math.pow(1000, unitOffset)).toFixed(3); + const percent = (100 - (profile.bestTime / fastest.bestTime) * 100).toFixed(0); + return ' ' + profile.profileName + ': ' + time + ' ' + unit + '(' + percent + '%)'; + }) + .join('\n')}` + ); + }; + return benchmark; +} diff --git a/benchmark/convert-instructions.ts b/benchmark/convert-instructions.ts new file mode 100644 index 0000000..7e8e3fd --- /dev/null +++ b/benchmark/convert-instructions.ts @@ -0,0 +1,61 @@ +import * as fs from 'fs'; +import * as prettier from 'prettier'; + +const input = fs.readFileSync('src/instruction.ts', { encoding: 'utf-8' }); +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) { + return ( + /* LDS */ + (opcode & 0xfe0f) === 0x9000 || + /* STS */ + (opcode & 0xfe0f) === 0x9200 || + /* CALL */ + (opcode & 0xfe0e) === 0x940e || + /* JMP */ + (opcode & 0xfe0e) === 0x940c + ); +} +`; +for (const line of input.split('\n')) { + if (line.startsWith(' /* ')) { + currentInstruction = line + .trim() + .split(',')[0] + .split(' ')[1]; + fnBody = ''; + openingBrace = false; + pattern = line.split(',')[1].split('*')[0]; + console.log(currentInstruction); + currentInstruction = currentInstruction.replace(/[\(\)]/g, ''); + } + if (line.startsWith(' }')) { + output += ` + export function inst${currentInstruction}(cpu: ICPU, opcode: number) { + /*${pattern}*/ + ${fnBody} + cpu.cycles++; + if (++cpu.pc >= cpu.progMem.length) { + cpu.pc = 0; + } + } + `; + currentInstruction = ''; + } else if (currentInstruction && openingBrace) { + fnBody += line; + } else if (currentInstruction && !openingBrace) { + openingBrace = line.includes('{'); + } +} + +const formattedOutput = prettier.format(output, { singleQuote: true, parser: 'babel' }); + +fs.writeFileSync('benchmark/instruction-fn.ts', formattedOutput, { + encoding: 'utf-8' +}); diff --git a/benchmark/index.ts b/benchmark/index.ts new file mode 100644 index 0000000..b90b6bd --- /dev/null +++ b/benchmark/index.ts @@ -0,0 +1,55 @@ +import { CPU } from '../src/cpu'; +import { avrInstruction } from '../src/instruction'; +import { createBenchmark } from './benchmark'; +import { instLDY } from './instruction-fn'; + +/* Approach 1: use large Uint16Array with all possible opcodes */ +const instructionMap = new Uint16Array(65536); +instructionMap[0x8088] = 0x5; + +function avrInstructionUintArray(cpu: CPU) { + const opcode = cpu.progMem[cpu.pc]; + const mapped = instructionMap[opcode]; + switch (mapped) { + case 5: + instLDY(cpu, opcode); + break; + } +} + +/* Approach 1: use Map() */ +const objMap = new Map void>(); +objMap.set(0x8088, instLDY); + +function avrInstructionObjMap(cpu: CPU) { + const opcode = cpu.progMem[cpu.pc]; + objMap.get(cpu.progMem[cpu.pc])(cpu, opcode); +} + +function run() { + const benchmark = createBenchmark('cpu-benchmark'); + + const cpu = new CPU(new Uint16Array(0x1000)); + cpu.progMem[0] = 0x8088; + const timeA = benchmark('avrInstruction'); + while (timeA()) { + cpu.pc = 0; + avrInstruction(cpu); + } + + const timeB = benchmark('avrInstructionObjMap'); + while (timeB()) { + cpu.pc = 0; + avrInstructionObjMap(cpu); + } + + const timeC = benchmark('avrInstructionUintArray'); + while (timeC()) { + cpu.pc = 0; + avrInstructionUintArray(cpu); + } + + benchmark.report(); +} + +run(); diff --git a/package-lock.json b/package-lock.json index 92e3573..b1c580d 100644 --- a/package-lock.json +++ b/package-lock.json @@ -1,6 +1,6 @@ { "name": "avr8js", - "version": "0.2.0", + "version": "0.3.3", "lockfileVersion": 1, "requires": true, "dependencies": { @@ -1443,6 +1443,12 @@ "integrity": "sha512-f5j5b/Gf71L+dbqxIpQ4Z2WlmI/mPJ0fOkGGmFgtb6sAu97EPczzbS3/tJKxmcYDj55OX6ssqwDAWOHIYDRDGA==", "dev": true }, + "@types/prettier": { + "version": "1.19.0", + "resolved": "https://registry.npmjs.org/@types/prettier/-/prettier-1.19.0.tgz", + "integrity": "sha512-gDE8JJEygpay7IjA/u3JiIURvwZW08f0cZSZLAzFoX/ZmeqvS0Sqv+97aKuHpNsalAMMhwPe+iAS6fQbfmbt7A==", + "dev": true + }, "@types/q": { "version": "1.5.2", "resolved": "https://registry.npmjs.org/@types/q/-/q-1.5.2.tgz", diff --git a/package.json b/package.json index c1d4dd4..2112003 100644 --- a/package.json +++ b/package.json @@ -13,7 +13,9 @@ "start": "parcel demo/src/index.html -d demo/build", "lint": "tslint --project tsconfig.json", "test": "npm run lint && jest", - "test:watch": "jest --watch" + "test:watch": "jest --watch", + "benchmark:prepare": "ts-node --project tsconfig.benchmark.json benchmark/convert-instructions.ts", + "benchmark": "ts-node --project tsconfig.benchmark.json benchmark/index.ts" }, "files": [ "dist" @@ -21,6 +23,7 @@ "devDependencies": { "@types/jest": "^24.0.23", "@types/node": "^12.12.7", + "@types/prettier": "^1.19.0", "husky": "^3.0.9", "jest": "^24.9.0", "lint-staged": "^9.4.2", diff --git a/src/instruction.ts b/src/instruction.ts index a72218e..cca5ea9 100644 --- a/src/instruction.ts +++ b/src/instruction.ts @@ -376,7 +376,7 @@ export function avrInstruction(cpu: ICPU) { cpu.data[(opcode & 0x1f0) >> 4] = cpu.readData(cpu.dataView.getUint16(26, true)); } - /* LDX, 1001 000d dddd 1101 */ + /* LDX(INC), 1001 000d dddd 1101 */ if ((opcode & 0xfe0f) === 0x900d) { const x = cpu.dataView.getUint16(26, true); cpu.data[(opcode & 0x1f0) >> 4] = cpu.readData(x); @@ -384,7 +384,7 @@ export function avrInstruction(cpu: ICPU) { cpu.cycles++; } - /* LDX, 1001 000d dddd 1110 */ + /* LDX(DEC), 1001 000d dddd 1110 */ if ((opcode & 0xfe0f) === 0x900e) { const x = cpu.dataView.getUint16(26, true) - 1; cpu.dataView.setUint16(26, x, true); @@ -397,7 +397,7 @@ export function avrInstruction(cpu: ICPU) { cpu.data[(opcode & 0x1f0) >> 4] = cpu.readData(cpu.dataView.getUint16(28, true)); } - /* LDY, 1001 000d dddd 1001 */ + /* LDY(INC), 1001 000d dddd 1001 */ if ((opcode & 0xfe0f) === 0x9009) { const y = cpu.dataView.getUint16(28, true); cpu.data[(opcode & 0x1f0) >> 4] = cpu.readData(y); @@ -405,7 +405,7 @@ export function avrInstruction(cpu: ICPU) { cpu.cycles++; } - /* LDY, 1001 000d dddd 1010 */ + /* LDY(DEC), 1001 000d dddd 1010 */ if ((opcode & 0xfe0f) === 0x900a) { const y = cpu.dataView.getUint16(28, true) - 1; cpu.dataView.setUint16(28, y, true); @@ -430,7 +430,7 @@ export function avrInstruction(cpu: ICPU) { cpu.data[(opcode & 0x1f0) >> 4] = cpu.readData(cpu.dataView.getUint16(30, true)); } - /* LDZ, 1001 000d dddd 0001 */ + /* LDZ(INC), 1001 000d dddd 0001 */ if ((opcode & 0xfe0f) === 0x9001) { const z = cpu.dataView.getUint16(30, true); cpu.data[(opcode & 0x1f0) >> 4] = cpu.readData(z); @@ -438,7 +438,7 @@ export function avrInstruction(cpu: ICPU) { cpu.cycles++; } - /* LDZ, 1001 000d dddd 0010 */ + /* LDZ(DEC), 1001 000d dddd 0010 */ if ((opcode & 0xfe0f) === 0x9002) { const z = cpu.dataView.getUint16(30, true) - 1; cpu.dataView.setUint16(30, z, true); @@ -464,13 +464,13 @@ export function avrInstruction(cpu: ICPU) { cpu.cycles += 2; } - /* LPM, 1001 000d dddd 0100 */ + /* LPM(REG), 1001 000d dddd 0100 */ if ((opcode & 0xfe0f) === 0x9004) { cpu.data[(opcode & 0x1f0) >> 4] = cpu.progBytes[cpu.dataView.getUint16(30, true)]; cpu.cycles += 2; } - /* LPM, 1001 000d dddd 0101 */ + /* LPM(INC), 1001 000d dddd 0101 */ if ((opcode & 0xfe0f) === 0x9005) { const i = cpu.dataView.getUint16(30, true); cpu.data[(opcode & 0x1f0) >> 4] = cpu.progBytes[i]; @@ -749,7 +749,7 @@ export function avrInstruction(cpu: ICPU) { /* not implemented */ } - /* SPM, 1001 0101 1111 1000 */ + /* SPM(INC), 1001 0101 1111 1000 */ if (opcode === 0x95f8) { /* not implemented */ } @@ -768,14 +768,14 @@ export function avrInstruction(cpu: ICPU) { cpu.writeData(cpu.dataView.getUint16(26, true), cpu.data[(opcode & 0x1f0) >> 4]); } - /* STX, 1001 001r rrrr 1101 */ + /* STX(INC), 1001 001r rrrr 1101 */ if ((opcode & 0xfe0f) === 0x920d) { const x = cpu.dataView.getUint16(26, true); cpu.writeData(x, cpu.data[(opcode & 0x1f0) >> 4]); cpu.dataView.setUint16(26, x + 1, true); } - /* STX, 1001 001r rrrr 1110 */ + /* STX(DEC), 1001 001r rrrr 1110 */ if ((opcode & 0xfe0f) === 0x920e) { const i = cpu.data[(opcode & 0x1f0) >> 4]; const x = cpu.dataView.getUint16(26, true) - 1; @@ -789,7 +789,7 @@ export function avrInstruction(cpu: ICPU) { cpu.writeData(cpu.dataView.getUint16(28, true), cpu.data[(opcode & 0x1f0) >> 4]); } - /* STY, 1001 001r rrrr 1001 */ + /* STY(INC), 1001 001r rrrr 1001 */ if ((opcode & 0xfe0f) === 0x9209) { const i = cpu.data[(opcode & 0x1f0) >> 4]; const y = cpu.dataView.getUint16(28, true); @@ -797,7 +797,7 @@ export function avrInstruction(cpu: ICPU) { cpu.dataView.setUint16(28, y + 1, true); } - /* STY, 1001 001r rrrr 1010 */ + /* STY(DEC), 1001 001r rrrr 1010 */ if ((opcode & 0xfe0f) === 0x920a) { const i = cpu.data[(opcode & 0x1f0) >> 4]; const y = cpu.dataView.getUint16(28, true) - 1; @@ -824,14 +824,14 @@ export function avrInstruction(cpu: ICPU) { cpu.writeData(cpu.dataView.getUint16(30, true), cpu.data[(opcode & 0x1f0) >> 4]); } - /* STZ, 1001 001r rrrr 0001 */ + /* STZ(INC), 1001 001r rrrr 0001 */ if ((opcode & 0xfe0f) === 0x9201) { const z = cpu.dataView.getUint16(30, true); cpu.writeData(z, cpu.data[(opcode & 0x1f0) >> 4]); cpu.dataView.setUint16(30, z + 1, true); } - /* STZ, 1001 001r rrrr 0010 */ + /* STZ(DEC), 1001 001r rrrr 0010 */ if ((opcode & 0xfe0f) === 0x9202) { const i = cpu.data[(opcode & 0x1f0) >> 4]; const z = cpu.dataView.getUint16(30, true) - 1; diff --git a/tsconfig.benchmark.json b/tsconfig.benchmark.json new file mode 100644 index 0000000..608b618 --- /dev/null +++ b/tsconfig.benchmark.json @@ -0,0 +1,5 @@ +{ + "extends": "./tsconfig.json", + "compilerOptions": { "rootDir": "." }, + "include": ["src/**/*.ts", "benchmark/**/*.ts"] +} -- cgit v1.2.3