Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #38176 > unrolled thread

Oforth : garbage collector

Back to article view | Back to comp.lang.forth

Contents

  Oforth : garbage collector franck.bensusan@gmail.com - 2015-04-13 13:43 -0700
    Re: Oforth : garbage collector Paul Rubin <no.email@nospam.invalid> - 2015-04-14 10:38 -0700
      Re: Oforth : garbage collector franck.bensusan@gmail.com - 2015-04-14 14:17 -0700
        Re: Oforth : garbage collector Paul Rubin <no.email@nospam.invalid> - 2015-04-15 13:21 -0700
          Re: Oforth : garbage collector hughaguilar96@gmail.com - 2015-04-15 14:04 -0700
            Re: Oforth : garbage collector Mark Wills <markwills1970@gmail.com> - 2015-04-16 00:57 -0700
              Re: Oforth : garbage collector franck.bensusan@gmail.com - 2015-04-16 10:42 -0700
                Re: Oforth : garbage collector Paul Rubin <no.email@nospam.invalid> - 2015-04-16 12:45 -0700
                  Re: Oforth : garbage collector franck.bensusan@gmail.com - 2015-04-16 13:27 -0700
                    Re: Oforth : garbage collector Paul Rubin <no.email@nospam.invalid> - 2015-04-16 13:56 -0700
                      Re: Oforth : garbage collector franck.bensusan@gmail.com - 2015-04-19 11:43 -0700
                        Re: Oforth : garbage collector Paul Rubin <no.email@nospam.invalid> - 2015-04-19 20:38 -0700

#38176 — Oforth : garbage collector

Hi,

Oforth is a Forth dialect that keeps Forth mecanisms and adds OOP as a 
builtin feature. It also comes with a garbage collector to handle the heap. 

I won't discuss about why/if a GC is needed or not, but I have received some 
questions about how this GC is working. I will try to answer in this post.

Oforth GC implementation : 
1) It is a mark and sweep algorithm.
2) Memory allocated at startup is only for initialization and for "lang"
package loading (245 Ko used from 320 Ko allocated).
3) GC is running every 120 ms to release memory as soon as possible.
4) A global GC is running every 1.2s.

To describe GC behavior, I have run some very basic stress tests.
Results are durations in microseconds.
(Oforth 32bits running on my laptop : a Core i7 2,4Ghz, Windows 7 64bits)


A) First, integers : just push integers on the stack and drop them :

func: testGC1(n)
{ 
| i j |
   5 loop: j [ 
      System getTick 
      n loop: i [ i drop ] 
      System getTick swap - println
      ]
}

>100000000 testGC1
217700
217374
217562
217642
217781

Here, GC has almost nothing to do because small integers (on Oforth 32bits
 from -2^30 to 2^30) are not created on the heap.
- Oforth does not allocate new memory (memory allocated remains 320 Ko).
- Every 120 ms, GC is running less that 4 micro seconds.
==> If mostly small integers are used, GC is almost not noticeable.

B) Next, object creation : testGC2 will create many objects on the heap, 
push them on the stack and drop them.

func: testGC2(n) 
{ 
| i j |
   5 loop: j [ 
      System getTick 
      n loop: i [ Object new drop ] 
      System getTick swap - println
      ]
}

>100000000 testGC2
2776879
2757239
2755653
2756141
2749884

Creating 100 millions small objects on the heap takes 2,8s on my laptop
(about 28 nanoseconds by loop, garbage included).
- GC is running during 11 milliseconds every 120 ms (even global GC).
- Max heap allocated is 40 Mo.
- After the test, memory allocated/used is back to 320Ko/245Ko.

C) To finish, we can run this test with a long lived object on the stack : 
a list of 1000 lists, each sublist storing 1000 strings
(so 1001 lists + 1000000 strings are created on the heap). 

