fix: ensure worker node is defined before emitting
[poolifier.git] / benchmarks / worker-selection / least.mjs
... / ...
CommitLineData
1import { randomInt } from 'node:crypto'
2import Benchmark from 'benchmark'
3import { LIST_FORMATTER } from '../benchmarks-utils.cjs'
4
5function generateRandomTasksMap (
6 numberOfWorkers,
7 maxNumberOfTasksPerWorker = 10
8) {
9 const tasksArray = []
10 for (let i = 0; i < numberOfWorkers; i++) {
11 const task = [i, randomInt(maxNumberOfTasksPerWorker)]
12 tasksArray.push(task)
13 }
14 return new Map(tasksArray)
15}
16
17const tasksMap = generateRandomTasksMap(60, 20)
18
19function loopSelect (tasksMap) {
20 let minKey
21 let minValue = Infinity
22 for (const [key, value] of tasksMap) {
23 if (value === 0) {
24 return key
25 } else if (value < minValue) {
26 minKey = key
27 minValue = value
28 }
29 }
30 return [minKey, minValue]
31}
32
33function arraySortSelect (tasksMap) {
34 const tasksArray = Array.from(tasksMap)
35 return tasksArray.sort((a, b) => {
36 if (a[1] < b[1]) {
37 return -1
38 } else if (a[1] > b[1]) {
39 return 1
40 }
41 return 0
42 })[0]
43}
44
45const defaultComparator = (a, b) => {
46 return a < b
47}
48
49const defaultPivotIndexSelect = (leftIndex, rightIndex) => {
50 return leftIndex + Math.floor((rightIndex - leftIndex) / 2)
51}
52
53const randomPivotIndexSelect = (leftIndex, rightIndex) => {
54 return randomInt(leftIndex, rightIndex)
55}
56
57function swap (array, index1, index2) {
58 const tmp = array[index1]
59 array[index1] = array[index2]
60 array[index2] = tmp
61}
62
63function partition (
64 array,
65 leftIndex,
66 rightIndex,
67 pivotIndex,
68 compare = defaultComparator
69) {
70 const pivotValue = array[pivotIndex]
71 swap(array, pivotIndex, rightIndex)
72 let storeIndex = leftIndex
73 for (let i = leftIndex; i < rightIndex; i++) {
74 if (compare(array[i], pivotValue)) {
75 swap(array, storeIndex, i)
76 storeIndex++
77 }
78 }
79 swap(array, rightIndex, storeIndex)
80 return storeIndex
81}
82
83function selectLoop (
84 array,
85 k,
86 leftIndex,
87 rightIndex,
88 compare = defaultComparator,
89 pivotIndexSelect = defaultPivotIndexSelect
90) {
91 while (true) {
92 if (leftIndex === rightIndex) return array[leftIndex]
93 let pivotIndex = pivotIndexSelect(leftIndex, rightIndex)
94 pivotIndex = partition(array, leftIndex, rightIndex, pivotIndex, compare)
95 if (k === pivotIndex) {
96 return array[k]
97 } else if (k < pivotIndex) {
98 rightIndex = pivotIndex - 1
99 } else {
100 leftIndex = pivotIndex + 1
101 }
102 }
103}
104
105function selectRecursion (
106 array,
107 k,
108 leftIndex,
109 rightIndex,
110 compare = defaultComparator,
111 pivotIndexSelect = defaultPivotIndexSelect
112) {
113 if (leftIndex === rightIndex) return array[leftIndex]
114 let pivotIndex = pivotIndexSelect(leftIndex, rightIndex)
115 pivotIndex = partition(array, leftIndex, rightIndex, pivotIndex, compare)
116 if (k === pivotIndex) {
117 return array[k]
118 } else if (k < pivotIndex) {
119 return selectRecursion(array, k, leftIndex, pivotIndex - 1, compare)
120 } else {
121 return selectRecursion(array, k, pivotIndex + 1, rightIndex, k, compare)
122 }
123}
124
125function quickSelectLoop (tasksMap) {
126 const tasksArray = Array.from(tasksMap)
127
128 return selectLoop(tasksArray, 0, 0, tasksArray.length - 1, (a, b) => {
129 return a[1] < b[1]
130 })
131}
132
133function quickSelectLoopRandomPivot (tasksMap) {
134 const tasksArray = Array.from(tasksMap)
135
136 return selectLoop(
137 tasksArray,
138 0,
139 0,
140 tasksArray.length - 1,
141 (a, b) => {
142 return a[1] < b[1]
143 },
144 randomPivotIndexSelect
145 )
146}
147
148function quickSelectRecursion (tasksMap) {
149 const tasksArray = Array.from(tasksMap)
150
151 return selectRecursion(tasksArray, 0, 0, tasksArray.length - 1, (a, b) => {
152 return a[1] < b[1]
153 })
154}
155
156function quickSelectRecursionRandomPivot (tasksMap) {
157 const tasksArray = Array.from(tasksMap)
158
159 return selectRecursion(
160 tasksArray,
161 0,
162 0,
163 tasksArray.length - 1,
164 (a, b) => {
165 return a[1] < b[1]
166 },
167 randomPivotIndexSelect
168 )
169}
170
171new Benchmark.Suite('Least used worker tasks distribution')
172 .add('Loop select', () => {
173 loopSelect(tasksMap)
174 })
175 .add('Array sort select', () => {
176 arraySortSelect(tasksMap)
177 })
178 .add('Quick select loop', () => {
179 quickSelectLoop(tasksMap)
180 })
181 .add('Quick select loop with random pivot', () => {
182 quickSelectLoopRandomPivot(tasksMap)
183 })
184 .add('Quick select recursion', () => {
185 quickSelectRecursion(tasksMap)
186 })
187 .add('Quick select recursion with random pivot', () => {
188 quickSelectRecursionRandomPivot(tasksMap)
189 })
190 .on('cycle', event => {
191 console.info(event.target.toString())
192 })
193 .on('complete', function () {
194 console.info(
195 'Fastest is ' + LIST_FORMATTER.format(this.filter('fastest').map('name'))
196 )
197 })
198 .run()