What *not* to use Haskell for

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

Re: Re: Go Haskell! -> array libraries

Don Stewart-2
andrewcoppin:

> Austin Seipp wrote:
> >Excerpts from Andrew Coppin's message of Sat Nov 29 03:37:58 -0600 2008:
> >  
> >>Are you seriously asserting that it's "bad" for people to stop and think
> >>about their designs before building?
> >
> >To be fair, I don't think you're in a position to say whether the
> >authors of these libraries took careful consideration in their design
> >or not; unless, of course, you wrote one of them and *didn't* think
> >about the design?
>
> I said "I think we should take a step back and work out a plan" and Don
> said "no, I think we should just keep blindly hacking away instead". So
> I said that seems like a very bad idea to me...


I didn't say that - you just made it up! And you even added fake quotes!

Andrew, seriously, it's about time you contributed some code, rather
than just empty noise on the list?

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

Re[2]: Re: Go Haskell! -> array libraries

Bulat Ziganshin-2
In reply to this post by Andrew Coppin
Hello Andrew,

Saturday, November 29, 2008, 9:23:29 PM, you wrote:

> This goes beyond array libraries; do you have any idea how many "binary"
> packages there are?

i wrote 3 :)))


--
Best regards,
 Bulat                            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: Re: Go Haskell! -> array libraries

Andrew Coppin
In reply to this post by Andrew Coppin
Henning Thielemann wrote:
> I suspect that this particular function is less useful than you think.
> It safes one allocation and might be faster since it uses less cache,
> but on the other hand, it cannot be fused.

If the array is "seriously large", you don't want to have five or six
versions of it sitting in memory until the GC comes along to remove it.
(OTOH, presumably an unboxed array can be allocated or freed quite
quickly...) At a minimum, you've going to end up with two copies in
memory - the existing one, and the one being built.

> I think in-place array
> updates are only sensible for writing array elements in really random
> order. As long as you can formulate your algorithm the way "read from
> random indices, but write a complete array from left to right", there is
> almost no need for mutable arrays.
>  

Does quick-sort fit that pattern? (I'm guessing yes, since all you need
to do is filtering and merging...)

Yeah, generally you only need arrays if you really want random access.
Except in Haskell, where an array also happens to be the only way of
storing large numbers of values unboxed. So sometimes you'll use an
array because you want to save space. (E.g., parsing text is usually a
sequential process with no random access, but you probably want to use
ByteString all the same!) I sometimes also use unboxed arrays for the
increase in strictness.

I guess the thing to do would be to measure the difference...

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

Re: Re: Go Haskell! -> array libraries

Roman Leshchinskiy
In reply to this post by Brad Larsen
On 30/11/2008, at 02:43, Brad Larsen wrote:

> On Fri, 28 Nov 2008 19:00:38 -0500, Roman Leshchinskiy <[hidden email]
> > wrote:
>
>> On 29/11/2008, at 10:47, Claus Reinke wrote:
> [...]
>>> And would it be difficult for you all to agree on a standard API, to
>>> make switching between the alternatives easy (if
>>> it is indeed impossible to unify their advantages in a single  
>>> library,
>>> the reasons for which should also be documented somewhere)?
>>
>> Yes, it is very difficult. A sensible API for a standard array  
>> library
>> is something that needs more research. FWIW, I don't know of any  
>> other
>> language that has what I'd like to see in Haskell. C++ probably comes
>> closest but they have it easy - they don't do fusion.
> [...]
>
> Would you elaborate on what you'd like to see in an array library?

I'd like to have a library which is efficient (in particular,  
implements aggressive fusion), is roughly equivalent to the current  
standard list library in power and supports strict/unboxed/mutable  
arrays. It should also provide a generic framework for implementing  
new kinds of arrays. And eventually, it should also be usable in high-
performance and parallel algorithms.

>  And perhaps which C++ array library you are thinking of?  Your C++  
> comment caught my attention, and now I'm curious.  Surely you don't  
> mean C-style arrays. :-D

No, I meant vector, basic_string and deque which are provided by the  
standard library.

Roman


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

Re: Re: Go Haskell! -> array libraries

Roman Leshchinskiy
In reply to this post by Andrew Coppin
On 30/11/2008, at 08:32, Andrew Coppin wrote:

> Henning Thielemann wrote:
>> I suspect that this particular function is less useful than you  
>> think.
>> It safes one allocation and might be faster since it uses less cache,
>> but on the other hand, it cannot be fused.

