GHC predictability

[Andrew Coppin]

Don Stewart wrote:
> Andrew, would you say you understand the original problem of why
>
>     mean xs = sum xs / fromIntegral (length xs)
>
> was a bad idea now? Or why the left folds were a better solution?
>  

That definition of mean is wrong because it traverses the list twice.
(Curiosity: would traversing it twice in parallel work any better?) As
for the folds - I always *always* mix up left and right folds. Every
single damn time I want a fold I have to look it up to see which one I
want. I had a similar problem with learning to drive, by the way... the
consequences there are of course much more serious than just crashing
your _computer_...

It was probably a poor example. The point I was attempting to make is
that in Haskell, very subtle little things can have an unexpectedly
profound effect. If you don't know what you're supposed to be looking
for, it can be really hard to see why your program is performing badly.

For what it's worth, I think I *do* currently have a reasonably gasp of
how lazzy evaluation works, normal order reduction, graph machines, and
so on. And yet, I still have trouble making my code go fast sometimes.
As I said in another post, if I can track down some *specific* programs
I've written and had problems with, maybe we can have a more meaningful
debate about it.

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Andrew Coppin]

Aaron Denney wrote:

> On 2008-05-12, Andrew Coppin <andrewcoppin@...> wrote:
>  
>> (Stupid little-endian nonsense... mutter mutter...)
>>    
>
> I used to be a big-endian advocate, on the principle that it doesn't
> really matter, and it was standard network byte order.  Now I'm
> convinced that little endian is the way to go, as bit number n should
> have value 2^n, byte number n should have value 256^n, and so forth.
>
> Yes, in human to human communication there is value in having the most
> significant bit first.  Not really true for computer-to-computer
> communication.
>  

It just annoys me that the number 0x12345678 has to be transmuted into
0x78563412 just because Intel says so. Why make everything so complicated?

[Oh GOD I hope I didn't just start a Holy War...]

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Lennart Augustsson]

Also, the way we write numbers is little endian when writing in
Arabic; we just forgot to reverse the digits when we borrowed the
notation.

Little endian is more logical unless you also number your bits with
MSB as bit 0.

On Tue, May 13, 2008 at 7:35 PM, Aaron Denney <wnoise@...> wrote:

> On 2008-05-12, Andrew Coppin <andrewcoppin@...> wrote:
>> (Stupid little-endian nonsense... mutter mutter...)
>
> I used to be a big-endian advocate, on the principle that it doesn't
> really matter, and it was standard network byte order.  Now I'm
> convinced that little endian is the way to go, as bit number n should
> have value 2^n, byte number n should have value 256^n, and so forth.
>
> Yes, in human to human communication there is value in having the most
> significant bit first.  Not really true for computer-to-computer
> communication.
>
> --
> Aaron Denney
> -><-
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe@...
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Achim Schneider]

Andrew Coppin <andrewcoppin@...> wrote:

> You're probably right about all that. I would humbly suggest that
> what is somewhat lacking is a good, introductory, high-level text on
> what makes Haskell go fast and what makes it go slow. As with many
> things in the Haskell world, there are bits and pieces of information
> out there, but it's difficult to track them all down and present a
> coherant picture. We've got a section on the wiki containing scraps
> and snippets of information. There are various GHC-related papers [if
> you can find them online]. GHC has various profiling possibilities,
> but thus far I've found it difficult to digest the results. We need a
> good, thorough body of text on this subject, I feel. [Of course, that
> still means somebody has to write one...]
>

Something like the history paper but concentrating on algorithms,
techniques & tricks would be great, yes. And, most importantly, less
buzzwords where you're lucky if you find a definition of it by googling.

> 1. What is "ghc-core"?
>
An intermediate language, I'm quoting from memory:

First comes a Syntax tree, then the type checker, then the translation
to core, then optimisations on core (, then the printout) and finally
c/assembly.  

> 2. Does anybody know how to actually read GHC's Core output anyway?
> To me, it looks almost exactly like very, very complicated Haskell
> source with a suspicious concentration of case expressions - but I
> understand that in the Core language, many constructs actually mean
> something quite different.
>
I found it rather easy to parse... as long as you succeed in finding
what you're looking for behind all that inlining. Types ending in #
mean they're unboxed.

It's particularly useful to find out how much ghc specialises your
code.

> 3. Any idea where the STG paper is? Is it still an accurate
> reflection of GHC's current technology?
>
http://research.microsoft.com/~simonpj/Papers/papers.html
Implementing lazy functional languages on stock hardware: the Spineless
Tagless G-machine, SL Peyton Jones, Journal of Functional Programming
2(2), Apr 1992, pp127-202.

while googling for it, I stumbled across
http://citeseer.ist.psu.edu/reid98putting.html

which might be more actual, but I neither read it yet or have any
idea whatsoever.

--
(c) this sig last receiving data processing entity. Inspect headers for
past copyright information. All rights reserved. Unauthorised copying,
hiring, renting, public performance and/or broadcasting of this
signature prohibited.

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Neil Mitchell]

Hi

>  1. What is "ghc-core"?

You actually answer this question as part of question 2. Think of it
as simple Haskell with some additional bits.

