build(deps): bump poolifier
[poolifier.git] / benchmarks / worker-selection / least.mjs
CommitLineData
c7ed5d3b 1import { randomInt } from 'node:crypto'
ded253e2 2
e0eafaff 3import { bench, group, run } from 'tatami-ng'
74750c7f 4
292ad316
JB
5function generateRandomTasksMap (
6 numberOfWorkers,
7 maxNumberOfTasksPerWorker = 10
8) {
9 const tasksArray = []
10 for (let i = 0; i < numberOfWorkers; i++) {
c7ed5d3b 11 const task = [i, randomInt(maxNumberOfTasksPerWorker)]
292ad316
JB
12 tasksArray.push(task)
13 }
14 return new Map(tasksArray)
15}
16
17const tasksMap = generateRandomTasksMap(60, 20)
74750c7f
JB
18
19function loopSelect (tasksMap) {
74750c7f 20 let minKey
2d909eab 21 let minValue = Infinity
74750c7f
JB
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
292ad316 53const randomPivotIndexSelect = (leftIndex, rightIndex) => {
c7ed5d3b 54 return randomInt(leftIndex, rightIndex)
292ad316
JB
55}
56
74750c7f
JB
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
292ad316 73 for (let i = leftIndex; i < rightIndex; i++) {
74750c7f
JB
74 if (compare(array[i], pivotValue)) {
75 swap(array, storeIndex, i)
292ad316 76 storeIndex++
74750c7f
JB
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 },
292ad316 144 randomPivotIndexSelect
74750c7f
JB
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 },
292ad316 167 randomPivotIndexSelect
74750c7f
JB
168 )
169}
170
0804b9b4
JB
171group('Least used worker tasks distribution', () => {
172 bench('Loop select', () => {
74750c7f 173 loopSelect(tasksMap)
f1c674cd 174 })
0804b9b4 175 bench('Array sort select', () => {
74750c7f 176 arraySortSelect(tasksMap)
f1c674cd 177 })
0804b9b4 178 bench('Quick select loop', () => {
74750c7f 179 quickSelectLoop(tasksMap)
f1c674cd 180 })
0804b9b4 181 bench('Quick select loop with random pivot', () => {
74750c7f 182 quickSelectLoopRandomPivot(tasksMap)
f1c674cd 183 })
0804b9b4 184 bench('Quick select recursion', () => {
74750c7f 185 quickSelectRecursion(tasksMap)
f1c674cd 186 })
0804b9b4 187 bench('Quick select recursion with random pivot', () => {
74750c7f 188 quickSelectRecursionRandomPivot(tasksMap)
f1c674cd 189 })
0804b9b4
JB
190})
191
192await run({ units: true })