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][ackermann].
• arithmetic-series: Print the summation operator from 1 to n, via the closed form solution.
• adj2csr: Convert a graph in [adjacency matrix][adj] format (dense representation) to [Compressed Sparse Row (CSR)][csr] format (sparse representation). The random graph is generated using the same [linear congruential generator][rng].
• adler32: Computes the [Adler-32 Checksum][adler32] of an integer array.
• armstrong: Determines if the input is an [Armstrong number][armstrong], a number that is the sum of its own digits each raised to the power of the number of digits.
• bin-search: Search a target integer within an integer range, outputs the target integer.
• 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.
• binpow: Recursive binary exponentiation. Implemented to be as close to tail-recursive as possible.
• 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
• bbs: Prints the least significant bit of each element in a given Blum Blum Blum PRNG sequence.
• 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.
• char-poly: Calculates the characteristic polynomial of a given 3x3 matrix, returning its coefficients as an array.
• 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.
• connected-components: Compute and print each [connected component][component] in the [adjacency matrix][adj] of an undirected graph.
• 1dconv: Creates a kernel and array, performs a one-dimensional convolution operation, and prints out the values in the resulting array.
• 2dconvol: Creates a 2d image and kernel and performs a 2d convolution on the image, and prints out the values of the image, kernel, and resulting output.
• 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)][csr] format with a dense vector. The matrix and input vector are generated using a Linear Feedback Shift Register random number generator.
• dayofweek: Returns the day of the week for a given date (year, month, day) as an integer: 1 = Monday, …, 7 = Sunday.
• 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.
• delannoy: Recusively computes the number of paths on square board with size n from southwest corner (0, 0) to northeast corner (n, n), using only single steps north, northeast or east. This number is known as the Delannoy number.
• 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][eight_queens].
• euclid: Calculates the greatest common divisor between two large numbers using the [Euclidean Algorithm][euclid] with a helper function for the modulo operator.
• euler: Approximates [Euler’s number][euler] using the Taylor series.
• exponentiation-by-squaring: Fast iterative computation of large integer powers using [exponentiation by squaring][exp_by_squaring].
• fact: Prints the factorial of n, computing it recursively.
• factors: Print the factors of the n using the [trial division][trialdivision] method.
• fib: Calculate the nth Fibonacci number by allocating and filling an array of numbers up to that point.
• filter: Filter records from a single table based on a condition.
• fizz-buzz: The infamous programming test.
• fnv1-hash: Compute the Fowler-Noll-Vo hash function of an integer array.
• function_call: For benchmarking the overhead of simple function calls.
• gebmm: Perform binary matrix multiplication of two matrices represented by packed integer arguments.
• gcd: Calculate Greatest Common Divisor (GCD) of two input positive integer using [Euclidean algorithm][euclidean_into].
• geometric-sum: Calculate Geometric Sum given first term, common ratio and number of terms.
• gol: Print the next iteration for a matrix in Conway’s Game of Life.
• gpf: Prints the greatest prime factor on an input integer
• grad_desc Use gradient descent to minimize f(w) = (w-t)^2.
• graycode: Compute the first n Gray codes using the formula G(i) = i ^ (i >> 1).
• hanoi: Print the solution to the n-disk [Tower of Hanoi][hanoi] puzzle.
• hamming: Computes the hamming distance between two integers.
• harmonic-sum: Computes the harmonic sum up to the index n.
• insertion-sort: Insertion sort algorithm in ascending order.
• is-decreasing: Print if a number contains strictly decreasing digits.
• karatsuba: Computes the product of 2 integers using Karatsuba’s Algorithm.
• lcm: Compute LCM for two numbers using a very inefficient loop.
• legendre: Compute the exponent for the largest power of the given prime p which divides the factorial n! using Legendre’s formula.
• leibniz: Approximates Pi using Leibniz formula.
• lis: Calculates the longest increasing subsequence of an 8-element array using dynamic programming.
• logistic: Compute the logistic map.
• 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][mandelbrot].
• mat-inv : Calculates the inverse of a 3x3 matrix and prints it out.
• mat-mul: Multiplies two nxn matrices using the [naive][matmul] matrix multiplication algorithm. The matrices are randomly generated using a [linear congruential generator][rng].
• max-subarray: solution to the classic Maximum Subarray problem.
• mccarthy91: Run the [McCarthy 91 function][mccarthy91], a nested-recursive function which always returns 91.
• mod_inv: Calculates the [modular inverse][modinv] of n under to a prime modulus p.
• montecarlo: Calculates the value of pi using a xorshift as the rng.
• montgomery: Computes modular multiplication using the [Montgomery reduction][montgomery] algorithm.
• mod_pow: Performs [modular exponentiation][modpow] using the right-to-left binary method.
• mountain: Determines if a given input is a mountain; that is, a non-decreasing segment of digits followed by a non-increasing segment.
• newton: Calculate the square root of 99,999 using the [newton method][newton]
• norm: Calculate the [euclidean norm][euclidean] 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][palindrome] number.
• perfect: Check if input argument is a perfect number. Returns output as Unix style return code.
• permutation: Calculates the number of possible permutations of k objects from a set of n.
• pi: Compute and print digits of Pi using a spigot algorithm.
• 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][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][qsort].
• quicksort-hoare: Quicksort using [Hoare partioning][qsort-hoare] and median of three pivot selection.
• random-walk: Perform a simple random walk on the integer lattice [Z^d][int_lattice]: that is, starting from the origin, repeatedly make a random move of length one in one of the lattice directions. The walk terminates after 100000 steps or upon returning to the start.
• ray-bbox-intersection: Finds whether a ray intersects an axis-aligned bounding box.
• 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.
• rgb2gray: Convert an RGB pixel to a grayscale color.
• 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][euclidean_into].
• riemann: Prints the left, midpoint, and right [Riemann][riemann] Sums for a specified function, which is the square function in this benchmark.
• rot13: Prints the [rot13][rot13] substitution of a character (represented as an integer in the range 0 to 25).
• shufflesort: Sorts a list by shuffling it until it is sorted.
• sieve: Print all prime numbers up to n using the Sieve of Eratosthenes.
• sorting-network-five: An optimal sorting network for 5 integer inputs.
• sqrt: Implements the [Newton–Raphson Method][newton] of approximating the square root of a number to arbitrary precision
• sqrt_bin_search: Uses a binary search to find the floor of the square root of an integer
• 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-digits: Compute the sum of the (base-10) digits of the input integer.
• sum-divisible-by-m: Compute the sum of integers between [1, n] which are divisible by m
• 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.
• sum-to-ten: Output the sum of all the numbers from 1 to 10
• sum-of-cubes: Computes the sum of the first n cubes using the closed-cube formula and prints the result.
• tail-call: Decrements a large counter recursively, nesting many function calls. It is written such that a smart interpreter or compiler could perform a tail call optimization to reduce stack usage.
• systolic: Multiply two matrices using a simulated [systolic][systolic] array approach.
• totient: Computes [Euler’s totient function][totient] on an input integer n.
• triangle: Computes the nth [triangular number][triangle] by summing over the first n integers in a loop.
• 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][uparrow] 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).
• combination: Compute binomial combination, ie. n choose k, for positive integers.
• fib_recursive: Computes the nth Fibonacci number using recursion, where fib(n) = fib(n-1) + fib(n-2), with base cases fib(0) = 0 and fib(1) = 1. Demonstrates recursive function calls and branching.
• cordic: Compute the sine of a number using the [CORDIC][cordic] algorithm
• squares: Print the squares of all integers from 1 up to input.
• braille: Convert the input integer into a Braille code.
• kadane: Compute the maximum sum of a contiguous subarray within a given array of numbers.

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

