argument-passing vs. dynamic variable lookup

Discussion of Common Lisp
Post Reply
garethw
Posts: 43
Joined: Fri Jul 13, 2012 12:56 pm
Location: Ottawa, ON

argument-passing vs. dynamic variable lookup

Post by garethw » Sat Oct 27, 2012 6:49 pm

For anyone who was curious as I was, I ran a quick and dirty test of the cost of doing dynamic variable lookups versus argument-passing.

Here's what I ran:

Code: Select all

(defparameter *cycle* 0)

(defun test-arg (num cycle)
  (rem cycle (1+ num)))

(defun test-dyn (num)
  (rem *cycle* (1+ num)))

(defun measure ()
  (time
   (let ((cycle 0)
         (acc 0))
     (dotimes (n 100000000)
       (Incf acc (test-arg n cycle))
       (incf cycle 7))))
  (time
   (let ((acc 0))
     (dotimes (n 100000000)
       (incf acc (test-dyn n))
       (incf *cycle* 7))))
  (time
   (let ((acc 0)
         (*cycle* 0))
     (dotimes (n 100000000)
       (Incf acc (test-dyn n))
       (incf *cycle* 7)))))
It looks at three scenarios: straight argument passing, using a special variable with its default binding, and using a special variable with a local binding. The test functions themselves don't do anything sensible, just calculating a remainder to give them something to do in each call.

Comments on methodology welcome!

Seems the results won't fit, so I'll post in a reply...
~garethw

garethw
Posts: 43
Joined: Fri Jul 13, 2012 12:56 pm
Location: Ottawa, ON

Re: argument-passing vs. dynamic variable lookup

Post by garethw » Sat Oct 27, 2012 6:55 pm

So here's a typical run on my system:

Code: Select all

(measure)
Evaluation took:
  5.237 seconds of real time
  5.236327 seconds of total run time (5.236327 user, 0.000000 system)
  99.98% CPU
  13,437,789,476 processor cycles
  32,768 bytes consed

Evaluation took:
  5.759 seconds of real time
  5.760360 seconds of total run time (5.760360 user, 0.000000 system)
  100.02% CPU
  15,041,308,093 processor cycles
  0 bytes consed

Evaluation took:
  6.153 seconds of real time
  6.156385 seconds of total run time (6.156385 user, 0.000000 system)
  100.05% CPU
  16,070,373,242 processor cycles
  65,168 bytes consed
  
AMD Athlon(tm) 64 X2 Dual Core Processor 5000
2G RAM
Debian GNU/Linux 6.0.6 (squeeze)
SBCL 1.1.0
~garethw

Konfusius
Posts: 62
Joined: Fri Jun 10, 2011 6:38 am

Re: argument-passing vs. dynamic variable lookup

Post by Konfusius » Sun Oct 28, 2012 3:21 am

Variable lookup is done only in interpreted Lisps. In modern compiled Lisps the "lookup" cost of dynamic and lexical variables is the same as for global and local variables in C++.

garethw
Posts: 43
Joined: Fri Jul 13, 2012 12:56 pm
Location: Ottawa, ON

Re: argument-passing vs. dynamic variable lookup

Post by garethw » Sun Oct 28, 2012 9:32 am

Konfusius wrote:Variable lookup is done only in interpreted Lisps. In modern compiled Lisps the "lookup" cost of dynamic and lexical variables is the same as for global and local variables in C++.
I'm a bit confused by this.

I don't see how the cost of accessing a global variable in C - which is just an address, and is established before runtime - can be compared to resolving a dynamic variable, whose value has to be assessed by first determining the dynamic environment in which its used, which is obviously only known at runtime.

Perhaps "lookup" was the wrong term to use - I just meant "resolution of the value of a dynamic variable". There must surely be some cost to the machinery needed to establish dynamic environment, and this is what I was trying to measure. My tests show that it is small but non-trivial. I'm pretty sure that the difference between using a parameter vs using a global in C or C++ would have been considerably smaller than the differential I see here. But I admit I have not yet measured it.

Have I missed something? I suppose that's likely. I have a pretty good idea of what a compiler generates (unoptimized, at least) for my C or C++ code; I can't say the same for Lisp.
~garethw

Post Reply