Hmm, I haven't seen your original message but I suspect you are  
talking about in-place map. In that case, this is not entirely true.  
Shameless plug:

http://www.cse.unsw.edu.au/~rl/publications/recycling.html

>> I think in-place array
>> updates are only sensible for writing array elements in really random
>> order. As long as you can formulate your algorithm the way "read from
>> random indices, but write a complete array from left to right",  
>> there is
>> almost no need for mutable arrays.

Many array algorithms cannot really be written in this way. I think we  
do need mutable arrays and they should provide much more than just  
read/write. How to integrate them nicely with immutable arrays is not  
really clear, though.

Roman


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

Re: Re: Go Haskell! -> array libraries

Don Stewart-2
rl:

> On 30/11/2008, at 08:32, Andrew Coppin wrote:
>
> >Henning Thielemann wrote:
> >>I suspect that this particular function is less useful than you  
> >>think.
> >>It safes one allocation and might be faster since it uses less cache,
> >>but on the other hand, it cannot be fused.
>
> Hmm, I haven't seen your original message but I suspect you are  
> talking about in-place map. In that case, this is not entirely true.  
> Shameless plug:
>
> http://www.cse.unsw.edu.au/~rl/publications/recycling.html
>
> >>I think in-place array
> >>updates are only sensible for writing array elements in really random
> >>order. As long as you can formulate your algorithm the way "read from
> >>random indices, but write a complete array from left to right",  
> >>there is
> >>almost no need for mutable arrays.
>
> Many array algorithms cannot really be written in this way. I think we  
> do need mutable arrays and they should provide much more than just  
> read/write. How to integrate them nicely with immutable arrays is not  
> really clear, though.

Should mutable arrays have list-like APIs? All the usual operations,
just in-place and destructive where appropriate?

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

Re: What *not* to use Haskell for

Belka
In reply to this post by Dave Tapley-2
(1) Function as a system of N concurrent inputs and 1 output is easy essence. How about function as N concurrent inputs and M concurrent outputs? I think it's not native to lambda calculus. So "system's programming" (if we ever had such paradigm) would solve this issue, while criticizing all FP.

(2) For me, I hope this category (What *not* to use Haskell for) won't include SOA. That's what I'am currently trying to decide.

(3) I think if CPU's would be lambda-based, not imperative, and paradigm be stronger, most of the "why *not* to use Haskell"'s would be solved, and imperative would be in opposition instead.. with it's enthusiasts. =) They would have good answers for your question.
Reply | Threaded
Open this post in threaded view
|

Re: Re: Go Haskell! -> array libraries

Roman Leshchinskiy
In reply to this post by Don Stewart-2
On 30/11/2008, at 11:36, Don Stewart wrote:

> Should mutable arrays have list-like APIs? All the usual operations,
> just in-place and destructive where appropriate?

I don't know. To be honest, I don't think that the term "mutable  
array" describes a single data structure. For instance, one of the  
central questions which unveils a whole bunch of design possibilities  
is: can mutable arrays be concatenated and how does that work if yes?

Roman


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

Re: Re: Go Haskell! -> array libraries

Claus Reinke
>> Should mutable arrays have list-like APIs? All the usual operations,
>> just in-place and destructive where appropriate?
>
> I don't know. To be honest, I don't think that the term "mutable  
> array" describes a single data structure. For instance, one of the  
> central questions which unveils a whole bunch of design possibilities  
> is: can mutable arrays be concatenated and how does that work if yes?

wrt the first part: within a pure functional language, mutable arrays
are something I (am forced to) choose when the implementation
is unable to see some essential optimization opportunities in the
way I am using immutable arrays; whenever I am forced to go
down that route, I'd at least like to have an equivalent set of
operations. The move from immutable arrays to mutable arrays
is painful enough as it is. So the suggested design criterion would
be: as uniform an API as possible, just that immutable arrays
cannot make some essential performance guarantees and some
operations sit a little uncomfortably in a librart where those
guarantees are important.

wrt the second part: I'm not sure whether you'll be able to choose
a single one of those design possibilities as the only one (perhaps
the concatenation is about simpler code, so virtual concatenation
would be sufficient and copying possible, but perhaps the goal
was locality, so copying would be needed, or perhaps a mixture
of both, and the limited disruption in locality is less expensive than
the cost of copying, ..), so you might want to expose several of
them, with a separate way of selecting a default or I-don't-care
choice (imilar to why you have several array libs at present,
just that there should be a common API and documentation of
design alternatives/rationales;-).

--

