GHC predictability

[Ketil Malde-5]

Jed Brown <jed@...> writes:

> This, of course, is because `od -x' regards the input as 16-bit integers.  We
> can get saner output if we regard it is 8-bit integers.

Yes, of course. The point was that for big-endian, the word size
won't matter.  Little-endian words will be reversed with respect to
the normal (left-to-right, most significant first) way we print
numbers.

-k
--
If I haven't seen further, it is by standing in the footprints of giants
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Aaron Denney]

On 2008-05-13, Ketil Malde <ketil@...> wrote:
> Jed Brown <jed@...> writes:
>
>> This, of course, is because `od -x' regards the input as 16-bit integers.  We
>> can get saner output if we regard it is 8-bit integers.
>
> Yes, of course. The point was that for big-endian, the word size
> won't matter.  Little-endian words will be reversed with respect to
> the normal (left-to-right, most significant first) way we print
> numbers.

Right.  Because we print numbers backwards.

--
Aaron Denney
-><-

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

[Anton van Straaten]

Achim Schneider wrote:
> To get a bit more on-topic: I currently completely fail to implement a
> layout rule in Parsec because I don't understand its inner workings,
> and thus constantly mess up my state. Parsec's ease of usage is
> deceiving as soon as you use more than combinators: Suddenly the
> plumbing becomes important, and hackage is full of such things. Haskell
> has potentially infinite learning curves, and each one of them
> usually represents a wall. To make them crumble, you have to get used to
> not understand anything until you understand everything.

A big component of this is just that a high level of abstraction is
involved.  Something similar occurs in other languages, for programs
that are written in a very abstract way.  Some frameworks in e.g.
Smalltalk, Java, or C++ are an example of this: full of classes whose
domain is mainly internal to the framework, and you have to understand
the framework's design principles in their full generality in order to
be able to really understand the code.

As a more concrete example related to Parsec, consider a generator of
table-driven parsers written in C, and compare this to writing a
recursive-descent parser directly.  The code for the parser generator is
completely impenetrable for someone who isn't familiar with the theory
behind it, so if they want to change the generator's behavior, they're
likely to be stuck.  Whereas for a recursive descent parser for a single
language, it's much easier to map between the ultimate application
goals, and how those are accomplished in the code, without much special
knowledge.

Of course there are pros and cons on either side.  One reason that DSLs
work well is that when done right, so that abstraction leakage is
minimal, they can insulate users from having to understand the
underlying system.  Embedded DSLs, like Parsec, seem more likely to
suffer from problems in this area, although in that case the tradeoff is
that you're getting to use them directly in a general-purpose language.

Anton

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

[Aaron Denney]

On 2008-05-13, Jed Brown <jed@...> wrote:
>> > 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.
>
> It's not that simple with bits.  They lack consistency just like the
> usual US date format and the way Germans read numbers.

Yes.  I'm saying what should be, not what is.  I'm saying one of those
ways is wrong, wrong, wrong.  It usually doesn't matter in practice,
because writes to e.g. RAM effectively happen at byte-level or higher,
making the internal labels fairly arbitrary.  It matters and can cause
confusion in actual serial protocols, of course, which have been making
a resurgence in recent years, though again, the bit order in these are
well understood.  Just possibly wrong.

--
Aaron Denney
-><-

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

[Luke Palmer-2]

On Tue, May 13, 2008 at 12:48 PM, Paul Johnson <paul@...> wrote:

