Added benchmark tool and some benchmarks.

2 files changed, 123 insertions, 0 deletions

diff --git a/tests/benchmarks/fannkuch.nim b/tests/benchmarks/fannkuch.nim
new file mode 100644
index 000000000..15f78f50c
--- /dev/null
+++ b/tests/benchmarks/fannkuch.nim
@@ -0,0 +1,69 @@
+import os
+import strutils
+
+proc fannkuch (n: int): int =
+    var 
+        count: seq[int]
+        maxFlips = 0
+        m        = n-1
+        r        = n
+        check    = 0
+        perm1: seq[int]
+        perm:  seq[int]
+
+    newSeq (count, n+1)
+    newSeq (perm1, n)
+    newSeq (perm, n)
+    for i in 0 .. n-1:
+        count[i] = i+1
+        perm1[i] = i
+        perm[i]  = i
+    count[n] = n+1
+
+    while True:
+        if check < 30:
+            for i in items (perm1):
+                write (stdout, $(i+1))
+            echo ("")
+            inc (check)
+
+        while r != 1:
+            count[r-1] = r
+            dec (r)
+
+        if perm1[0] != 0 and perm1[m] != m:
+            # perm = perm1
+            # The above line is between 3 and 4 times slower than the loop below!
+            for i in 0 .. n-1:
+                perm[i] = perm1[i]
+            var flipsCount = 0
+            var k = perm[0]
+            while k != 0:
+                for i in 0 .. (k div 2):
+                    swap (perm[i], perm[k-i])
+                inc (flipsCount)
+                k = perm[0]
+
+            if flipsCount > maxFlips:
+                maxFlips = flipsCount
+
+        block makePerm:
+            while r != n:
+                var tmp = perm1[0]
+                # # perm1.delete (0)
+                # # perm1.insert (tmp, r)
+                # # The above is about twice as slow as the following:
+                # moveMem (addr (perm1[0]), addr (perm1[1]), r * sizeof (int))
+                # The call to moveMem is about 50% slower than the loop below!
+                for i in 0 .. r-1:
+                    perm1[i] = perm1[i+1]
+                perm1[r] = tmp
+                
+                dec (count[r])
+                if count[r] > 0:
+                    break makePerm
+                inc (r)
+            return maxFlips
+
+var n = 10
+echo ("Pfannkuchen(" & $n & ") = " & $fannkuch (n))
\ No newline at end of file
diff --git a/tests/benchmarks/quicksort.nim b/tests/benchmarks/quicksort.nim
new file mode 100644
index 000000000..599e3674c
--- /dev/null
+++ b/tests/benchmarks/quicksort.nim
@@ -0,0 +1,54 @@
+import os
+import strutils
+
+# Generate some pseudo-random data
+var seed: tuple[s1, s2, s3: int32] = (2'i32, 8'i32, 16'i32)
+
+proc random(): int32 =
+    seed = (((((((seed[0] and 0x0007_FFFF'i32) shl 13'i32) xor seed[0]) shr
+               19'i32) and 0x0000_1FFF'i32) xor
+             ((seed[0] and 0x000F_FFFE'i32) shl 12'i32)),
+
+            ((((((seed[1] and 0x3FFF_FFFF'i32) shl  2'i32) xor seed[1]) shr
+               25'i32) and 0x0000_007F'i32) xor
+             ((seed[1] and 0x0FFF_FFF8'i32) shl  4'i32)),
+
+            ((((((seed[2] and 0x1FFF_FFFF'i32) shl  3'i32) xor seed[2]) shr
+               11'i32) and 0x001F_FFFF'i32) xor
+             ((seed[2] and 0x0000_7FF0'i32) shl 17'i32)))
+    return seed[0] xor seed[1] xor seed[2]
+
+var n = 9999999
+
+var data: seq[int32]
+newSeq (data, n)
+for i in 0 .. data.high():
+    data[i] = random()
+
+
+proc `$` (d: seq[int32]): string =
+    result = "[ "
+    for i in items (d):
+        result.addSep (", ", 2)
+        result.add ($(i and 0xFFFF_FFFF'i64))
+    result.add (" ]")
+
+# Sort the data
+proc sort (start, stop: int) =
+    if stop <= start+1:
+        return
+
+    var j = start
+    for i in start..stop-2:
+        if data[i] <% data[stop-1]:
+            swap (data[i], data[j])
+            inc (j)
+    swap (data[j], data[stop-1])
+
+    sort (start, j)
+    sort (j+1, stop)
+
+sort (0, data.len)
+echo (data[n div 2 - 1] and 0xFFFF_FFFF'i64, ", ",
+      data[n div 2] and 0xFFFF_FFFF'i64, ", ",
+      data[n div 2 + 1] and 0xFFFF_FFFF'i64)
\ No newline at end of file