proc rdtsc(): int64 =
var hi, lo: uint32
asm """
rdtsc
:"=a"(`lo`), "=d"(`hi`)
"""
result = int64(lo) or (int64(hi) shl 32)
proc sort1(d: var openarray[int]) =
template SWAP(x, y: int) =
let a = min(d[x], d[y])
let b = max(d[x], d[y])
d[x] = a
d[y] = b
SWAP(1, 2)
SWAP(4, 5)
SWAP(0, 2)
SWAP(3, 5)
SWAP(0, 1)
SWAP(3, 4)
SWAP(1, 4)
SWAP(0, 3)
SWAP(2, 5)
SWAP(1, 3)
SWAP(2, 4)
SWAP(2, 3)
proc sort2(d: var openarray[int]) =
template SWAP(x, y: int) =
if d[x] > d[y]: swap(d[x], d[y])
SWAP(1, 2)
SWAP(4, 5)
SWAP(0, 2)
SWAP(3, 5)
SWAP(0, 1)
SWAP(3, 4)
SWAP(1, 4)
SWAP(0, 3)
SWAP(2, 5)
SWAP(1, 3)
SWAP(2, 4)
SWAP(2, 3)
proc testIt =
var a = [0,1,2,3,4,5]
var b = [5,4,3,2,1,0]
var x: array [6, int]
var now, start: int64
x = a
start = rdtsc()
sort1(x)
now = rdtsc()
echo(repr(x))
echo "Cycles: " & $(now - start)
x = b
start = rdtsc()
sort1(x)
now = rdtsc()
echo(repr(x))
echo "Cycles: " & $(now - start)
x = a
start = rdtsc()
sort2(x)
now = rdtsc()
echo(repr(x))
echo "Cycles: " & $(now - start)
x = b
start = rdtsc()
sort2(x)
now = rdtsc()
echo(repr(x))
echo "Cycles: " & $(now - start)
when isMainModule:
testIt()
Recently I found
http://stackoverflow.com/questions/2786899/fastest-sort-of-fixed-length-6-int-array
That seems to be possible in C with only 26 clock cycles.
And indeed the Nim code version needs also only 26 cycles for a single array.
When I test with above code, I get these 26 cycles for the second value, and much more for the other 3:
[0, 1, 2, 3, 4, 5]
Cycles: 290
[0, 1, 2, 3, 4, 5]
Cycles: 26
[0, 1, 2, 3, 4, 5]
Cycles: 304
[0, 1, 2, 3, 4, 5]
Cycles: 212
Well, more meaningful and even more funny is this code with random numbers, where the compilers really can not remove the proc calls:
import random
proc rdtsc(): int64 =
var hi, lo: uint32
asm """
rdtsc
:"=a"(`lo`), "=d"(`hi`)
"""
result = int64(lo) or (int64(hi) shl 32)
proc sort1(d: var openarray[int]) {.inline.} =
template SWAP(x, y: int) =
let a = min(d[x], d[y])
let b = max(d[x], d[y])
d[x] = a
d[y] = b
SWAP(1, 2)
SWAP(4, 5)
SWAP(0, 2)
SWAP(3, 5)
SWAP(0, 1)
SWAP(3, 4)
SWAP(1, 4)
SWAP(0, 3)
SWAP(2, 5)
SWAP(1, 3)
SWAP(2, 4)
SWAP(2, 3)
proc sort2(d: var openarray[int]) =
template SWAP(x, y: int) =
if d[x] > d[y]: swap(d[x], d[y])
SWAP(1, 2)
SWAP(4, 5)
SWAP(0, 2)
SWAP(3, 5)
SWAP(0, 1)
SWAP(3, 4)
SWAP(1, 4)
SWAP(0, 3)
SWAP(2, 5)
SWAP(1, 3)
SWAP(2, 4)
SWAP(2, 3)
proc testIt =
var a = [0,1,2,3,4,5]
var b = [5,4,3,2,1,0]
var x: array [6, int]
var now, start: int64
for i in 0 .. 5: x[i] = random(6)
start = rdtsc()
sort1(x)
now = rdtsc()
echo(repr(x))
echo "Cycles: " & $(now - start)
for i in 0 .. 5: x[i] = random(6)
start = rdtsc()
sort1(x)
now = rdtsc()
echo(repr(x))
echo "Cycles: " & $(now - start)
for i in 0 .. 5: x[i] = random(6)
start = rdtsc()
sort2(x)
now = rdtsc()
echo(repr(x))
echo "Cycles: " & $(now - start)
for i in 0 .. 5: x[i] = random(6)
start = rdtsc()
sort2(x)
now = rdtsc()
echo(repr(x))
echo "Cycles: " & $(now - start)
when isMainModule:
testIt()
[0, 2, 2, 5, 5, 5]
Cycles: 36
[0, 0, 2, 2, 4, 5]
Cycles: 36
[0, 2, 2, 3, 4, 4]
Cycles: 140
[0, 0, 0, 3, 3, 5]
Cycles: 164