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