Ordinal vs Polymorphic OCaml Variants Performance Comparison

bench.sh

#!/bin/bash

function bench() {
  number_of_variants=$1
  number_of_args=$2
  echo "number_of_variants = $number_of_variants, number_of_args = $number_of_args"
  ./gen_bench.py $number_of_variants $number_of_args > out.ml
  ocamlopt.opt -w -8 unix.cmxa out.ml
  ./a.out
  echo
}

bench 3 2
bench 5 1
bench 30 1
bench 30 3
bench 70 4
bench 170 2
bench 246 2

gen_bench.py

#!/usr/bin/env python

import random
import string
import sys

rand = random.Random()

def get_variant_name(ordinal):
    primes = [5, 7, 11, 13, 17, 19, 23]
    letters = [string.letters[((ordinal + primes[i - 1]) * primes[i]) % len(string.letters)] for i in xrange(1, len(primes))]
    return "V" + "".join(letters) + str(ordinal)

def gen_type(polymorphic, number_of_variants = 240, number_of_args = 2):
    args_type_expression = " * ".join(["int"] * number_of_args)
    args = "" if number_of_args == 0 else " of " + args_type_expression
    print "type %s =%s" % (("polymorphic", " [") if polymorphic else ("ordinal", ""))
    for i in xrange(number_of_variants):
        print "  | %s%s%s" % (("`" if polymorphic else ""), get_variant_name(i), args)
    if polymorphic:
        print "]"
    print

def gen_function(polymorphic, number_of_variants = 240, number_of_args = 2):
    function_name = "fold_" + ("polymorphic" if polymorphic else "ordinal")
    args_list = ", ".join(["a%d" % i for i in xrange(number_of_args)])
    args = "" if number_of_args == 0 else " (%s)" % args_list
    expr = " ".join(["a%d lxor" % i for i in xrange(number_of_args)] + [function_name, "tl"])
    print "let rec %s = function" % function_name
    print "  | [] -> 0"
    for i in xrange(number_of_variants):
        print "  | %s%s%s :: tl -> %s" % (("`" if polymorphic else ""), get_variant_name(i), args, expr)
    print

def gen_item_generator(polymorphic, number_of_variants = 240, number_of_args = 2):
    function_name = "gen_%s_item" % ("polymorphic" if polymorphic else "ordinal")
    args_list = lambda: ", ".join(["%d" % rand.randint(i * 2**16, (i + 1) * 2**16) for i in xrange(number_of_args)])
    args = lambda: "" if number_of_args == 0 else " (%s)" % args_list()
    print "let %s = function" % function_name
    for i in xrange(number_of_variants):
        print "  | %d -> %s%s%s" % (i, ("`" if polymorphic else ""), get_variant_name(i), args())
    print

def gen_generator(polymorphic, number_of_variants = 240):
    kind = "polymorphic" if polymorphic else "ordinal"
    generator = \
        "let rec gen_%s_list = function\n" + \
        "  | 0 -> []\n" + \
        "  | n -> gen_%s_item (n mod %d) :: gen_%s_list (n - 1)\n"
    print generator % (kind, kind, number_of_variants, kind)

def gen_bench(polymorphic):
    kind = "polymorphic" if polymorphic else "ordinal"
    bench = \
        "let bench_%s size number_of_repetitions =\n" + \
        "  let start_time = Unix.gettimeofday () in\n" + \
        "  let test_list = gen_%s_list size in\n" + \
        "  for i = 1 to number_of_repetitions do\n" + \
        "    ignore (fold_%s test_list)\n" + \
        "  done;\n" + \
        "  let elapsed_time = Unix.gettimeofday () -. start_time in\n" + \
        "  Printf.printf \"bench_%s: %%f seconds elapsed\\n\" elapsed_time;\n" + \
        "  elapsed_time\n"
    print bench % (kind, kind, kind, kind)

def gen_main(size, number_of_repetitions):
    print "let () ="
    print "  let ordinal_time = bench_ordinal %d %d in" % (size, number_of_repetitions)
    print "  let polymorphic_time = bench_polymorphic %d %d in" % (size, number_of_repetitions)
    print "  Printf.printf \"polymorphic / ordinal = %f\\n\" (polymorphic_time /. ordinal_time)\n"

def gen_all(number_of_variants = 246, number_of_args = 3, size = 50000, number_of_repetitions = 1000):
    gen_type(True, number_of_variants, number_of_args)
    gen_type(False, number_of_variants, number_of_args)
    gen_function(True, number_of_variants, number_of_args)
    gen_function(False, number_of_variants, number_of_args)
    gen_item_generator(True, number_of_variants, number_of_args)
    gen_item_generator(False, number_of_variants, number_of_args)
    gen_generator(True, number_of_variants)
    gen_generator(False, number_of_variants)
    gen_bench(True)
    gen_bench(False)
    gen_main(size, number_of_repetitions)

gen_all(int(sys.argv[1]), int(sys.argv[2]))

out.ml

(* Autogenerated by gen_bench.py 5 1 *)

