fannkuch-redux benchmark | Computer Language Benchmarks Game

fannkuch-redux benchmark N=12

Each chart bar shows how many times slower, one ↓ fannkuch-redux program was, compared to the fastest program.

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	Ada 2005 GNAT #3	39.37	9.91	1,672	2100	100% 99% 99% 99%
1.3	C++ g++ #5	49.71	12.69	996	1440	98% 100% 94% 100%
1.3	C gcc #2	51.38	13.07	332	1557	96% 100% 100% 98%
1.4	C++ g++	53.84	13.73	936	1059	100% 98% 100% 95%
1.5	Lisp SBCL #4	57.30	14.77	14,112	1518	98% 99% 97% 94%
1.6	C++ g++ #4	61.89	15.93	1,004	1439	95% 100% 98% 96%
1.7	Pascal Free Pascal	65.31	16.36	748	1018	100% 100% 100% 100%
1.7	Fortran Intel #3	66.89	16.85	8,508	1148	100% 100% 100% 100%
1.7	Haskell GHC #3	66.80	17.02	3,264	1153	100% 99% 100% 94%
1.7	Java 7	67.91	17.17	14,460	1282	98% 99% 100% 100%
1.8	Scala #2	70.92	18.10	20,452	1017	98% 98% 98% 99%
2.2	Go	84.74	21.34	1,012	900	99% 99% 100% 100%
2.5	C gcc #4	24.72	24.74	292	1183	90% 0% 0% 10%
2.5	C++ g++ #7	25.09	25.11	292	1150	59% 0% 0% 41%
2.6	OCaml #3	0.01	26.07	18,544	1017	100% 100% 100% 100%
3.4	OCaml #4	0.00	33.41	8,996	1004	100% 100% 100% 100%
3.5	C# Mono #3	134.25	34.54	16,252	1096	97% 99% 96% 98%
4.2	F# Mono #3	157.46	41.69	20,488	945	96% 96% 94% 93%
4.5	C gcc #3	44.76	44.78	292	567	96% 0% 0% 4%
5.0	C++ g++ #3	49.77	49.79	292	593	0% 0% 25% 75%
5.7	C gcc	56.93	56.96	292	508	97% 0% 0% 4%
5.8	ATS #2	57.80	57.82	288	1571	0% 1% 100% 0%
5.9	ATS	58.28	58.29	288	1306	0% 0% 0% 100%
6.2	Lisp SBCL #3	61.52	61.55	13,748	821	100% 0% 0% 0%
6.9	Fortran Intel	68.41	68.43	520	590	100% 0% 0% 0%
6.9	C# Mono #2	68.52	68.55	15,172	564	61% 0% 40% 1%
7.4	OCaml #2	73.47	73.49	580	473	1% 0% 1% 100%
8.0	Dart #2	78.75	78.77	6,264	538	29% 0% 0% 71%
8.3	Clojure #2	277.79	81.98	70,084	1088	85% 85% 85% 85%
8.8	Java 7 #2	87.01	86.98	14,712	514	1% 0% 100% 0%
9.3	Haskell GHC #4	96.49	92.15	2,000	658	15% 38% 34% 18%
10	Scala	99.21	99.17	18,756	459	0% 0% 100% 0%
10	Lisp SBCL #2	101.90	101.94	3,832	513	98% 0% 0% 2%
11	Erlang HiPE	6 min	104.74	8,180	1038	95% 99% 99% 94%
11	F# Mono #2	113.03	113.06	17,460	548	95% 6% 0% 0%
12	C# Mono	120.21	120.24	15,144	520	0% 0% 0% 100%
15	OCaml	145.87	145.91	576	524	1% 0% 100% 0%
16	Haskell GHC #2	7 min	156.94	4,872	808	76% 76% 76% 77%
20	F# Mono	197.14	197.11	22,448	551	1% 0% 36% 64%
32	Racket	5 min	5 min	15,328	649	0% 0% 0% 100%
69	Haskell GHC	16 min	11 min	3,588	553	34% 42% 38% 30%
71	PHP #3	46 min	11 min	10,192	1150	99% 100% 99% 100%
91	Ruby JRuby	14 min	14 min	583,560	384	0% 33% 48% 20%
106	Python 3 #2	1h 08 min	17 min	25,128	797	99% 99% 98% 100%
122	Python 3	1h 19 min	20 min	25,276	1108	100% 100% 99% 99%
143	Dart	23 min	23 min	5,980	531	0% 0% 100% 0%
259	PHP #2	42 min	42 min	2,488	441	0% 0% 100% 0%
285	Perl	47 min	47 min	1,752	457	100% 0% 0% 0%
294	Python 3 #6	48 min	48 min	4,564	385	83% 6% 2% 10%
360	PHP	59 min	59 min	2,516	482	0% 94% 0% 7%
416	Ruby 2.0	1h 08 min	1h 08 min	4,864	384	29% 69% 4% 1%
"wrong" (different) algorithm / less comparable programs
0.7	C++ g++ #2	28.96	7.30	972	2106
1.1	Java 7 #3	42.14	10.69	15,796	1633
1.2	Lisp SBCL	46.66	11.76	18,532	1607
3.9	C++ g++ #6	38.26	38.28	292	894

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® quad-coreComputer Language Benchmarks Game [[ Play ]]

fannkuch-redux benchmark N=12

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

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