TypeScript - test algorithm performance
In this article, we would like to show how to test algorithms' performance in TypeScript.
Usually, when we compare algorithms that execution times are short, we repeat computations multiple times to get precise results. The number of repeats is selected empirically. The source code that is not an algorithm part shouldn't be measured.
Main concept:
xxxxxxxxxxconst test = (repeats: number, description: string, action: () => void): void => { const t1 = Date.now(); for (let i = 0; i < repeats; ++i) { action(); } const t2 = Date.now(); const dt = t2 - t1; console.log(`${description}: totoal time is ${dt} ms`);};// Usage example:const repeats: number = 100000; // set number of repeats depending on cases complexitytest(repeats, 'case 1', (): void => { /* source code case 1 */ });test(repeats, 'case 2', (): void => { /* source code case 2 */ });test(repeats, 'case 3', (): void => { /* source code case 3 */ });// add more cases here ...Example output:
xxxxxxxxxxcase 1: totoal time is 2 mscase 2: totoal time is 4 mscase 3: totoal time is 2 msHint: presented concept describes only a simple way how to test performance - in practice tests made by benchmarks are more complex.
In the below example we compare algorithms that computes Fibonacci sequence values.
In the test, we made 100000 repeats on Fibonacci algorithms using Ryzen 9 x5900 processor.
Test result:
xxxxxxxxxxIterative algorithm: total time is 78 msBinet's formula: total time is 2 msConclusion: iterative algorithm is ~39 times slower in the tested cases.
Test source code:
xxxxxxxxxx// ONLINE-RUNNER:browser;// ONLINE-RUNNER:browser;const test = (repeats: number, description: string, action: () => void): void => { const t1 = Date.now(); for (let i = 0; i < repeats; ++i) { action(); } const t2 = Date.now(); const dt = t2 - t1; console.log(`${description}: total time is ${dt} ms`);};// Tested algorithms:const fibonacci1 = (number: number): number => { if (number < 1) return 0; if (number < 2) return 1; return fibonacci1(number - 2) + fibonacci1(number - 1);}const fibonacci2 = (number: number): number => { const a = Math.pow(1 + 2.23606797749979, number); const b = Math.pow(1 - 2.23606797749979, number); const c = 2.23606797749979 * Math.pow(2, number); return Math.round((a - b) / c);}// Performance tests:const repeats = 100000; // set number of repeats depending on cases complexitytest(repeats, 'Iterative algorithm', (): void => { for (let i = 1; i < 10; ++i) { fibonacci1(i); }});test(repeats, 'Binet\'s formula', (): void => { for (let i = 1; i < 10; ++i) { fibonacci2(i); }});