Btw, it would really be nice if packages took a hint from academic
publishing: good papers are expected not only (a) to provide new
content, but also (b) to position that content wrt related work
and (c) to make explicit what the new contributions/goals are.

As forks have become more common on hackage, perhaps
.cabal files could be extended with two fields, pointing to related
packages (this is more specific than category, linking to packages
that might be used instead or in combination with the current
package) and giving the rationale/high-lights for the package in
text form.

In the meantime, it would be great if all packages came with good
old README files, which should be linked from the .cabal-based
package descriptions on hackage, covering all those useful bits of
information that are not yet covered in .cabal files, and giving an
overview of what the package is about if the package does not
have its own webspace (as is often the case). That would improve
on the current situation, where sometimes all one has to go on is
the package name and a one-liner description.

Random example: looking at hackage package categories, I'd
look for array libraries under 'data structures', but they are
actually spread over 'data structures', 'data', and 'maths' (perhaps
others?). Once I've found one, say 'vector' or 'uvector', what
do the package descriptions tell me about the packages and
their relation, or their relative advantages?

The descriptions are brief, the "home pages" are actually "home
repositories", the haddocks seem to have details only, no overview,
and from the references/authors/uvector README, one might
think these are actually the same library, sequential libs spun
off from the same data-parallelism project; only that the
haddock details suggest that these libraries are quite different.
How? Why? What other alternatives are there?

Note that I'm not attacking any specific packages, I would
just encourage all package authors to try and see their packages
from the perspective of a hackage user: what information does
the user look for, what information does the package description
offer?

--

While we're on the topic: hackage has grown so much and so
rapidly, that it might be worthwhile to have a hackage "editor",
not in the sense of accepting/rejecting packages (not wanted
at present), nor in the sense of objective quality measurements
(that is in the process of being automated, according to Duncan),
but in the sense of trying to guarantee a subjectively useful overall
presentation (category organisation, finding and putting side-by-side
related packages despite different names/categories, suitability of
package descriptions, getting package authors to talk, etc.).

And no, I'm not volunteering!-) But I would imagine that someone
might find this a useful way of contributing. Such a hackage editor
would also be able to give the Haskell Community Report editor
a hand by summarizing hackage activity/trends and highlighting
interesting projects that the HCAR editor might want to solicit
reports for. From my own time as HCAR editor, I recall finding
and chasing interesting projects as well as deciding how to
structure the tools&libraries sections as difficult parts of the job.

To take another hint from paper publishing: once the volume
and variety of publications passes certain thresholds, survey
papers become very valuable contributions. We do have time
based surveys (biannual, weekly, even daily, if you count
unedited RSS feeds;-), but topical surveys would help a lot
as well (what are all the options, relative advantages and status
of hackage packages for arrays, or databases, or web
programming, or..).

Such mini-surveys could appear in the Monad.Reader wiki
magazine, for instance, and be written by anyone looking for
that information the first time ("my experiences in looking for
database libraries", etc.), then updated on the wiki as the
package authors respond and improve the experience.

Obviously, I can't speak for the current hackage maintainers
or HCAR and Monad.Reader editors, but I assume they are
busy enough that they might welcome this kind of help.

Claus


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

Re: Re: Go Haskell! -> array libraries

Dan Doel
In reply to this post by Roman Leshchinskiy
On Sunday 30 November 2008 6:28:29 am Roman Leshchinskiy wrote:
> On 30/11/2008, at 11:36, Don Stewart wrote:
> > Should mutable arrays have list-like APIs? All the usual operations,
> > just in-place and destructive where appropriate?
>
> I don't know. To be honest, I don't think that the term "mutable
> array" describes a single data structure. For instance, one of the
> central questions which unveils a whole bunch of design possibilities
> is: can mutable arrays be concatenated and how does that work if yes?

I don't know about concatenation, but it is useful for them to be able to be
zipped. For instance:

  schwartz f arr = do keys <- cloneWith f arr
                      pairs <- zip keys arr
                      sortBy (comparing fst) pairs

(cloneWith should construct a new array where new[i] = f (old[i])) is a
mutable sort of arr using the comparison

  compare e e' = compare (f e) (f e')

caching the results of f for each element. This, obviously, takes advantage
of the fact that sorting the zipped array mutably updates the underlying
(original) arrays.

On the other hand, I could see such an operation easily leading to bugs if it
slips your mind that changing one array can effect another (maybe it should
be called unsafeZip :)).

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

Re: Go Haskell!