>1000 seq map(#[ drop 1000 seq map(#asString) ])

>100000000 testGC2
2838269
2833674
2849397
2830112
2848148

- Huge objects don't penalize too much performances.
- GC is running during 13 milliseconds every 120 ms 
- and 17 milliseconds for the global GC every 1,2 s.

Ok, 17 ms can be a problem for real time applications, 
but not for interative programs. Of course, if not many objects are created 
or no huge long lived objects are kept, Oforth GC will not be really 
noticeable (often less than 100 microseconds every 120 milliseconds).


There are some drawbacks, of course : 

- Unlike small integers, big integers, floats and strings are created 
on the heap (unless they appear into a definition).
==> Perhap's this could be improved.

- Memory used is growing during 120 ms before release.

And, even if no parallelism is used, Oforth needs 2 threads : 
- One that will run the interpreter (and run programs).
- One that will alert that a GC is needed every 120 ms.
==> Perhap's this point can be improved too (by allowing manual GC
management ?)

I hope this answers to questions/worry about Oforth garbage collector.

Franck

[toc] | [next] | [standalone]

#38191

franck.bensusan@gmail.com writes:
> And, even if no parallelism is used, Oforth needs 2 threads : 
> - One that will run the interpreter (and run programs).
> - One that will alert that a GC is needed every 120 ms.
> ==> Perhap's this point can be improved too (by allowing manual GC
> management ?)

Given that you have Erlang-like process isolation(?), you could use a
separate heap and GC in each thread, like Erlang does.  That should
reduce GC latency in any individual thread.  Or are you already doing
that?  I don't understand the difference between your local (120ms) and
global (1.2s) GC's.

[toc] | [prev] | [next] | [standalone]

#38196

Le mardi 14 avril 2015 19:38:04 UTC+2, Paul Rubin a écrit :
> Given that you have Erlang-like process isolation(?), you could use a
> separate heap and GC in each thread, like Erlang does.  That should
> reduce GC latency in any individual thread.  

Oforth doesn't really have process isolation.
Each thread has indeed a separate heap but objects can be shared
between tasks the threads are performing.

Erlang deals process isolation by copying messages between processes. I
have never liked this. It is, imo, a waste of time and memory.

In Oforth, two tasks can communicate using a channel. A task can send
objects into a channel but those objects must be immutables.
So just objects references are sent between tasks, without copying anything.
A mutable object, on the other hand, is isolated into the task that created it.

> Or are you already doing that?  

Oforth GC is also a concurrent GC (by thread). Each thread handle its own heap.
The only synchronisation is that all mark phases must end before each thread
begins its sweep phase. This allows to check that shared immutable objects 
are really no more used before freeing them.

Another thing is that an Erlang process will run GC only when it reaches an
amount of allocated memory. I don't like this either. 
I prefer a GC running every 120ms to keep memory allocation as small as 
possible.
But it could be an option to run GC only if an amount of memory allocated is
reached. Have to think about it :)


>I don't understand the difference between your local (120ms) and
> global (1.2s) GC's.

The mark phase tags all reachables objects, and, recursively, all its
attributes.
Oforth GC has various optimizations for immutables objects.
One of them is that, when an object is still alive when the GC runs, and if it
is immutable, it is (recursively) tagged as not removable.
Then it no more checked by the GC mark phase. 
It will be checked only by the global GC mark phase, every 1.2s

Franck

[toc] | [prev] | [next] | [standalone]

#38206

franck.bensusan@gmail.com writes:
> Oforth doesn't really have process isolation.
> Each thread has indeed a separate heap but objects can be shared
> between tasks the threads are performing.

Hmm, ok, I didn't realize that.  Erlang's implementation actually shares
large strings ("binaries") between processes: they are refcounted
instead of GC'd, which works ok since they don't contain pointers.
There is also Erlang Term Storage (ETS) which are shared through some
comparable implementation hack.  In both cases from the client code's
point of view, nothing is shared (the API is the same) but the
implementation gets to make some short cuts. 

> Erlang deals process isolation by copying messages between processes. I
> have never liked this. It is, imo, a waste of time and memory.

It's generally small stuff that's copied and the cpu usage is small.

> In Oforth,... objects references are sent between tasks, without
> copying anything.  A mutable object, on the other hand, is isolated
> into the task that created it.

Hmm, ok, that means the gc heaps can't be separate between tasks though.
Fair enough.

> Another thing is that an Erlang process will run GC only when it
> reaches an amount of allocated memory. I don't like this either.  I
> prefer a GC running every 120ms to keep memory allocation as small as
> possible.

