Optimizations for mutable structures?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
30 messages Options
12
Reply | Threaded
Open this post in threaded view
|

Optimizations for mutable structures?

Jan-Willem Maessen
Talk of uniqueness and so forth on the various Haskell mailing lists  
causes me to wonder: with so much imperative code being written in  
Haskell these days, to what extent is / should GHC perform standard  
imperative optimizations?  A few things come to mind:
   - Fetch elimination for imperative reads:
     writeIORef r e >> acts >> readIORef r === writeIORef r e >> acts  
 >> return e
     readIORef r >>= \e -> acts >> readIORef r ===
        readIORef r >>= \e -> acts >> return e
     And that sort of thing, generalized for other imperative monadic  
types...
     My feeling is this doesn't come up much in code as written on  
the page,
     but might well be relevant after inlining.
   - Some way to turn the following idiom into memcpy (for any array  
type):
     do a <- newArray
        writeArray a 0 e0
        writeArray a 1 e1
        writeArray a 2 e2
        ...etc...

What say others?  Is there a need yet?  (I don't honestly know the  
answer!)

-Jan-Willem Maessen
_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Reply | Threaded
Open this post in threaded view
|

Re: Optimizations for mutable structures?

Malcolm Wallace
Jan-Willem Maessen <[hidden email]> writes:

>    - Fetch elimination for imperative reads:
>      writeIORef r e >> acts >> readIORef r
>  === writeIORef r e >> acts >> return e

This transformation is valid only on single-threaded systems.
If there is any possibility of an IORef being shared across threads,
you are out of luck.

Regards,
    Malcolm
_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Reply | Threaded
Open this post in threaded view
|

RE: Optimizations for mutable structures?

Simon Marlow
In reply to this post by Jan-Willem Maessen
On 07 December 2005 13:38, Malcolm Wallace wrote:

> Jan-Willem Maessen <[hidden email]> writes:
>
>>    - Fetch elimination for imperative reads:
>>      writeIORef r e >> acts >> readIORef r
>>  === writeIORef r e >> acts >> return e
>
> This transformation is valid only on single-threaded systems.
> If there is any possibility of an IORef being shared across threads,
> you are out of luck.

