The Computer Language
Benchmarks Game

Background

Model the orbits of Jovian planets, using the same simple symplectic-integrator.

Thanks to Mark C. Lewis for suggesting this task.

Useful symplectic integrators are freely available, for example the HNBody Symplectic Integration Package.

How to implement

We ask that contributed programs not only give the correct result, but also use the same algorithm to calculate that result.

Each program should:

• use the same simple symplectic-integrator - see the Java program.

ndiff -abserr 1.0e-8 program output N = 1000 with this output file to check your program output has the correct format, before you contribute your program.

Use a larger command line argument (50000000) to check program performance.

Background

The fannkuch benchmark is defined by programs in Performing Lisp Analysis of the FANNKUCH Benchmark, Kenneth R. Anderson and Duane Rettig. FANNKUCH is an abbreviation for the German word Pfannkuchen, or pancakes, in analogy to flipping pancakes. The conjecture is that the maximum count is approximated by n*log(n) when n goes to infinity.

How to implement

We ask that contributed programs not only give the correct result, but also use the same algorithm to calculate that result.

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.

diff program output N = 7 with this output file to check your program output has the correct format, before you contribute your program.

Use a larger command line argument (12) to check program performance.

Example

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

• 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.

Background

MathWorld: "Hundred-Dollar, Hundred-Digit Challenge Problems", Challenge #3.

Thanks to Sebastien Loisel for suggesting this task.

How to implement

We ask that contributed programs not only give the correct result, but also use the same algorithm to calculate that result.

Each program should:

• calculate the spectral norm of an infinite matrix A, with entries a₁₁=1, a₁₂=1/2, a₂₁=1/3, a₁₃=1/4, a₂₂=1/5, a₃₁=1/6, etc

• implement 4 separate functions / procedures / methods like the C# program

diff program output N = 100 with this output file to check your program output has the correct format, before you contribute your program.

Use a larger command line argument (5500) to check program performance.

Background

MathWorld: Mandelbrot Set.

Thanks to Greg Buchholz for suggesting this task.

How to implement

We ask that contributed programs not only give the correct result, but also use the same algorithm to calculate that result.

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.

cmp program output N = 200 with this 5KB output file to check your program output has the correct format, before you contribute your program.

Use a larger command line argument (16000) to check program performance.

Background

MathWorld: Pi Digits.

How to implement

We ask that contributed programs not only give the correct result, but also use the same algorithm to calculate that result.

Each program should:

• calculate the first N digits of Pi

• print the digits 10-to-a-line, with the running total of digits calculated

diff program output N = 27 with this output file to check your program output has the correct format, before you contribute your program.

Use a larger command line argument (10000) to check program performance.

Adapt the step-by-step algorithm given on pages 4,6 & 7 of [pdf 156KB] Unbounded Spigot Algorithms for the Digits of Pi. (Not the deliberately obscure version given on page 2. Not the Rabinowitz-Wagon algorithm.)

Variance

Some language implementations have regex built-in; some provide a regex library; some use a third-party regex library.

The regex algorithm implemented is very likely to be different in different libraries.

The work

The work is to use the same simple regex patterns and actions to manipulate FASTA format data. Don't optimize away the work.

How to implement

We ask that contributed programs not only give the correct result, but also use the same algorithm to calculate that result.

Each program should:

• read all of a redirected FASTA format file from stdin, and record the sequence length

• use the same simple regex pattern match-replace to remove FASTA sequence descriptions and all linefeed characters, and record the sequence length

• use the same simple regex patterns -

  agggtaaa|tttaccct
  [cgt]gggtaaa|tttaccc[acg]
  a[act]ggtaaa|tttacc[agt]t
  ag[act]gtaaa|tttac[agt]ct
  agg[act]taaa|ttta[agt]cct
  aggg[acg]aaa|ttt[cgt]ccct
  agggt[cgt]aa|tt[acg]accct
  agggta[cgt]a|t[acg]taccct
  agggtaa[cgt]|[acg]ttaccct

  - representing DNA 8-mers and their reverse complement (with a wildcard in one position), and (one pattern at a time) count matches in the redirected file