[component] : https://en.wikipedia.org/wiki/Component_(graph_theory) [ackermann]: https://en.wikipedia.org/wiki/Ackermann_function [newton]: https://en.wikipedia.org/wiki/Newton%27s_method [matmul]: https://en.wikipedia.org/wiki/Matrix_multiplication_algorithm#Iterative_algorithm [rng]: https://en.wikipedia.org/wiki/Linear_congruential_generator [euclidean_into]: https://en.wikipedia.org/wiki/Euclidean_algorithm [euclid]: https://en.wikipedia.org/wiki/Euclidean_algorithm#Euclidean_division [eight_queens]: https://en.wikipedia.org/wiki/Eight_queens_puzzle [newton]: https://en.wikipedia.org/wiki/Newton%27s_method [trialdivision]: https://en.wikipedia.org/wiki/Trial_division [adj]: https://en.wikipedia.org/wiki/Adjacency_matrix [csr]: https://en.wikipedia.org/wiki/Sparse_matrix [armstrong]: https://en.wikipedia.org/wiki/Narcissistic_number [adler32]: https://en.wikipedia.org/wiki/Adler-32 [uparrow]: https://en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation [riemann]: https://en.wikipedia.org/wiki/Riemann_sum [rot13]: https://en.wikipedia.org/wiki/ROT13 [primitive_root]: https://en.wikipedia.org/wiki/Primitive_root_modulo_n [mandelbrot]: https://en.wikipedia.org/wiki/Mandelbrot_set [palindrome]: https://en.wikipedia.org/wiki/Palindrome [hanoi]: https://en.wikipedia.org/wiki/Tower_of_Hanoi [euler]: https://en.wikipedia.org/wiki/E_(mathematical_constant) [euclidean]: https://en.wikipedia.org/wiki/Norm_(mathematics) [qsort]: https://en.wikipedia.org/wiki/Quicksort#Lomuto_partition_scheme [qsort-hoare]: https://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme [modinv]: https://en.wikipedia.org/wiki/Modular_multiplicative_inverse [totient]: https://en.wikipedia.org/wiki/Euler’s_totient_function [mccarthy91]: https://en.wikipedia.org/wiki/McCarthy_91_function [exp_by_squaring]: https://en.wikipedia.org/wiki/Exponentiation_by_squaring [montgomery]: https://en.wikipedia.org/wiki/Montgomery_modular_multiplication#The_REDC_algorithm [modpow]: https://en.wikipedia.org/wiki/Modular_exponentiation [cordic]: https://en.wikipedia.org/wiki/CORDIC [int_lattice]: https://en.wikipedia.org/wiki/Integer_lattice [triangle]: https://en.wikipedia.org/wiki/Triangular_number [systolic]: https://en.wikipedia.org/wiki/Systolic_array