fannkuch-redux benchmark | Computer Language Benchmarks Game

fannkuch-redux benchmark N=12

Each chart bar shows how many times more Memory, one ↓ fannkuch-redux program used, compared to the program that used least Memory.

These are not the only programs that could be written. These are not the only compilers and interpreters. These are not the only programming languages.

Column × shows how many times more each program used compared to the benchmark program that used least.

×	Program Source Code	CPU secs	Elapsed secs	Memory KB	Code B	≈ CPU Load
		sort	sort		sort
1.0	Fortran Intel	68.30	68.32	260	590	0% 0% 0% 100%
1.1	ATS	58.26	58.27	288	1306	0% 0% 0% 100%
1.1	C gcc #3	44.77	44.79	288	567	0% 0% 0% 100%
1.1	ATS #2	57.80	57.82	288	1571	0% 0% 0% 100%
1.1	C++ g++ #3	50.57	50.59	292	593	0% 0% 0% 100%
1.1	C gcc #4	24.61	24.62	292	1183	1% 0% 0% 100%
1.1	C++ g++ #7	25.04	25.05	292	1150	1% 0% 0% 100%
1.1	C gcc	56.93	56.96	292	508	0% 0% 0% 100%
1.3	C gcc #2	50.77	50.79	332	1557	0% 0% 0% 100%
2.2	OCaml	146.98	147.01	576	524	0% 0% 0% 100%
2.2	OCaml #2	73.46	73.47	580	473	0% 0% 0% 100%
2.9	Pascal Free Pascal	65.33	65.35	744	1018	0% 0% 0% 100%
3.2	Lua	35 min	35 min	820	462	0% 0% 0% 100%
3.6	C++ g++	53.82	53.84	932	1059	0% 0% 0% 100%
3.8	C++ g++ #5	49.66	49.68	1,000	1440	0% 0% 0% 100%
3.9	C++ g++ #4	61.86	61.89	1,004	1439	0% 0% 0% 100%
3.9	Go	84.71	84.75	1,012	900	0% 0% 0% 100%
5.6	Perl	40 min	40 min	1,464	457	0% 0% 0% 100%
6.1	Haskell GHC #3	63.92	63.94	1,588	1153	0% 0% 0% 100%
6.4	Ada 2005 GNAT #3	39.29	39.32	1,652	2100	0% 1% 0% 100%
7.1	Haskell GHC #4	90.33	90.36	1,836	658	0% 0% 0% 100%
9.5	PHP #2	45 min	45 min	2,476	441	0% 0% 0% 100%
9.6	PHP	59 min	59 min	2,508	482	0% 0% 0% 100%
12	Haskell GHC #2	289.09	289.19	3,160	808	0% 0% 0% 100%
12	Haskell GHC	9 min	9 min	3,164	553	0% 0% 0% 100%
15	Lisp SBCL #2	101.92	101.95	3,828	513	0% 0% 0% 100%
18	Python 3 #6	48 min	53 min	4,564	385	0% 0% 0% 100%
19	Ruby 2.0	1h 06 min	1h 06 min	4,864	384	0% 0% 0% 100%
20	C CINT	2h 57 min	2h 57 min	5,116	536	0% 0% 0% 100%
21	JavaScript V8	90.73	90.76	5,472	463	0% 0% 0% 100%
21	JavaScript V8 #2	78.42	78.46	5,484	472	0% 0% 0% 100%
21	JavaScript V8 #3	71.57	71.60	5,508	539	1% 0% 0% 100%
23	Dart	23 min	23 min	5,980	531	0% 0% 0% 100%
24	Dart #2	78.75	78.77	6,264	538	0% 0% 0% 100%
29	Fortran Intel #3	69.69	69.71	7,580	1148	0% 0% 0% 100%
29	Erlang HiPE	6 min	6 min	7,644	1038	0% 0% 0% 100%
35	OCaml #4	0.00	133.22	8,996	1004	0% 0% 0% 100%
39	PHP #3	47 min	47 min	10,132	1150	0% 0% 0% 100%
52	C# Mono	116.60	116.62	13,520	520	0% 0% 0% 100%
52	C# Mono #2	69.18	69.19	13,548	564	0% 0% 0% 100%
53	Lisp SBCL #3	61.48	61.50	13,744	821	0% 0% 0% 100%
54	Java 7	71.26	71.28	13,936	1282	0% 0% 0% 100%
54	Lisp SBCL #4	57.29	57.31	14,108	1518	0% 0% 0% 100%
55	C# Mono #3	134.00	134.03	14,340	1096	0% 0% 0% 100%
55	Java 7 #2	102.74	102.77	14,420	514	0% 0% 0% 100%
58	F# Mono #2	113.62	113.64	15,148	548	0% 0% 0% 100%
58	F# Mono	5 min	5 min	15,152	551	0% 0% 0% 100%
59	Racket	5 min	5 min	15,332	649	0% 0% 0% 100%
65	F# Mono #3	136.95	136.98	16,964	945	1% 0% 0% 100%
71	OCaml #3	0.00	103.96	18,520	1017	0% 1% 0% 100%
72	Scala	97.59	97.62	18,696	459	0% 1% 0% 100%
79	Scala #2	56.56	56.58	20,472	1017	0% 1% 0% 100%
84	Smalltalk VisualWorks	10 min	10 min	21,952	838	0% 0% 0% 100%
254	Clojure #2	280.95	281.08	66,088	1088	0% 0% 0% 100%
2,243	Ruby JRuby	15 min	15 min	583,116	384	0% 0% 0% 100%
	Python 3 #2	Timed Out	1h 00 min		797
	Python 3	Timed Out	1h 00 min		1108
