Sort by number (v5)

Revision 5 of this benchmark created on

Description

Sort by number (without mutation)

Setup

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


const sortByNumber = (items, key) => {
  const l = items.length
  const b = 32 - Math.clz32(l)
  const m = (1 << b) - 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 << b) | i
    } else {
      res[--j] = item
    }
  }
  const sorted = tmp.subarray(0, j).sort()
  while (j--) {
    res[j] = items[sorted[j] & m]
  }
  return res
}

const sortByNumberMath = (items, key) => {
  const l = items.length
  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 * l + i
    } else {
      res[--j] = item
    }
  }
  const sorted = tmp.subarray(0, j).sort()
  while (j--) {
    res[j] = items[sorted[j] % l]
  }
  return res
}

const sortByNumberExp = (items, key) => {
  const l = items.length
  const b = 32 - Math.clz32(l)
  const x = Math.pow(2, b)
  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] % l]
  }
  return res
}

const sortByNumberBigInt = (items, key) => {
  const l = items.length
  const b = 32 - Math.clz32(l)
  const m = BigInt((1 << b) - 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] = Number((BigInt(v) << BigInt(b)) | BigInt(i))
    } else {
      res[--j] = item
    }
  }
  const sorted = tmp.subarray(0, j).sort()

  while (j--) {
    res[j] = items[Number(BigInt(sorted[j]) & m)]
  }
  return res
}

const sortByNumberAlt = (items, key) => {
  const l = items.length
  const b = 32 - Math.clz32(l)
  const m = (1 << b) - 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 * 2 ** b + i
    } else {
      res[--j] = item
    }
  }
  const sorted = tmp.subarray(0, j).sort()

  while (j--) {
    res[j] = items[sorted[j] % (1 << b)]
  }
  return res
}

const sortByNumberMathOrBits = (items, key) => {
  const l = items.length
  const b = 32 - Math.clz32(l)
  const m = (1 << b) - 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] = Math.clz32(v) < b ? v * 2 ** b + i : (v << b) | i
    } else {
      res[--j] = item
    }
  }

  const sorted = tmp.subarray(0, j).sort()
  while (j--) {
    const v = sorted[j]
    res[j] = items[v >>> 0 === v ? v & m : v % (1 << b)]
  }
  return res
}

const sortByBigInt = (items, key) => {
  const l = items.length
  const b = BigInt(32 - Math.clz32(l))
  const m = (1n << b) - 1n
  const tmp = new BigInt64Array(l)
  const res = Array(l)
  let i = l
  let bi = BigInt(l)
  let j = l
  while (i--) {
    const item = items[i]
    const v = item[key]
    bi--
    if (typeof v === 'number') {
      tmp[i] = (BigInt(v) << b) | bi
    } else {
      res[--j] = item
    }
  }
  const sorted = tmp.subarray(0, j).sort()
  while (j--) {
    res[j] = items[Number(sorted[j] & m)]
  }
  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
sortByNumber
const sorted = sortByNumber(items, 'publishedAt')
ready
sortByNumberMath
const sorted = sortByNumberMath(items, 'publishedAt')
ready
sortByNumberExp
const sorted = sortByNumberExp(items, 'publishedAt')
ready
sortByNumberBigInt
const sorted = sortByNumberBigInt(items, 'publishedAt')
ready
sortByNumberAlt
const sorted = sortByNumberAlt(items, 'publishedAt')
ready
sortByNumberMathOrBits
const sorted = sortByNumberMathOrBits(items, 'publishedAt')
ready
sortByBigInt
const sorted = sortByBigInt(items, 'publishedAt')
ready

Revisions

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