• write the regex pattern and count

• use the same magic regex patterns -

  tHa[Nt]
  aND|caN|Ha[DS]|WaS
  a[NSt]|BY
  <[^>]*>
  \\|[^|][^|]*\\|

  - to (one pattern at a time, in the same order) match-replace the pattern in the redirected file with -

  <4>
  <3>
  <2>
  |
  -

  - and record the sequence length

• write the 3 recorded sequence lengths

diff program output for this 10KB input file (generated with the fasta program N = 1000) with this output file to check your program output has the correct format, before you contribute your program.

Generate a larger input file (using one of the fasta programs with command line arguments: 5000000 > input5000000.txt) to check program performance.

Thanks to Jeremy Zerfas for insisting that the programs follow the "one pattern at a time" guideline, and developing the magic regex patterns. Thanks to Matt Brubeck for the good enough magic regex pattern.

Variance

Please don't optimize the cumulative-probabilities lookup (for example, by using a scaling factor) or naïve LCG arithmetic - those programs will not be accepted.

How to implement

We ask that contributed programs not only give the correct result, but also use the same algorithm to calculate that result.

Each program should:

• generate DNA sequences, by copying from a given sequence

• generate DNA sequences, by weighted random selection from 2 alphabets

  • convert the expected probability of selecting each nucleotide into cumulative probabilities

  • match a random number against those cumulative probabilities to select each nucleotide (use linear search or binary search)

  • use this naïve linear congruential generator to calculate a random number each time a nucleotide needs to be selected (don't cache the random number sequence)

    IM = 139968
    IA = 3877
    IC = 29573
    Seed = 42
     	
    Random (Max)
       Seed = (Seed * IA + IC) modulo IM
       = Max * Seed / IM
    

diff program output N = 1000 with this 10KB output file to check your program output has the correct format, before you contribute your program.

Use a larger command line argument (25000000) to check program performance.

Variance

Some language implementations have hash tables built-in; some provide a hash table as part of a collections library; some use a third-party hash table library. (For example, use either khash or CK_HT for C language k-nucleotide programs.) The hash table algorithm implemented is likely to be different in different libraries.

Please don't implement your own custom "hash table" - it will not be accepted.

The work

The work is to use the built-in or library hash table implementation to accumulate count values - lookup the count for a key and update the count in the hash table. Don't optimize away the work.

Mapping the DNA letters to the bytes 0, 1, 2, 3, and using a hash function that concatenates those two-byte codes is an acceptable (but not a required) optimization.

How to implement

We ask that contributed programs not only give the correct result, but also use the same algorithm to calculate that result.

Each program should:

• read line-by-line a redirected FASTA format file from stdin

• extract DNA sequence THREE

• define a procedure/function to update a hashtable of k-nucleotide keys and count values, for a particular reading-frame — even though we'll combine k-nucleotide counts for all reading-frames (grow the hashtable from a small default size)

• use that procedure/function and hashtable to

  • count all the 1-nucleotide and 2-nucleotide sequences, and write the code and percentage frequency, sorted by descending frequency and then ascending k-nucleotide key

  • count all the 3- 4- 6- 12- and 18-nucleotide sequences, and write the count and code for the specific sequences GGT GGTA GGTATT GGTATTTTAATT GGTATTTTAATTTATAGT

diff program output for this 10KB input file (generated with the fasta program N = 1000) with this output file to check your program output has the correct format, before you contribute your program.

Generate a larger input file (using one of the fasta programs with command line arguments: 25000000 > input25000000.txt) to check program performance.

Background

… by knowing the sequence of bases of one strand of DNA we immediately know the sequence of the DNA strand which will bind to it, this strand is called the reverse complement …

How to implement

We ask that contributed programs not only give the correct result, but also use the same algorithm to calculate that result.

Each program should:

• read line-by-line a redirected FASTA format file from stdin

• for each sequence:

  • write the id, description, and the reverse-complement sequence in FASTA format to stdout

Use these code complements:

code  meaning   complement
A    A                   T
C    C                   G
G    G                   C
T/U  T                   A
M    A or C              K
R    A or G              Y
W    A or T              W
S    C or G              S
Y    C or T              R
K    G or T              M
V    A or C or G         B
H    A or C or T         D
D    A or G or T         H
B    C or G or T         V
N    G or A or T or C    N

diff program output for this 10KB input file (generated with the fasta program N = 1000) with this output file to check your program output has the correct format, before you contribute your program.

Generate a larger input file (using one of the fasta programs with command line arguments: 25000000 > input25000000.txt) to check program performance.

Background

A simplistic adaptation of Hans Boehm's GCBench, which in turn was adapted from a benchmark by John Ellis and Pete Kovac.

Thanks to Christophe Troestler and Einar Karttunen for help with this benchmark.

Variance

Use default GC, use per node allocation or use a library memory pool.

As a practical matter, the myriad ways to tune GC will not be accepted.

As a practical matter, the myriad ways to custom allocate memory will not be accepted.

Please don't implement your own custom "arena" or "memory pool" or "free list" - they will not be accepted.

The work

The work is to fully create perfect binary trees - before any tree nodes are GC'd - using at-minimum the number of allocations of Jeremy Zerfas's C program. Don't optimize away the work.

How to implement

We ask that contributed programs not only give the correct result, but also use the same algorithm to calculate that result.

Each program should:

• define a tree node class and methods, or 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

  • allocate a tree

  • walk the tree, counting the nodes (and maybe deallocate the nodes)

  • deallocate the tree

• check that the long-lived binary tree still exists

diff program output N = 10 with this 1KB output file to check your program output has the correct format, before you contribute your program.

Use a larger command line argument (21) to check program performance.

Thanks to Eamon Nerbonne for repeatedly showing what was wrong with the old way of checking these programs, and to Brad Chamberlain for suggesting that a simple check should work.

Background

An adaptation of [pdf 100KB] "Chameneos, a Concurrency Game for Java, Ada and Others" (which includes example implementations in Java, Ada and C).

Variance

Use OS threads or the language implementation pre-emptive lightweight threads.

As a practical matter, continuations & coroutines & cooperative threading will not be accepted.

Please don't implement your own custom "custom scheduler" or use "continuations" or "coroutines" or "cooperative threading" - they will not be accepted.

How to implement

We ask that contributed programs not only give the correct result, but also use the same algorithm to calculate that result.

Each program should:

• create differently coloured (blue, red, yellow), differently named, concurrent chameneos creatures

• each creature will repeatedly go to the meeting place and meet, or wait to meet, another chameneos "(at the request the caller does not know whether another chameneos is already present or not, neither if there will be one in some future)"

• both creatures will change colour to complement the colour of the chameneos that they met - don't use arithmetic to complement the colour, use if-else or switch/case or pattern-match

• write all the colour changes for blue red and yellow creatures, using the colour complement function

• for rendezvouses with an odd number of creatures (blue red yellow) and with an even number of creatures (blue red yellow red yellow blue red yellow red blue)

  • write the colours the creatures start with

  • after N meetings have taken place, for each creature write the number of creatures met and spell out the number of times the creature met a creature with the same name (should be zero)

  • spell out the sum of the number of creatures met (should be 2N)

ndiff -fields 2-10 program output N = 600 with this output file to check your program output has the correct format, before you contribute your program.

Use a larger command line argument (6000000) to check program performance.

Background

The Meteor Puzzle board is made up of 10 rows of 5 hexagonal Cells. There are 10 puzzle pieces to be placed on the board, we'll number them 0 to 9. Each puzzle piece is made up of 5 hexagonal Cells. As different algorithms may be used to generate the puzzle solutions, we require that the solutions be printed in a standard order and format. Here's one approach - working along each row left to right, and down the board from top to bottom, take the number of the piece placed in each cell on the board, and create a string from all 50 numbers, for example the smallest puzzle solution would be represented by

00001222012661126155865558633348893448934747977799

Print the smallest and largest Meteor Puzzle 50 character solution string in this format to mimic the hexagonal puzzle board:

0 0 0 0 1 
 2 2 2 0 1 
2 6 6 1 1 
 2 6 1 5 5 
8 6 5 5 5 
 8 6 3 3 3 
4 8 8 9 3 
 4 4 8 9 3 
4 7 4 7 9 
 7 7 7 9 9 

The command line parameter N should limit how many solutions will be found before the program halts, so that you can work with just a few solutions to debug and optimize your program.

The puzzle board

cell    NW NE W  E  SW SE
0       -- -- -- 01 -- 05
1       -- -- 00 02 05 06
2       -- -- 01 03 06 07
3       -- -- 02 04 07 08
4       -- -- 03 -- 08 09
5       00 01 -- 06 10 11
6       01 02 05 07 11 12
7       02 03 06 08 12 13
8       03 04 07 09 13 14
9       04 -- 08 -- 14 --
10      -- 05 -- 11 -- 15
11      05 06 10 12 15 16
12      06 07 11 13 16 17
13      07 08 12 14 17 18
14      08 09 13 -- 18 19
15      10 11 -- 16 20 21
16      11 12 15 17 21 22
17      12 13 16 18 22 23
18      13 14 17 19 23 24
19      14 -- 18 -- 24 --
20      -- 15 -- 21 -- 25
21      15 16 20 22 25 26
22      16 17 21 23 26 27
23      17 18 22 24 27 28
24      18 19 23 -- 28 29
25      20 21 -- 26 30 31
26      21 22 25 27 31 32
27      22 23 26 28 32 33
28      23 24 27 29 33 34
29      24 -- 28 -- 34 --
30      -- 25 -- 31 -- 35
31      25 26 30 32 35 36
32      26 27 31 33 36 37
33      27 28 32 34 37 38
34      28 29 33 -- 38 39
35      30 31 -- 36 40 41
36      31 32 35 37 41 42
37      32 33 36 38 42 43
38      33 34 37 39 43 44
39      34 -- 38 -- 44 --
40      -- 35 -- 41 -- 45
41      35 36 40 42 45 46
42      36 37 41 43 46 47
43      37 38 42 44 47 48
44      38 39 43 -- 48 49
45      40 41 -- 46 -- --
46      41 42 45 47 -- --
47      42 43 46 48 -- --
48      43 44 47 49 -- --
49      44 -- 48 -- -- --

How to implement

The Meteor Puzzle and 3 Java puzzle solvers are described in [pdf 111KB] "Optimize your Java application's performance".

You are expected to diff the output from your program N = 2098 against this output file to check your program output has the correct format, before you contribute your program.

Background

A simplistic adaptation of Performance Measurements of Threads in Java and Processes in Erlang and A Benchmark Test for BCPL Style Coroutines.

Variance

Use OS threads or the language implementation pre-emptive lightweight threads.

As a practical matter, continuations & coroutines & cooperative threading will not be accepted.

Please don't implement your own custom "custom scheduler" or use "continuations" or "coroutines" or "cooperative threading" - they will not be accepted.

How to implement

We ask that contributed programs not only give the correct result, but also use the same algorithm to calculate that result.

Each program should:

• create 503 linked pre-emptive threads (named 1 to 503)

• thread 503 should be linked to thread 1, forming an unbroken ring

• pass a token to thread 1

• pass the token from thread to thread N times

• print the name of the last thread (1 to 503) to take the token

diff program output N = 1000 with this output file to check your program output has the correct format, before you contribute your program.

Use a larger command line argument (50000000) to check program performance.