Replacement for GMP: Update

[skaller]

On Sat, 2006-08-12 at 16:58 +0400, Bulat Ziganshin wrote:
> Hello skaller,

hi .. :)

> > The problem will occur if the 'stack' is aged: in that case
> > the sweep can miss the mutation and reap a live object.
> 
> well, i don't know how updatable vars in stack interoperate with GC.
> let's someone else answer this question.

I know very little about Haskell, let alone GHC internals
(I'm mainly using Ocaml at the moment, to implement my
own programming language).

Haskell seems to be on the right track in many ways: I view the
desirable upgrade path for programmers as roughly:

C --> C++ --> Felix --> ML --> Haskell

which represents a gradual move towards a more functional
and declarative style. It is not just that this is 
'easier to reason about' for the human programmer, and thus
provide better ways of ensuring correctness, but also that
it is 'easier to reason about' for machine algorithms,
and thus provides for better optimisation and much faster code.

The move to multi-processing on desktop computers seems to
accelerate the need for better languages than C++ (don't even
mention that J*** language .. :)

>  but afaik GHC 6.5 supports
> multi-cpu execution of multiple Haskell threads (which makes it a
> better language for modern multi-core cpus), tail-call optimization
> and 2-generation GC (actually, it supports any number of generations).
> also, GHC supports mutable arrays. you search GHC bug tickets for one
> that optimized GC with mutable vars: in ghc64 _each_ GC, including
> minor ones need to scan _every_ updatable reference (IORef/STRef) and
> _each_ element of _every_ updatable array (IOArray/STArray) and this
> significantly slowdowns many programs, including GHC itself. in ghc65
> better scheme now used

Cool. I guess what I'm saying is: there seems to be a contradiction
between multi-processing and mutation, perhaps more specifically
shared state. The tail-rec and array optimisation stuff may map
functional code to a procedural model, and obtain good performance
on a uni-processor.. but perhaps it does so at the cost of
bad performance on a multi-processor?

It may turn out that the underlying reason for preferring a
lazy purely functional high level programming language is 
also a reason for a similar low level execution model.

In particular .. it seems to me it defeats high performance
garbage collection of the very kind Haskell already uses.
The issue isn't making the collector faster .. but being
able to run it asynchronously. We all surely conceive the
functional model as constructive: you make new objects
as you need them, but never change old ones. This is basically
how 'mathematics' works. You don't worry about objects you
don't need any more. Since we don't have infinite memory
on real computers, we use a garbage collector to recycle
the unreachable store. And we all 'conceive' that as
a transparent background process.

Clearly, we need not just an asynchronous reaper -- we
also need to be able to execute multiple reapers in 
parallel, otherwise the system will not scale to a large
number of CPUs.

But the state of the art is then two stages behind the
requirement: Haskell still has to 'world stop' threads
to do a major collection. My suggestion that the cause
of this is precisely that it is possible to age the
independent per thread young heaps so that the aged
objects, now in the shared major heap, are mutable.
To prevent the mutable parts changing during collection,
all the threads have to be stopped. 

Do I understand correctly this is what actually happens
at the moment?

To fix the problem, we have to prevent the mutable
store ever getting into the major heap. That can
be done by throwing out the tail-rec, array, and
other optimisations that 'cheat' the collector
by manually reusing store, and bypassing the collection.
That works for a single thread only because you can't
collect and spew objects at the same time, ensuring
synchronisation. 

So I'm bringing into question whether these nice
'optimisations' are actually worthwhile. They actually
seem to *degrade* performance, not improve it, when we're
running with a large number of CPUs. Stopping the world
if you have 20,000 CPU's will happen so often, all the
CPU's will be idle 99.99% of the time :)

Removing the optimisation will slow down each CPU,
but remove any need to stop the world for long periods.
The world WILL have to pause to serialise aging the
young heaps.

It would be even better if the collection space could
somehow be partitioned so you could dedicate say 1%
of the CPU's to collection, that is, support multiple
parallel background collection: that is mandatory 
for scalability.

I note in passing that because the problem is with
*aging* mutable store .. the problem also goes away
if it is not aged. In particular if all mutable
objects are forcibly retained in the young heap,
there's no problem. For tail-rec optimisation this
is probably viable, and the implementation is possibly
quite simple, at least in principle: allow the machine
stack as an 'additional' generation, with the special
property it only permits FILO allocation in the
usual way.  This means (a) no copying into the major
heap and (b) no compaction (unnecessary). 

If the system supported this, there should
be no problem using the stack for a couple of mutable
variables needed for a tail-rec optimisation.
[Array might be a different story, don't know]


-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net