>  2. Does anybody know how to actually read GHC's Core output anyway?
> To me,
> it looks almost exactly like very, very complicated Haskell source with a
> suspicious concentration of case expressions - but I understand that in the
> Core language, many constructs actually mean something quite different.

There is one different from standard Haskell I am aware of. In Core,
case x of _ -> 1 will evaluate x, in Haskell it won't. Other than
that, its just Haskell, but without pattern matching and only cases -
hence the rather high number of cases.

Thanks

Neil
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Don Stewart-2]

ndmitchell:

> Hi
>
> >  1. What is "ghc-core"?
>
> You actually answer this question as part of question 2. Think of it
> as simple Haskell with some additional bits.
>
> >  2. Does anybody know how to actually read GHC's Core output anyway?
> > To me,
> > it looks almost exactly like very, very complicated Haskell source with a
> > suspicious concentration of case expressions - but I understand that in the
> > Core language, many constructs actually mean something quite different.
>
> There is one different from standard Haskell I am aware of. In Core,
> case x of _ -> 1 will evaluate x, in Haskell it won't. Other than
> that, its just Haskell, but without pattern matching and only cases -
> hence the rather high number of cases.

Well, 'let's too, which bind either unlifted or lifted values.

If they're binding lifted things, that's a thunk being allocated.

-- Don
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Aaron Denney]

On 2008-05-13, Andrew Coppin <andrewcoppin@...> wrote:

> Aaron Denney wrote:
>> On 2008-05-12, Andrew Coppin <andrewcoppin@...> wrote:
>>  
>>> (Stupid little-endian nonsense... mutter mutter...)
>>>    
>>
>> I used to be a big-endian advocate, on the principle that it doesn't
>> really matter, and it was standard network byte order.  Now I'm
>> convinced that little endian is the way to go, as bit number n should
>> have value 2^n, byte number n should have value 256^n, and so forth.
>>
>> Yes, in human to human communication there is value in having the most
>> significant bit first.  Not really true for computer-to-computer
>> communication.
>>  
>
> It just annoys me that the number 0x12345678 has to be transmuted into
> 0x78563412 just because Intel says so. Why make everything so complicated?
>
> [Oh GOD I hope I didn't just start a Holy War...]

On the other hand I appreciate that the consecutive memory locations
containing [1][0][0][0] are the number 1, no matter whether you're
reading a byte, a short, or an int.

--
Aaron Denney
-><-

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Brandon S. Allbery KF8NH]

On 2008 May 13, at 17:01, Andrew Coppin wrote:

> That definition of mean is wrong because it traverses the list  
> twice. (Curiosity: would traversing it twice in parallel work any  
> better?) As for the folds - I always *always* mix up

It might work "better" but you're still wasting a core that could be  
put to better use doing something more sensible.  It's pretty much  
always best to do all the calculations that require traversing a given  
list in a single traversal.

--
brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allbery@...
system administrator [openafs,heimdal,too many hats] allbery@...
electrical and computer engineering, carnegie mellon university    KF8NH


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Brandon S. Allbery KF8NH]

On 2008 May 13, at 17:12, Andrew Coppin wrote:

> [Oh GOD I hope I didn't just start a Holy War...]


Er, I'd say it's already well in progress.  :/

--
brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allbery@...
system administrator [openafs,heimdal,too many hats] allbery@...
electrical and computer engineering, carnegie mellon university    KF8NH


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Albert Y. C. Lai]

Andrew Coppin wrote:
> 2. Does anybody know how to actually read GHC's Core output anyway? To
> me, it looks almost exactly like very, very complicated Haskell source
> with a suspicious concentration of case expressions - but I understand
> that in the Core language, many constructs actually mean something quite
> different.

I can read most of GHC Core. I was never taught, and I never asked. I
did not read GHC's source code. I just guessed.

I agree with your assessment about the domination by case expressions.
They spell out the evaluation order. You need truckloads of them.

I slightly agree with your assessment about "complicated", but I call it
detailed and tedious. This is an assembly language for functional
programming. If it weren't detailed and tedious, it would have no right
to exist.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Richard A. O'Keefe]

On 14 May 2008, at 8:58 am, Andrew Coppin wrote:
> What I'm trying to say [and saying very badly] is that Haskell is an  
> almost terrifyingly subtle language.

Name me a useful programming language that isn't.
Simply interchanging two for-loops, from
        for (i = 0; i < N; i++) for (j = 0; j < N; j++)
to for (j = 0; j < N; j++) for (i = 0; i < N; i++)
when marching over an array, can easily slow you down
by nearly two orders of magnitude in C.
[Hint: read "What every computer scientist needs to know
about memory".]  For a real shock, take a look at what
your C++ templates are doing...

There's one big difference between Haskell and language T (my other
preferred language).  Seemingly insignificant changes in Haskell can
kill performance, but seemingly insignificant changes in language T
can take you into territory the library designers never thought of
where there are lions, tigers, and bears in abundance.  "Unexpectedly
slow" is better than "inexplicably buggy".


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Henning Thielemann]

On Tue, 13 May 2008, Achim Schneider wrote:

