Arc Forumnew | comments | leaders | submitlogin
Profiling with time, recursion faster or slower?
3 points by globalrev 6096 days ago | 7 comments
so i used (time (power 234 34445)) and got the following results:

nonrecursive: 8927 9434 8838 av: 9066msec

recursive: 8826 9447 9493 av: 9255msec

edit: then did this, better:

nonrecursive: arc> (time (repeat 100(power 12 12345))) time: 20141 msec. nil

recursive: arc> (time (repeat 100(power 12 12345))) time: 23484 msec. nil

but consideriing the difference between each run it seems it could swing either way, too small a samplesize.

but: 1) time isnt very reliable? 2) is there a better way to profile? 3) which are generally considered to be the fastest, recursive or imperative functions?

  (def power (nbr pow)
    (if (is pow 0) 1
        (> pow 0)
	    (let acc nbr
    		(for x 1 (- pow 1)
        		(= acc (* acc nbr))) acc)
	(< pow 0)
	    (let acc 1
    		(for x pow -1
			(= acc (/ acc nbr))) (/ acc 1.0))))

  (def power (nbr pow)
    (if (is pow 0) 
	    1
        (> pow 0)
	    (* nbr (power nbr (- pow 1)))
	(< pow 0)
	    (/ 1 (power nbr (* -1 pow)))))


3 points by cchooper 6096 days ago | link

Here are my results:

non-recursive: 13469 13610 13480 13098 13139 avg. 13360

recursive: 13199 13279 13249 13340 13329 avg. 13279

I also tried a tail-recursive version, which should be faster than simple recursive:

  (def power (nbr pow (o retval 1))
    (if (is pow 0)
            retval
        (> pow 0)
            (power nbr (- pow 1) (* nbr retval))
        (< pow 0)
            (power nbr (+ pow 1) (/ retval nbr))))
and I got this:

13450 13449 13449 12938 13139 avg. 13285

So it looks to me like MzScheme can optimise them all to be about equal.

Edit: actually, as Sacado pointed out, Arc expands for into a recursive function, so we're not really testing iteration.

-----

1 point by globalrev 6096 days ago | link

is it possible to do a tail-recursive power-function? would it then be faster than both or still slower than the normal recursive function?

-----

3 points by sacado 6096 days ago | link

Not tested, but it should work and is tail-recursive :

  (def power (nbr pow res)
    (if (is pow 0)
	    res
        (> pow 0)
            (power nbr (- pow 1) (* nbr res))
	(< pow 0)
            (power nbr (* -1 pow) (/ 1 res))))
Not sure for the case where (< pow 0), though. Just run the tests, but I think the tail-recursive function is at least as fast as the iterative one. Actually, in fine, iterative code is transformed into its tail-recursive equivalent : code involving for is transformed as a bunch of tail-recursive functions for example.

-----

1 point by globalrev 6096 days ago | link

is possible to make any of the 2 functions faster?

-----

2 points by cchooper 6096 days ago | link

You don't need to check that pow is less than zero in that last case.

  (def power (nbr pow)
    (if (is pow 0) 1
        (> pow 0)
	    (let acc nbr
    		(for x 1 (- pow 1)
        		(= acc (* acc nbr))) acc)
	(let acc 1
    	    (for x pow -1
		(= acc (/ acc nbr))) (/ acc 1.0))))

  (def power (nbr pow)
    (if (is pow 0) 
	    1
        (> pow 0)
	    (* nbr (power nbr (- pow 1)))
	(/ 1 (power nbr (* -1 pow)))))
Of course, if you want it to be really fast...

  (time (expt 234 34445)) => 101 msec.

-----

1 point by globalrev 6091 days ago | link

how can it be so much faster? its written in C or something? its built in the language somehow i guess, its not possible to recreate for me by writing a def?

-----

1 point by sacado 6090 days ago | link

It is probably written in C and does not check its args every time it is called. Basically, every time you call 'is, '<, '+, or any other primitive operation, it checks whether its arguments are numbers, then performs the operation. All these checks are useless since, within the body of your function, you know the type of your args are numbers, but you cannot avoid them anyway. Optimization will come, later :)

-----