benchmarks/worker-selection/least.mjs

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