Simon Marlow-7
In reply to this post by Simon Marlow-7
I finally got around to making my code for random Go playouts available.
Here it is:

   http://www.haskell.org/~simonmar/goboard.tar.gz

If someone were to make a nice library API on top of this and upload it to
hackage, I'd be delighted.  Hack away.

Cheers,
        Simon

Simon Marlow wrote:

> Claus Reinke wrote:
>>> Do you have an example of a mutable state/ IO bound application, like,
>>> hmm, a window manager or a revision control system or a file system...?
>>
>> If you're looking for a challenge, how about this one (there used to
>> be lots of Haskellers into this game, any of you still around?-):
>>
>> http://computer-go.org/pipermail/computer-go/2008-October/016680.html
>
> [ catching up with old haskell-cafe email ]
>
> Interestingly, I did this a while ago.  Here's my results:
>
> $ ./Bench 1 100000
> b: 14840, w: 17143 mercy: 67982
> elapsed time: 3.42s
> playouts/sec: 29208
>
>
> so, nearly 30k/sec random playouts on 9x9.  That's using a hack that
> stops the game when the score is heavily in favour of one player, it
> drops to around 20k/sec with that turned off.
>
> Not bad, but probably I'd guess an order of magnitude worse than you can
> do in tightly-coded C.  The Haskell implementation isn't nice, as you
> predicted.  Also the code is derived from some non-free internal MS
> code, so unfortunately I can't share it (but I could perhaps extract the
> free bits if anyone is really interested).
>
> W wins slightly more often I think because komi 5.5 on a 9x9 board is a
> tad high.
>
> It does parallelise too, of course:
>
> $ ./Bench 8 100000 +RTS -N8
> b: 14872, w: 17488 mercy: 67584
> elapsed time: 1.00s
> playouts/sec: 99908
>
> though still room for improvement there.
>
> Cheers,
>     Simon

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

Re: Go Haskell!

Claus Reinke
>I finally got around to making my code for random Go playouts available.
> Here it is:
>
>   http://www.haskell.org/~simonmar/goboard.tar.gz

Cool!-) To reciprocate, I've temporarily put a snapshot of my code here:
http://www.cs.kent.ac.uk/~cr3/tmp/SimpleGo.hs

I've not yet decided whether to be depressed or encouraged by the
timings;-) without mercy rule, your code simulates at about 17k/s runs
here, vs only about 3k/s for mine. There are some obvious aspects, such
as hardcoding the boardsize isn't quite as straightforward when GTP
allows to change it at runtime, but I don't think that explains the bulk
of the difference. I do hope there are lots of small things to learn (perhaps
you could summarize your findings in a performance tips paper?-), but
at first glance, I suspect the difference in approach: my early experiments
suggested that maintaining chains/strings wasn't going to be more efficient
than following the affected parts of strings when needed - but I didn't
think of representing strings as cyclicly referenced lists (which allows
for string merge in constant instead of linear time). Nice idea!-)

Thanks,
Claus

>
> If someone were to make a nice library API on top of this and upload it to
> hackage, I'd be delighted.  Hack away.

A GTP interface would be useful, to allow playing against other bots.
 

> Cheers,
> Simon
>
> Simon Marlow wrote:
>> Claus Reinke wrote:
>>>> Do you have an example of a mutable state/ IO bound application, like,
>>>> hmm, a window manager or a revision control system or a file system...?
>>>
>>> If you're looking for a challenge, how about this one (there used to
>>> be lots of Haskellers into this game, any of you still around?-):
>>>
>>> http://computer-go.org/pipermail/computer-go/2008-October/016680.html
>>
>> [ catching up with old haskell-cafe email ]
>>
>> Interestingly, I did this a while ago.  Here's my results:
>>
>> $ ./Bench 1 100000
>> b: 14840, w: 17143 mercy: 67982
>> elapsed time: 3.42s
>> playouts/sec: 29208
>>
>>
>> so, nearly 30k/sec random playouts on 9x9.  That's using a hack that
>> stops the game when the score is heavily in favour of one player, it
>> drops to around 20k/sec with that turned off.
>>
>> Not bad, but probably I'd guess an order of magnitude worse than you can
>> do in tightly-coded C.  The Haskell implementation isn't nice, as you
>> predicted.  Also the code is derived from some non-free internal MS
>> code, so unfortunately I can't share it (but I could perhaps extract the
>> free bits if anyone is really interested).
>>
>> W wins slightly more often I think because komi 5.5 on a 9x9 board is a
>> tad high.
>>
>> It does parallelise too, of course:
>>
>> $ ./Bench 8 100000 +RTS -N8
>> b: 14872, w: 17488 mercy: 67584
>> elapsed time: 1.00s
>> playouts/sec: 99908
>>
>> though still room for improvement there.
>>
>> Cheers,
>>     Simon
>
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Go Haskell!

