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