"wrong" (different) algorithm / less comparable programs
1.1	C++ g++ #6	38.22	38.24	292	894
3.8	C++ g++ #2	29.11	29.13	988	2106
60	Java 7 #3	41.34	41.35	15,688	1633
71	Lisp SBCL	46.66	46.68	18,528	1607

fannkuch-redux benchmark : Indexed-access to tiny integer-sequence

diff program output N = 7 with this output file to check your program is correct before contributing.

We are trying to show the performance of various programming language implementations - so we ask that contributed programs not only give the correct result, but also use the same algorithm to calculate that result.

For N = 7 programs should generate these permutations (40KB) - which, incidentally, seem to be in the same order as permutations generated by the Tompkins-Paige algorithm, see pages 150-151 Permutation Generation Methods Robert Sedgewick.

The fannkuch benchmark is defined by programs in Performing Lisp Analysis of the FANNKUCH Benchmark, Kenneth R. Anderson and Duane Rettig.

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.
Keep a checksum
- checksum = checksum + (if permutation_index is even then flips_count else -flips_count)
- checksum = checksum + (toggle_sign_-1_1 * flips_count)
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.

Thanks to Oleg Mazurov for insisting on a checksum and providing this helpful description of the approach he took -

A common idea for parallel implementation is to divide all work (n! permutations) into chunks small enough to avoid load imbalance but large enough to keep overhead low. I set the number of chunks as a parameter (NCHUNKS = 150) from which I derive the size of a chunk (CHUNKSZ) and the actual number of chunks/tasks to be processed (NTASKS), which may be different from NCHUNKS because of rounding.
Task scheduling is trivial: threads will atomically get and increment the taskId variable to derive a range of permutation indices to work on:
```
    task = taskId.getAndIncrement();
    idxMin = task * CHUNKSZ;
    idxMax = min( idxMin + CHUNKSZ, n! );
```
Maximum flip counts and partial checksums can be computed for chunks in arbitrary order and recombined to generate the required result at the final step (CHUNKSZ must be even for adding partial checksums to be associative - I didn't enforce it in my submission).
Now I need to go from a permutation index to the permutation itself.
The predefined order in which all permutations are to be generated can be described as follows: to generate n! permutations of n arbitrary numbers, rotate the numbers left (from higher position to lower) n times, so that each number appears in the n-th position, and for each rotation recursively generate (n-1)! permutations of the first n-1 numbers whatever they are.
To optimize the process I use an intermediate data structure, count[], which keeps count of how many rotations have been done at every level. Apparently, count[0] is always 0, as there is only one element at that level, which can't be rotated; count[1] = 0..1 for two elements, count[2] = 0..2 for three elements, etc.
To generate next permutation I swap the first two elements and increase count[1]. If count[1] becomes greater than 1, I'm done with rotations at level 1 and need to "return" (as it would have been in the recursive implementation) to level 2. Now, I rotate 3 elements and increment count[2]. If it becomes greater than 2, I'm done with level 2 and need to go to level 3, etc.
It should be clear now how to generate a permutation and corresponding count[] array from an arbitrary index. Basically, count[k] = ( index % (k+1)! ) / k! is the number of rotations we need to perform on elements 0..k. Doing it in the descending order from n-1 to 1 gives us both the count[] array and the permutation.

Home Conclusions License Play

Ubuntu : Intel® Q6600® one coreComputer Language Benchmarks Game [[ Play ]]

fannkuch-redux benchmark N=12

fannkuch-redux benchmark : Indexed-access to tiny integer-sequence

Ubuntu : Intel® Q6600® one core
Computer Language Benchmarks Game [[ Play ]]