Merge branch 'master' of github.com:jerome-benoit/poolifier
[poolifier.git] / benchmarks / worker-selection / less.mjs
1 import Benchmark from 'benny'
2 import { generateRandomInteger } from '../benchmarks-utils.mjs'
3
4 function 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
16 const tasksMap = generateRandomTasksMap(60, 20)
17
18 function loopSelect (tasksMap) {
19 let minValue = Infinity
20 let minKey
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
32 function 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
44 const defaultComparator = (a, b) => {
45 return a < b
46 }
47
48 const defaultPivotIndexSelect = (leftIndex, rightIndex) => {
49 return leftIndex + Math.floor((rightIndex - leftIndex) / 2)
50 }
51
52 const randomPivotIndexSelect = (leftIndex, rightIndex) => {
53 return generateRandomInteger(rightIndex, leftIndex)
54 }
55
56 function swap (array, index1, index2) {
57 const tmp = array[index1]
58 array[index1] = array[index2]
59 array[index2] = tmp
60 }
61
62 function 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
72 for (let i = leftIndex; i < rightIndex; i++) {
73 if (compare(array[i], pivotValue)) {
74 swap(array, storeIndex, i)
75 storeIndex++
76 }
77 }
78 swap(array, rightIndex, storeIndex)
79 return storeIndex
80 }
81
82 function 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
104 function 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
124 function 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
132 function 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 },
143 randomPivotIndexSelect
144 )
145 }
146
147 function 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
155 function 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 },
166 randomPivotIndexSelect
167 )
168 }
169
170 Benchmark.suite(
171 'Least used worker tasks distribution',
172 Benchmark.add('Loop select', () => {
173 loopSelect(tasksMap)
174 }),
175 Benchmark.add('Array sort select', () => {
176 arraySortSelect(tasksMap)
177 }),
178 Benchmark.add('Quick select loop', () => {
179 quickSelectLoop(tasksMap)
180 }),
181 Benchmark.add('Quick select loop with random pivot', () => {
182 quickSelectLoopRandomPivot(tasksMap)
183 }),
184 Benchmark.add('Quick select recursion', () => {
185 quickSelectRecursion(tasksMap)
186 }),
187 Benchmark.add('Quick select recursion with random pivot', () => {
188 quickSelectRecursionRandomPivot(tasksMap)
189 }),
190 Benchmark.cycle(),
191 Benchmark.complete()
192 )