> Jed Brown <jed@...> wrote:
>
>> It's not that simple with bits.  They lack consistency just like the
>> usual US date format and the way Germans read numbers.
>>
> So you claim that you pronounce 14 tenty-four? In German pronunciation
> is completely uniform from 13 to 99.

http://www.verein-zwanzigeins.de/
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Achim Schneider]

Henning Thielemann <lemming@...> wrote:

>
> On Tue, 13 May 2008, Achim Schneider wrote:
>
> > Jed Brown <jed@...> wrote:
> >
> >> It's not that simple with bits.  They lack consistency just like
> >> the usual US date format and the way Germans read numbers.
> >>
> > So you claim that you pronounce 14 tenty-four? In German
> > pronunciation is completely uniform from 13 to 99.
>
> http://www.verein-zwanzigeins.de/
>

Dammit! Don't affirm the stereotype that any group of like-minded
Germans forms an association to affirm importance and ultimately
get drowned by the "well I don't care at all" mentality of the rest.

--
(c) this sig last receiving data processing entity. Inspect headers for
past copyright information. All rights reserved. Unauthorised copying,
hiring, renting, public performance and/or broadcasting of this
signature prohibited.

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Andrew Coppin]

Don Stewart wrote:

> ndmitchell:
>  
>>>  2. Does anybody know how to actually read GHC's Core output anyway?
>>>      
>> There is one different from standard Haskell I am aware of. In Core,
>> case x of _ -> 1 will evaluate x, in Haskell it won't. Other than
>> that, its just Haskell, but without pattern matching and only cases -
>> hence the rather high number of cases.
>>    
>
> Well, 'let's too, which bind either unlifted or lifted values.
>
> If they're binding lifted things, that's a thunk being allocated.
>  

See, somebody needs to write all this down - in language comprehensible
to people who don't already know what an "unlifed value" is. ;-)

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Andrew Coppin]

Neil Mitchell wrote:
> Hi
>
>  
>>  1. What is "ghc-core"?
>>    
>
> You actually answer this question as part of question 2. Think of it
> as simple Haskell with some additional bits.
>  

I rephrase: I know what GHC's Core language is. But Dons said "I suggest
you install ghc-core", which suggests the existence of an item of
software named "ghc-core". This I know nothing about...

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Andrew Coppin]

Brandon S. Allbery KF8NH wrote:

>
> On 2008 May 13, at 17:01, Andrew Coppin wrote:
>
>> That definition of mean is wrong because it traverses the list twice.
>> (Curiosity: would traversing it twice in parallel work any better?)
>> As for the folds - I always *always* mix up
>
> It might work "better" but you're still wasting a core that could be
> put to better use doing something more sensible.  It's pretty much
> always best to do all the calculations that require traversing a given
> list in a single traversal.

Yeah, you're probably right there. I mean, with sufficient inlining,
maybe you would end up with a loop that doesn't even construct any
heap-allocated list nodes, just adds up the integers as fast as it can
generate them.

On the other hand, N(N+1)/2N is probably even faster! ;-) So I guess
it's kinda of a daft example...

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Andrew Coppin]

Brandon S. Allbery KF8NH wrote:
>
> On 2008 May 13, at 17:12, Andrew Coppin wrote:
>
>> [Oh GOD I hope I didn't just start a Holy War...]
>
>
> Er, I'd say it's already well in progress.  :/
>

Oh dear.

Appologies to everybody who doesn't actually _care_ about which endian
mode their computer uses...

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Don Stewart-2]

andrewcoppin:
> Brandon S. Allbery KF8NH wrote:
> >
> >On 2008 May 13, at 17:01, Andrew Coppin wrote:
> >
> >>That definition of mean is wrong because it traverses the list twice.
> >>(Curiosity: would traversing it twice in parallel work any better?)
> >>As for the folds - I always *always* mix up

Yes, using parallelism does work. It turns the naive definition into
one which traverses the list on two cores at the same time, so the
garbage collector does get clean up the list as each core races along
it.

    mean ls = count `par` (total/count)
      where count = fromIntegral (length ls)
            total = foldl' (+) 0 ls

It is kind of amazing how parallelism and laziness enable the naive
definition to fall out as much the same as the explicitly recursive
version.

--  Don
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Andrew Coppin]

Richard A. O'Keefe wrote:

>
> On 14 May 2008, at 8:58 am, Andrew Coppin wrote:
>> What I'm trying to say [and saying very badly] is that Haskell is an
>> almost terrifyingly subtle language.
>
> Name me a useful programming language that isn't.
> Simply interchanging two for-loops, from
>     for (i = 0; i < N; i++) for (j = 0; j < N; j++)
> to    for (j = 0; j < N; j++) for (i = 0; i < N; i++)
> when marching over an array, can easily slow you down
> by nearly two orders of magnitude in C.
> [Hint: read "What every computer scientist needs to know
> about memory".]

OK, well *that* is news... :-o

I would suggest that for heap-allocated data that isn't an array, both
cases will be equally unperformant. I can't prove that though...

> "Unexpectedly slow" is better than "inexplicably buggy".

+184   o_O

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...