benchmarks/worker-selection/lru.js

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