OCaml vs. Lua for Datalog

classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

OCaml vs. Lua for Datalog

John D. Ramsdell
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

Reply | Threaded
Open this post in threaded view
|

Re: OCaml vs. Lua for Datalog

Dimiter 'malkia' Stanev
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
>
>

Reply | Threaded
Open this post in threaded view
|

Re: OCaml vs. Lua for Datalog

Ömer Sinan Ağacan
Can we see the source of Lua version ?


2013/2/6 Dimiter 'malkia' Stanev <[hidden email]>
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




Reply | Threaded
Open this post in threaded view
|

Re: OCaml vs. Lua for Datalog

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

John

On Wed, Feb 6, 2013 at 9:09 AM, Ömer Sinan Ağacan <[hidden email]> wrote:

> Can we see the source of Lua version ?
>
>
>
> 2013/2/6 Dimiter 'malkia' Stanev <[hidden email]>
>>
>> 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
>>>
>>>
>>
>

Reply | Threaded
Open this post in threaded view
|

Re: OCaml vs. Lua for Datalog

John D. Ramsdell
In reply to this post by Dimiter 'malkia' Stanev
I have not tried LuaJIT, but forecasts say I might be snowed in
soon--a perfect time to investigate it.

John

On Tue, Feb 5, 2013 at 10:08 PM, Dimiter 'malkia' Stanev
<[hidden email]> wrote:

> 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
>>
>>
>

Reply | Threaded
Open this post in threaded view
|

Re: OCaml vs. Lua for Datalog

John D. Ramsdell
Testing using LuaJIT wasn't that difficult.  You just have to
configure Datalog with:

$ ./configure CPPFLAGS=-I/usr/include/luajit-2.0 --with-lua-suffix=jit-5.1

My results say LuaJIT 2.0.0 didn't do all that much better than Lua 5.1.4.

John

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

        LuaJIT vs. OCaml Datalog Performance

        Elapsed Time    Max Resident

induction 200
LuaJIT  0.23 Sec        3188 KB
OCaml   0.02 Sec        3888 KB

induction 500
LuaJIT  0.80 Sec        5788 KB
OCaml   0.13 Sec        4800 KB

induction 1000
LuaJIT  2.39 Sec        9840 KB
OCaml   0.49 Sec        6816 KB

induction 1500
LuaJIT  5.07 Sec        14016 KB
OCaml   1.09 Sec        8848 KB

reachable 200
LuaJIT  0.66 Sec        28340 KB
OCaml   0.24 Sec        15616 KB

reachable 500
LuaJIT  7.92 Sec        147080 KB
OCaml   2.43 Sec        81856 KB

reachable 1000
LuaJIT  56.49 Sec       573824 KB
OCaml   19.71 Sec       323516 KB

reachable 1500
LuaJITnot enough memory
Internal error in dl_ask
        63.40 Sec       1027572 KB
OCaml   47.40 Sec       683024 KB

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

        Lua vs. OCaml Datalog Performance

        Elapsed Time    Max Resident

induction 200
Lua     0.16 Sec        3912 KB
OCaml   0.02 Sec        3884 KB

induction 500
Lua     0.90 Sec        8328 KB
OCaml   0.13 Sec        4796 KB

induction 1000
Lua     3.66 Sec        14444 KB
OCaml   0.49 Sec        6808 KB

induction 1500
Lua     8.86 Sec        20664 KB
OCaml   1.09 Sec        8844 KB

reachable 200
Lua     1.01 Sec        40316 KB
OCaml   0.24 Sec        15608 KB

reachable 500
Lua     6.86 Sec        229144 KB
OCaml   2.43 Sec        81852 KB

reachable 1000
Lua     28.51 Sec       972408 KB
OCaml   19.59 Sec       323508 KB

reachable 1500
Lua     70.63 Sec       2169552 KB
OCaml   47.47 Sec       681840 KB


On Wed, Feb 6, 2013 at 5:01 PM, John D. Ramsdell <[hidden email]> wrote:

> I have not tried LuaJIT, but forecasts say I might be snowed in
> soon--a perfect time to investigate it.
>
> John
>
> On Tue, Feb 5, 2013 at 10:08 PM, Dimiter 'malkia' Stanev
> <[hidden email]> wrote:
>> 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
>>>
>>>
>>