Re: Garbage Collection
Chris Burch wrote:
>
> Vincent wrote:
> >
> > Robert Craig wrote:
> > >
> > > As most of you know, Euphoria uses reference-counting to
> > > reclaim unused blocks of storage. Over the years, I've
> > > periodically looked at the latest algorithms for
> > > garbage collection, and after careful analysis I've
> > > always decided to stick with reference counting.
> > >
> > > If you search the Web for "garbage collection",
> > > you'll find many different algorithms, such as
> > > mark/sweep, mark/compact and generational garbage collection.
> > > It's a fairly active and interesting area of research.
> > > There are many approaches, and many trade-offs to consider.
> > >
> > > Most people say that reference counting is slower than true
> > > garbage collection (GC) because of the time wasted incrementing
> > > and decrementing reference counts during execution. They also point out
> > > that "circular" data structures can't be garbage collected this way
> > > because the reference counts will never drop to zero.
> > > Euphoria carefully avoids creating circular structures of pointers
> > > (e.g. A -> B -> C -> A) so this is not a problem.
> > > It's acknowledged that reference counting generally
> > > avoids the random, noticable delays that can occur with the other methods.
> > > e.g. you wouldn't want your action game to freeze for a second
> > > every minute or so. If it were a big non-interactive program,
> > > you wouldn't notice the GC delay, and the total time might
> > > be less than with reference counting (RC).
> > >
> > > Main Advantages to GC over RC in Euphoria:
> > > - eliminates all DeRef's (faster program execution
> > > and reduced size (by 15%?) of translated code.
> > > Less chance for coding errors.)
> > > - very fast allocation of blocks (with most methods) and deallocation
> > > is a no-op
> > > - eliminates overheads (such as ref count field) on each block of
> > > storage
> > > - eliminates storage fragmentation (with most methods) that could
> > > prevent allocation of a big block, even though many small
> > > non-contiguous blocks are free
> > >
> > > Main Disadvantages:
> > > - random pauses in execution (there are ways to control this but
> > > not completely eliminate it. RC can also cause small pauses
> > > sometimes,
> > > but that can be almost completely eliminated quite easily)
> > > - for efficiency you must pre-reserve memory well in excess of what
> > > you actually need
> > > - some Ref's of a sequence would have to become full copies
> > > (maybe you could "lock" sequences that are going to be modified
> > > repeatedly)
> > > - RC seems to have better cache performance, since it reuses
> > > blocks that were used recently, while GC keeps moving further
> > > into fresh areas of memory
> > > - GC is known for introducing subtle bugs. The algorithms must
> > > be implemented very carefully.
> > >
> > > If anyone has any ideas on this, please post them.
> > > I'm still actively thinking about all these issues.
> > >
> > > Regards,
> > > Rob Craig
> > > Rapid Deployment Software
> > > <a href="http://www.RapidEuphoria.com">http://www.RapidEuphoria.com</a>
> > >
> >
> > Rob, In more detail.. what are the main advanatages and disadvantages of
> > using a reference
> > counting technique over various garbage collection implementations?
> >
> > Regards,
> > Vincent
> >
> > --
> > Without walls and fences, there is no need for Windows and Gates.
> >
>
> Hi
>
> I don't think it matters what sort of garbage collection you use, as
> its lightning fast, and no one realises its going on, and there are no
> memory leaks or lock ups etc. ( 
)
>
> However, why not give the programmer the choice
>
> with auto_garbage_collection
> without garbage_collection
>
> then to manually collect garbage at quiet times
> procedure collect_garbage()
>
> (Perhaps you could write one for my kids while your at it
> procedure take_out_garbage()
> )
>
> Chris
>
> (ps I've just given up smoking, and am slightly insane)
>
> <a
> href="http://members.aol.com/chriscrylex/euphoria.htm">http://members.aol.com/chriscrylex/euphoria.htm</a>
> <a href="http://uboard.proboards32.com/">http://uboard.proboards32.com/</a>
>
I just concluded after reading a bunch of stuff online, that Robert should just
stick with either pure reference counting or use a hybrid reference counting &
trace garbage collector to handle cyclic structures.
The problem with reference counting besides implementing mutex locks properly
is, objects within cyclic structures will never obtain a zero reference count,
and the unused block will never be freed).
But Rob claims Euphoria ignores cyclic structures of pointers. Are the garbage
blocks still freed by a conversion, or just left to build up?
After all these years of the reference counting technique being used in
Euphoria. It is safe to say, Robert has been using it correctly (as of v2.5:
virtually no known memory leaks or premature freeing of blocks, with excellent
performance despite the added overhead of ref de/increments). Difficulties will
arise when implementing mutex locks, having counts on each data structure, in
order to ensure thread-safety. But I suppose Rob wants to hold that off a while
longer (lots of work, not lot of fun).
Regards,
Vincent
--
Without walls and fences, there is no need for Windows and Gates.
|
Not Categorized, Please Help
|
|
