Benchmarks

The bench directory in the Bril repository contains a fledgling suite of microbenchmarks that you can use to measure the impact of your optimizations. (Benchmarks are different from tests because they are meant to actually calculate something instead of just exercising a language feature.)

The current benchmarks are:

  • ackermann: Print the value of Ack(m, n), the two-argument Ackermann–Péter function.
  • adj2csr: Convert a graph in adjacency matrix format (dense representation) to Compressed Sparse Row (CSR) format (sparse representation). The random graph is generated using the same linear congruential generator.
  • adler32: Computes the Adler-32 Checksum of an integer array.
  • armstrong: Determines if the input is an Armstrong number, a number that is the sum of its own digits each raised to the power of the number of digits.
  • binary-fmt: Print the binary format for the given positive integer.
  • binary-search: Search a target integer within an integer array, outputs the index of target.
  • birthday: Simulation of the birthday paradox with an input of n people in a given room.
  • bitwise-ops: Computes the OR, AND, or XOR between two 64-bit integers. (Three modes: 0 = AND, 1 = OR, 2 = XOR)
  • bitshift: Computes the LEFTSHIFT and RIGHTSHIFT for any integer, also implements an efficient pow function for integers
  • bubblesort: Sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.
  • catalan: Print the nth term in the Catalan sequence, compute using recursive function calls.
  • check-primes: Check the first n natural numbers for primality, printing out a 1 if the number is prime and a 0 if it’s not.
  • cholesky: Perform Cholesky decomposition of a Hermitian and positive definite matrix. The result is validated by comparing with Python’s scipy.linalg.cholesky.
  • collatz: Print the Collatz sequence starting at n. Note: it is not known whether this will terminate for all n.
  • conjugate-gradient: Uses conjugate gradients to solve Ax=b for any arbitrary positive semidefinite A.
  • cordic: Print an approximation of sine(radians) using 8 iterations of the CORDIC algorithm.
  • csrmv: Multiply a sparse matrix in the Compressed Sparse Row (CSR) format with a dense vector. The matrix and input vector are generated using a Linear Feedback Shift Register random number generator.
  • digial-root: Computes the digital root of the input number.
  • dead-branch: Repeatedly call a br instruction whose condition always evaluates to false. The dead branch should be pruned by a smart compiler.
  • dot-product: Computes the dot product of two vectors.
  • eight-queens: Counts the number of solutions for n queens problem, a generalization of Eight queens puzzle.
  • euclid: Calculates the greatest common divisor between two large numbers using the Euclidean Algorithm with a helper function for the modulo operator.
  • euler: Approximates Euler’s number using the Taylor series.
  • fact: Prints the factorial of n, computing it recursively.
  • factors: Print the factors of the n using the trial division method.
  • fib: Calculate the nth Fibonacci number by allocating and filling an array of numbers up to that point.
  • fizz-buzz: The infamous programming test.
  • function_call: For benchmarking the overhead of simple function calls.
  • gcd: Calculate Greatest Common Divisor (GCD) of two input positive integer using Euclidean algorithm.
  • hanoi: Print the solution to the n-disk Tower of Hanoi puzzle.
  • is-decreasing: Print if a number contains strictly decreasing digits.
  • lcm: Compute LCM for two numbers using a very inefficient loop.
  • leibniz: Approximates Pi using Leibniz formula.
  • loopfact: Compute n! imperatively using a loop.
  • major-elm: Find the majority element in an array using a linear time voting algorithm.
  • mandelbrot: Generates a really low resolution, ascii, mandelbrot set.
  • mat-inv : Calculates the inverse of a 3x3 matrix and prints it out.
  • mat-mul: Multiplies two nxn matrices using the naive matrix multiplication algorithm. The matrices are randomly generated using a linear congruential generator.
  • max-subarray: solution to the classic Maximum Subarray problem.
  • mod_inv: Calculates the modular inverse of n under to a prime modulus p.
  • newton: Calculate the square root of 99,999 using the newton method
  • norm: Calculate the euclidean norm of a vector
  • n_root: Calculate nth root of a float using newton’s method.
  • orders: Compute the order ord(u) for each u in a cyclic group <Zn,+> of integers modulo n under the group operation + (modulo n). Set the second argument is_lcm to true if you would like to compute the orders using the lowest common multiple and otherwise the program will use the greatest common divisor.
  • pascals-row: Computes a row in Pascal’s Triangle.
  • palindrome: Outputs a 0-1 value indicating whether the input is a palindrome number.
  • perfect: Check if input argument is a perfect number. Returns output as Unix style return code.
  • pow: Computes the n^th power of a given (float) number.
  • primes-between: Print the primes in the interval [a, b].
  • primitive-root: Computes a primitive root modulo a prime number input.
  • pythagorean_triple: Prints all Pythagorean triples with the given c, if such triples exist. An intentionally very naive implementation.
  • quadratic: The quadratic formula, including a hand-rolled implementation of square root.
  • quickselect: Find the kth smallest element in an array using the quickselect algorithm.
  • quicksort: Quicksort using the Lomuto partition scheme.
  • quicksort-hoare: Quicksort using Hoare partioning and median of three pivot selection.
  • recfact: Compute n! using recursive function calls.
  • rectangles-area-difference: Output the difference between the areas of rectangles (as a positive value) given their respective side lengths.
  • fitsinside: Output whether or not a rectangle fits inside of another rectangle given the width and height lengths.
  • relative-primes: Print all numbers relatively prime to n using Euclidean algorithm.
  • riemann: Prints the left, midpoint, and right Riemann Sums for a specified function, which is the square function in this benchmark.
  • sieve: Print all prime numbers up to n using the Sieve of Eratosthenes.
  • sqrt: Implements the Newton–Raphson Method of approximating the square root of a number to arbitrary precision
  • sum-bit: Print the number of 1-bits in the binary representation of the input integer.
  • sum-check: Compute the sum of [1, n] by both loop and formula, and check if the result is the same.
  • sum-divisors: Prints the positive integer divisors of the input integer, followed by the sum of the divisors.
  • sum-sq-diff: Output the difference between the sum of the squares of the first n natural numbers and the square of their sum.
  • totient: Computes Euler’s totient function on an input integer n.
  • two-sum: Print the indices of two distinct elements in the list [2, 7, 11, 13] whose sum equals the input.
  • up-arrow: Computes Knuth’s up arrow notation, with the first argument being the number, the second argument being the number of Knuth’s up arrows, and the third argument being the number of repeats.
  • vsmul: Multiplies a constant scalar to each element of a large array. Tests the performance of vectorization optimizations.
  • reverse: Compute number with reversed digits (e.g. 123 -> 321).

Credit for several of these benchmarks goes to Alexa VanHattum and Gregory Yauney, who implemented them for their global value numbering project.