Benchmarks ========== The tests/benchmark directory contains a number of small tests to help profile the Slate VM and image performance. Currently most of these are from the latest incarnation of "The Computer Language Shootout" (http://shootout.alioth.debian.org/). As such they are not typical Slate code, use little of the Slate standard library, and are implemented with a very limited focus. Despite this they do give a quick indication of significant changes in VM performance and will hopefully evolve over time into more targetted and sophisticated tests. Running ======= To run the benchmarks build the time plug-in ('make time'), ensure your dynamic library path variable (e.g. LD_LIBRARY_PATH) is set to point to the Slate top-level directory, and then evaluate the following from the REPL: Slate 5> load: 'tests/benchmark/init.slate'. runAllBenchmarks. Alternatively run 'make benchmark' from the top-level directory. A detailed profile of the VM using the GNU Profiler (gprof) may be obtained by building an instrumented VM ('make PROFILE=1'), evaluating some test code (e.g. 'make check'), and then dumping the contents of the generated gmon.out file using 'gprof vm gmon.out'. Shootout Tests ============== For reference individual test descriptions from The Computer Language Shootout are provided below. The functionality of each benchmark is validated using tests in the tests/regression directory. ackermann --------- Each program should calculate the Ackermann function using the same naive recursive-algorithm A(x,y) x = 0 = y+1 y = 0 = A(x-1,1) otherwise = A(x-1, A(x,y-1)) Calculate A(3,N). Correct output N = 4 is: A(3,4): 125 The Ackermann benchmark is described in Timing Trials, or, the Trials of Timing: Experiments with Scripting and User-Interface Languages. For more information see Eric W. Weisstein, "Ackermann Function." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/AckermannFunction.html binary-trees ------------ Each program should * define a tree node class and methods, a tree node record and procedures, or an algebraic data type and functions, or… * allocate a binary tree to 'stretch' memory, check it exists, and deallocate it * allocate a long-lived binary tree which will live-on while other trees are allocated and deallocated * allocate, walk, and deallocate many bottom-up binary trees o allocate a tree o walk the tree nodes, checksum node items (and maybe deallocate the node) o deallocate the tree * check that the long-lived binary tree still exists (Note: the left subtrees are heads of the right subtrees, keeping a depth counter in the accessors to avoid duplication is cheating!) Correct output N = 10 is: stretch tree of depth 11 check: -1 2048 trees of depth 4 check: -2048 512 trees of depth 6 check: -512 128 trees of depth 8 check: -128 32 trees of depth 10 check: -32 long lived tree of depth 10 check: -1 The binary-trees benchmark is a simplistic adaptation of Hans Boehm's GCBench, which in turn was adapted from a benchmark by John Ellis and Pete Kovac. fannkuch -------- Each program should * "Take a permutation of {1,...,n}, for example: {4,2,1,5,3}. * Take the first element, here 4, and reverse the order of the first 4 elements: {5,1,2,4,3}. * Repeat this until the first element is a 1, so flipping won't change anything more: {3,4,2,1,5}, {2,4,3,1,5}, {4,2,3,1,5}, {1,3,2,4,5}. * Count the number of flips, here 5. * Do this for all n! permutations, and record the maximum number of flips needed for any permutation. The conjecture is that this maximum count is approximated by n*log(n) when n goes to infinity. FANNKUCH is an abbreviation for the German word Pfannkuchen, or pancakes, in analogy to flipping pancakes." Each program should generate the same sequence of n! permutations - Correct output N = 7 is: Pfannkuchen(7) = 16 Correct output N = 8 is: Pfannkuchen(8) = 22 The fannkuch benchmark is defined in Performing Lisp Analysis of the FANNKUCH Benchmark, Kenneth R. Anderson and Duane Rettig. harmonic -------- Each program should calculate the partial sum of the Harmonic series using the same naive double-precision algorithm. Correct output N = 10,000,000 is: 16.695311366 For more information see Eric W. Weisstein, "Harmonic Series." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/HarmonicSeries.html mandelbrot ---------- Each program should plot the Mandelbrot set [-1.5-i,0.5+i] on an N-by-N bitmap. Write output byte-by-byte in portable bitmap format. Correct output N = 200 is in this 5KB output file. Mandlebrot output N=200,converted to PNG For more information see Eric W. Weisstein, "Mandelbrot Set." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/MandelbrotSet.html nbody ----- Each program should model the orbits of Jovian planets, using the same simple symplectic-integrator - see the Java program. Correct output N = 1000 is -0.169075164 -0.169087605 For background information see N-body problem. Useful symplectic integrators are freely available, for example the HNBody Symplectic Integration Package. pidigits -------- Each program should use the same step-by-step spigot algorithm to calculate digits of Pi. Each program should * calculate the first N digits of Pi * print the digits 10-to-a-line, with the running total of digits calculated Programs should adapt the step-by-step algorithm given on pages 4,6 & 7 of Unbounded Spigot Algorithms for the Digits of Pi. Correct output N = 27 is: 3141592653 :10 5897932384 :20 6264338 :27 For more information see Eric W. Weisstein, "Pi Digits." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/PiDigits.html random ------ Implement a function that generates a random double-precision floating point number using a linear congruential generator as described in Numerical Recipes in C by Press, Flannery, Teukolsky, Vetterling, section 7.1. S[j] = (A * S[j-1] + C) modulo M R = N * S[j] / M A (multiplier), C (increment), M (modulus) are appropriately chosen integral constants. S[j] (seed) is calculated from S[j-1] R (random number) is normalized to the interval [N,0]. Correct output N = 1000 is: 8.163294467 Each program should use symbolic constants (or whatever is closest) to define the A, C, and M constants in the algorithm, not literal constants. spectral-norm ------------- Each program should calculate the spectral norm of an infinite matrix A, with entries a11=1, a12=1/2, a21=1/3, a13=1/4, a22=1/5, a31=1/6, etc Each program must implement 4 separate functions / procedures / methods like the C# program. Correct output N = 100 is: 1.274219991 For more information see challenge #3 in Eric W. Weisstein, "Hundred-Dollar, Hundred-Digit Challenge Problems" and "Spectral Norm" From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/Hundred-DollarHundred-DigitChallengeProblems.html http://mathworld.wolfram.com/SpectralNorm.html startup ------- Each program should print "hello world" and exit. Correct output N = 1 is: hello world This benchmark measures startup costs. It is run differently than the others - each program is run N times in a loop by a shell script wrapper. The CPU Times measured in this test are used to adjust CPU Time for the other benchmarks. takfp ----- Each program should calculate this TAK function using the same naive floating-point recursive-algorithm TAK(x,y,z) y < x = TAK(TAK(x-1.0,y,z),TAK(y-1.0,z,x),TAK(z-1.0,x,y)) y >= x = z Calculate TAK(3.0, 2.0, 1.0). Correct output N = 7 is: 14.0 Correct output N = 8 is: 9.0 Correct output N = 9 is: 18.0 Correct output N = 10 is: 11.0 The tak benchmark is described in Performance and Evaluation of Lisp Systems, Richard P. Gabriel, 1985, page 81. (1.1MB pdf) For more information see Eric W. Weisstein, "TAK Function." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/TAKFunction.html