type polymorphic = [
  | `VJzNnlv0 of int
  | `VQKaEES1 of int
  | `VXVnVXp2 of int
  | `VegAmqM3 of int
  | `VlrNDJj4 of int
]

type ordinal =
  | VJzNnlv0 of int
  | VQKaEES1 of int
  | VXVnVXp2 of int
  | VegAmqM3 of int
  | VlrNDJj4 of int

let rec fold_polymorphic = function
  | [] -> 0
  | `VJzNnlv0 (a0) :: tl -> a0 lxor fold_polymorphic tl
  | `VQKaEES1 (a0) :: tl -> a0 lxor fold_polymorphic tl
  | `VXVnVXp2 (a0) :: tl -> a0 lxor fold_polymorphic tl
  | `VegAmqM3 (a0) :: tl -> a0 lxor fold_polymorphic tl
  | `VlrNDJj4 (a0) :: tl -> a0 lxor fold_polymorphic tl

let rec fold_ordinal = function
  | [] -> 0
  | VJzNnlv0 (a0) :: tl -> a0 lxor fold_ordinal tl
  | VQKaEES1 (a0) :: tl -> a0 lxor fold_ordinal tl
  | VXVnVXp2 (a0) :: tl -> a0 lxor fold_ordinal tl
  | VegAmqM3 (a0) :: tl -> a0 lxor fold_ordinal tl
  | VlrNDJj4 (a0) :: tl -> a0 lxor fold_ordinal tl

let gen_polymorphic_item = function
  | 0 -> `VJzNnlv0 (61489)
  | 1 -> `VQKaEES1 (5647)
  | 2 -> `VXVnVXp2 (14591)
  | 3 -> `VegAmqM3 (54982)
  | 4 -> `VlrNDJj4 (61664)

let gen_ordinal_item = function
  | 0 -> VJzNnlv0 (41219)
  | 1 -> VQKaEES1 (8578)
  | 2 -> VXVnVXp2 (21078)
  | 3 -> VegAmqM3 (51755)
  | 4 -> VlrNDJj4 (36539)

let rec gen_polymorphic_list = function
  | 0 -> []
  | n -> gen_polymorphic_item (n mod 5) :: gen_polymorphic_list (n - 1)

let rec gen_ordinal_list = function
  | 0 -> []
  | n -> gen_ordinal_item (n mod 5) :: gen_ordinal_list (n - 1)

let bench_polymorphic size number_of_repetitions =
  let start_time = Unix.gettimeofday () in
  let test_list = gen_polymorphic_list size in
  for i = 1 to number_of_repetitions do
    ignore (fold_polymorphic test_list)
  done;
  let elapsed_time = Unix.gettimeofday () -. start_time in
  Printf.printf "bench_polymorphic: %f seconds elapsed\n" elapsed_time;
  elapsed_time

let bench_ordinal size number_of_repetitions =
  let start_time = Unix.gettimeofday () in
  let test_list = gen_ordinal_list size in
  for i = 1 to number_of_repetitions do
    ignore (fold_ordinal test_list)
  done;
  let elapsed_time = Unix.gettimeofday () -. start_time in
  Printf.printf "bench_ordinal: %f seconds elapsed\n" elapsed_time;
  elapsed_time

let () =
  let ordinal_time = bench_ordinal 50000 1000 in
  let polymorphic_time = bench_polymorphic 50000 1000 in
  Printf.printf "polymorphic / ordinal = %f\n" (polymorphic_time /. ordinal_time)

$ ./bench.sh
number_of_variants = 3, number_of_args = 2
bench_ordinal: 0.111527 seconds elapsed
bench_polymorphic: 0.306109 seconds elapsed
polymorphic / ordinal = 2.744710

number_of_variants = 5, number_of_args = 1
bench_ordinal: 0.110245 seconds elapsed
bench_polymorphic: 0.327958 seconds elapsed
polymorphic / ordinal = 2.974812

number_of_variants = 30, number_of_args = 1
bench_ordinal: 0.114785 seconds elapsed
bench_polymorphic: 0.392246 seconds elapsed
polymorphic / ordinal = 3.417225

number_of_variants = 30, number_of_args = 3
bench_ordinal: 0.123398 seconds elapsed
bench_polymorphic: 0.421935 seconds elapsed
polymorphic / ordinal = 3.419301

number_of_variants = 70, number_of_args = 4
bench_ordinal: 0.135165 seconds elapsed
bench_polymorphic: 0.514177 seconds elapsed
polymorphic / ordinal = 3.804069

number_of_variants = 170, number_of_args = 2
bench_ordinal: 0.110260 seconds elapsed
bench_polymorphic: 0.533869 seconds elapsed
polymorphic / ordinal = 4.841910

number_of_variants = 246, number_of_args = 2
bench_ordinal: 0.111801 seconds elapsed
bench_polymorphic: 0.547543 seconds elapsed
polymorphic / ordinal = 4.897473

$ ocamlopt.opt -version
4.01.0

$ cat /proc/cpuinfo
processor   : 0
<...>
model name  : Intel(R) Core(TM) i7-4790 CPU @ 3.60GHz
stepping    : 3
<...>