OpenEuphoria

2. Re: Garbage Collection

• Posted by Vincent <darkvincentdude at yahoo.com> Jun 26, 2005
• 717 views
• Last edited Jun 27, 2005

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>
> 
http://cpptips.hyperformix.com/cpptips/rc_vs_gc

You might find this link and other links kind of interesting... 
Comparing reference counting verses various garbage collection 
techniques.


Regards,
Vincent

--
Without walls and fences, there is no need for Windows and Gates.

4. Re: Garbage Collection

• Posted by Vincent <darkvincentdude at yahoo.com> Jun 27, 2005
• 703 views
• Last edited Jun 28, 2005

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.

6. Re: Garbage Collection

• Posted by Vincent <darkvincentdude at yahoo.com> Jun 27, 2005
• 693 views
• Last edited Jun 28, 2005

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.

8. Re: Garbage Collection

• Posted by Robert Craig <rds at RapidEuphoria.com> Jun 28, 2005
• 678 views

Vincent wrote:
> 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?

In parser.e where assignments to subscripted variables are handled,
there's a tiny bit of code that prevents cycles. So the cycle problem
they always talk about doesn't exist. Cycles do not happen.

Here's how a cycle could occur (without precautions):

     A[5] = A

You might just store a pointer to A in A[5].
That means A[5] will point to A, but A will also
contain a pointer to A[5], since A[5] is an element of the
sequence A. That's circular. The ref count on A will
never drop to zero, because A[5] points at it. The ref count
on A[5] will never drop to zero, because A points at it.

Euphoria avoids this problem by making a copy
of A (call it A_TEMP) and pointing A[5] at the *copy*, rather than
at the original sequence that A[5] is a part of. So there's
no cycle. A points to A[5] which points to A_TEMP, and A_TEMP[5]
points wherever A[5] originally pointed (if anywhere).

This costs some time because a copy of A is made, but this
is a rare case. Not many people do A[5] = A. It's strange code.
But the bottom line is Euphoria can use reference counting
without worrying about cycles.

Regards,
   Rob Craig
   Rapid Deployment Software
   http://www.RapidEuphoria.com

10. Re: Garbage Collection

• Posted by Pete Lomax <petelomax at blueyonder.co.uk> Jun 28, 2005
• 695 views

On Mon, 27 Jun 2005 17:18:32 -0700, Robert Craig
<guest at RapidEuphoria.com> wrote:

>Vincent wrote:
>> But Rob claims Euphoria ignores cyclic structures of pointers. 
I found reference counting, done properly, made cyclic structures
impossible:

<snip>

>Robert Craig wrote:
>Here's how a cycle could occur (without precautions):
>
>     A[5] = A
>
IIRC, in posetf it went something like this:
1) "= A" made the refcount of A increase to 2, the same way it would
in the statement "B = A".
2) "A[5] =" noticed a refcount>1 and therefore cloned the root
sequence before allowing the subscripted assignment (the same way it
would in B=A followed by A[5]=0). The assignment would itself decref
the "original" A (aka A[5]), putting it back to 1.

Regards,
Pete
PS a subsequent A={} would recursively deref A, and hence deref A[5],
consequently freeing it.
PPS Rob has been playing this game longer than me, so I accept the
above may be non-optimal, but it seemed to work for me (and I had
heavy/exact memory counting code in there to prove it)

12. Re: Garbage Collection

• Posted by "Igor Kachan" <kinz at peterlink.ru> Jun 29, 2005
• 713 views

Robert Craig wrote:

> posted by: Robert Craig <rds at RapidEuphoria.com>
> 
> 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.

Rob, for example, in BASICs, there is the FRE() function,
it returns amount of the available memory.

Sometimes, we can see the Euphoria message:

"You program has run out of memory.
 One moment, please ..."

I'd prefer to make something like to:

    if eu_FRE() < 256000 then
        ok = collect_all_garbage_immediatelly()
    end if
   

than get that message above.

This collect_all_garbage_immediatelly() function
may be the most powerful of the existent ones as
plus to automated fast collection, I think.

Then all pauses will be under programmer's control.

I'm not very specialist on these things, just my
$.02.

Good Luck!

Regards,
Igor Kachan
kinz at peterlink.ru

14. Re: Garbage Collection

• Posted by Derek Parnell <ddparnell at bigpond.com> Mar 11, 2003
• 674 views

On Tue, 11 Mar 2003 22:27:50 +0000, Gabriella Leveron 
<gleveron at hotmail.com> wrote:

>
> Before I start, I didn't notice I typed "their" instead of "they're", I 
> actually always re-read stuff before I post, but this time I was in a 
> hurry.
>
> Anyway, my question.
>
> What is the garbage collection algorithm that Euphoria uses? Where can I 
> see it?
>

You can purchase the source code for $US49 from the 
http://www.rapideuphoria.com site.

Or you can ask someone whose already got the source to document the GC 
algorithm.

-- 

cheers,
Derek Parnell