Re: OCaml vs. Lua for Datalog

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

The Lua version is at <http://datalog.sf.net>.

John

On Wed, Feb 6, 2013 at 9:09 AM, Ömer Sinan Ağacan <omeragacan@gmail.com> wrote:
> Can we see the source of Lua version ?
>
>
>
> 2013/2/6 Dimiter 'malkia' Stanev <malkia@gmail.com>
>>
>> Have you tried this against luajit?
>>
>> http://luajit.org
>>
>>
>> On 2/5/2013 3:25 PM, John D. Ramsdell wrote:
>>>
>>> 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
>>>
>>>
>>
>