In a lightweight tasking system this will burn lots of cpu, since the
tasks will usually be idle, waiting on i/o.

> But it could be an option to run GC only if an amount of memory
> allocated is reached. Have to think about it :)

That's how every system I've ever seen does it.  There are some realtime
GC schemes that do a little bit of GC with every allocation, but even
that's not on a fixed timer.  

[toc] | [prev] | [next] | [standalone]

#38207

On Wednesday, April 15, 2015 at 1:21:31 PM UTC-7, Paul Rubin wrote:
> franck.bensusan@gmail.com writes:
> > Another thing is that an Erlang process will run GC only when it
> > reaches an amount of allocated memory. I don't like this either.  I
> > prefer a GC running every 120ms to keep memory allocation as small as
> > possible.
> 
> In a lightweight tasking system this will burn lots of cpu, since the
> tasks will usually be idle, waiting on i/o.
> 
> > But it could be an option to run GC only if an amount of memory
> > allocated is reached. Have to think about it :)
> 
> That's how every system I've ever seen does it.  There are some realtime
> GC schemes that do a little bit of GC with every allocation, but even
> that's not on a fixed timer.

I agree with Paul on this one. GC should generally only be done when it is necessary because free memory is running low, or when there is nothing else to do. 

I suspect that many of those every-120msGCs don't do anything at all except take time to determine that there is nothing to do. The problem with a fixed timer is that this assumes that you know how much GC is needed in a "typical" application program --- but you don't --- otoh, doing GC with every allocation makes it correspond to how much usage of the heap there is.

I haven't delved into your language yet --- but it is still on my list of interesting things to look into. :-)

[toc] | [prev] | [next] | [standalone]

#38215

On Wednesday, 15 April 2015 22:04:53 UTC+1, hughag...@gmail.com  wrote:
> On Wednesday, April 15, 2015 at 1:21:31 PM UTC-7, Paul Rubin wrote:
> > franck.bensusanghghg@gmail.com writes:
> > > Another thing is that an Erlang process will run GC only when it
> > > reaches an amount of allocated memory. I don't like this either.  I
> > > prefer a GC running every 120ms to keep memory allocation as small as
> > > possible.
> > 
> > In a lightweight tasking system this will burn lots of cpu, since the
> > tasks will usually be idle, waiting on i/o.
> > 
> > > But it could be an option to run GC only if an amount of memory
> > > allocated is reached. Have to think about it :)
> > 
> > That's how every system I've ever seen does it.  There are some realtime
> > GC schemes that do a little bit of GC with every allocation, but even
> > that's not on a fixed timer.
> 
> I agree with Paul on this one. GC should generally only be done when it is necessary because free memory is running low, or when there is nothing else to do. 
> 
> I suspect that many of those every-120msGCs don't do anything at all except take time to determine that there is nothing to do. The problem with a fixed timer is that this assumes that you know how much GC is needed in a "typical" application program --- but you don't --- otoh, doing GC with every allocation makes it correspond to how much usage of the heap there is.
> 
> I haven't delved into your language yet --- but it is still on my list of interesting things to look into. :-)

It's all about compromise. Imagine an embedded application that runs
on a fairly slow processor. If you have an embedded application, you
generally want it's performance to be as deterministic as possible.
It's quite likely that you are doing certain operations on a timed
or round-robin basis (reading I/O, sending data out of a serial port,
polling other slave devices, etc). In this case, you will normally
prefer your program to be as deterministic as possible wrt to scan
time (the time taken to run the entire program from top to bottom).
In this case, taking a small hit every few milliseconds may actually
be preferable to running the GC say, once every 5 minutes and having
the program "hang" for 5 seconds. During that 5 seconds, the MCU might
miss a poll from a master device, causing the master device to log a
comms timeout error etc. You then go looking for issues with your
comms lines, thinking there is some intereference, whereas in reality
the main task is just suspended while the GC completes.

Different horses for different courses.

