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	ATS #2	51.47	51.49	364	1571	0% 0% 0% 100%
1.0	ATS	51.75	51.76	364	1306	0% 100% 0% 0%
1.0	C++ g++ #3	53.41	53.43	372	593	0% 0% 100% 0%
1.0	C++ g++ #7	22.54	22.55	372	1150	0% 13% 87% 0%
1.0	C gcc #4	22.70	22.70	372	1183	0% 0% 0% 100%
1.0	C gcc	71.60	71.62	376	508	0% 0% 0% 100%
1.0	C gcc #3	50.35	50.37	376	567	0% 0% 0% 100%
1.1	C gcc #2	48.38	12.42	412	1557	98% 93% 98% 100%
1.4	Fortran Intel	58.82	58.84	520	590	0% 0% 0% 100%
2.1	OCaml	106.88	106.91	752	524	0% 0% 100% 0%
2.1	OCaml #2	91.99	92.02	752	473	0% 0% 0% 100%
2.3	Pascal Free Pascal	75.34	18.87	832	1018	100% 100% 100% 100%
3.1	C++ g++	54.86	14.03	1,144	1059	100% 97% 97% 98%
3.4	C++ g++ #5	47.95	12.29	1,236	1440	100% 93% 100% 98%
3.4	C++ g++ #4	60.15	15.36	1,240	1439	98% 100% 97% 97%
3.5	Go	73.57	18.49	1,276	900	100% 99% 99% 99%
5.1	Perl	43 min	43 min	1,864	457	0% 0% 0% 100%
5.4	Ada 2005 GNAT #3	38.18	9.58	1,976	2100	100% 100% 100% 100%
6.4	Haskell GHC #4	75.48	68.67	2,336	658	15% 42% 43% 10%
8.8	PHP #2	49 min	49 min	3,188	441	19% 74% 0% 7%
8.9	PHP	57 min	57 min	3,228	482	59% 37% 4% 0%
11	Haskell GHC	18 min	12 min	3,876	553	39% 32% 48% 32%
13	Lisp SBCL #2	86.73	86.76	4,780	513	0% 0% 100% 0%
16	Haskell GHC #2	12 min	223.87	5,824	808	81% 81% 81% 81%
17	Python 3 #6	38 min	38 min	6,148	385	100% 0% 0% 0%
17	Ruby 2.0	53 min	53 min	6,152	384	0% 100% 0% 0%
24	Fortran Intel #3	51.20	12.84	8,564	1148	100% 100% 100% 100%
24	Dart	26 min	26 min	8,656	531	51% 49% 0% 0%
25	Dart #2	82.45	82.47	8,988	538	0% 100% 0% 0%
32	OCaml #4	0.00	16.36	11,552	1004	100% 100% 100% 100%
32	Erlang	13 min	203.76	11,796	1038	100% 98% 100% 100%
35	Erlang HiPE	8 min	125.73	12,872	1038	99% 100% 97% 97%
39	C# Mono	104.66	104.68	14,100	520	0% 0% 0% 100%
39	C# Mono #2	67.24	67.26	14,364	564	99% 0% 0% 0%
40	PHP #3	48 min	12 min	14,688	1150	100% 100% 100% 100%
42	F# Mono #2	97.84	97.87	15,152	548	96% 0% 0% 4%
42	F# Mono	9 min	7 min	15,420	551	20% 39% 41% 21%
43	C# Mono #3	110.78	28.14	15,588	1096	99% 100% 98% 97%
48	Java 7	51.90	13.15	17,348	1282	99% 99% 98% 98%
48	Java 7 #2	73.63	73.59	17,476	514	100% 0% 0% 0%
50	Racket	298.70	298.70	18,092	649	0% 0% 0% 100%
51	F# Mono #3	125.30	32.82	18,464	945	95% 98% 91% 98%
57	Lisp SBCL #3	63.36	63.38	20,624	821	0% 0% 100% 0%
58	OCaml #3	0.01	16.40	21,012	1017	100% 100% 100% 100%
58	Lisp SBCL #4	53.42	13.81	21,188	1518	98% 99% 97% 93%
63	Scala	87.36	87.32	22,912	459	100% 0% 0% 0%
70	Scala #2	55.35	14.13	25,604	1017	98% 97% 99% 98%
100	Python 3 #2	59 min	15 min	36,288	797	99% 100% 97% 99%
100	Python 3	1h 06 min	16 min	36,388	1108	100% 98% 100% 99%
152	Clojure #2	156.20	48.96	55,216	1088	80% 79% 77% 79%
1,642	Ruby JRuby	14 min	14 min	597,824	384	83% 17% 0% 0%
	Haskell GHC #3	Timed Out	1h 00 min		1153
"wrong" (different) algorithm / less comparable programs
1.0	C++ g++ #6	40.53	40.55	372	894
3.3	C++ g++ #2	31.55	8.00	1,216	2106
53	Java 7 #3	44.57	11.27	19,408	1633
74	Lisp SBCL	44.20	11.14	26,844	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

x64 Ubuntu : Intel® Q6600® quad-coreComputer Language Benchmarks Game [[ Play ]]

fannkuch-redux benchmark N=12

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

x64 Ubuntu : Intel® Q6600® quad-core
Computer Language Benchmarks Game [[ Play ]]