[Haskell-cafe] In-place modification

[Stefan O'Rear]

On Sun, Jul 08, 2007 at 07:52:19PM +0100, Andrew Coppin wrote:
> Bulat Ziganshin wrote:
>> Hello Andrew,
>> Sunday, July 8, 2007, 9:40:15 PM, you wrote:
>>> I've asked this before and nobody answered, so I take it that nobody
>>> knows the answer... Does GHC *ever* do an in-place update on anything?
>>
>> no. this will break GC's heart :)
>
> Yeah, having only immutable objects to collect must simplify a whole bunch 
> of stuff...

Yes, GHC does in-place updates on almost everything.  But probably not
in the way you wanted.

The crucial feature of laziness, that distinguishes it from call-by-name
as found in old ALGOL, is that when you finish evaluating an expression
you overwrite the expression with its value.  This guarantees that
expressions are only evaluated once, and is crucial for the performance
of idioms such as circular programming and array-memoization.

This does mean that GHC needs a *very* simple write barrier in the GC -
it just tacks the current node onto a linked list.  No overflow checks,
no occurence checks, just a couple of fast instructions.

But this does mean that everything overwritable (with pointers)
(MutVar#, MutArray#, SynchVar#, TVar#, indirections) needs an extra link
pointer.

>>> Does the STG even have a command for that?
>>>     
>>
>> hm. there are ghc primitives that work with mutable arrays. look for
>> primops.txt.pp in ghc sources.
>
> The GHC sources. Scary place. ;-)

You could also look at the HTMLized primop documentation:

http://haskell.org/ghc/dist/current/docs/libraries/base/GHC-Prim.html

writeArray#, write<type>Array#, write<type>OffAddr#, writeMutVar#,
writeTVar#, takeMVar#, tryTakeMVar#, putMVar#, tryPutMVar#, do inplace
writes.

> I did think about compiling GHC myself once. But then I found out that it's 
> not actually written in Haskell - it's written in Haskell + C + asm + Perl 
> (?!) and it's utterly *huge*...

Perl may die soon - GHC HQ is considering retiring the registerised
-fvia-C path, leaving only native code for normal use and ANSI C for
porting.  This is because mangled C is only about 3% faster according to
the GHC benchmark suite, and carries a high maintaince cost.

Stefan