Ur Performance Comparisons

From Impredicative Wiki
Revision as of 11:59, 14 February 2010 by Adam Chlipala (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Contents

OPA

This is a simple comparison of recursive function execution time, based on one performed for OPA. See the "Performance" section of their documentation. You can download the Ur/Web source code for this comparison.

The Ur examples are compiled as CGI scripts generating pages containing the text that, in the OPA versions, is written to a log channel instead. If anything, this should only add overhead. OPA programs are compiled with no extra compiler flags; I don't know whether this corresponds to "with optimizations" or "without optimizations" on the OPA performance page.

Preliminaries: Implementing a Bit of the OPA Standard Library

File int.urs:

val fold : a ::: Type -> (a -> int -> a) -> a -> int -> a

File int.ur:

fun fold [a] (f : a -> int -> a) (i : a) max =
    let
        fun ifold acc n =
            if n < max then
                ifold (f acc n) (n + 1)
            else
                acc
    in
        ifold i 0
    end

Test 1: Stack management

Ur source:

fun fibo n =
    if n <= 1 then
        1
    else
        fibo (n - 1) + fibo (n - 2)

fun main () =
    let
        val result = Int.fold (fn _ n => fibo n) 0 40
    in
        return <xml>Computed {[result]}</xml>
    end

OPA compilation:

time opa stack.opa
real	0m15.525s
user	0m15.125s
sys	0m0.300s

Ur/Web compilation:

time urweb -protocol cgi stack
real	0m1.272s
user	0m0.988s
sys	0m0.288s

OPA execution:

time ./stack.exe
real	0m23.284s
user	0m23.217s
sys	0m0.032s

Ur/Web execution:

time REQUEST_METHOD=GET SCRIPT_NAME=/Stack/main </dev/null ./stack.exe
real	0m1.611s
user	0m1.604s
sys	0m0.004s

It's worth noting that, while the OPA performance page says this program contains "two non-optimisable recursive calls," the Ur/Web program is compiled into a loop-like form, thanks to standard GCC optimizations.

Test 2: Loops

Ur source:

fun fibo n = 
    let
        fun aux a b i =
            if i > n then
                a
            else
                aux (a + b) a (i + 1)
    in
        aux 1 1 2
    end

fun main () =
    let
        val result = Int.fold (fn _ n =>
                                  Int.fold (fn _ _ => fibo(n)) 0 1000000)
                              0 40
    in
        return <xml>Computed {[result]}</xml>
    end

OPA compilation:

time opa loop.opa
real	0m15.774s
user	0m15.385s
sys	0m0.340s

Ur/Web compilation:

time urweb -protocol cgi loop
real	0m1.300s
user	0m1.032s
sys	0m0.264s

OPA execution:

time ./loop.exe
real	0m33.161s
user	0m33.066s
sys	0m0.024s

Ur/Web execution:

time REQUEST_METHOD=GET SCRIPT_NAME=/Loop/main </dev/null ./loop.exe
real	0m1.477s
user	0m1.472s
sys	0m0.000s
Personal tools