Darren New <dne### [at] sanrrcom> wrote:
> Warp wrote:
> >   Oh, you have discovered a method to completely avoid memory
> > fragmentation? :-o Is it efficient?

> Yes, and yes.

  That would mean that the memory allocation engine knows ahead of time
the order in which objects will be "forgotten" (ie. nothing points to them
anymore so they can be freed) so that it can group them in contiguous
memory. Of course this is impossible (not even by analyzing the program
because the order in which objects are "forgotten" may depend on things
like user input).

  The only other alternative is that it performs memory defragmentation
before freeing the objects. But that doesn't sound any faster than
freeing the objects directly. (Memory defragmentation is something
useful per se, but doesn't sound like a fast way of freeing objects
in highly fragmented memory before the defragmentation has happened.)

  Oh, of course there's a third possibility: It doesn't free objects if
freeing them would cause fragmentation. But then they would consume
memory even though they are not used. Doesn't sound reasonable if that
memory would be needed for something else.

-- 
                                                          - Warp

Post a reply to this message

>   Btw, could you finally give me even a slight hint at how GC knows
> that an object is not used anylonger?
> 
>   I don't get it.

You mark every object that exists as "garbage". Then you take each 
global variable, local variable in currently running threads, etc. in 
turn, and you mark the object that variable points to as "not garbage". 
And then you find every object it points to and mark all those as "not 
garbage". And then all the objects that *those* objects point to, and so 
forth. Follow all the pointers until you stop finding objects that 
aren't already marked.

At this point, anything still marked "garbage" gets deleted.

Simple, really. And slow. And various optimisations make it go much faster.

Post a reply to this message

>>>   Oh, you have discovered a method to completely avoid memory
>>> fragmentation? :-o Is it efficient?
> 
>> Yes, and yes.
> 
>   That would mean that the memory allocation engine knows ahead of time
> the order in which objects will be "forgotten" (ie. nothing points to them
> anymore so they can be freed) so that it can group them in contiguous
> memory. Of course this is impossible (not even by analyzing the program
> because the order in which objects are "forgotten" may depend on things
> like user input).
> 
>   The only other alternative is that it performs memory defragmentation
> before freeing the objects. But that doesn't sound any faster than
> freeing the objects directly.

Go through memory, find all the dead objects, and *then* defrag the 
whole lot in a single pass. Done.

Post a reply to this message

Warp wrote:
>   Btw, could you finally give me even a slight hint at how GC knows
> that an object is not used anylonger?

GIYF.

Try ".net garbage collection" to see how .net does it, which is more 
sophisticated than the "mark and sweep" algorithm Orchid described.

>   What you write sounds like it knows it by magic.

No more than a compiler knows "by magic" what you meant, or a SQL engine 
knows "by magic" how to best order the operations to get good performance.

> be reference counting!) then how? The GC has to also make a difference
> between a reference being actually used in the currently-executed code
> and an orphan reference.

Yep. In the other message you already followed up to, I put both a 
simplistic description and a number of links.  If you still have 
questions, feel free to ask. I'll assume you followed that up.

-- 
   Darren New / San Diego, CA, USA (PST)
     Just because you find out you are
     telepathic, don't let it go to your head.

Post a reply to this message

Warp wrote:
>   That would mean that the memory allocation engine knows ahead of time
> the order in which objects will be "forgotten" (ie. nothing points to them
> anymore so they can be freed) so that it can group them in contiguous
> memory. Of course this is impossible 

Um, yes. So, the reasonable conclusion would be "my initial premise is 
incorrect."

>   The only other alternative is that it performs memory defragmentation
> before freeing the objects. 

No. It usually performs memory defragmentation as a concurrent part of 
freeing the objects.

> But that doesn't sound any faster than
> freeing the objects directly. 

It depends on the ratio of freed objects to retained objects. If you 
retain only 2% of the objects you created since the last GC, it's a net win.

>   Oh, of course there's a third possibility: It doesn't free objects if
> freeing them would cause fragmentation. But then they would consume
> memory even though they are not used. Doesn't sound reasonable if that
> memory would be needed for something else.
That is generally only done in systems that use pointers rather than 
references. (I.e., systems where the address of the object can't change 
due to the semantics of the language, like C, rather than something like 
Java where there's no way to get to the underlying address given the 
refernece.)  Optimistic garbage collection (GIYF) often works that way.



-- 
   Darren New / San Diego, CA, USA (PST)
     Just because you find out you are
     telepathic, don't let it go to your head.

Post a reply to this message

