benchmarks/worker-selection/least.mjs

   1 import { randomInt } from 'node:crypto'
   2
   3 import { bench, group, run } from 'tatami-ng'
   4
   5 /**
   6  *
   7  * @param numberOfWorkers
   8  * @param maxNumberOfTasksPerWorker
   9  */
  10 function generateRandomTasksMap (
  11   numberOfWorkers,
  12   maxNumberOfTasksPerWorker = 10
  13 ) {
  14   const tasksArray = []
  15   for (let i = 0; i < numberOfWorkers; i++) {
  16     const task = [i, randomInt(maxNumberOfTasksPerWorker)]
  17     tasksArray.push(task)
  18   }
  19   return new Map(tasksArray)
  20 }
  21
  22 const tasksMap = generateRandomTasksMap(60, 20)
  23
  24 /**
  25  *
  26  * @param tasksMap
  27  */
  28 function loopSelect (tasksMap) {
  29   let minKey
  30   let minValue = Number.POSITIVE_INFINITY
  31   for (const [key, value] of tasksMap) {
  32     if (value === 0) {
  33       return key
  34     } else if (value < minValue) {
  35       minKey = key
  36       minValue = value
  37     }
  38   }
  39   return [minKey, minValue]
  40 }
  41
  42 /**
  43  *
  44  * @param tasksMap
  45  */
  46 function arraySortSelect (tasksMap) {
  47   const tasksArray = Array.from(tasksMap)
  48   return tasksArray.sort((a, b) => {
  49     if (a[1] < b[1]) {
  50       return -1
  51     } else if (a[1] > b[1]) {
  52       return 1
  53     }
  54     return 0
  55   })[0]
  56 }
  57
  58 const defaultComparator = (a, b) => {
  59   return a < b
  60 }
  61
  62 const defaultPivotIndexSelect = (leftIndex, rightIndex) => {
  63   return leftIndex + Math.floor((rightIndex - leftIndex) / 2)
  64 }
  65
  66 const randomPivotIndexSelect = (leftIndex, rightIndex) => {
  67   return randomInt(leftIndex, rightIndex)
  68 }
  69
  70 /**
  71  *
  72  * @param array
  73  * @param index1
  74  * @param index2
  75  */
  76 function swap (array, index1, index2) {
  77   const tmp = array[index1]
  78   array[index1] = array[index2]
  79   array[index2] = tmp
  80 }
  81
  82 /**
  83  *
  84  * @param array
  85  * @param leftIndex
  86  * @param rightIndex
  87  * @param pivotIndex
  88  * @param compare
  89  */
  90 function partition (
  91   array,
  92   leftIndex,
  93   rightIndex,
  94   pivotIndex,
  95   compare = defaultComparator
  96 ) {
  97   const pivotValue = array[pivotIndex]
  98   swap(array, pivotIndex, rightIndex)
  99   let storeIndex = leftIndex
 100   for (let i = leftIndex; i < rightIndex; i++) {
 101     if (compare(array[i], pivotValue)) {
 102       swap(array, storeIndex, i)
 103       storeIndex++
 104     }
 105   }
 106   swap(array, rightIndex, storeIndex)
 107   return storeIndex
 108 }
 109
 110 /**
 111  *
 112  * @param array
 113  * @param k
 114  * @param leftIndex
 115  * @param rightIndex
 116  * @param compare
 117  * @param pivotIndexSelect
 118  */
 119 function selectLoop (
 120   array,
 121   k,
 122   leftIndex,
 123   rightIndex,
 124   compare = defaultComparator,
 125   pivotIndexSelect = defaultPivotIndexSelect
 126 ) {
 127   while (true) {
 128     if (leftIndex === rightIndex) return array[leftIndex]
 129     let pivotIndex = pivotIndexSelect(leftIndex, rightIndex)
 130     pivotIndex = partition(array, leftIndex, rightIndex, pivotIndex, compare)
 131     if (k === pivotIndex) {
 132       return array[k]
 133     } else if (k < pivotIndex) {
 134       rightIndex = pivotIndex - 1
 135     } else {
 136       leftIndex = pivotIndex + 1
 137     }
 138   }
 139 }
 140
 141 /**
 142  *
 143  * @param array
 144  * @param k
 145  * @param leftIndex
 146  * @param rightIndex
 147  * @param compare
 148  * @param pivotIndexSelect
 149  */
 150 function selectRecursion (
 151   array,
 152   k,
 153   leftIndex,
 154   rightIndex,
 155   compare = defaultComparator,
 156   pivotIndexSelect = defaultPivotIndexSelect
 157 ) {
 158   if (leftIndex === rightIndex) return array[leftIndex]
 159   let pivotIndex = pivotIndexSelect(leftIndex, rightIndex)
 160   pivotIndex = partition(array, leftIndex, rightIndex, pivotIndex, compare)
 161   if (k === pivotIndex) {
 162     return array[k]
 163   } else if (k < pivotIndex) {
 164     return selectRecursion(array, k, leftIndex, pivotIndex - 1, compare)
 165   } else {
 166     return selectRecursion(array, k, pivotIndex + 1, rightIndex, k, compare)
 167   }
 168 }
 169
 170 /**
 171  *
 172  * @param tasksMap
 173  */
 174 function quickSelectLoop (tasksMap) {
 175   const tasksArray = Array.from(tasksMap)
 176
 177   return selectLoop(tasksArray, 0, 0, tasksArray.length - 1, (a, b) => {
 178     return a[1] < b[1]
 179   })
 180 }
 181
 182 /**
 183  *
 184  * @param tasksMap
 185  */
 186 function quickSelectLoopRandomPivot (tasksMap) {
 187   const tasksArray = Array.from(tasksMap)
 188
 189   return selectLoop(
 190     tasksArray,
 191     0,
 192     0,
 193     tasksArray.length - 1,
 194     (a, b) => {
 195       return a[1] < b[1]
 196     },
 197     randomPivotIndexSelect
 198   )
 199 }
 200
 201 /**
 202  *
 203  * @param tasksMap
 204  */
 205 function quickSelectRecursion (tasksMap) {
 206   const tasksArray = Array.from(tasksMap)
 207
 208   return selectRecursion(tasksArray, 0, 0, tasksArray.length - 1, (a, b) => {
 209     return a[1] < b[1]
 210   })
 211 }
 212
 213 /**
 214  *
 215  * @param tasksMap
 216  */
 217 function quickSelectRecursionRandomPivot (tasksMap) {
 218   const tasksArray = Array.from(tasksMap)
 219
 220   return selectRecursion(
 221     tasksArray,
 222     0,
 223     0,
 224     tasksArray.length - 1,
 225     (a, b) => {
 226       return a[1] < b[1]
 227     },
 228     randomPivotIndexSelect
 229   )
 230 }
 231
 232 group('Least used worker tasks distribution', () => {
 233   bench('Loop select', () => {
 234     loopSelect(tasksMap)
 235   })
 236   bench('Array sort select', () => {
 237     arraySortSelect(tasksMap)
 238   })
 239   bench('Quick select loop', () => {
 240     quickSelectLoop(tasksMap)
 241   })
 242   bench('Quick select loop with random pivot', () => {
 243     quickSelectLoopRandomPivot(tasksMap)
 244   })
 245   bench('Quick select recursion', () => {
 246     quickSelectRecursion(tasksMap)
 247   })
 248   bench('Quick select recursion with random pivot', () => {
 249     quickSelectRecursionRandomPivot(tasksMap)
 250   })
 251 })
 252
 253 await run({ units: true })