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
