Darren New <dne### [at] sanrrcom> wrote:
> http://www.iecc.com/gclist/GC-faq.html

  "Most allocated objects have short lifetimes."

  Hmm, that may be so with languages which force you to allocate everything
on the heap (ie. things which potentially have longer lifetimes than
stack-allocated local objects).

  Personally I seldom find myself allocating memory dynamically for short
periods of time in time-critical parts of the program, when coding in C++.
Most short-lived objects and variables can usually be handled on the stack.

  Stack allocation is actually pretty fast (at least with gcc in linux).
I have made some tests which sometimes even gave surprising results:
Having a single heap-allocated array which is used by a function each
time this function is called can sometimes be even slower than having
the function allocate the array from the stack each time it's called.
(In other words, having allocated an array just once with 'new' and
having the function, which is being called repeatedly, just use that
array, may in some cases be slower than if the function allocated the
array for itself from the stack each time the function is called.)

  That's a bit surprising of a result, but might be explainable by
cache behavior or something similar.

  (The reason why I tested this was because having the function use
the externally-allocated array is not thread-safe, while having it
allocate the array locally is.)

-- 
                                                          - Warp

Post a reply to this message

On Mon, 31 Mar 2008 22:58:31 +0200, Warp <war### [at] tagpovrayorg> wrote:
>   Stack allocation is actually pretty fast (at least with gcc in linux).

That stack allocation is fast should come as no surprise since it  
typically requires a grand total of zero additional CPU instructions. In  
the worst case it requires a single one-cycle instruction.


-- 
FE

Post a reply to this message

Warp wrote:
> (Naturally if it's a long chain of references, destroying the first
> object will destroy all the others like dominoes falling.)

That's where the "nondeterministic time" comes in with reference 
counting, just so you recognise.

>> Reference counting really is far too simplistic to work properly.
> 
>   Well, as long as you don't have circular references (there are ways
> to make it *difficult* to create them) I don't see a problem.

That's the primary problem, yes. That, and the size of the counter, if 
it needs to be the same as the size of a pointer. And that it's probably 
the slowest way to do GC.

-- 
   Darren New / San Diego, CA, USA (PST)
     "That's pretty. Where's that?"
          "It's the Age of Channelwood."
     "We should go there on vacation some time."

Post a reply to this message

Warp wrote:
> Darren New <dne### [at] sanrrcom> wrote:
>> http://www.iecc.com/gclist/GC-faq.html
> 
>   "Most allocated objects have short lifetimes."
> 
>   Hmm, that may be so with languages which force you to allocate everything
> on the heap (ie. things which potentially have longer lifetimes than
> stack-allocated local objects).

And if it's not on the heap, but on the stack instead, it *still* has a 
pretty short lifetime. :-)

>   Personally I seldom find myself allocating memory dynamically for short
> periods of time in time-critical parts of the program, when coding in C++.
> Most short-lived objects and variables can usually be handled on the stack.

Yep. And a lot of languages are smart enough to figure that out 
automatically. Not Java as initially implemented.

One of the advantages of letting the compiler handle stuff like this for 
you is that the compiler can get smarter.

>   That's a bit surprising of a result, but might be explainable by
> cache behavior or something similar.

Yeah, or better addressing modes maybe?

-- 
   Darren New / San Diego, CA, USA (PST)
     "That's pretty. Where's that?"
          "It's the Age of Channelwood."
     "We should go there on vacation some time."

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> Warp wrote:
> > (Naturally if it's a long chain of references, destroying the first
> > object will destroy all the others like dominoes falling.)

> That's where the "nondeterministic time" comes in with reference 
> counting, just so you recognise.

  How is that nondeterministic? It's perfectly predictable when those
objects will be destroyed. Just because destroying one object causes
the destruction of another doesn't make it "nondeterministic".

-- 
                                                          - Warp

Post a reply to this message

Fredrik Eriksson <fe79}--at--{yahoo}--dot--{com> wrote:
> On Mon, 31 Mar 2008 22:58:31 +0200, Warp <war### [at] tagpovrayorg> wrote:
> >   Stack allocation is actually pretty fast (at least with gcc in linux).

> That stack allocation is fast should come as no surprise since it  
> typically requires a grand total of zero additional CPU instructions. In  
> the worst case it requires a single one-cycle instruction.

  But so does using a pre-allocated array. The array is *already* allocated.
The function doesn't need to allocate it each time. Yet, in some cases,
the function becomes faster by using the stack-allocated array than the
pre-allocated array in the heap.

-- 
                                                          - Warp

Post a reply to this message

On Tue, 01 Apr 2008 11:08:34 +0200, Warp <war### [at] tagpovrayorg> wrote:
> Fredrik Eriksson <fe79}--at--{yahoo}--dot--{com> wrote:
>> That stack allocation is fast should come as no surprise since it
>> typically requires a grand total of zero additional CPU instructions. In
>> the worst case it requires a single one-cycle instruction.
>
>   But so does using a pre-allocated array. The array is *already*  
> allocated.
> The function doesn't need to allocate it each time. Yet, in some cases,
> the function becomes faster by using the stack-allocated array than the
> pre-allocated array in the heap.

Two points to consider:

- Data locality
Allocating the array from the stack keeps it close to the local variables,  
thus confining memory accesses to a smaller area. This plays better with  
memory caches.

- Register contention
Accessing a heap-allocated array requires loading its address into a CPU  
register. Accessing a stack-allocated array can be done with the stack  
register, freeing other registers for use in calculations.


-- 
FE

Post a reply to this message

Warp wrote:
>   How is that nondeterministic? It's perfectly predictable when those
> objects will be destroyed. Just because destroying one object causes
> the destruction of another doesn't make it "nondeterministic".

You can't tell by looking at
   a = null;
how long it will take to execute that statement.

It depends entirely on how long the system has been running, how much 
data is hanging off pointers in "a", and so on. I.e., you get the same 
sort of stop-and-wait-for-GC that you get with mark-and-sweep.

This is usually people talking about things close to real time but not 
critical enough to actually figure out how long it would take, like 
games and such.

If "a" points to a parsed XML file read from a file specified by the 
user, you don't know how long it'll take to collect it, as an example.

-- 
   Darren New / San Diego, CA, USA (PST)
     "That's pretty. Where's that?"
          "It's the Age of Channelwood."
     "We should go there on vacation some time."

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> Warp wrote:
> >   How is that nondeterministic? It's perfectly predictable when those
> > objects will be destroyed. Just because destroying one object causes
> > the destruction of another doesn't make it "nondeterministic".

> You can't tell by looking at
>    a = null;
> how long it will take to execute that statement.

  By the same logic something like 'printf("Hello\n");' is nondeterministic
because I can't know how long it will take. It could take hours for all
I know.

  The subject was about deterministic object destruction, not deterministic
runtime.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
>   The subject was about deterministic object destruction, not deterministic
> runtime.

No, actually, my comment was
    That's where the "nondeterministic time" comes in with reference
    counting, just so you recognise.

*I* was talking about the fact that people discussing real-time GC don't 
like reference counting because you have to run an arbitrarily large 
number of links to reclaim memory.

When it happens is deterministic. How long it takes is (while 
deterministic) too complicated to calculate reliably.

-- 
   Darren New / San Diego, CA, USA (PST)
     "That's pretty. Where's that?"
          "It's the Age of Channelwood."
     "We should go there on vacation some time."

Post a reply to this message