benchmarks/worker-selection/least.mjs

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