From 74750c7f0a8b83b3a579f4d7fc96070ca540b234 Mon Sep 17 00:00:00 2001 From: =?utf8?q?J=C3=A9r=C3=B4me=20Benoit?= Date: Sat, 6 Mar 2021 20:22:31 +0100 Subject: [PATCH] Add benchmark for quick select algorithm evaluation. (#255) --- .eslintrc.js | 1 + README.md | 2 +- benchmarks/README.md | 2 +- benchmarks/internal/benchmark-utils.js | 11 +- benchmarks/internal/cluster/dynamic.js | 6 +- benchmarks/internal/cluster/fixed.js | 4 +- benchmarks/internal/quick-select.js | 233 ++++++++++++++++++++++ benchmarks/internal/thread/dynamic.js | 8 +- benchmarks/internal/thread/fixed.js | 4 +- benchmarks/versus-external-pools/bench.sh | 2 +- 10 files changed, 257 insertions(+), 16 deletions(-) create mode 100644 benchmarks/internal/quick-select.js diff --git a/.eslintrc.js b/.eslintrc.js index 10597e77..850110e8 100644 --- a/.eslintrc.js +++ b/.eslintrc.js @@ -52,6 +52,7 @@ module.exports = { { skipWords: [ 'christopher', + 'comparator', 'ecma', 'enum', 'inheritdoc', diff --git a/README.md b/README.md index 7bb71d80..1ddad503 100644 --- a/README.md +++ b/README.md @@ -29,7 +29,7 @@ No dependencies

-## Why Poolifier? +## Why Poolifier? Poolifier is used to perform CPU intensive and I/O intensive tasks on nodejs servers, it implements worker pools (yes, more worker pool implementations, so you can choose which one fit better for you) using [worker-threads](https://nodejs.org/api/worker_threads.html#worker_threads_worker_threads) and cluster pools using [Node.js cluster](https://nodejs.org/api/cluster.html) modules. With poolifier you can improve your **performance** and resolve problems related to the event loop. diff --git a/benchmarks/README.md b/benchmarks/README.md index d368e861..61b57518 100644 --- a/benchmarks/README.md +++ b/benchmarks/README.md @@ -19,7 +19,7 @@ External pools with which we compared the poolifier results: Those are our results: -- CPU Intensive task with 100k operations submitted to each pool [BENCH-100000.MD](./versus-external-pools/BENCH-100000.MD). +- CPU Intensive task with 100k operations submitted to each pool [BENCH-100000.md](./versus-external-pools/BENCH-100000.md). This benchmark ran on a MacBook Pro 2015, 2,2 GHz Intel Core i7 quad-core, 16 GB 1600 MHz DDR3. > :warning: **We would need funds to run our benchmarks more often and on Cloud VMs, please consider to sponsor this project** diff --git a/benchmarks/internal/benchmark-utils.js b/benchmarks/internal/benchmark-utils.js index f84227d3..cbf69307 100644 --- a/benchmarks/internal/benchmark-utils.js +++ b/benchmarks/internal/benchmark-utils.js @@ -1,4 +1,4 @@ -async function runTest (pool, { tasks, workerData }) { +async function runPoolifierTest (pool, { tasks, workerData }) { return new Promise((resolve, reject) => { let executions = 0 for (let i = 0; i <= tasks; i++) { @@ -16,4 +16,11 @@ async function runTest (pool, { tasks, workerData }) { }) } -module.exports = { runTest } +function generateRandomInteger (max, min = 0) { + if (min) { + return Math.floor(Math.random() * (max - min + 1) + min) + } + return Math.floor(Math.random() * max + 1) +} + +module.exports = { runPoolifierTest, generateRandomInteger } diff --git a/benchmarks/internal/cluster/dynamic.js b/benchmarks/internal/cluster/dynamic.js index 7ad9dd28..6838e07a 100644 --- a/benchmarks/internal/cluster/dynamic.js +++ b/benchmarks/internal/cluster/dynamic.js @@ -2,7 +2,7 @@ const { DynamicClusterPool, WorkerChoiceStrategies } = require('../../../lib/index') -const { runTest } = require('../benchmark-utils') +const { runPoolifierTest } = require('../benchmark-utils') const size = 30 @@ -22,13 +22,13 @@ const dynamicPoolLessRecentlyUsed = new DynamicClusterPool( async function dynamicClusterTest ( { tasks, workerData } = { tasks: 1, workerData: { proof: 'ok' } } ) { - return runTest(dynamicPool, { tasks, workerData }) + return runPoolifierTest(dynamicPool, { tasks, workerData }) } async function dynamicClusterTestLessRecentlyUsed ( { tasks, workerData } = { tasks: 1, workerData: { proof: 'ok' } } ) { - return runTest(dynamicPoolLessRecentlyUsed, { tasks, workerData }) + return runPoolifierTest(dynamicPoolLessRecentlyUsed, { tasks, workerData }) } module.exports = { diff --git a/benchmarks/internal/cluster/fixed.js b/benchmarks/internal/cluster/fixed.js index 60a5b938..62c19aab 100644 --- a/benchmarks/internal/cluster/fixed.js +++ b/benchmarks/internal/cluster/fixed.js @@ -1,5 +1,5 @@ const { FixedClusterPool } = require('../../../lib/index') -const { runTest } = require('../benchmark-utils') +const { runPoolifierTest } = require('../benchmark-utils') const size = 30 @@ -11,7 +11,7 @@ const fixedPool = new FixedClusterPool( async function fixedClusterTest ( { tasks, workerData } = { tasks: 1, workerData: { proof: 'ok' } } ) { - return runTest(fixedPool, { tasks, workerData }) + return runPoolifierTest(fixedPool, { tasks, workerData }) } module.exports = { fixedClusterTest } diff --git a/benchmarks/internal/quick-select.js b/benchmarks/internal/quick-select.js new file mode 100644 index 00000000..dcebaaf8 --- /dev/null +++ b/benchmarks/internal/quick-select.js @@ -0,0 +1,233 @@ +const Benchmark = require('benchmark') +const { generateRandomInteger } = require('./benchmark-utils') + +const suite = new Benchmark.Suite() + +const LIST_FORMATTER = new Intl.ListFormat('en-US', { + style: 'long', + type: 'conjunction' +}) + +const tasksMap = new Map([ + [0, generateRandomInteger(10)], + [1, generateRandomInteger(10)], + [2, generateRandomInteger(10)], + [3, generateRandomInteger(10)], + [4, generateRandomInteger(10)], + [5, generateRandomInteger(10)], + [6, generateRandomInteger(10)], + [7, generateRandomInteger(10)], + [8, generateRandomInteger(10)], + [9, generateRandomInteger(10)], + [10, generateRandomInteger(10)], + [11, generateRandomInteger(10)], + [12, generateRandomInteger(10)], + [13, generateRandomInteger(10)], + [14, generateRandomInteger(10)], + [15, generateRandomInteger(10)], + [16, generateRandomInteger(10)], + [17, generateRandomInteger(10)], + [18, generateRandomInteger(10)], + [19, generateRandomInteger(10)], + [20, generateRandomInteger(10)], + [21, generateRandomInteger(10)], + [22, generateRandomInteger(10)], + [23, generateRandomInteger(10)], + [24, generateRandomInteger(10)], + [25, generateRandomInteger(10)], + [26, generateRandomInteger(10)], + [27, generateRandomInteger(10)], + [28, generateRandomInteger(10)], + [29, generateRandomInteger(10)] +]) + +function loopSelect (tasksMap) { + let minValue = Infinity + let minKey + for (const [key, value] of tasksMap) { + if (value === 0) { + return key + } else if (value < minValue) { + minKey = key + minValue = value + } + } + return [minKey, minValue] +} + +function arraySortSelect (tasksMap) { + const tasksArray = Array.from(tasksMap) + return tasksArray.sort((a, b) => { + if (a[1] < b[1]) { + return -1 + } else if (a[1] > b[1]) { + return 1 + } + return 0 + })[0] +} + +const defaultComparator = (a, b) => { + return a < b +} + +const defaultPivotIndexSelect = (leftIndex, rightIndex) => { + return leftIndex + Math.floor((rightIndex - leftIndex) / 2) +} + +function swap (array, index1, index2) { + const tmp = array[index1] + array[index1] = array[index2] + array[index2] = tmp +} + +function partition ( + array, + leftIndex, + rightIndex, + pivotIndex, + compare = defaultComparator +) { + const pivotValue = array[pivotIndex] + swap(array, pivotIndex, rightIndex) + let storeIndex = leftIndex + for (let i = leftIndex; i < rightIndex; i += 1) { + if (compare(array[i], pivotValue)) { + swap(array, storeIndex, i) + storeIndex += 1 + } + } + swap(array, rightIndex, storeIndex) + return storeIndex +} + +function selectLoop ( + array, + k, + leftIndex, + rightIndex, + compare = defaultComparator, + pivotIndexSelect = defaultPivotIndexSelect +) { + while (true) { + if (leftIndex === rightIndex) return array[leftIndex] + let pivotIndex = pivotIndexSelect(leftIndex, rightIndex) + pivotIndex = partition(array, leftIndex, rightIndex, pivotIndex, compare) + if (k === pivotIndex) { + return array[k] + } else if (k < pivotIndex) { + rightIndex = pivotIndex - 1 + } else { + leftIndex = pivotIndex + 1 + } + } +} + +function selectRecursion ( + array, + k, + leftIndex, + rightIndex, + compare = defaultComparator, + pivotIndexSelect = defaultPivotIndexSelect +) { + if (leftIndex === rightIndex) return array[leftIndex] + let pivotIndex = pivotIndexSelect(leftIndex, rightIndex) + pivotIndex = partition(array, leftIndex, rightIndex, pivotIndex, compare) + if (k === pivotIndex) { + return array[k] + } else if (k < pivotIndex) { + return selectRecursion(array, k, leftIndex, pivotIndex - 1, compare) + } else { + return selectRecursion(array, k, pivotIndex + 1, rightIndex, k, compare) + } +} + +function quickSelectLoop (tasksMap) { + const tasksArray = Array.from(tasksMap) + + return selectLoop(tasksArray, 0, 0, tasksArray.length - 1, (a, b) => { + return a[1] < b[1] + }) +} + +function quickSelectLoopRandomPivot (tasksMap) { + const tasksArray = Array.from(tasksMap) + + return selectLoop( + tasksArray, + 0, + 0, + tasksArray.length - 1, + (a, b) => { + return a[1] < b[1] + }, + (leftIndex, rightIndex) => { + return generateRandomInteger(leftIndex, rightIndex) + } + ) +} + +function quickSelectRecursion (tasksMap) { + const tasksArray = Array.from(tasksMap) + + return selectRecursion(tasksArray, 0, 0, tasksArray.length - 1, (a, b) => { + return a[1] < b[1] + }) +} + +function quickSelectRecursionRandomPivot (tasksMap) { + const tasksArray = Array.from(tasksMap) + + return selectRecursion( + tasksArray, + 0, + 0, + tasksArray.length - 1, + (a, b) => { + return a[1] < b[1] + }, + (leftIndex, rightIndex) => { + return generateRandomInteger(leftIndex, rightIndex) + } + ) +} + +// console.log(Array.from(tasksMap)) +// console.log(loopSelect(tasksMap)) +// console.log(arraySortSelect(tasksMap)) +// console.log(quickSelectLoop(tasksMap)) +// console.log(quickSelectLoopRandomPivot(tasksMap)) +// console.log(quickSelectRecursion(tasksMap)) +// console.log(quickSelectRecursionRandomPivot(tasksMap)) + +suite + .add('Loop select', function () { + loopSelect(tasksMap) + }) + .add('Array sort select', function () { + arraySortSelect(tasksMap) + }) + .add('Quick select loop', function () { + quickSelectLoop(tasksMap) + }) + .add('Quick select loop with random pivot', function () { + quickSelectLoopRandomPivot(tasksMap) + }) + .add('Quick select recursion', function () { + quickSelectRecursion(tasksMap) + }) + .add('Quick select recursion with random pivot', function () { + quickSelectRecursionRandomPivot(tasksMap) + }) + .on('cycle', function (event) { + console.log(event.target.toString()) + }) + .on('complete', function () { + console.log( + 'Fastest is ' + LIST_FORMATTER.format(this.filter('fastest').map('name')) + ) + // eslint-disable-next-line no-process-exit + process.exit() + }) + .run() diff --git a/benchmarks/internal/thread/dynamic.js b/benchmarks/internal/thread/dynamic.js index bc9b3d81..fb74d898 100644 --- a/benchmarks/internal/thread/dynamic.js +++ b/benchmarks/internal/thread/dynamic.js @@ -2,7 +2,7 @@ const { DynamicThreadPool, WorkerChoiceStrategies } = require('../../../lib/index') -const { runTest } = require('../benchmark-utils') +const { runPoolifierTest } = require('../benchmark-utils') const size = 30 @@ -16,19 +16,19 @@ const dynamicPoolLessRecentlyUsed = new DynamicThreadPool( size / 2, size * 3, './benchmarks/internal/thread/worker.js', - { workerChoiceStrategy: DynamicThreadPool.LESS_RECENTLY_USED } + { workerChoiceStrategy: WorkerChoiceStrategies.LESS_RECENTLY_USED } ) async function dynamicThreadTest ( { tasks, workerData } = { tasks: 1, workerData: { proof: 'ok' } } ) { - return runTest(dynamicPool, { tasks, workerData }) + return runPoolifierTest(dynamicPool, { tasks, workerData }) } async function dynamicThreadTestLessRecentlyUsed ( { tasks, workerData } = { tasks: 1, workerData: { proof: 'ok' } } ) { - return runTest(dynamicPoolLessRecentlyUsed, { tasks, workerData }) + return runPoolifierTest(dynamicPoolLessRecentlyUsed, { tasks, workerData }) } module.exports = { diff --git a/benchmarks/internal/thread/fixed.js b/benchmarks/internal/thread/fixed.js index 7ad60eeb..966fc0e1 100644 --- a/benchmarks/internal/thread/fixed.js +++ b/benchmarks/internal/thread/fixed.js @@ -1,5 +1,5 @@ const { FixedThreadPool } = require('../../../lib/index') -const { runTest } = require('../benchmark-utils') +const { runPoolifierTest } = require('../benchmark-utils') const size = 30 @@ -11,7 +11,7 @@ const fixedPool = new FixedThreadPool( async function fixedThreadTest ( { tasks, workerData } = { tasks: 1, workerData: { proof: 'ok' } } ) { - return runTest(fixedPool, { tasks, workerData }) + return runPoolifierTest(fixedPool, { tasks, workerData }) } module.exports = { fixedThreadTest } diff --git a/benchmarks/versus-external-pools/bench.sh b/benchmarks/versus-external-pools/bench.sh index cf17aabe..b6c339f8 100755 --- a/benchmarks/versus-external-pools/bench.sh +++ b/benchmarks/versus-external-pools/bench.sh @@ -15,7 +15,7 @@ export TASK_TYPE=$taskType export NODE_ENV=production export POOL_SIZE=10 export NUM_ITERATIONS=100000 -hyperfine --export-markdown BENCH-100000.MD --min-runs 10 \ +hyperfine --export-markdown BENCH-100000.md --min-runs 10 \ --prepare 'sleep 15' \ 'node dynamic-piscina.js' \ 'node fixed-piscina.js' \ -- 2.34.1