Orchid XP v3 <voi### [at] devnull> wrote:
> You mark every object that exists as "garbage". Then you take each 
> global variable, local variable in currently running threads, etc. in 
> turn, and you mark the object that variable points to as "not garbage". 
> And then you find every object it points to and mark all those as "not 
> garbage". And then all the objects that *those* objects point to, and so 
> forth. Follow all the pointers until you stop finding objects that 
> aren't already marked.

  GC was supposed to be faster than a RC method.

-- 
                                                          - Warp

Post a reply to this message

Orchid XP v3 <voi### [at] devnull> wrote:
> Go through memory, find all the dead objects, and *then* defrag the 
> whole lot in a single pass. Done.

  And how is that faster from simply freeing the dead objects? The original
point was that GC is much faster than freeing each object individually.
Moving the dead objects around in memory before freeing them isn't going
to help.

-- 
                                                          - Warp

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> >   The only other alternative is that it performs memory defragmentation
> > before freeing the objects. 

> No. It usually performs memory defragmentation as a concurrent part of 
> freeing the objects.

  If it performs memory defragmentation, that means that memory does get
fragmented (and thus need the defragmentation in the first place). Your
original claim was that there's *no* fragmentation at all and that's why
freeing a group of objects is faster.

> > But that doesn't sound any faster than
> > freeing the objects directly. 

> It depends on the ratio of freed objects to retained objects. If you 
> retain only 2% of the objects you created since the last GC, it's a net win.

  So it's faster only under certain conditions, not all?

-- 
                                                          - Warp

Post a reply to this message

Please you all in this fight: STOP IT! It becomes ridiculous ans off-topic.
This thread is for 'advanced' users. I can't see no advanced behaviour
here...

   Thanks in advance for your comprehension.

       Bruno.

Post a reply to this message

Warp wrote:
>   GC was supposed to be faster than a RC method.

That's called "Mark and sweep."  It's also fairly slow, if you don't 
tend to generate a lot of garbage. That and reference counting are 
basically the two oldest, most primitive attempts at garbage collection. 
25 years of research has improved things tremendously. Even generational 
GC like MS uses is a dozen years old.

Warp wrote:
 >   And how is that faster from simply freeing the dead objects?
 > The original
 > point was that GC is much faster than freeing each
 > object individually.

Well, it's faster than freeing each one individually *and* doing the 
math to maintain the reference counters.

 > Moving the dead objects around in memory before freeing
 > them isn't going to help.

You don't move the dead objects around, any more than a disk defrag 
copies the contents of unallocated sectors out of the way of the file 
being moved. You only move the live objects around. If you have many 
more dead objects than live objects, it's a win, especially if new 
allocations are sped up by not having to avoid clobbering live objects 
(i.e., sped up by not having to walk a free-space chain looking for a 
sufficiently-large hole). Figuring out how to identify dead objects 
without actually looking at them at all is challenging but mostly solved.

If you're looking for a description with reference to C++, try
ftp://gatekeeper.research.compaq.com/pub/DEC/SRC/research-reports/SRC-102.pdf
which is probably about as extensive and detailed as you need. Note that 
  this paper too is 15 years old, and people haven't stopped researching.

Note that [Zorn 92] in the citations discusses actual measurements of 
actual efficiency. If you don't want to do the googling,
http://www.cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol23/issue7/spe836.pdf
This paper is also 15 years old, so it's saying 15 years ago, we already 
knew how to make GC more efficient than doing things manually, including 
with reference counting. Note that cfrac was written using reference 
counting, and when the researcher changed it to use GC, the time went 
from 215 seconds to 175 seconds. And this is conservative GC, meaning 
there's no support from the language helping out, which isn't the norm 
for GCed languages.

Wow! Look!  Actual Data!  But don't mind me, because I don't know 
anything about the topic at all, no. Because, ya know, I just make stuff 
up without ever having read any research in the field I'm talking about, 
thinking that if I don't understand it already, it must not be important 
enough to learn about.

Of course, the performance relative to explicit management depends in 
part on the algorithm your version of new and delete uses. What 
algorithm are you comparing to? Do you even know what algorithm your 
libraries use? Do you even know the order of efficiency of it? Have you 
tried replacing it with a faster one?

http://gcc.gnu.org/ml/gcc/2002-08/msg00577.html
Wow. Linus himself saying "The gcc allocators have just always been 
bad." So what are you comparing your manual-allocation efficiency to?

-- 
   Darren New / San Diego, CA, USA (PST)
     Just because you find out you are
     telepathic, don't let it go to your head.

Post a reply to this message