From: jurgen_defurne
Subject: (Stupid) Implementation-dependent CL tricks ?
Date: 
Message-ID: <89b6ef22-4f9c-4180-a4a9-e9307938b0e8@w34g2000yqm.googlegroups.com>
Recently I came across the fact that I could, inside a function
definition, define another named function bound to the lexical
environment of the outer function. This worked as expected : the named
function was available, and it was a closure (a named closure?).

Upon further reflection I supposed that I could extend this in a
broader way. Use a top level 'let' to define a lexical environment and
in this environment define some named functions bound to it.

Simple example :

(let
         ((counter 1))
       (defun counter-up ()
         (incf counter))

       (defun counter-down ()
         (decf counter)))

Now, the main reason to do this was that a couple of weeks ago I did
some testing on access times of variable values in CLISP, and found
out that accessing a lexical variable was the fastest, accessing a
dynamic variable was only half as fast, and that accessing a member of
a structure or an array was very slow compared to both.

However, the same way of working in SBCL yielded less difference.
Lexical variables where still the fastest, but accessing dynamic
variables or array or structure members was comparatively much faster
than in CLISP, and the access times where more or less the same.

I know, premature optimisation is the root of all evil, but I can't
help it. If I can build a faster program with a SIMPLE change, then I
will use it.

Regards,

Jurgen

From: Jeff M.
Subject: Re: (Stupid) Implementation-dependent CL tricks ?
Date: 
Message-ID: <e9f5a27e-b930-4028-9458-30bbf8ec7ed9@e38g2000yqa.googlegroups.com>
On Mar 13, 8:33 am, jurgen_defurne <··············@pandora.be> wrote:
>
> Now, the main reason to do this was that a couple of weeks ago I did
> some testing on access times of variable values in CLISP, and found
> out that accessing a lexical variable was the fastest, accessing a
> dynamic variable was only half as fast, and that accessing a member of
> a structure or an array was very slow compared to both.
>

You're comparing apples, oranges, elephants, and cats together. ;-)

Lexical bindings can very often be optimized to a stack frame address
and sometimes even a register, based on usage in the code and the
optimizing power of the compiler (and SBCL is one of the best!).
Entire lexical environments can often times be pre-fetched into cache
as well, and are usually *very* small.

Dynamic bindings are powerful, but that power also comes with a little
bit of overhead. They are thread local (and if not would require a
lock for a write) and far away in address space compared to the code
being executed. While the algorithmic time to access them is
technically the same as a lexical binding - O(1) - there's a little
more work that needs to be done.

Structures can be implemented in many different ways, and I don't
believe the CL spec defined how an implementation decides to store a
structure internally. Also, the method by which you access the
structure can have a decent performance impact as well. Consider,

  (defstruct point x y z)

There are now several methods to access the members of the point
structure. You can use accessor methods (POINT-X, POINT-Y, POINT-Z),
get a slot by name (SLOT-VALUE, which could end up being O(N) at
worst), or a couple others. Each of these has its advantages and
disadvantages.

Arrays are... well, arrays.


> I know, premature optimisation is the root of all evil, ...

And you would be right. Don't worry about this. Honestly, if you are
dealing with an end-product for which 2 cycles or a few nanoseconds of
time is going to impact you, then my guess is Common Lisp is the wrong
choice for you; take a look at assembly, Forth, or possibly something
only slightly higher-level such as C.

My guess is that it doesn't matter, though, and what will be more
important in the end are the algorithmic complexities in the solutions
you choose to implement.

Each problem can be solved in many ways. That's why Common Lisp has so
many different tools at its disposal to solve them. Begin able to
directly access a structure member via function, or by name with SLOT-
VALUE. Lexical closures allow for a whole class of problems to be
simplified, as do dynamic bindings.

Make your program work, then start dealing with these things. Early
optimization is a good thing, but only at the big-picture level: 1 MB
of RAM vs. 400, O(1) vs. O(N^2), etc.

Jeff M.
From: Rob Warnock
Subject: Re: (Stupid) Implementation-dependent CL tricks ?
Date: 
Message-ID: <UZ6dnal3wMc8hibUnZ2dnUVZ_oTinZ2d@speakeasy.net>
Jeff M. <·······@gmail.com> wrote:
+---------------
| Lexical bindings can very often be optimized to a stack frame address
| and sometimes even a register, based on usage in the code and the
| optimizing power of the compiler (and SBCL is one of the best!).
+---------------

Indeed. However, lexical bindings can't be optimized into stack frame
addresses if they're shared between independent closures *and* are
mutated. [Note that if they're only shared and never mutated, the
bindings can safely be "split" and separate copies stored with each
closure.] In that case, the lexical variable must be evicted into the
heap. Implementations such as MzScheme and CMUCL [and presumably SBCL]
do this by rewriting such variables into indirect references to "box"es,
such that the binding between the "variable" and the box is again constant
[even though the box's contents are mutable], which permits sharing and/or
splitting/copying of the binding. For example, give this code:

    (defun make-account (&optional (initial-balance 0))
      (let ((balance initial-balance))
	(values (lambda () balance)  ; a "getter"
		(lambda (increment)  ; a "setter" [well, an "incrementer"]
		  (incr balance increment)))))

if can be re-written as:

    (defun make-account (&optional (initial-balance 0))
      (let ((balance (make-box :value initial-balance)))
	(values (lambda () (box-value balance))
		(lambda (increment)
		  (incr (box-value balance) increment)))))

and now the "balance" binding is read-only again
[after the initial binding] and can be safely shared/split.


-Rob

-----
Rob Warnock			<····@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607
From: John Thingstad
Subject: Re: (Stupid) Implementation-dependent CL tricks ?
Date: 
Message-ID: <op.uqqhvwriut4oq5@pandora.alfanett.no>
P� Fri, 13 Mar 2009 14:33:21 +0100, skrev jurgen_defurne  
<··············@pandora.be>:

> Recently I came across the fact that I could, inside a function
> definition, define another named function bound to the lexical
> environment of the outer function. This worked as expected : the named
> function was available, and it was a closure (a named closure?).
>
> Upon further reflection I supposed that I could extend this in a
> broader way. Use a top level 'let' to define a lexical environment and
> in this environment define some named functions bound to it.
>
> Simple example :
>
> (let
>          ((counter 1))
>        (defun counter-up ()
>          (incf counter))
>
>        (defun counter-down ()
>          (decf counter)))
>
> Now, the main reason to do this was that a couple of weeks ago I did
> some testing on access times of variable values in CLISP, and found
> out that accessing a lexical variable was the fastest, accessing a
> dynamic variable was only half as fast, and that accessing a member of
> a structure or an array was very slow compared to both.
>
> However, the same way of working in SBCL yielded less difference.
> Lexical variables where still the fastest, but accessing dynamic
> variables or array or structure members was comparatively much faster
> than in CLISP, and the access times where more or less the same.
>
> I know, premature optimisation is the root of all evil, but I can't
> help it. If I can build a faster program with a SIMPLE change, then I
> will use it.
>
> Regards,
>
> Jurgen


Lexical closures (what you describe above) are far from stupid. They are a  
powerful programming technique. A lexical closure is superior to global  
variables in some cases because it provides encapsulation. (The book "let  
over lambda" uses this extensively.) More important that the performance  
difference is the fact that global variables BEHAVE differently. They have  
dynamic scope.
Rather than give some sloppy and description I will just refer you to this  
link:
"Scope and extent" from Common Lisp the Language 2 ed."
http://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node43.html


--------------
John Thingstad