build(deps): bump poolifier
[poolifier.git] / benchmarks / worker-selection / least.mjs
1 import { randomInt } from 'node:crypto'
2
3 import { bench, group, run } from 'tatami-ng'
4
5 function 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
17 const tasksMap = generateRandomTasksMap(60, 20)
18
19 function 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
33 function 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
45 const defaultComparator = (a, b) => {
46 return a < b
47 }
48
49 const defaultPivotIndexSelect = (leftIndex, rightIndex) => {
50 return leftIndex + Math.floor((rightIndex - leftIndex) / 2)
51 }
52
53 const randomPivotIndexSelect = (leftIndex, rightIndex) => {
54 return randomInt(leftIndex, rightIndex)
55 }
56
57 function swap (array, index1, index2) {
58 const tmp = array[index1]
59 array[index1] = array[index2]
60 array[index2] = tmp
61 }
62
63 function 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
83 function 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
105 function 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
125 function 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
133 function 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
148 function 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
156 function 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
171 group('Least used worker tasks distribution', () => {
172 bench('Loop select', () => {
173 loopSelect(tasksMap)
174 })
175 bench('Array sort select', () => {
176 arraySortSelect(tasksMap)
177 })
178 bench('Quick select loop', () => {
179 quickSelectLoop(tasksMap)
180 })
181 bench('Quick select loop with random pivot', () => {
182 quickSelectLoopRandomPivot(tasksMap)
183 })
184 bench('Quick select recursion', () => {
185 quickSelectRecursion(tasksMap)
186 })
187 bench('Quick select recursion with random pivot', () => {
188 quickSelectRecursionRandomPivot(tasksMap)
189 })
190 })
191
192 await run({ units: true })