(assuming 'acts' doesn't modify 'r').

No, Jan's transformation is correct even in a multithreaded setting.  It
might eliminate some possible outcomes from a non-deterministic program,
but that's ok.  There's no requirement that all interleavings according
to the semantics have to be implemented.  This is a hard property to
state precisely, indeed we gave up trying to in the concurrency/FFI
paper: http://www.haskell.org/~simonmar/papers/conc-ffi.pdf, see Section
6.1.

Cheers,
        Simon
_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Reply | Threaded
Open this post in threaded view
|

Re: Optimizations for mutable structures?

Ian Lynagh
On Wed, Dec 07, 2005 at 02:15:24PM -0000, Simon Marlow wrote:

> On 07 December 2005 13:38, Malcolm Wallace wrote:
>
> > Jan-Willem Maessen <[hidden email]> writes:
> >
> >>    - Fetch elimination for imperative reads:
> >>      writeIORef r e >> acts >> readIORef r
> >>  === writeIORef r e >> acts >> return e
> >
> > This transformation is valid only on single-threaded systems.
> > If there is any possibility of an IORef being shared across threads,
> > you are out of luck.
>
> (assuming 'acts' doesn't modify 'r').
>
> No, Jan's transformation is correct even in a multithreaded setting.  It
> might eliminate some possible outcomes from a non-deterministic program,
> but that's ok.  There's no requirement that all interleavings according
> to the semantics have to be implemented.  This is a hard property to
> state precisely, indeed we gave up trying to in the concurrency/FFI
> paper: http://www.haskell.org/~simonmar/papers/conc-ffi.pdf, see Section
> 6.1.

I don't think it's true for this program:

import Data.IORef
import Control.Concurrent

main = do m1 <- newEmptyMVar
          m2 <- newEmptyMVar
          let e = 6
              not_e = 7
              acts = putMVar m1 () >> takeMVar m2
          r <- newIORef 5
          forkIO $ do takeMVar m1
                      writeIORef r not_e
                      putMVar m2 ()
          writeIORef r e
          acts
          readIORef r >>= print


Thanks
Ian

_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Reply | Threaded
Open this post in threaded view
|

Re: Optimizations for mutable structures?

Claus Reinke
In reply to this post by Simon Marlow
|>>    - Fetch elimination for imperative reads:
|>>      writeIORef r e >> acts >> readIORef r
|>>  === writeIORef r e >> acts >> return e
|>
|> This transformation is valid only on single-threaded systems.
|> If there is any possibility of an IORef being shared across threads,
|> you are out of luck.
|
|(assuming 'acts' doesn't modify 'r').

this remark is the problem.

|No, Jan's transformation is correct even in a multithreaded setting.  It
|might eliminate some possible outcomes from a non-deterministic program,
|but that's ok.  There's no requirement that all interleavings according
|to the semantics have to be implemented. ..

not implementing traces promised as possible by the semantics is not
a good idea, imho, as programmers have some control over the set of
traces themselves.

in this case, acts could implement the synchronisation with another
thread working on r, ie., even if acts does not modify r itself, it might
reliably cause another thread to modify r before acts can end. if such
synchronisations depend on traces you have eliminated, the code
would just block (without apparent reason), whereas in this case, r
will have a value after acts that shouldn't have been possible, due
to the explicit synchronisation code (again, happy debugging) ..

of course, you could try to infer non-sequential interference with r
resulting from act, but that is what Malcolm pointed out - you have
to take the full semantics into account when doing such transformations
(btw, java originally made a mess of this- hope that has been fixed by now).

cheers,
claus


_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Reply | Threaded
Open this post in threaded view
|

RE: Optimizations for mutable structures?

Simon Marlow
In reply to this post by Jan-Willem Maessen
On 07 December 2005 15:21, Claus Reinke wrote:

>> (assuming 'acts' doesn't modify 'r').
>
> this remark is the problem.
>
>> No, Jan's transformation is correct even in a multithreaded setting.
>> It might eliminate some possible outcomes from a non-deterministic
>> program, but that's ok.  There's no requirement that all
>> interleavings according to the semantics have to be implemented. ..
>
> not implementing traces promised as possible by the semantics is not
> a good idea, imho, as programmers have some control over the set of
> traces themselves.

It's unreasonable to expect an implementation to provide *all*
transitions specified by the semantics.  How could you tell, for one
thing?  For example, what if the compiler doesn't allow a context switch
between two adjacent operations:

    writeIORef r e
    x <- readIORef r

this is a good example, in fact, because GHC will quite possibly compile
this code into a single basic block that doesn't allow a context switch
between the two statements.  However, the semantics certainly allows a
context switch between these two operations.  Is GHC wrong?  No way!  So
how do you specify which transitions an implementation must provide?
Perhaps there's a good formulation, but I don't know what it is.

> in this case, acts could implement the synchronisation with another
> thread working on r, ie., even if acts does not modify r itself, it
> might reliably cause another thread to modify r before acts can end.
> if such synchronisations depend on traces you have eliminated, the
> code
> would just block (without apparent reason), whereas in this case, r
> will have a value after acts that shouldn't have been possible, due
> to the explicit synchronisation code (again, happy debugging) ..

I should have said that if 'acts' blocks, then the transformation is
invalid.  When I say "acts doesn't modify r", I mean to include all ways
of modifying r, including synchronising with another thread, or calling
an unknown function.

> of course, you could try to infer non-sequential interference with r
> resulting from act, but that is what Malcolm pointed out - you have
> to take the full semantics into account when doing such
> transformations (btw, java originally made a mess of this- hope that
> has been fixed by now).

I don't think so.  Malcolm asserted that the transformation was invalid
in a multi-threaded implementation; I disagree - it's just as valid in a
multi-threaded implementation as a single-threaded one.  You don't have
to preserve non-deterministic interactions with other threads, because
they're non-deterministic!

Cheers,
        Simon
_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Reply | Threaded
Open this post in threaded view
|

RE: Optimizations for mutable structures?

Simon Marlow
In reply to this post by Jan-Willem Maessen
On 07 December 2005 15:14, Ian Lynagh wrote:

> On Wed, Dec 07, 2005 at 02:15:24PM -0000, Simon Marlow wrote:
>> On 07 December 2005 13:38, Malcolm Wallace wrote:
>>
>>> Jan-Willem Maessen <[hidden email]> writes:
>>>
>>>>    - Fetch elimination for imperative reads:
>>>>      writeIORef r e >> acts >> readIORef r
>>>>  === writeIORef r e >> acts >> return e
>>>
>>> This transformation is valid only on single-threaded systems.
>>> If there is any possibility of an IORef being shared across threads,
>>> you are out of luck.
>>
>> (assuming 'acts' doesn't modify 'r').
>>
>> No, Jan's transformation is correct even in a multithreaded setting.
>> It might eliminate some possible outcomes from a non-deterministic
>> program, but that's ok.  There's no requirement that all
>> interleavings according to the semantics have to be implemented.
>> This is a hard property to state precisely, indeed we gave up trying
>> to in the concurrency/FFI paper:
>> http://www.haskell.org/~simonmar/papers/conc-ffi.pdf, see Section
>> 6.1.
>
> I don't think it's true for this program:
>
> import Data.IORef
> import Control.Concurrent
>
> main = do m1 <- newEmptyMVar
>           m2 <- newEmptyMVar
>           let e = 6
>               not_e = 7
>               acts = putMVar m1 () >> takeMVar m2
>           r <- newIORef 5
>           forkIO $ do takeMVar m1
>                       writeIORef r not_e
>                       putMVar m2 ()
>           writeIORef r e
>           acts
>           readIORef r >>= print

Sorry for not being clear enough, see my other message.  I agree the
transformation is not valid in this case.  putMVar and takeMVar count as
modifying the IORef.

However... remove all the putMVars and takeMVars.  Do you think it's
valid now?  Even though after the transformation the program might
deliver a different answer?  (I claim yes).

Now, take the original program, but change the creation of m2 to
"newMVar ()", i.e. m2 starts off full.  Is the transformation valid now?
Well maybe, because in some interleavings acts does not block, and we
can prove that at compilation time.  Interesting - I think you could
justify doing the transformation in this case too, but I doubt any
compiler would go that far.

Cheers,
        Simon
_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Reply | Threaded
Open this post in threaded view
|

Re: Optimizations for mutable structures?

Malcolm Wallace
In reply to this post by Simon Marlow
"Simon Marlow" <[hidden email]> writes:

> I should have said that if 'acts' blocks, then the transformation is
> invalid.

Well that is exactly what I was assuming when I said that the
transformation is invalid.  In the general case, for some arbitrary
actions between the write and the read (excluding another write of
course), there is no guarantee that the IORef remains unmodified.

If you want to restrict the intermediate actions to be non-blocking,
such that another thread cannot run, then that is an extra (and
significant) proof obligation.

And AFAICS your non-blocking argument only applies to co-operative
scheduling.  If pre-emption is permitted (e.g. interrupt-handling),
then all bets are off, because an arbitrary thread could write to
the IORef at any moment.

> I don't think so.  Malcolm asserted that the transformation was invalid
> in a multi-threaded implementation; I disagree - it's just as valid in a
> multi-threaded implementation as a single-threaded one.

I think what I said was correct in general.  You need quite a lot of
side-conditions to assert the opposite.

Regards,
    Malcolm
_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Reply | Threaded
Open this post in threaded view
|

Re: Optimizations for mutable structures?

Tony Finch
The following paper seems relevant to this thread. Although it's written
in the context of C and C++, it's relevant to any language that combines
pre-emptive threads and imperative features.

http://www.hpl.hp.com/techreports/2004/HPL-2004-209.pdf

Tony.
--
f.a.n.finch  <[hidden email]>  http://dotat.at/
BISCAY: WEST 5 OR 6 BECOMING VARIABLE 3 OR 4. SHOWERS AT FIRST. MODERATE OR
GOOD.
_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Reply | Threaded
Open this post in threaded view
|

RE: Optimizations for mutable structures?

Simon Marlow
In reply to this post by Jan-Willem Maessen
On 07 December 2005 16:38, Malcolm Wallace wrote:

> "Simon Marlow" <[hidden email]> writes:
>
>> I should have said that if 'acts' blocks, then the transformation is
>> invalid.
>
> Well that is exactly what I was assuming when I said that the
> transformation is invalid. In the general case, for some arbitrary
> actions between the write and the read (excluding another write of
> course), there is no guarantee that the IORef remains unmodified.

This is an analysis that's performed all the time in C compilers, it's
quite straightforward to do a good approximation.  One simple algorithm
is: a store can be forwarded to a matching read as long as there are no
intervening writes that may alias, or function calls.

C does this and C has threads, so what's the difference?

> If you want to restrict the intermediate actions to be non-blocking,
> such that another thread cannot run, then that is an extra (and
> significant) proof obligation.
>
> And AFAICS your non-blocking argument only applies to co-operative
> scheduling.  If pre-emption is permitted (e.g. interrupt-handling),
> then all bets are off, because an arbitrary thread could write to
> the IORef at any moment.

No, that is exactly what I disagree with.  Faced with non-derministic
semantics, the compiler does *not* have to preserve all possible
outcomes.  In other words, it does not have to assume that an IORef can
be modified between any two arbitrary instructions.  If we had to assume
this, then indeed all bets would be off, and C compilers would be very
much more restricted in what optimisations they could perform.  

I don't know how I can explain this a different way - it seems pretty
obvious to me, but I'm probably not explaining it well :-/

You cut the example from my message - did you agree with the conclusion?
Or the conclusion I made from Ian's example?

Cheers,
        Simon
_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Reply | Threaded
Open this post in threaded view
|

Re: Optimizations for mutable structures?

Bugzilla from robdockins@fastmail.fm

On Dec 7, 2005, at 12:05 PM, Simon Marlow wrote:

> On 07 December 2005 16:38, Malcolm Wallace wrote:
>
>> "Simon Marlow" <[hidden email]> writes:
>>
>>> I should have said that if 'acts' blocks, then the transformation is
>>> invalid.
>>
>> Well that is exactly what I was assuming when I said that the
>> transformation is invalid. In the general case, for some arbitrary
>> actions between the write and the read (excluding another write of
>> course), there is no guarantee that the IORef remains unmodified.
>
> This is an analysis that's performed all the time in C compilers, it's
> quite straightforward to do a good approximation.  One simple  
> algorithm
> is: a store can be forwarded to a matching read as long as there  
> are no
> intervening writes that may alias, or function calls.
>
> C does this and C has threads, so what's the difference?

I would personally be very uncomfortable justifying a semantic  
transformation based on common practice in C compilers.  What exactly  
are the semantics of C programs and why do we believe that C  
compilers are correct?

I'd much rather see some argument in terms of an appropriate  
definition of observational equivalence.

[snip]

Rob Dockins
_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Reply | Threaded
Open this post in threaded view
|

Re: Optimizations for mutable structures?

Tony Finch
On Wed, 7 Dec 2005, Robert Dockins wrote:
>
> What exactly are the semantics of C programs and why do we believe that
> C compilers are correct?

With regards to threading, the semantics are undefined and the compilers
are subtly broken :-)

Tony.
--
f.a.n.finch  <[hidden email]>  http://dotat.at/
BISCAY: WEST 5 OR 6 BECOMING VARIABLE 3 OR 4. SHOWERS AT FIRST. MODERATE OR
GOOD.
_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Reply | Threaded
Open this post in threaded view
|

Re: Optimizations for mutable structures?

Malcolm Wallace
In reply to this post by Jan-Willem Maessen
[previously sent by mistake to Simon only - new para at end]

"Simon Marlow" <[hidden email]> writes:

> Now, take the original program, but change the creation of m2 to
> "newMVar ()", i.e. m2 starts off full.  Is the transformation valid now?
> Well maybe, because in some interleavings acts does not block, and we
> can prove that at compilation time.

I don't think it is valid for a compiler to say that "one possible
execution path permits me to remove some code, therefore I will remove
that code on all possible execution paths".

The example I had in mind was a GUI where the action
          writeIORef r e >> acts >> readIORef r
is intended to capture a situation where first we record some global
configuration data for the application, then permit some arbitrary GUI
actions to occur, and then we retrieve the configuration data again.

My expectation is that the config data /will/ have been changed by
some other GUI thread.  Surely it cannot be OK for the compiler to
silently deliver the original unchanged data here - it goes against
the programmer's intention.

Surely, if a Haskell programmer is going to write code that explicitly
reads from a reference after writing to it, that sequence must 9/10
be intentional: otherwise wouldn't she have just used a let-binding?

Regards,
    Malcolm
_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Reply | Threaded
Open this post in threaded view
|

Re: Optimizations for mutable structures?

Claus Reinke
In reply to this post by Simon Marlow
there seem to be two issues here - can we agree on that at least?

1) scheduling non-sequential programs on sequential processors

i wasn't arguing that the scheduler should realise all possible
interleavings at once. the issue i was referring to is known as
"fairness" in concurrent systems literature. as with referential
transparency, various non-equivalent definitions are in use,
but one informal description might be something like:

    if, for a given experiment, some event is possible according to
    the semantics, it should happen eventually if the experiment is
    repeated often enough.

see, eg,
http://research.microsoft.com/users/lamport/pubs/pubs.html#lamport-fairness

otherwise -if the event cannot happen no matter how often the
experiment is repeated, one could hardly call it "possible"?

scheduling is usually more difficult to implement with fairness
guarantees than without, but reasoning about programs is more
difficult without such guarantees. i wouldn't expect every
concurrent haskell implementation to suceed in guaranteeing
fairness, but i would expect the semantics to do so, and would
consider any implementation failing in this to be incomplete
(perhaps neccessarily so, for well-documented pragmatic reasons).

2) compiler optimisation validity in sequential and non-sequential
    environments

the original motivation of this thread - are sequential transformations
still valid in a non-sequential setting?

in general, the answer is no, to the surprise/annoyance of many many
compiler implementors who want their valuable optimisations to work
even when their sequential language acquires threads. this is in fact
so annoying that some languages, notably Java, have tried to specify
the language semantics in such a way that some level of sequential
optimisations would still be valid in spite of the language having
threads - the search keyword here is "memory model".

as I mentioned, they messed up the first time round, and have been
through a lengthy re-design phase that involved *changes to the
semantics*. I haven't followed that process - the original Java language
spec of concurrency and memory model was sufficient to drive me
away from the language for good (fingers crossed..).

see, eg:

http://www.cs.umd.edu/~pugh/java/memoryModel/
http://www.cs.umd.edu/~pugh/java/memoryModel/jsr-133-faq.html

[concurrent haskell doesn't seem to have this kind of memory hierarchy,
 but when you're suggesting to transform single threads based on local
 knowledge of shared variables, you implicitly assume a hierarchy, and
 a weak memory model rather than a strong one - a memory model is
 one way of specifying the conditions under which reordering and other
 transformations remain valid in a non-sequential setting]

i'd really, really prefer concurrent haskell not to go down a route in which
demands of simpler implementation leads to subtle problems in reasoning
about programs.

cheers,
claus


_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Reply | Threaded
Open this post in threaded view
|

Re: Optimizations for mutable structures?

Matthias Neubauer
In reply to this post by Tony Finch
Tony Finch <[hidden email]> writes:

> On Wed, 7 Dec 2005, Robert Dockins wrote:
>>
>> What exactly are the semantics of C programs and why do we believe that
>> C compilers are correct?
>
> With regards to threading, the semantics are undefined and the compilers
> are subtly broken :-)

Just have a look at Hans Boehm's page for more details on that ...

http://www.hpl.hp.com/personal/Hans_Boehm/c++mm/

-Matthias

--
Matthias Neubauer                                       |
Universit?t Freiburg, Institut f?r Informatik           | tel +49 761 203 8060
Georges-K?hler-Allee 79, 79110 Freiburg i. Br., Germany | fax +49 761 203 8052
_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Reply | Threaded
Open this post in threaded view
|

Re: Optimizations for mutable structures?

John Meacham
In reply to this post by Jan-Willem Maessen
On Wed, Dec 07, 2005 at 08:30:36AM -0500, Jan-Willem Maessen wrote:
> What say others?  Is there a need yet?  (I don't honestly know the  
> answer!)

Although I don't think impertive optimizations at this high of a level
will benefit much for how much they cost, after the code has been
processed and is in cmm form or about to be I think there is a lot of
room for improvement. even a few basic optimizations there can help.
ideally we would rely on gcc, but it seems to fall down on a lot of code
that ghc generates.

        John

--
John Meacham - ?repetae.net?john?
_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Reply | Threaded
Open this post in threaded view
|

Re: Optimizations for mutable structures?

John Meacham
In reply to this post by Simon Marlow
On Wed, Dec 07, 2005 at 05:05:58PM -0000, Simon Marlow wrote:
> No, that is exactly what I disagree with.  Faced with non-derministic
> semantics, the compiler does *not* have to preserve all possible
> outcomes.  In other words, it does not have to assume that an IORef can
> be modified between any two arbitrary instructions.  If we had to assume
> this, then indeed all bets would be off, and C compilers would be very
> much more restricted in what optimisations they could perform.  

Yup. this is exactly why C has the 'volatile' keyword. variables that
are declared volatile will always be read and written to memory and
never stored in a register because they could be modified by external
interrupts or threads. If every varibale were considered volatile
everything would be a whole whole lot slower. I have only had need to
use it 3 times and all were in an operating system kernel.

In any case, ghc IORefs are not 'volatile' in the C sense and that is a
good thing.
       
        John

--
John Meacham - ?repetae.net?john?
_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Reply | Threaded
Open this post in threaded view
|

Re: Optimizations for mutable structures?

John Meacham
In reply to this post by Malcolm Wallace
On Wed, Dec 07, 2005 at 05:36:09PM +0000, Malcolm Wallace wrote:
> My expectation is that the config data /will/ have been changed by
> some other GUI thread.  Surely it cannot be OK for the compiler to
> silently deliver the original unchanged data here - it goes against
> the programmer's intention.

then you should be using MVars. I don't think ghc guarentees (except by
accident of implementation) anything about using IORefs from multiple
threads and you shouldn't count on code which does so working in the
future. At least it shouldn't, since thread synchronization is a very
expensive thing compared to direct memory access and registers.

