benchmarks/worker-selection/least.mjs

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