OCaml vs. Lua for Datalog

["John D. Ramsdell" <ramsdell0@...>]

I came across the sources to an implementation of Datalog I wrote in
OCaml and placed them on GitHub at
<https://github.com/ramsdell/ocaml-datalog>.  The algorithm is
identical to the one I wrote in Lua, in fact, the OCaml version
preceded the Lua version.  I used a test suite created by Simon
Cruanes and compared the elapse time and the max resident memory size
of the two programs.  Lua was a bit slower and used more memory.  Not
unexpected I suppose.

John

---------------------------------------------------------

	Lua vs. OCaml Datalog Performance

	Elapsed Time	Max Resident

induction 200
Lua	0.25 Sec	3916 KB
OCaml	0.03 Sec	3884 KB

induction 500
Lua	1.42 Sec	8328 KB
OCaml	0.20 Sec	4800 KB

induction 1000
Lua	5.65 Sec	14440 KB
OCaml	0.77 Sec	6808 KB

induction 1500
Lua	14.26 Sec	20668 KB
OCaml	1.16 Sec	8844 KB

reachable 200
Lua	1.05 Sec	40316 KB
OCaml	0.25 Sec	15608 KB

reachable 500
Lua	7.14 Sec	229216 KB
OCaml	3.37 Sec	81852 KB

reachable 1000
Lua	40.16 Sec	972408 KB
OCaml	25.36 Sec	323516 KB

reachable 1500
Lua	97.66 Sec	2169556 KB
OCaml	61.68 Sec	681012 KB
---------------------------------------------------------
#! /bin/sh

# Compares the performance of Datalog in Lua and Datalog in OCaml

# Based on a test suite by Simon Cruanes <https://github.com/c-cube>

# Be sure to make OCaml Datalog with "make native-code"

# Location of Datalog in Lua
DATALOG=${1:-datalog}

# Sizes of test cases
TESTS="200 500 1000 1500"

# Time format
export TIME="\t%e Sec\t%M KB"

# INDUCTION TEST

# Generate a recursive induction example of given size; it makes rules
# p(n+1) if p(n),q(n+1)
# and
# q(n+1) if p(n), q(n)
# for n ranging in [0...size], and adds facts p(0) and q(0)

induction() {
    local n=${1:-10}
    echo '% Problem size: '$n
    for ((i=0; i<$n; i++))
    do
	let j=$i+1
	echo 'p('$j') :- p('$i'), q('$j').'
	echo 'q('$j') :- p('$i'), q('$i').'
    done
    echo 'p(0).'
    echo 'q(0).'
    echo 'p(X)?'
}

# REACHABLE TEST

# Generate a graph example of given size. It produces a cyclic graph
# with vertices in [0...size-1] and edges from i to i+1 mod size. The
# single rule computes a transitive closure of the graph, the
# predicate reachable() describes a clique of size size.

reachable() {
    local n=${1:-10}
    echo '% Problem size: '$n
    echo 'reachable(X,Y) :- edge(X,Y).'
    echo 'reachable(X,Y) :- edge(X,Z), reachable(Z,Y).'
    for ((i=0; i<$n; i++))
    do
	let j=$i+1
	echo 'edge('$i', '$j').'
    done
    echo 'edge('$n', 0).'
    echo 'reachable(X,Y)?'
}

printf "\tLua vs. OCaml Datalog Performance\n\n"
printf "\tElapsed Time\tMax Resident\n"

for i in ${TESTS}
do
    echo
    echo induction $i
    echo -n Lua
    induction $i | /usr/bin/time $DATALOG -o /dev/null
    echo -n OCaml
    induction $i | /usr/bin/time ./datalog -o /dev/null
done

for i in ${TESTS}
do
    echo
    echo reachable $i
    echo -n Lua
    reachable $i | /usr/bin/time $DATALOG -o /dev/null
    echo -n OCaml
    reachable $i | /usr/bin/time ./datalog -o /dev/null
done