Allocation 
Author Message
 Allocation

Hi,
  What determines wether an object is allocated statically, on the stack or on
the heap in Lisp?
Thank you.

Fahd



Sun, 11 Jul 2004 23:43:55 GMT  
 Allocation

Quote:

> What determines wether an object is allocated statically, on the
> stack or on the heap in Lisp?

Why do you care about where it is allocated?  It depends very much
on the compiler you're using and it's optimization settings.

Regards,
--
Nils Goesche
"Don't ask for whom the <CTRL-G> tolls."

PGP key ID 0x42B32FC9



Mon, 12 Jul 2004 00:02:49 GMT  
 Allocation

Quote:

> Hi,
>   What determines wether an object is allocated statically, on the
> stack or on the heap in Lisp?

When writing code to solve a problem, you first care to get it right
and then to get it fast.  Hence the answer is

"in CL, you may avoid to think to such low level issues, and take care
of them only after extensive profiling of your application
bottlenecks".

Of course, your application may turn out to be just "fast enough", in
which case you are home free.

Once you get past profiling and you have determined that in some
places, stack allocation may speed up your code, the DYNAMIC-EXTENT
declaration, and a knowledge of the implementation you are using are
your friends.

Quote:
> Thank you.

You are welcome.

Cheers

--
Marco Antoniotti ========================================================
NYU Courant Bioinformatics Group        tel. +1 - 212 - 998 3488
719 Broadway 12th Floor                 fax  +1 - 212 - 995 4122
New York, NY 10003, USA                 http://bioinformatics.cat.nyu.edu
                    "Hello New York! We'll do what we can!"
                           Bill Murray in `Ghostbusters'.



Mon, 12 Jul 2004 00:11:05 GMT  
 Allocation

Quote:

>   What determines wether an object is allocated statically, on the stack or on
> the heap in Lisp?

To first order, everything is heap allocated.  Things may be stack
allocated if you either say they can be, they are defined in such a
way as to be stack allocatable (restarts), or if the compiler can
prove that stack allocation is safe.

I don't really know what static allocation is.

--tim



Mon, 12 Jul 2004 00:22:54 GMT  
 Allocation

Quote:

>Hi,
>  What determines wether an object is allocated statically, on the stack or on
>the heap in Lisp?

Lisp isn't defined in terms of these concepts. An object's lifetime
is called its extent.  The extent can be dynamic or indefinite.

Dynamic extent means that an object disappears when the expression in
which it was created terminates. This is obviously bad if the program
continues to refer to the object after that!  So dynamic extent isn't
done if the programmer doesn't explicitly request it with a declaration,
and might not be done even if the programmer does request it. Blowing away
dynamic-extent objects is a matter of compiler optimization.  The reason
Lisp programmers sometimes declare objects to have dynamic-extent is
simply for performance reasons; it may be possible to allocate the object
more efficiently, and generate less garbage or none at all.

Indefinite extent means that an object persists for as long as it cannot
be proven that the program can no longer refer to it. Indefinite extent
is the norm for objects things in Lisp, including lexical variable
bindings. Thus even if a function terminates, its local variables can
still be used, their values intact. This property is very important
to closures.

To get an effect similar to static variables in other programming
languages, you have two options.

One is to use special variables, which are Lisp's globals. When you assign
a value to some symbol that is not lexically bound, a global binding
is set up which persists until a different value is assigned. Using
a variable binding construct such as let causes a local binding to be
established which shadows any global ones or less enclosed local ones.

If you want a variable that is associated with some functions, whose
value persists across function calls, but is only known to those function,
you can surround function definitions in a lexical variable binding
construct:

(let ((count 0))
  (defun counting-function ()
    (incf count))
  ;; ... possibly other functions
)

(counting-function)  ==> 1
(counting-function)  ==> 2
(setf count 0)
(counting-function)  ==> 3

Here, count is not a global variable; as you can see by the lack of
effect that the (setf count 0) assignment has on the value computed
by counting-function. Rather, it is a lexical variable binding that
is captured by a closure. The (let ...) form is evaluated at the top
level right after it is read and establishes a local variable. The
functions defined within that form capture that variable's binding.
That binding has indefinite extent which allows it to persist
from one function call to the next.



Mon, 12 Jul 2004 00:37:45 GMT  
 Allocation

Quote:


> >   What determines wether an object is allocated statically, on the stack or on
> > the heap in Lisp?

> To first order, everything is heap allocated.  Things may be stack
> allocated if you either say they can be, they are defined in such a
> way as to be stack allocatable (restarts), or if the compiler can
> prove that stack allocation is safe.

> I don't really know what static allocation is.

In a generational GC (or any GC that copies, for that matter) it is
sometimes important to know that an object is not going to move.
This usually occurs in FFIs where you are converting a lisp object to
a foreign pointer, and it is important for that pointer to continue to
point to the same object at all times during the foreign call. If
the object is heap allocated, then the pointer becomes invalid if
the object moves out from under it during a GC, because the pointer
has been captured by the foreign language and is thus not affected
by the GC.  A static object removes any chance of the object moving
out from under a pointer in that manner.

Allegro CL provides for static objects, usually arrays (make-array
has an :allocation keyword as an extension, which can accept among other
things :static as its value) or foreign object types, which can be
specified as being in static (immovable) space.  In all cases, the
programmer makes the judgement that an object will be static as opposed
to the heap.

Also, stack-allocated objects can be considered static, though not
of indefinite scope like statically allocated objects.

--
Duane Rettig          Franz Inc.            http://www.franz.com/ (www)
1995 University Ave Suite 275  Berkeley, CA 94704



Mon, 12 Jul 2004 01:00:01 GMT  
 Allocation

Quote:

> In a generational GC (or any GC that copies, for that matter) it is
> sometimes important to know that an object is not going to move.
> This usually occurs in FFIs where you are converting a lisp object to
> a foreign pointer, and it is important for that pointer to continue to
> point to the same object at all times during the foreign call. If
> the object is heap allocated, then the pointer becomes invalid if
> the object moves out from under it during a GC, because the pointer
> has been captured by the foreign language and is thus not affected
> by the GC.  A static object removes any chance of the object moving
> out from under a pointer in that manner.

Yes, that's what I'd assume is meant normally in the context of Lisp
(except you've put it better than I would have).  But I am wondering,
in the context of the question, whether the person meant something
more like what C's `static' keyword does, which you'd typically
achieve in CL by either #. or LOAD-TIME-VALUE, I think:

