Byte Histogram

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

Byte Histogram

Andrew Coppin
There now follows a small grab-bag of miscelaneous but related thoughts.
(Which probably means that this post will spawn a 2000 message thread
discussing one tiny side-issue, rather than the main thrust of the
message...)



First of all, benchmarking. We have The Great Language Shootout, which
tests how fast solutions implemented in various programming languages
can be, given unbounded amounts of time, energy, expertise, and compiler
modifications. Which is interesting, from a certain point of view.

In another sense, it's less interesting. For example, a C program can be
as fast as any Haskell program, since compiling Haskell entails
transforming it *into* C. (Unless you're seriously going to suggest that
GHC's native code generator is any match for the might of a half-decent
C compiler...)

That got me thinking about a more interesting question: Not *how fast*
can it go, but *how easily* can it go fast? People have written fast C
programs and fast Haskell programs, but how easy is it to write a
"typical" program and have it go fast, without spending years optimising it?

With that in mind, I set of with a plan to do some small-scale
benchmarking. Pick a problem, solve it in both Haskell and C++, in the
"simplest, most obvious way", and then apply "the simplest, most obvious
optimisations". Measure performance and compare.

There are benchmarks that just output some data. ("Find all the prime
numbers less than 1000...") I dislike these for a couple of reasons, not
least because you can precompute the correct answer and just write a
program which outputs that. (!) So I decided that all my benchmark
programs should take a variable-sized data file as input, and save the
results as output.

There's an old maxim of running benchmarks multiple times, to ensure
that whatever time you got wasn't just a fluke. But then, maybe the
first run pulls the input file into the file cache, and subsequent runs
go faster. If your input data was randomly generated, perhaps you chose
a particularly optimal or pessimal data set by accident. So I decided
that each test run should use a different input file of approximately
the same characteristics (size, random distribution, etc.)

So I ended up picking benchmarks like "sort the lines of this file into
ascending order", "count the number of unique words in this file",
"produce a histogram of byte values", "compute some statistics of this
list of numbers", etc. The tasks are all extremely simple, so that there
is some hope of it being possible to also implement them in C++.



One benchmark turned out to be particularly interesting: I call it "byte
histogram". The task is simple:
- Open a binary input file.
- Read a stream of bytes from it.
- Count how many times each of the 256 possible byte values appears.
The test inputs are binary files of various sizes, some with a uniform
distribution, some with variously skewed distributions (so that some
bytes have a vastly higher count than others).

Assuming we have some suitable import statements, it's quite easy to do
this:

   bytes <- BS.readFile "Input.bin"
   let out = BS.foldl' (\ map byte -> MAP.insertWith (+) byte 1 map)
MAP.empty bytes
   writeFile "Output.csv" (unlines $ map (\(k,v) -> show k ++ "," ++
show v) $ MAP.toAscList out)

(There is some slight trickiness if you want bytes with zero frequency
to still be listed.)

All of this *works* perfectly - i.e., it produces the correct answers.
It's also astronomically slow, and it's very easy to make it eat many
gigabytes of RAM while it runs. (If the program starts actually
swapping, then you will truly know what "slow" is!)

OK, so what happens if we replace Data.Map with Data.IntMap? Well, it
goes slightly faster, and consumes slightly less RAM. Inputs which
didn't quite complete before will run to completion now. But performance
is still abysmal.

Enough with this tree sillyness. What happens if you use an array? Given
that the entire program (apart from the last 0.02% of it) spends its
time notionally mutating the data, a mutable array would be the logical
choise. Dial up an IOArray Word8 Int and the structure of the program
changes slightly, but it's still only a handful of lines of code. And
the performance? Still glacial.

In particular, suppose we have

   inc :: IOArray Word8 Int -> Word8 -> IO ()
   inc array byte = do
     count <- readArray array byte
     let count' = count + 1
     writeArray array byte count'

in the main loop. The program is giving us the right answer, but using
absurd amounts of time and space to get it. Now watch this:

   inc :: IOArray Word8 Int -> Word8 -> IO ()
   inc array byte = do
     count <- readArray array byte
     let count' = count + 1
     count' `seq` writeArray array byte count'

And now, suddenly, memory usage becomes constant, regardless of input
size, and run-time is slashed. The program goes from taking 50 seconds
to process a certain file to taking only 0.02 seconds. And from taking
400 MB of RAM to taking... less RAM than I can actually measure properly.

If we now replace the IOArray with an IOUArray then the seq call becomes
superfluous, and there's a small performance increase, but nothing major.



None of this should be any surprise to anybody who actually knows how
Haskell works. For anybody not yet expert enough to see the problem: The
"inc" function doesn't read the array, see that a given byte has a count
of 5, and overwrite that with a 6. It sees a 5 and overwrites it with a
5+1. By the end of the main loop, every single array cell contains
1+(1+(1+(1+(1+(1+....)))), which takes a stackload of RAM to hold.

That explains why RAM usage is so absurd. On top of all that, creating
all this data takes time, and the spiralling RAM usage makes the GC go
crazy trying to find garbage to get rid of (when of course there is
none). And finally, at the end, you have to unwind all these
expressions. (Curiously, I haven't seen a stack overflow yet...)

Adding the seq call forces 5+1 to actually turn into 6, not eventualy
but *right now*, and so each array cell ends up actually containing a
fully-evaluated integer. (No doubt this change in strictness also
triggers an avalanche of optimisation opportunities, but the basic thing
of importants is that we're not uselessly delaying evaluation now.)

As I say, none of this is a surprise to anybody who actually knows how
to get performance out of Haskell. The strict version is actually faster
than the C++ version. (I imagine I'm doing something horribly wrong with
C++, of course...) Not drastically faster, but faster. Which probably
just means that ByteString is doing nicer buffering than whatever the
C++ standard library is called.

The important obsevation is this: One tiny, almost insignificant change
can transform a program from taking 50 seconds and 400 MB of RAM into
one that takes 0.02 seconds and 0.1 MB of RAM. And, at least in this
case, the simpler version is the slow one.

To say that Haskell is "slow" is both a little bit vague, and not really
backed up by facts. In about 5 minutes flat, I managed to write a
Haskell program that's very simple, and yet faster than a comparably
simple C++ program (and C++ is supposed to be "fast"). So it's not that
Haskell is "slow". It's that Haskell is *tricky*. Tiny, tiny little
changes that look innocuous can have vast effects on performance. And
this is a nice little example of that effect.

As we (probably?) all know, strictness is a subtle and fickle thing.
Consider:

   or :: Bool -> Bool -> Bool
   or True  True  = True
   or True  False = True
   or False True  = True
   or False False = False

Overlooking the obvious name clash, this seems like a perfectly
legitimate definition for the logical-OR function. But now try this:

   xs `contains` x = foldr or False $ map (x ==) xs

A nice, pretty Haskell definition. But oh dears - this does not have the
performance you would expect at all! But if you change the definition
above to the apparently equivilent

   or True  _ = True
   or False x = x

then "contains" becomes much faster. If you saw these two functions side
by side, you might well wonder what the hell the difference is. You
might even wonder if the compiler would transform one to the other
(although I'm not sure in which direction). But there is, in fact, a
very, very big difference: one is lazier than the other.

For counting bytes, lazy = bad. For searching for matches, lazy = good.
Similarly, if you take the byte histogram program and replace the lazy
ByteString with a strict one, RAM usage spikes sharply.

In all, laziness is a tricky, tricky little hobbitses. I wrote a C++
program, in the obvious way, and it was very, very fast. I wrote a
Haskell program in several comparably obvious ways, and they were all
cripplingly slow. Until I added the magic "seq", and suddenly got
blinding speed. So while it is not correct to say "Haskell is slow", one
could justifyably say "C++ is fast more reliably than Haskell".



Consider for a moment the original implementation with Data.Map. Adding
a seq or two here will do no good at all; seq reduces to WHNF. What we
are wanting is NF, and I can see no way at all of doing that. (Other
than doing something very expensive like looking up every possible key,
which is far more operations than actually necessary.)

I wrote my own little BST algorithm, customised to the fact that there
are always exactly 256 keys of type Word8. It was also nausiatingly
slow. And then I did something: I inserted a few strictness annotations
on the constructor fields. And (as you already worked out), performance
increased drastically.

I can do that if *I* define the data structure. But if it's in a
library, I am powerless to make it more strict (or less, if that were
what I wanted).

That got me thinking... What would happen if, instead of "Integer", we
had two types, "evaluated Integer" and "possibly unevaluated Integer"?
What if the strictness or otherwise of a data structure were exposed at
the type level?

The general idea here is that anything declared has having type
"evaluated Integer" can never contain an unevaluated expression. It must
always contain an actual integer. This of course implies that you might
be able to unbox it or do other interesting things with it, but it also
says something about evaluation.

The principle question is "what happens if you assign an unevaluated
Integer to an evaluated Integer?" Is that legal? Do you have to
explicitly evaluate it first? Or does that happen implicitly? Presumably
"evaluated Integer" means evaluated to WHNF only - which for an integer
is the same thing as NF, but for some more complex structure it might
not be.

If the type system worked like this, I could do "Data.Map with evaluated
integer keys and possibly evaluated integer values", and it would hold
its values lazily. Or I could say "Data.Map with evaluated integer keys
and evaluated integer values", and the structure would now magically be
strict. Which is to say, the type system would ensure that any data
passed into the structure was evaluated first, and the compiler could do
any applicable optimisations based on the assumption of data being
already evaluated. (For primitive types, that might be unboxing or
passing in registors. For ADTs, it might just mean skipping an
evaluation check.)

Currently, if you want a strict list, you have to implement one
yourself. But is that strict in the spine, or the elements, or what? You
have to implement every combination that you want. And, let us not
forget, then go implement all the functions in Data.List over your new
data structure. Not fun.

If, on the other hand, strictness where in the type system, data
structures would be *parameterised* over the level of strictness required.

I have no idea what the syntax for that would look like, and backwards
compatibility looks like a nightmare. You would need to answer questions
like "what does it mean for a function to return an evaluated type?" and
"is evaluation implicit or explicit?" But it seems like a rather
interesting idea.

(Let us not forget: *Everything* is trivial for the person who doesn't
have to write the implementation...)

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

Re: Byte Histogram

Daniel Fischer
To illustrate your prediction about the side-issues:

On Thursday 03 February 2011 22:10:51, Andrew Coppin wrote:
> Consider for a moment the original implementation with Data.Map. Adding
> a seq or two here will do no good at all; seq reduces to WHNF. What we
> are wanting is NF, and I can see no way at all of doing that.

Check out Data.Map.insertWith'

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

Re: Byte Histogram

Andrew Coppin
On 03/02/2011 09:37 PM, Daniel Fischer wrote:
> To illustrate your prediction about the side-issues:
>
> On Thursday 03 February 2011 22:10:51, Andrew Coppin wrote:
>> Consider for a moment the original implementation with Data.Map. Adding
>> a seq or two here will do no good at all; seq reduces to WHNF. What we
>> are wanting is NF, and I can see no way at all of doing that.
>
> Check out Data.Map.insertWith'

*facepalm*

Wouldn't that still mean that the spine of the map is still lazy though?

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

Re: Byte Histogram

Johan Tibell-2
In reply to this post by Andrew Coppin
Hi,

Thanks for bringing up these issues. It's something we could be better
at addressing as a community.

First, we need to stop pretending that you can use Haskell effectively
without first learning to reason about program evaluation order.
Learning how is not terrible difficult, but there's very little
material on how to do it [1]. Some of us have learnt it the hard way
by experimentation or by talking to people who do understand lazy
evaluation [2] (the Simons, Don, and Bryan to name a few). At the very
least we need to teach people how to tell which arguments a pure
function is strict in by looking at its definition.

Second, many of our core data structures are lazy, but most uses are
strict. That keeping a simple map of counters is tricky should tell us
that something is wrong (you need to use insertWith'). It wouldn't be
if Data.Map was strict in the values. Many strictness related problems
people have are due to common data types like Maybe, tuples, and
arrays being lazy. This is rarely what you want.

1. I tried to start creating some. For example, by giving a high
performance Haskell talk at CUFP. Unfortunately the talk wasn't taped.
2. Haskell is non-strict, which doesn't necessarily imply lazy
evaluation. However, lazy evaluation is what we actually deal with.

Johan

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

Re: Byte Histogram

Johan Tibell-2
In reply to this post by Andrew Coppin
On Thu, Feb 3, 2011 at 11:10 PM, Andrew Coppin
<[hidden email]> wrote:
> Wouldn't that still mean that the spine of the map is still lazy though?

No, Data.Map and Data.Set are both spine strict (which should be
documented!). Data.Map is key strict in addition. Both are value lazy.

Johan

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

Re: Byte Histogram

Johan Tibell-2
In reply to this post by Andrew Coppin
Hi,

For what it's worth I saw the problems in your counting examples right
away, without reading the explanatory text below. Hopefully that means
that it's possibly to learn how to spot such things without resorting
to e.g. running the program or reading Core *gasp*.

Johan

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

Re: Byte Histogram

Daniel Fischer
On Thursday 03 February 2011 23:19:31, Johan Tibell wrote:
> Hi,
>
> For what it's worth I saw the problems in your counting examples right
> away, without reading the explanatory text below.

Yes, they were pretty obvious with enough experience. For beginners I
expect it to be a rather insidious trap.

> Hopefully that means
> that it's possibly to learn how to spot such things without resorting
> to e.g. running the program or reading Core *gasp*.

Within limits. Detrimental laziness or strictness can be arbitrarily well
hidden.


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

Re: Byte Histogram

Richard A. O'Keefe
In reply to this post by Andrew Coppin

On 4/02/2011, at 10:10 AM, Andrew Coppin wrote:
>
> The important obsevation is this: One tiny, almost insignificant change can transform a program from taking 50 seconds and 400 MB of RAM into one that takes 0.02 seconds and 0.1 MB of RAM. And, at least in this case, the simpler version is the slow one.
>
> To say that Haskell is "slow" is both a little bit vague, and not really backed up by facts. In about 5 minutes flat, I managed to write a Haskell program that's very simple, and yet faster than a comparably simple C++ program (and C++ is supposed to be "fast"). So it's not that Haskell is "slow". It's that Haskell is *tricky*. Tiny, tiny little changes that look innocuous can have vast effects on performance. And this is a nice little example of that effect.

This seems to me to be the heart of the message, so maybe this reply is on-topic.

Back in the days when systems other than Wintel and maybe sort of intel Linux were
supported by Clean, I used to really love one of the features of the Clean compiler.
One simple command line switch and the compiler would list the names of all your
top level functions together with their types, and the types included strictness.
(Also uniqueness, not relevant to Haskell.)

The GHC documentation says the information is in the interface files,
but they are binary now, and I can't find it there.

> That got me thinking... What would happen if, instead of "Integer", we had two types, "evaluated Integer" and "possibly unevaluated Integer"? What if the strictness or otherwise of a data structure were exposed at the type level?

Oh, you mean like "!Int" and "Int" in Clean?  I used to find bang *types* rather easier to deal with
than I now do bang *patterns*.

> Currently, if you want a strict list, you have to implement one yourself. But is that strict in the spine, or the elements, or what?

Spine strict: ![t].
Spine and element strict: ![!t].
>
> I have no idea what the syntax for that would look like,

Clean?



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

Re: Byte Histogram

Erik de Castro Lopo-34
In reply to this post by Daniel Fischer
Daniel Fischer wrote:

> On Thursday 03 February 2011 23:19:31, Johan Tibell wrote:
> > Hi,
> >
> > For what it's worth I saw the problems in your counting examples right
> > away, without reading the explanatory text below.
>
> Yes, they were pretty obvious with enough experience. For beginners I
> expect it to be a rather insidious trap.
>
> > Hopefully that means
> > that it's possibly to learn how to spot such things without resorting
> > to e.g. running the program or reading Core *gasp*.
>
> Within limits. Detrimental laziness or strictness can be arbitrarily well
> hidden.

I am a relative newcomer to Haskell, but I think I have a reasonable
understanding of the executaion model. Enough to fix performance
issues in simple code like the example given.

However, one of the Haskell projects I work on is Ben Lippmeier's
DDC compiler. Thats about 50000 lines of Haskell code and finding
performance issues there is really difficult.

Erik
--
----------------------------------------------------------------------
Erik de Castro Lopo
http://www.mega-nerd.com/

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

Re: Byte Histogram

Johan Tibell-2
In reply to this post by Richard A. O'Keefe
On Thu, Feb 3, 2011 at 11:40 PM, Richard O'Keefe <[hidden email]> wrote:
> Back in the days when systems other than Wintel and maybe sort of intel Linux were
> supported by Clean, I used to really love one of the features of the Clean compiler.
> One simple command line switch and the compiler would list the names of all your
> top level functions together with their types, and the types included strictness.
> (Also uniqueness, not relevant to Haskell.)
>
> The GHC documentation says the information is in the interface files,
> but they are binary now, and I can't find it there.

ghc --show-iface HI_FILE

The strictness signatures are a bit hard to parse though. Having a
cheat sheet would be nice.

Johan

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

Re: Byte Histogram

Johan Tibell-2
In reply to this post by Erik de Castro Lopo-34
On Fri, Feb 4, 2011 at 12:38 AM, Erik de Castro Lopo
<[hidden email]> wrote:
> However, one of the Haskell projects I work on is Ben Lippmeier's
> DDC compiler. Thats about 50000 lines of Haskell code and finding
> performance issues there is really difficult.

Right. It can still be tricky. I think we can get rid of a large
number of strictness issues by using strict data structures more
often, this should help beginners in particular. For the rest better
tooling would help. For example, a lint tool that marked up code with
the strictness information inferred by the compiler would be useful. I
had time to write one I would make the output look like HPC html
reports, with one color for strict function arguments and one color
for lazy function arguments.

Johan

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

Re: Byte Histogram

Jake McArthur
In reply to this post by Andrew Coppin
On 02/03/2011 03:10 PM, Andrew Coppin wrote:
> (Unless you're seriously going to suggest that GHC's native code
> generator is any match for the might of a half-decent C compiler...)

I don't know enough about the native code generator to make a claim like
that, but we're not comparing the native code generator against a C
compiler; we're comparing it against a C code generator whose output is
fed through a C compiler. These are very different things, and I think
it gives the native code generator an edge. My own observations from
immediately before the C backend was deprecated was that the native code
generator averaged slightly better performing code.

- Jake

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

Re: Byte Histogram

Richard A. O'Keefe
In reply to this post by Johan Tibell-2

On 4/02/2011, at 8:26 PM, Johan Tibell wrote:

> --show-iface HI_FILE

sort.hs has 50 top level functions.
One of them is main, and the others are all reachable from it.

ghc -O sort.hs
ghc --show-iface sort.hi

The only functions listed are variants of main.
Dropping -O leaves one variant of main only;
the other 49 functions have disappeared.

It is, by the way, something of a nuisance that if you do
        ghc sort.hs
        ...
        ghc -O sort.hs
it insists "compilation NOT required" despite the fact that
the previous compilation was with materially *different* options.
(GHC 6.12.3)

Given this clue I was able to get the information I wanted by
exporting all the functions.

This is the wrong interface.  If a programmer is concerned that
strictness analysis might not be finding something they thought
was strict, they would ideally like to have *all* the functions
reported, but at a minimum, all of the top level functions.



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

Re: Byte Histogram

Evan Laforge
In reply to this post by Erik de Castro Lopo-34
On Thu, Feb 3, 2011 at 3:38 PM, Erik de Castro Lopo
<[hidden email]> wrote:
> I am a relative newcomer to Haskell, but I think I have a reasonable
> understanding of the executaion model. Enough to fix performance
> issues in simple code like the example given.
>
> However, one of the Haskell projects I work on is Ben Lippmeier's
> DDC compiler. Thats about 50000 lines of Haskell code and finding
> performance issues there is really difficult.

Lately I've been trying to go the other direction: make a large
section of formerly strict code lazy.  I fully agree that once code
size gets big these problems get a lot harder.  You have to be very
careful passing around state that you don't do anything that causes
too much to be evaluated at the wrong time.  E.g., you can put back
the final result of a mapAccumL into a StateT but you want to make
sure it doesn't get looked at until the output of the mapAccumL would
be evaluated.  Even something seemingly innocuous like bundling it
into a newtype will cause the mapAccumL to run over the entire list
and evaluate a bunch of stuff too early and probably wind up with a
bunch of lag.  And the only way I can think of to find out what order
these things are running is to throw and infinite list and see if they
hang or put in a bunch of unsafePerformIO logging... not very
satisfying in either case, especially when trying to inspect things
can change the evaluation order.

Sometimes I wonder what this would look like if I were generating
incremental output with python yields... while getting the data
dependencies right is essential in any case, I'm suspicious it would
be easier to think about and understand in a strict language.

But there's definitely a knack to be learned, and I think I might
eventually get better at it.  For example, I realized that the
criteria to make something non-strict wrt data dependency are the same
as trying to parallelize.  Sometimes it's easier to think "what do I
have to do to make these two processes run in parallel" and that's the
same thing I have to do to make them interleave with each other
lazily.

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

Re: Byte Histogram

Claus Reinke
> Lately I've been trying to go the other direction: make a large
> section of formerly strict code lazy.  

There used to be a couple of tools trying to make suggestions
when a function could be made less strict (Olaf Chitil's StrictCheck
and another that escapes memory at the moment). Often, it
comes down to some form of eta-expansion - making information
available earlier [(\x->f x) tells us we have a function without
having to evaluate f, (\p->(fst p,snd p)) marks a pair without
needing to evaluate p, and so on].

> I fully agree that once code size gets big these problems get a lot
> harder.  You have to be very careful passing around state that you
> don't do anything that causes too much to be evaluated at the
> wrong time.  

Generally, the trick is to develop an intuitition early, before
growing the program in size;-) However, as long as you can
run your big code with small data sets, you might want to try
GHood, maintained on hackage thanks to Hugo Pacheco:

    http://hackage.haskell.org/package/GHood
    http://community.haskell.org/~claus/GHood/ (currently unavailable:-(

The latter url has a few examples and a paper describing how
GHood can be useful for observing relative strictness, ie, when
data at one probe is forced relative to when it is forced at another.

(it seems that citeseerx has a copy of the paper, at least:
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.132.1397 )

For instance, if you put one probe on the output and one on the
input, you can see which parts of the input are forced to produce
which parts of the output. As I said, small data sets help, but since
you put in probes manually and selectively, large code size should
not interfere with observations (though it might hinder intuition:-).

> But there's definitely a knack to be learned, and I think I might
> eventually get better at it.  For example, I realized that the
> criteria to make something non-strict wrt data dependency are the same
> as trying to parallelize.  Sometimes it's easier to think "what do I
> have to do to make these two processes run in parallel" and that's the
> same thing I have to do to make them interleave with each other
> lazily.

Sometimes, I think of non-strict evaluation as "spark a thread for
everything, then process the threads with a single processor"..

Claus
 

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

Re: Byte Histogram

wren ng thornton
On 2/5/11 4:26 AM, Claus Reinke wrote:
>> Lately I've been trying to go the other direction: make a large
>> section of formerly strict code lazy.
>
> There used to be a couple of tools trying to make suggestions
> when a function could be made less strict (Olaf Chitil's StrictCheck and
> another that escapes memory at the moment).

Perhaps you're thinking of the chasing bottoms[1] library?

[1] http://hackage.haskell.org/package/ChasingBottoms

--
Live well,
~wren

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

Re: Byte Histogram

Janis Voigtländer-2
In reply to this post by Andrew Coppin
On 2/5/11 4:26 AM, Claus Reinke wrote:
>> Lately I've been trying to go the other direction: make a large
>> section of formerly strict code lazy.
>
> There used to be a couple of tools trying to make suggestions when a
> function could be made less strict (Olaf Chitil's StrictCheck and
> another that escapes memory at the moment).

Probably Sloth:

http://korsika.informatik.uni-kiel.de/~jac/wordpress/
http://korsika.informatik.uni-kiel.de/~jac/wordpress/wp-content/uploads/PADL2011.pdf

Best,
Janis.

--
Jun.-Prof. Dr. Janis Voigtländer
http://www.iai.uni-bonn.de/~jv/
mailto:[hidden email]

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

Re: Byte Histogram

Andrew Coppin
In reply to this post by Daniel Fischer
On 03/02/2011 09:37 PM, Daniel Fischer wrote:
> To illustrate your prediction about the side-issues:
>
> On Thursday 03 February 2011 22:10:51, Andrew Coppin wrote:
>> Consider for a moment the original implementation with Data.Map. Adding
>> a seq or two here will do no good at all; seq reduces to WHNF. What we
>> are wanting is NF, and I can see no way at all of doing that.
>
> Check out Data.Map.insertWith'

Random fact: Data.Map.insertWith' exists. Data.IntMap.insertWith' does
*not* exist.

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

Re: Byte Histogram

Andrew Coppin
In reply to this post by Richard A. O'Keefe
>> That got me thinking... What would happen if, instead of "Integer", we had two types, "evaluated Integer" and "possibly unevaluated Integer"? What if the strictness or otherwise of a data structure were exposed at the type level?
>
> Oh, you mean like "!Int" and "Int" in Clean?  I used to find bang *types* rather easier to deal with
> than I now do bang *patterns*.
>
>> I have no idea what the syntax for that would look like,
>
> Clean?

I didn't think Clean supported laziness at all? I thought it was a
strict language.

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

Re: Byte Histogram

Andrew Coppin
In reply to this post by Johan Tibell-2
On 03/02/2011 10:15 PM, Johan Tibell wrote:

> First, we need to stop pretending that you can use Haskell effectively
> without first learning to reason about program evaluation order.

Writing a program in *any* language without understanding the
performance implications of different language constructs is unlikely to
produce performant code. OTOH, Haskell is unusual in just how easily
seemingly trivial alternations of a few characters can cause utterly
*giagintic* performance differences in both time and space.

> Learning how is not terrible difficult, but there's very little
> material on how to do it [1]. Some of us have learnt it the hard way
> by experimentation or by talking to people who do understand lazy
> evaluation [2] (the Simons, Don, and Bryan to name a few).

I think perhaps the problem is that Haskell's execution model is so
utterly *implicit*. In some imperative languag, if you call an expensive
function, it will be expensive. In Haskell, if you call an expensive
function and then never touch the result, it's cheap. Touch the result
once, and you might get fusion. Touch it twice and suddenly the space
complexity of the program changes. So simply adding a debug statement
can utterly transform your program's runtime.

What it comes down to is: Tiny changes sometimes have profound effects.

Best of all, there is little tool support for detecting these effects.
If you change your program and it suddenly slows down, you need to go
look at what you just changed. But if you write a brand new program and
it's drop-dead slow, where do you start looking? (Assuming you're not
writing a micro-benchmark.)

> At the very
> least we need to teach people how to tell which arguments a pure
> function is strict in by looking at its definition.

That's not necessarily tractible. It depends on what other functions you
call. Many functions have obvious strictness properties, but very few
have *documented* strictness properties.

> That keeping a simple map of counters is tricky should tell us
> that something is wrong.

Agreed.

> Many strictness related problems
> people have are due to common data types like Maybe, tuples, and
> arrays being lazy. This is rarely what you want.

I'm not sure that's 100% true. You might have a function that returns a
tuple, and on occasion you're only actually interested in one of the two
results. But that looks like the exception rather than the rule.

Lazy lists are rather useful, but it looks like strict lists would be
useful too. The number of times I've written !String and then thought
"hey, wait, that's not helping me..."

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
1234