Although, I would say (defeating my own argument slightly) that on
the occasions over the years that I have written embedded software
(there's been quite a few occasions) I have *always* used static
memory allocation at power-up, which lasts for the life of the
sytem (until it's switched off). I've never ever had a requirement
for dynamic memory allocation in an embedded application. Not saying
that that applies universally, but (I would suggest) that in many 
cases, careful design could, if not completely eliminate, then 
drastically minimise the requirement for such elaborate memory
management.

If you're programming OOP then all bets are off. You're on your
own ;-)

[toc] | [prev] | [next] | [standalone]

#38232

Le jeudi 16 avril 2015 09:57:45 UTC+2, Mark Wills a écrit :
> It's all about compromise. Imagine an embedded application that runs
> on a fairly slow processor. If you have an embedded application, you
> generally want it's performance to be as deterministic as possible.
> It's quite likely that you are doing certain operations on a timed
> or round-robin basis (reading I/O, sending data out of a serial port,
> polling other slave devices, etc). In this case, you will normally
> prefer your program to be as deterministic as possible wrt to scan
> time (the time taken to run the entire program from top to bottom).
> In this case, taking a small hit every few milliseconds may actually
> be preferable to running the GC say, once every 5 minutes and having
> the program "hang" for 5 seconds. During that 5 seconds, the MCU might
> miss a poll from a master device, causing the master device to log a
> comms timeout error etc. You then go looking for issues with your
> comms lines, thinking there is some intereference, whereas in reality
> the main task is just suspended while the GC completes.
> 

I would say that this does not apply only to embedded applications.

Even for desktop/servers targets, I think I wouldn't use a language that
allocates 500 Mo at startup or leave memory grow up with many unused 
objects or blocks during seconds when GC runs.

If the cost of GC is limited (less than 1 ms each 120 ms for instance),
and if this allows to keep memory low and GC impact limited, why not do it
(even if GC doesn't do anything but determine that there is nothing to do) ?
Programs will be more determinists without big impact.
Well, it is Oforth philosophy... :)

>In a lightweight tasking system this will burn lots of cpu, since the
>tasks will usually be idle, waiting on i/o. 

Sorry, Paul, but I don't understand this. If no new objects are allocated, why
GC would burn cpu : it will run quicker, that's all.


But I agree, there are many different situations. I will open some parameters
to programmer as command line options to adjust GC behavior.

Franck

[toc] | [prev] | [next] | [standalone]

#38236

franck.bensusan@gmail.com writes:
>>In a lightweight tasking system this will burn lots of cpu, since the
>>tasks will usually be idle, waiting on i/o. 
>
> Sorry, Paul, but I don't understand this. If no new objects are
> allocated, why GC would burn cpu : it will run quicker, that's all.

It's a mark-sweep collector so you have to trace all the live objects
even if no new ones have been allocated.  So the usual strategy is to gc
after some given amount of allocation, rather than some given amount of
milliseconds.

There are real-time gc algorithms that aren't that horribly complicated.
If your goal is to guarantee latency bounds, implementing a realtime gc
sounds like the right approach.

Maybe you could also reconsider the Erlang approach of copying objects
between processes.  Besides minimizing gc latency (by letting you run
separate gc's per thread), it also lets you distribute applications
across multiple machines.  Maybe the Oforth compiler could even target
the Erlang virtual machine.  There are already a couple of other
languages (Elixir and LFE) that target it.

[toc] | [prev] | [next] | [standalone]

#38237

Le jeudi 16 avril 2015 21:45:27 UTC+2, Paul Rubin a écrit :
> There are real-time gc algorithms that aren't that horribly complicated.
> If your goal is to guarantee latency bounds, implementing a realtime gc
> sounds like the right approach.

Thank you, I didn't know realtime GC could exist.

I just searched for it and the first link I found is : 

http://michaelrbernste.in/2013/06/03/real-time-garbage-collection-is-real.html

Extracts :  

"We show both analytically and experimentally that time-based scheduling is
 superior, particularly at the short intervals that are typically of 
interest in real-time systems. 
Work-based algorithms may achieve short individual pause times, 
but are unable to achieve consistent utilization."

"I see a growing consensus that time-based methods, in which the garbage
 collector is treated as a separate task in the real-time scheduling problem,
 allow more realistic timing analysis of the real-time code, by decreasing GC
 "taxes" on mutator operations."

Well, it seems that I have already implemented a sort of real time GC 
without even knowing it...

I will study this more precisely , particulary their Metronome algorithm.


> 
> Maybe you could also reconsider the Erlang approach of copying objects
> between processes.  Besides minimizing gc latency (by letting you run
> separate gc's per thread), it also lets you distribute applications
> across multiple machines.  Maybe the Oforth compiler could even target
> the Erlang virtual machine.  There are already a couple of other
> languages (Elixir and LFE) that target it.

Ok, I will try to reconsider, but I'am not ready for this yet... 
I can't stand doing memory copies when they are not absolutely necessary. 
This is too much for me... :) 

Franck

[toc] | [prev] | [next] | [standalone]

#38238

franck.bensusan@gmail.com writes:
> "I see a growing consensus that time-based methods...
>  allow more realistic timing analysis of the real-time code
> Well, it seems that I have already implemented a sort of real time GC 
> without even knowing it...

Not really, the above only makes sense in the context of incremental
collectors that do a bounded amount of work at each operation.
Mark-sweep is a traditional stop-the-world algorithm and doesn't fit
this picture.

> I will study this more precisely , particulary their Metronome algorithm.

Perry Cheng's PhD thesis is pretty readable, if you can find it online.

Here's a paper by Cheng and Blelloch that is probably an overview:

http://www.cs.cmu.edu/~blelloch/papers/gc2001.pdf

The cool trick is being a parallel real-time GC and I think Metronome
related but newer and fancier.  But, single-threaded real-time GC has
existed for a long time, e.g the Baker treadmill:

http://home.pipeline.com/~hbaker1/NoMotionGC.html

It might be possible to just write the real-time parts of your program
to do no allocation, then run them in separate tasks with guaranteed
time slices, so no GC at all need be run in them.  I think I've heard of
some robotics stuff programmed that way in Scheme.

[toc] | [prev] | [next] | [standalone]

#38379

Le jeudi 16 avril 2015 22:57:02 UTC+2, Paul Rubin a écrit :
 > Not really, the above only makes sense in the context of incremental
> collectors that do a bounded amount of work at each operation.
> Mark-sweep is a traditional stop-the-world algorithm and doesn't fit
> this picture.
> 

Thank you for the links. Interesting.

Yes, a mark and sweep is a stop the world algorithm. But does this mean that
a program can't run as a real time program when GC is a mark and sweep ?

For me, a real time application is not an application that is always alive, 
but an application that is alive enough to handle any events. A mark and sweep GC that allows that is not incompatible with a real time behavior, imo.

For instance, for a program that will create 10000 objects at startup
and will use them without creating many other objects, Oforth GC will
run less than 10 microseconds every 120 ms. Fast enough for some real time
applications, I suppose.

Well, this subject is not easy (and, btw, I had not in mind to make Oforth 
a real time language). So, for next version, I will add two options:
- a minimal allocated memory for GC to run ==> M
- A number of milliseconds between 2 GC ==> T
==> GC will run every T ms, but only if current allocated memory is greater M.

After, we'll see... :)

Franck

[toc] | [prev] | [next] | [standalone]

#38402

franck.bensusan@gmail.com writes:
> Yes, a mark and sweep is a stop the world algorithm. But does this
> mean that a program can't run as a real time program when GC is a mark
> and sweep ?

At least for traditional M&S, I would think so.  You seem to be using
some kind of incremental version and you have another post about it that
I'll have to find again for info.



> For instance, for a program that will create 10000 objects at startup
> and will use them without creating many other objects, Oforth GC will
> run less than 10 microseconds every 120 ms. Fast enough for some real time
> applications, I suppose.

But the GC can't tell in general how many objects will be created
between GC passes.  If you're going to code in a style that allocates no
objects after startup, you don't need GC at all.  Real-time GC means
that the GC is guaranteed to never stop the program for longer than X
microseconds for some X, with some additional guarantees about how much
work the application ("mutator" in GC jargon) must be allowed to do
between GC passes.


>  for next version, I will add two options:
> - a minimal allocated memory for GC to run ==> M
> - A number of milliseconds between 2 GC ==> T

I think it could be cool to actually implement one of the real-time GC
algorithms.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.forth

csiph-web