this is something of an argument for providing MVars or some thread-safe
version of IORefs with all haskell implementations whether they have
concurrency or not so people can write portable thread-safe libraries
that don't actually use concurrency themselves.

        John

--
John Meacham - ?repetae.net?john?
_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Reply | Threaded
Open this post in threaded view
|

Re: Optimizations for mutable structures?

Claus Reinke
In reply to this post by John Meacham
> Yup. this is exactly why C has the 'volatile' keyword. variables that
> are declared volatile will always be read and written to memory and
> never stored in a register because they could be modified by external
> interrupts or threads. If every varibale were considered volatile
> everything would be a whole whole lot slower. I have only had need to
> use it 3 times and all were in an operating system kernel.
> In any case, ghc IORefs are not 'volatile' in the C sense and that is a
> good thing.

but concurrent haskell (ch) is not c! in ch, you can adjust the scopes
of your variables so that scopes do not include other threads, so no
need for any slowdown - local variables are available for local
optimisations. but when the scope of a variable does include
other threads, i for one do not want to go back to c/java-style efficiency
annotations as a means for code-obfuscation: if a variable is shared
between threads, those threads should all see the same variable contents,
without me having to insert special synchronisation calls (or worse,
wonder which operations might involve synchronisation and which
won't); if some variable's contents do not need to be seen by other
threads, don't make that variable available to them.

scope extrusion/passing variables to other threads does not seem to
be problematic, either: if thread A updates a variable passed to it by
thread B, then those updates should be visible outside A.

but perhaps i am missing something? do you have any example in
mind where you'd actually need those extra annotations for efficiency?

cheers,
claus

ps does your later email imply that you suggest IORef/MVar as
    the non-volatile/volative separation? i'd rather see non-thread-
    local IORefs phased out of ch..



_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Reply | Threaded
Open this post in threaded view
|

Re: Optimizations for mutable structures?

John Meacham
On Thu, Dec 08, 2005 at 12:17:36AM -0000, Claus Reinke wrote:
> ps does your later email imply that you suggest IORef/MVar as
>     the non-volatile/volative separation? i'd rather see non-thread-
>     local IORefs phased out of ch..

yeah. exactly. thread local storage is also quite expensive though so
making all IORefs them would be a waste 90% of the time (as would making
them threadsafe).

I propose IORefs make no guarentees when it comes to concurrency, it is
the users burden to make sure they use them in a single threaded manner.

MVars should make guarentees when it comes to concurrency, and you
should use those whenever they might be accesed by different threads..

The reason all implementations should provide MVars (even if they are
just wrappers around IORefs) is so people can write portable threadsafe
libraries. mostly they can use IORefs, but should use MVars for things
like the unsafePerformIO global variable trick.

a thread-local version of MVars might also be interesting...

        John


--
John Meacham - ?repetae.net?john?
_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
12