On Wed, 2007-10-10 at 11:20 +1000, skaller wrote:
> Felix now has first stage support for a new gc configuration.
> This is a part of a critical revamping which makes functional
> programming in Felix feasible.
> * This algorithm is CRUDE.
> * As of this commit, flxg does not allow any collection!
>
> The last * will be repaired next so the mechanism can be tested.
*** Ouch. One oversight, which is rather nasty: the design isn't
thread safe. In order to work correctly with 'spawn_pthread',
the profile also needs access to the thread_control object,
which is currently part of flx_run, not even in the RTL.
The following logic in the driver:
case svc_collect:
{
// requires fthreads to be immobile
if(debug_driver)fprintf(stderr,"svc collect\n");
if (thread_control->world_stop())
{
if(debug_driver)fprintf(stderr,"ACTUALLY COLLECTING\n");
gcp->actually_collect();
thread_control->world_start();
}
else {
if(debug_driver)fprintf(stderr,"RACE: someone else is
collecting, just yield\n");
thread_control->yield();
}
}
goto process_active;
shows the current situation.
The yield() function is called by a pthread when it is out of active
fthreads. This function basically checks if a world stop is required,
and if so suspends itself until the condition is released.
The 'actually_collect' function must encapsulate the logic above.
Note: stopping the world to do collections is more or less mandatory
in a language with mutable store unless read or write barriers are used.
Felix doesn't and can't support such barriers without imposing a burden
on plain C/C++ code with respect to loading or storing Felix pointers.
For example you'd have to say:
store(&v,p);
to store a pointer p in a variable v, instead of just
v = p;
It is possible this COULD be done using an overloaded assignment
operator. The problem is quite nasty though. If you consider a
structure with 10 pointers, the barrier would be called 10 times.
I note with some humour that now that Felix uses raw C pointers instead
of types derived from _ref_, it is no longer possible to actually
provide such an overloaded assignment. In particular, Felix allows
mixing these pointers up freely now, since the GC can tell the
difference, however the cost of a suitable check in a write
barrier (a Judy array lookup or 3) would be prohibitive.
Ocaml uses a write barrier. Functional programs don't write store
as much as procedural ones, so the cost isn't so bad. However,
Ocaml can't multi-process, so it doesn't need to mutex the write
barrier, it just uses a single 'transaction level' global lock
to interleave threads.
Felix is specifically designed to allow multi-processing,
so this option isn't available. Instead, the standard implementation
(not using lock free operations) would have to mutex every memory
write. The problem isn't that the memory write itself needs locking,
but that the check on the 'world stop' flag requires that flag
to be loaded into the CPU cache, and the only portable way to
ensure that is to use a lock.
In fact, using non-cached memory on processors like AMD64 would be
much more efficient, as would a lock-free atomic read with a suitable
barrier to ensure cache synchronisation.
The bottom line is that without barrier, we have to wait until
all the CPUs have stopped doing stuff before collecting: they
can be stopped at any service call, and now, allocation, but
if one of 10 CPUs is doing a matrix inversion the other 9 will
just idle waiting for it to finish (other processes can run of
course).
--
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net
-------------------------------------------------------------------------
This SF.net email is sponsored by: Splunk Inc.
Still grepping through log files to find problems? Stop.
Now Search log events and configuration files using AJAX and a browser.
Download your FREE copy of Splunk now >> http://get.splunk.com/
_______________________________________________
Felix-language mailing list
Felix-language@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/felix-language