Simon Marlow-7
Claus Reinke wrote:

>> I finally got around to making my code for random Go playouts
>> available. Here it is:
>>
>>   http://www.haskell.org/~simonmar/goboard.tar.gz
>
> Cool!-) To reciprocate, I've temporarily put a snapshot of my code here:
> http://www.cs.kent.ac.uk/~cr3/tmp/SimpleGo.hs
>
> I've not yet decided whether to be depressed or encouraged by the
> timings;-) without mercy rule, your code simulates at about 17k/s runs
> here, vs only about 3k/s for mine. There are some obvious aspects, such
> as hardcoding the boardsize isn't quite as straightforward when GTP
> allows to change it at runtime, but I don't think that explains the bulk
> of the difference.

Different board sizes would be best done by just compiling the code
multiple times, for 9, 13 and 19.

> I do hope there are lots of small things to learn
> (perhaps
> you could summarize your findings in a performance tips paper?-)

Partly it's making good representation choices: lots of unboxed mutable
arrays, and the IntRef type.  I happen to know that boxed mutable arrays
expose poor behaviour in GHC's garbage collector :-)

If I could unpack MutableByteArray# directly in an enclosing constructor,
that would make this code a lot faster, by removing more indirections.
Duncan Coutts has been thinking about similar things in the context of
bytestring.

Most of the other things I found were really just bugs in GHC.  For
example, I wanted to use newtypes in various places, but I didn't get as
good code as just using a type synonym.  We had problems with record
selectors not optimising well, which is now fixed (I believe).

> but
> at first glance, I suspect the difference in approach: my early experiments
> suggested that maintaining chains/strings wasn't going to be more efficient
> than following the affected parts of strings when needed - but I didn't
> think of representing strings as cyclicly referenced lists (which allows
> for string merge in constant instead of linear time). Nice idea!-)

It wasn't my idea - I don't know where it originally came from, but it was
in the F# code I translated.  String merge isn't really O(1), since you
have to traverse one of the strings to update its string Id, maybe that
would be better done by having another level of indirection.

Cheers,
        Simon

> Thanks,
> Claus
>
>>
>> If someone were to make a nice library API on top of this and upload
>> it to hackage, I'd be delighted.  Hack away.
>
> A GTP interface would be useful, to allow playing against other bots.
>
>> Cheers,
>> Simon
>>
>> Simon Marlow wrote:
>>> Claus Reinke wrote:
>>>>> Do you have an example of a mutable state/ IO bound application, like,
>>>>> hmm, a window manager or a revision control system or a file
>>>>> system...?
>>>>
>>>> If you're looking for a challenge, how about this one (there used to
>>>> be lots of Haskellers into this game, any of you still around?-):
>>>>
>>>> http://computer-go.org/pipermail/computer-go/2008-October/016680.html
>>>
>>> [ catching up with old haskell-cafe email ]
>>>
>>> Interestingly, I did this a while ago.  Here's my results:
>>>
>>> $ ./Bench 1 100000
>>> b: 14840, w: 17143 mercy: 67982
>>> elapsed time: 3.42s
>>> playouts/sec: 29208
>>>
>>>
>>> so, nearly 30k/sec random playouts on 9x9.  That's using a hack that
>>> stops the game when the score is heavily in favour of one player, it
>>> drops to around 20k/sec with that turned off.
>>>
>>> Not bad, but probably I'd guess an order of magnitude worse than you
>>> can do in tightly-coded C.  The Haskell implementation isn't nice, as
>>> you predicted.  Also the code is derived from some non-free internal
>>> MS code, so unfortunately I can't share it (but I could perhaps
>>> extract the free bits if anyone is really interested).
>>>
>>> W wins slightly more often I think because komi 5.5 on a 9x9 board is
>>> a tad high.
>>>
>>> It does parallelise too, of course:
>>>
>>> $ ./Bench 8 100000 +RTS -N8
>>> b: 14872, w: 17488 mercy: 67584
>>> elapsed time: 1.00s
>>> playouts/sec: 99908
>>>
>>> though still room for improvement there.
>>>
>>> Cheers,
>>>     Simon
>>

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