cost of argument passing in scheme [closed]

Question

Closed. This question needs details or clarity. It is not currently accepting answers.

---

Want to improve this question? Add details and clarify the problem by editing this post.

Closed 8 years ago.

Improve this question

I found a interesting thing. Passing argument may deserve consideration, especially in which situation time is important. the code like below.

(define (collatz-num n)
  (define (collatz-iter n m)
    (cond
     ((= n 1)
      m)
     ((even? n)
      (collatz-iter (/ n 2) (+ m 1)))
     (else
      (collatz-iter (+ (* 3 n) 1) (+ m 1)))))
  (collatz-iter n 1))


(define (collatz-iter n m)
  (cond
   ((= n 1)
    m)
   ((even? n)
    (collatz-iter (/ n 2) (+ m 1)))
   (else
    (collatz-iter (+ (* 3 n) 1) (+ m 1)))))

(define (euler14 n limit)
  (define (help-iter m len n limit)
    (let ((collatz (collatz-iter n 1)))
      (cond
       ((> n limit)
        (list m len))
       ((> collatz len)
        (help-iter n collatz (+ n 2) limit))
       (else
        (help-iter m len (+ n 2) limit)))))
  (help-iter 0 0 n limit))

for collatz-iter

> (time (euler14 1 1000000))
cpu time: 1596 real time: 1596 gc time: 0

for collatz-num

> (time (euler14 1 1000000))
cpu time: 1787 real time: 1789 gc time: 0

My question:

1. How big is the cost of passing argument in scheme

2. In function euler14, I let limit as argument of help-iter, will it save some time this way? as I have seen somewhere, the free variable will have cost.

Maybe I am too mean.

Answer 1

Again. this is very implementation specific!

I tested your code and since it does consume memory and do a lot of computations the order in which I tested the two interfered with the second result. I separated the two tests in each file and run each 40 times separately and looked at average running time for both. The differences were num: 1059.75 and iter: 1018.85. 4% difference on average, but might as well be 12% when picking two samples. I'd guess the running time of the same program might differ in more than 4% on average so the difference between these are irrelevant in one run.

You have an extra application in your code so to check how much impact an argument has I made this little test. The usage of the arguments in the base case is so that Scheme won't optimize them away:

(define (three-params x y z)
  (if (zero? x)
      (cons y z)
      (three-params (- x 1) x x)))

(define (two-params x y)
  (if (zero? x)
      (cons x y)
      (two-params (- x 1) x)))

(define (one-param x)
    (if (zero? x)
      (cons x x)
      (one-param (- x 1))))

(define numtimes 100000000)
(time (one-param  numtimes))
(time (two-params numtimes #f))
(time (three-params numtimes #f #f))

Comment out 2 of the three last lines and make 3 files. Compile them if you can. The do the average of several runs. I choose 50 and in Ikarus I get the following averages:

      agvms  diffms
one   402.4
two   417.82 15.42
three 433.14 15.32
two2  551.38 133.56 (with an extra addition compared to two)

Just looking at the 50 results I see that the times overlap between one, two, and three, but statistically it looks like the average argument cost 0,15ns. if, zero?, - and cons and gc cost a lot more even if they are primitives. Neither extra applications nor extra arguments should be your concern. Sometimes a different implementation optimizes your code differently so changing from racket to ikarus, gambit or chicken might improve you code in production.