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