(defun foo (n &optional m)
  (let ((v (load-time-value (make-array 10 :element-type 'real :initial-element 0))))
    (if (null m)
        (aref v n)
        (setf (aref v n) m))))

or something like that, anyway.  Of course this is, I guess, just heap
allocation at load time - I just thought that might be what they were
after, though I'm not sure.

--tim



Mon, 12 Jul 2004 02:39:44 GMT  
 Allocation
Thanks, Kaz, for your long and detailed articles.


Quote:
> Indefinite extent means that an object persists for as long as it cannot
> be proven that the program can no longer refer to it. Indefinite extent
> is the norm for objects things in Lisp, including lexical variable
> bindings. Thus even if a function terminates, its local variables can
> still be used, their values intact. This property is very important
> to closures.

I was wondering about the above.  Is it just not worded very carefully, or is
there something for me to learn here.  How can a function's local variables be
accessed?  (unless in (let (foo) (defun bar() foo)) foo can correctly be called
"local")

--
Coby



Mon, 12 Jul 2004 02:59:57 GMT  
 Allocation

[...]
    >> Indefinite extent means that an object persists for as long as
    >> it cannot be proven that the program can no longer refer to
    >> it. Indefinite extent is the norm for objects things in Lisp,
    >> including lexical variable bindings. Thus even if a function
    >> terminates, its local variables can still be used, their values
    >> intact. This property is very important to closures.

    CB> I was wondering about the above.  Is it just not worded very
    CB> carefully, or is there something for me to learn here.  

I don't know, but based on what you say below it might be that you are
confusing scope and extent.  I was going to write an ill-worded paragragh
and possibly cause Kent to come out here, but I am lazy so I googled:

http://www.psg.com/~dlamkins/sl/chapter08.html

appears very lucid.

    CB> How
    CB> can a function's local variables be accessed?  (unless in (let
    CB> (foo) (defun bar() foo)) foo can correctly be called "local")

(defun foo (x)
        (let (y)  
        ; ... something
                (list x y)))

you are returning y even though y is invisible outside foo.  This may appear
natural in CL but some languages don't allow thingsequivalent to this.  
Eg in C:

int * foo (int x)
{
   int y;
   // something
   return &y;

Quote:
}

is not kosher as &y makes no sense outside foo.  You can use 'static' to get
the semantics of your example or explicitly malloc the storage for the value
of y to give it indefinite extent (until free is called).

cheers,

BM



Mon, 12 Jul 2004 03:27:20 GMT  
 Allocation

Quote:

> I was wondering about the above.  Is it just not worded very carefully, or is
> there something for me to learn here.  How can a function's local variables be
> accessed?  (unless in (let (foo) (defun bar() foo)) foo can correctly be called
> "local")

Well, a better example is something like the standard kar/kons/kdr
thing (untested code, or perhaps kode).

(defun kons (car cdr)
  #'(lambda (key &optional val)
      (ecase key
        ((kar) car)
        ((set-kar) (setf car val))
        ((kdr) cdr)
        ((set-kdr) (setf cdr va)))))

(defun kar (kons)
  (funcall kons 'kar))

(defun kdr (kons)
  (funcall kons 'kdr))

(defun (setf kar) (new kons)
  (funcall kons 'set-kar new))

(defun (setf kdr) (new kons)
  (funcall kons 'set-kdr new))

where the local variables of KONS remain accessible by the closure it
returns.

--tim



Mon, 12 Jul 2004 03:39:27 GMT  
 Allocation

Quote:
>   What determines wether an object is allocated statically, on the stack
>   or on the heap in Lisp?

The implementation.

Quote:
> Thank you.

You're welcome.


Tue, 13 Jul 2004 12:09:21 GMT  
 Allocation

Quote:


> > In a generational GC (or any GC that copies, for that matter) it is
> > sometimes important to know that an object is not going to move.
> > This usually occurs in FFIs where you are converting a lisp object to
> > a foreign pointer, and it is important for that pointer to continue to
> > point to the same object at all times during the foreign call. If
> > the object is heap allocated, then the pointer becomes invalid if
> > the object moves out from under it during a GC, because the pointer
> > has been captured by the foreign language and is thus not affected
> > by the GC.  A static object removes any chance of the object moving
> > out from under a pointer in that manner.

> Yes, that's what I'd assume is meant normally in the context of Lisp
> (except you've put it better than I would have).  But I am wondering,
> in the context of the question, whether the person meant something
> more like what C's `static' keyword does, which you'd typically
> achieve in CL by either #. or LOAD-TIME-VALUE, I think:

Well, the "static" storage specifier in C basically means 'this is not
on the stack'.

Any variable taht's declared outside a function (global scope, as it
were) is by default static and can most easily be modelled by DEFVAR
or DEFPARAMETER, I think.

Something like:
int bad_incrementer (void)
{
  int n=0;

  return n++;

Quote:
}

can most easily be turned into:

(LET ((n 0))
  (DEFUN bad-incrementer ()
     (INCF n)))

Quote:
> (defun foo (n &optional m)
>   (let ((v (load-time-value (make-array 10 :element-type 'real :initial-element 0))))
>     (if (null m)
>         (aref v n)
>         (setf (aref v n) m))))

LOAD-TIME-VALUE works for arrays, but works less well for other things.

//Ingvar
--
"I'm in 386 enchanted mode."



Tue, 13 Jul 2004 18:02:37 GMT  
 Allocation

Quote:

> Well, the "static" storage specifier in C basically means 'this is not
> on the stack'.

Not really.  It also tells you things about the visibility for globals.

Quote:
> Any variable taht's declared outside a function (global scope, as it
> were) is by default static and can most easily be modelled by DEFVAR
> or DEFPARAMETER, I think.

Yes, but the interesting case is static *within* functions.

Quote:
> Something like:
> int bad_incrementer (void)
> {
>   int n=0;
>   return n++;
> }

Do you mean to have a `static' here?  Otherwise I can't understand the
below.

Quote:
> (LET ((n 0))
>   (DEFUN bad-incrementer ()
>      (INCF n)))

Or, alternatively, this:

(defun bad-incrementor ()
  (let ((x (load-time-value (list 0))))
    (incf (car x))))

Quote:
> LOAD-TIME-VALUE works for arrays, but works less well for other things.

Anything immutable (like a number) needs to be wrapped in a mutable
container, I agree.

--tim



Tue, 13 Jul 2004 23:17:29 GMT  
 Allocation

Quote:


> > Well, the "static" storage specifier in C basically means 'this is not
> > on the stack'.

> Not really.  It also tells you things about the visibility for globals.

That too, but I was quite sure taht the C standard said "the storage
class for variables defined in a global scope is ``static''". *shug*
C is quite often a bizarre language.

Quote:
> > Any variable taht's declared outside a function (global scope, as it
> > were) is by default static and can most easily be modelled by DEFVAR
> > or DEFPARAMETER, I think.

> Yes, but the interesting case is static *within* functions.

Yup.

Quote:
> > Something like:
> > int bad_incrementer (void)
> > {
> >   int n=0;

> >   return n++;
> > }

> Do you mean to have a `static' here?  Otherwise I can't understand the
> below.

Yep, "static int n=0;". Lack of proof-reading and a spine saying
"static inside a function, are you *sure* this is the right thing?".

Quote:
> > (LET ((n 0))
> >   (DEFUN bad-incrementer ()
> >      (INCF n)))

> Or, alternatively, this:

> (defun bad-incrementor ()
>   (let ((x (load-time-value (list 0))))
>     (incf (car x))))

> > LOAD-TIME-VALUE works for arrays, but works less well for other things.

> Anything immutable (like a number) needs to be wrapped in a mutable
> container, I agree.

Indeed. Though I still think the LET-wrapped defun is a closer
analogy. The latter feels more like poking at a struct. Not that it
makes a difference in the end, though.

//Ingvar
--
When the SysAdmin answers the phone politely, say "sorry", hang up and
run awaaaaay!
        Informal advice to users at Karolinska Institutet, 1993-1994



Wed, 14 Jul 2004 00:02:08 GMT  
 Allocation

Quote:

> That too, but I was quite sure taht the C standard said "the storage
> class for variables defined in a global scope is ``static''". *shug*
> C is quite often a bizarre language.

Yes, I think it may say that - it may be that static means a whole
load of things (which it kind of does - non-top-level static is
already sort of different than top-level static...).  I don't have
access to anything newer than a 2nd edition K&R to check unfortunately...

Quote:
> Indeed. Though I still think the LET-wrapped defun is a closer
> analogy. The latter feels more like poking at a struct. Not that it
> makes a difference in the end, though.

Yes, I think it is sort of better.  The load-time-value thing really
just shows that you can get the behaviour of a local variable which is
initialised once, at load-time though, without doing thing that I
suspect people who aren't comfortable with closures might find
uncomfortable.

--tim



Wed, 14 Jul 2004 00:25:24 GMT  
 
 [ 17 post ]  Go to page: [1] [2]

 Relevant Pages 

1. Memory allocation (was: Re: Herman wants dynamic allocation)

2. Stack based allocation vs. Dynamic allocation

3. Changing static allocation to dynamic allocation.

4. Dynamic Allocation

5. Checking for INTRDR allocation

6. Space Allocation on P/390

7. ?? Tape Unit Reserved for dynamic allocation - HELP!!

8. Dynamic Allocation question for C or assembler experts.

9. TeX, Pascal/VS, dynamic memory allocation, and so forth

10. Memory allocation on DOS 6.22 / TAWK 4.0

11. RAM allocation weirdness

 

 
Powered by phpBB® Forum Software