>  > $ pointfree "\xs -> foldl' (+) 0 xs / fromIntegral (length xs)"
>  > ap ((/) . foldl' (+) 0) (fromIntegral . length)
>
>  But when I try this in GHCi 6.8.2 I get:
>
>  > Prelude Data.List Control.Monad> let mean2 = ap ((/) . foldl' (+) 0)
> (fromIntegral . length)
>  >
>  > <interactive>:1:12:
>  >    No instance for (Monad ((->) [b]))
>  >       arising from a use of `ap' at <interactive>:1:12-58
>  >     Possible fix: add an instance declaration for (Monad ((->) [b]))
>  >    In the expression: ap ((/) . foldl' (+) 0) (fromIntegral . length)
>  >    In the definition of `mean2':
>  >        mean2 = ap ((/) . foldl' (+) 0) (fromIntegral . length)

It's using the Monad ((->) r) instance, which doesn't exist by
default.  import Control.Monad.Instances to get it.

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

[Bryan O'Sullivan]

Darrin Thompson wrote:

> These "tricks" going into Real World Haskell?

Some will, yes.

For example, the natural and naive way to write Andrew's "mean" function
doesn't involve tuples at all: simply tail recurse with two accumulator
parameters, and compute the mean at the end.  GHC's strictness analyser
does the right thing with this, so there's no need for seq, $!, or the
like.  It's about 3 lines of code.

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

[Daniel Fischer-4]

Am Dienstag, 13. Mai 2008 21:28 schrieb Aaron Denney:

> On 2008-05-13, Ketil Malde <ketil@...> wrote:
> > Jed Brown <jed@...> writes:
> >> This, of course, is because `od -x' regards the input as 16-bit
> >> integers.  We can get saner output if we regard it is 8-bit integers.
> >
> > Yes, of course. The point was that for big-endian, the word size
> > won't matter.  Little-endian words will be reversed with respect to
> > the normal (left-to-right, most significant first) way we print
> > numbers.
>
> Right.  Because we print numbers backwards.

Try hebrew or arab then, they have the least significant digit first in
reading order :)

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

[Jeff Polakow]

Hello,

> For example, the natural and naive way to write Andrew's "mean" function
> doesn't involve tuples at all: simply tail recurse with two accumulator
> parameters, and compute the mean at the end.  GHC's strictness analyser
> does the right thing with this, so there's no need for seq, $!, or the
> like.  It's about 3 lines of code.
>
Is this the code you mean?

    meanNat = go 0 0 where
        go s n [] = s / n
        go s n (x:xs) = go (s+x) (n+1) xs

If so, bang patterns are still required bang patterns in ghc-6.8.2 to run in constant memory:

    meanNat = go 0 0 where
        go s n [] = s / n
        go !s !n (x:xs) = go (s+x) (n+1) xs

Is there some other way to write it so that ghc will essentially insert the bangs for me?

-Jeff


---

This e-mail may contain confidential and/or privileged information. If you
are not the intended recipient (or have received this e-mail in error)
please notify the sender immediately and destroy this e-mail. Any
unauthorized copying, disclosure or distribution of the material in this
e-mail is strictly forbidden.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Jeff Polakow]

Hello,

>  > $ pointfree "\xs -> foldl' (+) 0 xs / fromIntegral (length xs)"
>  > ap ((/) . foldl' (+) 0) (fromIntegral . length)
>
This will have the same space usage as the pointed version. You can see this by looking at the monad instance for ((->) r):

    instance Monad ((->) r) where
       return = const
        f >>= k = \ r -> k (f r) r

-Jeff

---

This e-mail may contain confidential and/or privileged information. If you
are not the intended recipient (or have received this e-mail in error)
please notify the sender immediately and destroy this e-mail. Any
unauthorized copying, disclosure or distribution of the material in this
e-mail is strictly forbidden.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Achim Schneider]

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.


--
(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

[Don Stewart-2]

jeff.polakow:

>    Hello,
>
>    > For example, the natural and naive way to write Andrew's "mean" function
>    > doesn't involve tuples at all: simply tail recurse with two accumulator
>    > parameters, and compute the mean at the end.  GHC's strictness analyser
>    > does the right thing with this, so there's no need for seq, $!, or the
>    > like.  It's about 3 lines of code.
>    >
>    Is this the code you mean?
>
>        meanNat = go 0 0 where
>            go s n [] = s / n
>            go s n (x:xs) = go (s+x) (n+1) xs
>    If so, bang patterns are still required bang patterns in ghc-6.8.2 to run
>    in constant memory:
>
>        meanNat = go 0 0 where
>            go s n [] = s / n
>            go !s !n (x:xs) = go (s+x) (n+1) xs
>
>    Is there some other way to write it so that ghc will essentially insert
>    the bangs for me?

Yes, give a type annotation, constraining 'n' to Int.

    meanNat :: [Double] -> Double
    meanNat = go 0 0
      where
       go :: Double -> Int -> [Double] -> Double
       go s n []     = s / fromIntegral n
       go s n (x:xs) = go (s+x) (n+1) xs

And you get this loop:

    M.$wgo :: Double#
              -> Int#
              -> [Double]
              -> Double#

    M.$wgo =
      \ (ww_smN :: Double#)
        (ww1_smR :: Int#)
        (w_smT :: [Double]) ->
        case w_smT of wild_B1 {
          [] -> /## ww_smN (int2Double# ww1_smR);
          : x_a9k xs_a9l ->
            case x_a9k of wild1_am7 { D# y_am9 ->
            M.$wgo (+## ww_smN y_am9) (+# ww1_smR 1) xs_a9l
            }
        }

Without the annotation you get:

    M.$wgo :: Double#
          -> Integer
          -> [Double]
          -> Double

GHC sees through the strictness of I#.

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

[Dan Doel]

On Tuesday 13 May 2008, Jeff Polakow wrote:

> Is this the code you mean?
>
>     meanNat = go 0 0 where
>         go s n [] = s / n
>         go s n (x:xs) = go (s+x) (n+1) xs
>
> If so, bang patterns are still required bang patterns in ghc-6.8.2 to run
> in constant memory:
>
>     meanNat = go 0 0 where
>         go s n [] = s / n
>         go !s !n (x:xs) = go (s+x) (n+1) xs
>
> Is there some other way to write it so that ghc will essentially insert
> the bangs for me?

It works fine here when compiled with -O or better.

Perhaps that should be a tip in the book? Make sure you're compiling with
optimizations. :)

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

[Andrew Coppin]

Jeff Polakow wrote:

> Then, I immediately blow my stack if I try something like:
>
>     mean [1..1000000000].
>
> The culprit is actually sum which is defined in the base libraries as
> either a foldl or a direct recursion depending on a compiler flag. In
> either case, the code is not strict enough; just trying to compute:
>
>      sum [1..10000000]
>
> blows the stack. This can be easily fixed by defining a suitable
> strict sum:
>
>     sum' = foldl' (+) 0
>
> and now sum' has constant space.

OK *now* I'm worried... I thought sum was _already_ defined this way? o_O

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

[Don Stewart-2]

dons:

> jeff.polakow:
> >    Hello,
> >
> >    > For example, the natural and naive way to write Andrew's "mean" function
> >    > doesn't involve tuples at all: simply tail recurse with two accumulator
> >    > parameters, and compute the mean at the end.  GHC's strictness analyser
> >    > does the right thing with this, so there's no need for seq, $!, or the
> >    > like.  It's about 3 lines of code.
> >    >
> >    Is this the code you mean?
> >
> >        meanNat = go 0 0 where
> >            go s n [] = s / n
> >            go s n (x:xs) = go (s+x) (n+1) xs
> >    If so, bang patterns are still required bang patterns in ghc-6.8.2 to run
> >    in constant memory:
> >
> >        meanNat = go 0 0 where
> >            go s n [] = s / n
> >            go !s !n (x:xs) = go (s+x) (n+1) xs
> >
> >    Is there some other way to write it so that ghc will essentially insert
> >    the bangs for me?
>
> Yes, give a type annotation, constraining 'n' to Int.
>
>     meanNat :: [Double] -> Double
>     meanNat = go 0 0
>       where
>        go :: Double -> Int -> [Double] -> Double
>        go s n []     = s / fromIntegral n
>        go s n (x:xs) = go (s+x) (n+1) xs
>
> And you get this loop:
>
>     M.$wgo :: Double#
>               -> Int#
>               -> [Double]
>               -> Double#
>
>     M.$wgo =
>       \ (ww_smN :: Double#)
>         (ww1_smR :: Int#)
>         (w_smT :: [Double]) ->
>         case w_smT of wild_B1 {
>           [] -> /## ww_smN (int2Double# ww1_smR);
>           : x_a9k xs_a9l ->
>             case x_a9k of wild1_am7 { D# y_am9 ->
>             M.$wgo (+## ww_smN y_am9) (+# ww1_smR 1) xs_a9l
>             }
>         }
>

Note this is pretty much identical to the code you get with a foldl' (though
without the unboxed pair return):

    import Data.List
    import Text.Printf
    import Data.Array.Vector

    mean :: [Double] -> Double
    mean arr = b / fromIntegral a
      where
        k (n :*: s) a = (n+1 :*: s+a)
        (a :*: b) = foldl' k (0 :*: 0) arr :: (Int :*: Double)

    main = printf "%f\n" . mean $ [1 .. 1e9]

Note I'm using strict pairs for the accumulator, instead of banging lazy
pairs.

    $s$wlgo :: [Double]
                    -> Double#
                    -> Int#
                    -> (# Int, Double #)

    $s$wlgo =
      \ (xs1_aMQ :: [Double])
        (sc_sYK :: Double#)
        (sc1_sYL :: Int#) ->
        case xs1_aMQ of wild_aML {
          [] -> (# I# sc1_sYL, D# sc_sYK #);
          : x_aMP xs11_XMX ->
            case x_aMP of wild1_aOg { D# y_aOi ->
            $s$wlgo xs11_XMX (+## sc_sYK y_aOi) (+# sc1_sYL 1)
            }
        }

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

[Andrew Coppin]

Darrin Thompson wrote:
> These "tricks" going into Real World Haskell?

Seconded.

> When you say someone
> needs to get familiar with the "STG paper" it scares me (a beginner)
> off a little, an I've been making an effort to approach the papers.

Well, I'm the sort of contrary person who reads random papers like that
just for the fun of it. But when somebody says something like this, I
don't think "ooo, that's scary", I think "ooo, somebody really ought to
sit down and write a more gentle introduction". You really shouldn't
*need* to know the exact implementation details to get some idea of what
will perform well and what won't. But obviously you do need some kind of
high-level understanding of what's going on. The STG paper isn't a good
way to get that high-level overview.

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

[Don Stewart-2]

andrewcoppin:

> Darrin Thompson wrote:
> >These "tricks" going into Real World Haskell?
>
> Seconded.
>
> >When you say someone
> >needs to get familiar with the "STG paper" it scares me (a beginner)
> >off a little, an I've been making an effort to approach the papers.
>
> Well, I'm the sort of contrary person who reads random papers like that
> just for the fun of it. But when somebody says something like this, I
> don't think "ooo, that's scary", I think "ooo, somebody really ought to
> sit down and write a more gentle introduction". You really shouldn't
> *need* to know the exact implementation details to get some idea of what
> will perform well and what won't. But obviously you do need some kind of
> high-level understanding of what's going on. The STG paper isn't a good
> way to get that high-level overview.

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?

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

[Darrin Thompson]

On Tue, May 13, 2008 at 4:30 PM, Andrew Coppin
<andrewcoppin@...> wrote:
>  Well, I'm the sort of contrary person who reads random papers like that
> just for the fun of it. But when somebody says something like this, I don't
> think "ooo, that's scary", I think "ooo, somebody really ought to sit down
> and write a more gentle introduction". You really shouldn't *need* to know
> the exact implementation details to get some idea of what will perform well
> and what won't. But obviously you do need some kind of high-level
> understanding of what's going on. The STG paper isn't a good way to get that
> high-level overview.
>

I don't think anyone would disagree with that. Reflecting on what I
already know, I can optimize python pretty well and the principles are
pretty similar for C. The reason I can't just port that knowledge is
that with GHC I'm in the land of optimizing for cache hits and at the
same time I'm at a really high level of abstraction so I have to have
some mental picture of how the plumbing connects.

I'm hoping that the optimization chapter of RWH covers a lot of
individual techniques. I think the sum of the techniques will shed
light on the compiler internals in a practical way. But then I'm not
the one doing the work.

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

[Jed Brown]

On Tue 2008-05-13 22:14, 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.

I would argue that 100n+11 to 100n+19 are special cases in both German and
English, but only 100n+11 to 100n+15 in Spanish.  In any case, the order of the
digits is dependent on where the decimal falls.  If the ordering is pure little
endian (not x86 halfway) or big endian, the bit order is not dependent on the
width of the field.  Converting breaks this nice property.  Convention is to
write numbers in big endian and it would be nice if there were fewer exceptions.
Yet another argument for ISO 8601 dates.  A somewhat dramatic change would be to
put the exponent first in scientific notation.  Alas, this seems unlikely to
happen.

Jed


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