Curried performance

[Julian Fondren]

Consider the following:

#include "share/atspre_staload.hats"

typedef oobindex(n:int) = [m:int | m >= ~1; m < n] int(m)
typedef coins(n:int) = arrayref(int, n)

fun count{n:nat}(sum: int, i: oobindex(n), coins: coins(n)): int =
        ifcase
        | i < 0 => 0
        | sum < 0 => 0
        | sum = 0 => 1
        | _ => smaller + same where {
                val smaller = count(sum, i-1, coins)
                val same = count(sum - coins[i], i, coins)
        }

val coins = (arrayref)$arrpsz{int}(1, 5, 10, 25, 50)
implement main0() =
        println!("(A) count(1000) = ", count(1000, 4, coins))

and:

#include "share/atspre_staload.hats"

typedef oobindex(n:int) = [m:int | m >= ~1; m < n] int(m)
typedef coins(n:int) = arrayref(int, n)

fun count{n:nat}(sum: int)(i: oobindex(n))(coins: coins(n)): int =
        ifcase
        | i < 0 => 0
        | sum < 0 => 0
        | sum = 0 => 1
        | _ => smaller + same where {
                val smaller = count(sum)(i-1)(coins)
                val same = count(sum - coins[i])(i)(coins)
        }

val coins = (arrayref)$arrpsz{int}(1, 5, 10, 25, 50)
implement main0() =
        println!("(A) count(1000) = ", count(1000)(4)(coins))

Compiled and timed:

$ patscc -DATS_MEMALLOC_GCBDW -O3 -o coin coin.dats -lgc
$ patscc -DATS_MEMALLOC_GCBDW -O3 -o coin2 coin2.dats -lgc
$ for v in '' 2; do for x in 1 2 3; do time ./coin$v; done; echo -----; done
(A) count(1000) = 801451

real    0m0.363s
user    0m0.355s
sys     0m0.009s
(A) count(1000) = 801451

real    0m0.307s
user    0m0.303s
sys     0m0.004s
(A) count(1000) = 801451

real    0m0.307s
user    0m0.305s
sys     0m0.002s
-----
(A) count(1000) = 801451

real    0m33.251s
user    0m36.228s
sys     0m7.117s
(A) count(1000) = 801451

real    0m35.519s
user    0m38.485s
sys     0m6.951s
(A) count(1000) = 801451

real    0m36.157s
user    0m39.029s
sys     0m7.151s
-----

s -lgc

"Introduction to Programming in ATS" already recommends against currying, but with the above in mind I'd recommend against it a bit more strongly :)

[Hongwei Xi]

As of now, ATS does not perform any optimization wrt. currying.

So calling curried functions results in closures to be formed at run-time,

which can be very costly in terms of performance.

An optimizer for currying essentially turns your second version of 'count'

into the first version. I will try to structure ATS3 in a way to allow interested

parties to provide such optimizers.

Cheers!

--
You received this message because you are subscribed to the Google Groups "ats-lang-users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ats-lang-user...@googlegroups.com.
To post to this group, send email to ats-lan...@googlegroups.com.
Visit this group at https://groups.google.com/group/ats-lang-users.
To view this discussion on the web visit https://groups.google.com/d/msgid/ats-lang-users/3e73ad42-12b4-4749-a409-dc54e47b732c%40googlegroups.com.