Sort by number (v12)

Revision 12 of this benchmark created on

Description

Sort by number (without mutation)

Setup

const items = Array.from({ length: 1e3 }).map((_, index) => {
	const publishedAt = Math.floor(Math.random() * Date.now())
  return {
    publishedAt,
    name: 'Article ' + index }
})

const sortMap = (items, key) => {
  const l = items.length
  const tmp = new Float64Array(l)
  const res = Array(l)
  const map = new Map()
  let i = l
  let j = l
  while (i--) {
    const item = items[i]
    const v = item[key]
    if (typeof v === 'number') {
      const k = v * l + i
      map.set(k, item)
      tmp[i] = k
    } else {
      res[--j] = item
    }
  }
  const sorted = tmp.subarray(0, j).sort()
  while (j--) {
    res[j] = map.get(sorted[j])
  }
  return res
}

const sortSmart = (items, key) => {
  const l = items.length
  const b = 32 - Math.clz32(l)
  const x = 1 << b
  const m = x - 1
  const tmp = new Float64Array(l)
  const res = Array(l)
  let i = l
  let j = l
  while (i--) {
    const item = items[i]
    const v = item[key]
    if (typeof v === 'number') {
      tmp[i] = v * x + i
    } else {
      res[--j] = item
    }
  }
  const sorted = tmp.subarray(0, j).sort()
  while (j--) {
    res[j] = items[sorted[j] & m]
  }
  return res
}

const sortMap2 = (items, key) => {
  const l = items.length
  const tmp = new Float64Array(l)
  const res = Array(l)
  const map = new Map()
  let i = l
  let j = l
  let n = 0

  while (i--) {
    const item = items[i]
    const v = item[key]
    if (typeof v === 'number') {
      const store = map.get(v)
      if (store === undefined) {
        map.set(v, [item])
        tmp[n++] = v
      } else {
        map.set(v, [item, store])
      }
    } else {
      res[--j] = item
    }
  }

  let k = l - n
  const sorted = tmp.subarray(0, k).sort()
  while (k--) {
    let store = map.get(sorted[k])
    while (store) {
      res[--j] = store[0]
      store = store[1]
    }
  }
  return res
}

Test runner

Ready to run.

Testing in
TestOps/sec
native sort
const sorted = Array.from(items).sort((a,b) => a.publishedAt - b.publishedAt)
ready
native toSorted
const sorted = items.toSorted((a,b) => a.publishedAt - b.publishedAt)
ready
sortSmart
const sorted = sortSmart(items, 'publishedAt')
ready
sortMap
const sorted = sortMap(items, 'publishedAt')
ready
sortMap2
const sorted = sortMap2(items, 'publishedAt')
ready

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.