Re: [Haskell-cafe] stream interface vs string interface: references
On 3/09/2013, at 5:17 PM, damodar kulkarni wrote:
I didn't want to clutter that thread so I am asking a question here.
Where do I find foundational and/or other good references on the topic of
stream interface vs string interface to convert objects to text? I tried
google but failed.
It has to do with the cost of string concatenation.
Let's take a simple thing.
A Set of Strings.
Smalltalk has
String
printOn: aStream
aStream nextPut: $'.
self do: [:each |
each = $' ifTrue: [aStream nextPut: $'].
aStream nextPut: each].
aStream nextPut: $'.
(Smalltalk uses '' for strings with quote doubling for embedded
quotes and has no character escapes. s nextPut: c writes character
c to stream s. do: [:...] is a loop.)
Set
printOn: aStream
|started|
started := false.
aStream nextPutAll: 'a Set ('.
self do: [:each |
started ifTrue: [aStream space] ifFalse: [started := true].
each printOn: aStream].
aStream nextPut: $'.
Object
printString
|stream|
stream := WriteStream on: (String new: 40).
self printOn: stream.
^stream contents
(A WriteStream is an internal stream. It starts with the
array-like object you give it and grows it, typically by
doubling, as needed. `contents' returns the part actually
written to.)
Let's actually do something subtly different.
Each Set will contain the printString of a number
and also another set, so
a Set('3' a Set('2' a Set('1' a Set(
s := Set new.
1 to: 1000*1000 do: [:i |
s := Set with: s with: i printString].
s printOn: Transcript.
The set having been created, how much allocation is done
by the output phase? *NONE*. And the time is *LINEAR*
in the size of the output.
To summarise: Smalltalk makes append print version to output stream
the basic form and obtain print version as a string a derived form.
The result is that printing (acyclic) objects of any size takes time
linear in the size of the output.
Now consider the Java version.
Java makes obtain print version as a string the basic form and
append print version to output stream a derived form.
There's a nasty little wrinkle which is that foo.toString() is
foo instead of the expected \foo\ in Java. So the output
will be [3, [2, [1, []]] or something like that.
String {
String toString() {
return this;
}
}
HashSet {
String toString() {
StringBuilder b = new StringBuilder();
boolean started = false;
b.append([);
for (Object o: this) {
if (started) b.append(, ); else started = true;
b.append(o.toString());
}
b.append(]);
return b.toString();
}
}
This takes *QUADRATIC* time, but it's annoyingly hard to demonstrate
because it keeps crashing with a stack overflow for even quite small n.
Thankfully, the -Xss option comes to the rescue.
ntime (seconds)
1000.16
2000.18
5000.22
10000.30
20000.62
50002.58
1 12.08
2 51.54
Not only does it take an obscene amount of time to print a large
object, it turns over a totally unwarranted amount of space.
Now you might object that sets like this are not realistic.
If you are trying to write large circuits or abstract syntax
trees or the like to a file, or using this *style* even if
not this specific *interface* to write XML documents, the
example errs by being unrealistically *easy* for Java.
It's easy to understand what's going wrong.
Consider [2, [1, []]]
When visiting {}, we create []. So far so good.
When visiting {1, {}}, we *copy* the [] into [1, []].
When visiting {2, {1, {}}}, we *copy* the [1, []] into
[2, [1, []]].
And so it goes. This does an awful lot of copying and
*none* of it is needed given a sane interface.
What is the take of Haskell on this?
There is a *reason* 'shows' exists.
newtype Date = Date (Int,Int,Int)
instance Show Date
where showsPrec _ (Date (y,m,d)) rest =
Date ( ++ shows y (, ++ shows m (, ++ shows d () ++ rest)))
The only uses of ++ here are where the left operand is a short literal.
Using this approach, Haskell programs can produce strings in linear time
and linear space.
For lazy I/O, using shows in Haskell is a good analogue of using
#printOn: in Smalltalk. The basic form is include this as PART of
a stream, with convert this to a whole string as a derived form.
What the equivalent of this would be for Iteratees I don't yet
understand.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] stream interface vs string interface: references
Thank you very much for the detailed explanation. It surely was an
enlightenment for me. Especially the comments
Java makes obtain print version as a string the basic form and append
print version to output stream a derived form.
Smalltalk makes append print version to output stream
the basic form and obtain print version as a string a derived form.
I wonder, this seems a good example of how such a seemingly 'small' design
decision can mean so much in terms of performance difference.
Surely, in Java I will have to take a detour to get around this handicap by
implementing something 'shows' on my own or may be use an equivalent
function from some library BUT in any case I will have to be aware of this.
Please give me a more general principle that can be learnt from this design
lesson, which you might think of. It doesn't quite seem to be the 'kiss'
principle i.e. keep it simple stupid.
What is really behind the Smalltalk's decision?
Thanks and regards,
-Damodar Kulkarni
On Tue, Sep 3, 2013 at 12:06 PM, Richard A. O'Keefe o...@cs.otago.ac.nzwrote:
On 3/09/2013, at 5:17 PM, damodar kulkarni wrote:
I didn't want to clutter that thread so I am asking a question here.
Where do I find foundational and/or other good references on the topic
of stream interface vs string interface to convert objects to text? I
tried google but failed.
It has to do with the cost of string concatenation.
Let's take a simple thing.
A Set of Strings.
Smalltalk has
String
printOn: aStream
aStream nextPut: $'.
self do: [:each |
each = $' ifTrue: [aStream nextPut: $'].
aStream nextPut: each].
aStream nextPut: $'.
(Smalltalk uses '' for strings with quote doubling for embedded
quotes and has no character escapes. s nextPut: c writes character
c to stream s. do: [:...] is a loop.)
Set
printOn: aStream
|started|
started := false.
aStream nextPutAll: 'a Set ('.
self do: [:each |
started ifTrue: [aStream space] ifFalse: [started := true].
each printOn: aStream].
aStream nextPut: $'.
Object
printString
|stream|
stream := WriteStream on: (String new: 40).
self printOn: stream.
^stream contents
(A WriteStream is an internal stream. It starts with the
array-like object you give it and grows it, typically by
doubling, as needed. `contents' returns the part actually
written to.)
Let's actually do something subtly different.
Each Set will contain the printString of a number
and also another set, so
a Set('3' a Set('2' a Set('1' a Set(
s := Set new.
1 to: 1000*1000 do: [:i |
s := Set with: s with: i printString].
s printOn: Transcript.
The set having been created, how much allocation is done
by the output phase? *NONE*. And the time is *LINEAR*
in the size of the output.
To summarise: Smalltalk makes append print version to output stream
the basic form and obtain print version as a string a derived form.
The result is that printing (acyclic) objects of any size takes time
linear in the size of the output.
Now consider the Java version.
Java makes obtain print version as a string the basic form and
append print version to output stream a derived form.
There's a nasty little wrinkle which is that foo.toString() is
foo instead of the expected \foo\ in Java. So the output
will be [3, [2, [1, []]] or something like that.
String {
String toString() {
return this;
}
}
HashSet {
String toString() {
StringBuilder b = new StringBuilder();
boolean started = false;
b.append([);
for (Object o: this) {
if (started) b.append(, ); else started = true;
b.append(o.toString());
}
b.append(]);
return b.toString();
}
}
This takes *QUADRATIC* time, but it's annoyingly hard to demonstrate
because it keeps crashing with a stack overflow for even quite small n.
Thankfully, the -Xss option comes to the rescue.
ntime (seconds)
1000.16
2000.18
5000.22
10000.30
20000.62
50002.58
1 12.08
2 51.54
Not only does it take an obscene amount of time to print a large
object, it turns over a totally unwarranted amount of space.
Now you might object that sets like this are not realistic.
If you are trying to write large circuits or abstract syntax
trees or the like to a file, or using this *style* even if
not this specific *interface* to write XML documents, the
example errs by being unrealistically *easy* for Java.
It's easy to understand what's going wrong.
Consider [2, [1, []]]
When visiting {}, we create []. So far so good.
When visiting {1, {}}, we *copy* the
Re: [Haskell-cafe] stream interface vs string interface: references
For lazy I/O, using shows in Haskell is a good analogue of using
#printOn: in Smalltalk. The basic form is include this as PART of
a stream, with convert this to a whole string as a derived form.
What the equivalent of this would be for Iteratees I don't yet
understand.
Why not to try simple generators first, which are simpler, truly. It seems
generators reproduce the Smalltalk printing patterns pretty well --
even simpler since we don't have to specify any stream. The printing
takes linear time in input size. The same `printing' generator can be
used even if we don't actually want to see any output -- rather, we
only want the statistics (e.g., number of characters printed, or
number of lines, etc). Likewise, the same printing generator
print_yield can be used if we are to encode the output somehow (e.g.,
compress it). The entire pipeline can run in constant space (if
encoding is in constant space).
Here is the code
module PrintYield where
-- http://okmij.org/ftp/continuations/PPYield/
import GenT
import Data.Set as S
import Data.Foldable
import Control.Monad.State.Strict
type Producer m e= GenT e m ()
class PrintYield a where
print_yield :: Monad m = a - Producer m String
instance PrintYield Int where
print_yield = yield . show
instance (PrintYield a, PrintYield b) = PrintYield (Either a b) where
print_yield (Left x) = yield Leftprint_yield x
print_yield (Right x) = yield Right print_yield x
instance (PrintYield a) = PrintYield (Set a) where
print_yield x = do
yield {
let f True x = print_yield x return False
f False x = yield , print_yield x return False
foldlM f True x
yield }
instance PrintYield ISet where
print_yield (ISet x) = print_yield x
newtype ISet = ISet (Either Int (Set ISet))
deriving (Eq, Ord)
set1 :: Set ISet
set1 = Prelude.foldr
(\e s - S.fromList [ISet (Left e), ISet (Right s)]) S.empty [1..20]
-- Real printing
print_set :: Set ISet - IO ()
print_set s = print_yield s `runGenT` putStr
t1 = print_set set1
-- Counting the number of characters
-- Could use Writer but the Writer is too lazy, may leak memory
count_printed :: Set ISet - Integer
count_printed s = (print_yield s `runGenT` counter) `execState` 0
where
counter _ = get = put . succ_strict
succ_strict x = x `seq` succ x
-- According to GHCi statistics, counting is linear in time
-- (space is harder to estimate: it is not clear what GHCi prints
-- for memory statistics; we need max bytes allocated rather than
-- total bytes allocated)
t2 = count_printed set1
-- Doesn't do anything but ensures the set is constructed
t3 :: IO ()
t3 = print_yield set1 `runGenT` (\x - return ())
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Fwd: MVar problem in acid-state?
It's conceivable. It might help if you list what version of acid-stateyou're using and what parts of it. And maybe file a bug https://github.com/acid-state/acid-state/issues upstream even if you're not sure it is acid-state. On Mon, Sep 2, 2013 at 7:35 PM, Corentin Dupont corentin.dup...@gmail.comwrote: Hi the list, I have compiled my application on my PC, it works fine, but when I copy it on my server (same architecture), I get: Nomyx: thread blocked indefinitely in an MVar operation I don't use MVars in my application, is it possible that it's coming from acid-state? Thanks, Corentin ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Fwd: Can I use String without in ghci?
On Mon, Sep 2, 2013 at 10:43 AM, Richard A. O'Keefe o...@cs.otago.ac.nzwrote: On 2/09/2013, at 3:55 PM, Rustom Mody wrote: On Mon, Sep 2, 2013 at 5:43 AM, Richard A. O'Keefe wrote: A slogan I have programmed by since I first met C and recognised how vastly superior to PL/I it was for text manipulation _because_ it didn't have a proper string type is Strings are Wrong!. C rode to fame on the back of Unix. And Unix's innovation – one of many – is that at the OS level the string type was made common fare – a universal type. So everything from file names to file contents to IPC is a string. The idea of file names being strings was no innovation. Yes, in crippled monstrosities like TOPS-10 file names were weird records -- I can still remember too much of the details -- and every ruddy TOPS-10 program had to do its own file name parsing and it seemed as if they all did it differently. But the B6700 MCP interfaces treated file names as strings before UNIX was dreamed of. File contents in UNIX are *not* strings and never have been -- NUL termination is no part of files and binary files have been commonplace since the beginning (an a.out file is not a string!). They are *byte arrays*. As for IPC, since when have System V shared memory, semaphores, or message queues had anything to do with strings? (Hint: the 'name' of a System V shared memory segment is a key_t, and that's an integral type, not a string. Hint: the 'name' of a System V semaphore is also a key_t integer, not a string. Hint: the 'name' of a System V message queue is also a key_t integer, not a string. Hint: messages sent using msgsnd are not strings, they are byte arrays with a separate count parameter. ) Whoops! my bad -- I was *thinking* 'pipes' but ended up *writing* 'IPC' :-) So let me restate more explicitly what I intended -- pipes, FIFOs, sockets, etc. IOW read/write/send/recv calls and the mathematical model represented by the (non-firstclass) pair of C data structures in those functions: buf, len (or count). As an aside: modern usage types the buf as void * . The version 7 unix manuals on which I grew up (and first edition of KR), there was no void; buf would be just 'char *buf; ' Classic UNIX uses strings for file names, and really, that's it. (The command line argv[] is not really an exception, because it was used for file names as well as options, and in fact mixing the two up caused endless problems.) Everything else in V7, S3, or SysV was identified by a *number*. Plan 9 has exit(string) but Unix has exit(byte). From the perspective of someone who used UNIX v6 in 1979, *POSIX* IPC -- with its IPC objects *might* be in the file system but then again might *not* be so their names are sorta-kinda-like file names but not really) -- and /proc are recent innovations. The idea that 'string' was even remotely like a universal type in UNIX is bizarre. Heck, UNIX never even used 'string' for *lines* in text files! Of course when instructing a beginning programmer your basic premise 'Strings are Wrong!' is most likely right. No, I'm talking about experienced programmers writing high performance programs. However if programs are seen as entities interacting with an 'external' world, the currency at the portals is invariably string. - The currency at the portals is *not* invariably string. Learn PowerShell. - Text is one thing and string is another. This was the B6700 lesson (well, really the B5500 lesson): for many purposes you want a text *stream* not a text *string* at the interface. It's also the what-Smalltalk-got-right-and-Java-got-wrong lesson: the right way to convert objects to text is via a *stream* interface, not a *string* interface. I realize this is a terminology issue: My usage of terminology like string/file are evidently more aligned to http://en.wikipedia.org/wiki/Vienna_Development_Method#Collections:_Sets.2C_Mappings_and_Sequences file(chap 4): http://red.cs.nott.ac.uk/~rxq/files/SpecificationCaseStudies.pdf Contrariwise 'file' can mean http://en.wikipedia.org/wiki/Data_set_%28IBM_mainframe%29 So coming back from terminology to principles... And more than just noob programmers have got this wrong – think of the precious one-byte opcodes that Intel wastes on ascii and decimal arithmetic. Hang on, they are there in order to *support* the numbers are text model. You can't have it both ways. So let me restate (actually I didn't state it earlier!) my point in this example: When Intel introduced these instructions in 8008 (or whatever) decades ago, it seemed like a good idea to help programmers and reduce their burden by allowing them to do some minimal arithmetic on data without burdensome conversion-to-binary functions. 4 decades on and (Intel's very own Gordon) Moore's law ensuring our machines and networks some 7 orders of magnitude larger, the cost-equations look different. printf and scanf are a
[Haskell-cafe] type constructor section for (- Bool), _not_ ((-) Bool)
I'm probably being dumb, but Hoogle nor the wiki are helping me. I want an instance and type improvement constraint of the form instance (f ~ (- Bool)) = C Foo (f b) where ... The first arg to C is driving type improvement, for example: instance (f ~ []) = C Bar (f b) where ... (The real instances are more complex, and involve overlap, of course.) I'm trying to write a section to get the improved type (b - Bool), but (- Bool) or ((- Bool) b) is invalid syntax. This is valid, but wrong: ((-) Bool) b -- gives (Bool - b). I could do: data FlipFun b -- abstract instance (f ~ FlipFun) = C Foo (f b) where ... And a type function inside the class to generate the type. But then I'd have to apply the type function for all instances, and in most places it'd be id. ?? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Fwd: MVar problem in acid-state?
OK, my mistake: it's working now. It was because I'm using an haskell interpreter in my program, and the version of GHC was different on my PC (where I compile) and on the server (where I run)... On Tue, Sep 3, 2013 at 11:13 AM, Dag Odenhall dag.odenh...@gmail.comwrote: It's conceivable. It might help if you list what version of acid-stateyou're using and what parts of it. And maybe file a bug https://github.com/acid-state/acid-state/issues upstream even if you're not sure it is acid-state. On Mon, Sep 2, 2013 at 7:35 PM, Corentin Dupont corentin.dup...@gmail.com wrote: Hi the list, I have compiled my application on my PC, it works fine, but when I copy it on my server (same architecture), I get: Nomyx: thread blocked indefinitely in an MVar operation I don't use MVars in my application, is it possible that it's coming from acid-state? Thanks, Corentin ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] On Markdown in Haddock and why it's not going to happen
On 30/08/13 10:30, Mateusz Kowalczyk wrote: I would also like to remind you that if there's something that you'd like to see in Haddock or something that you feel is broken, a good way express this is to make a ticket on the Haddock Trac[2]. I made one: http://trac.haskell.org/haddock/ticket/257 This is very useful for us because haddock is broken by some TH issue. This way, we can have most of our docs anyway. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] type constructor section for (- Bool), _not_ ((-) Bool)
On Tue, Sep 03, 2013 at 11:33:46AM +, AntC wrote: I'm probably being dumb, but Hoogle nor the wiki are helping me. I want an instance and type improvement constraint of the form instance (f ~ (- Bool)) = C Foo (f b) where ... The first arg to C is driving type improvement, for example: instance (f ~ []) = C Bar (f b) where ... (The real instances are more complex, and involve overlap, of course.) I'm trying to write a section to get the improved type (b - Bool), but (- Bool) or ((- Bool) b) is invalid syntax. There is no operator section syntax for types. Moreover, this is not just an issue of syntax: it is impossible to partially apply a type constructor to anything other than its first argument, because there is no type-level lambda. This is valid, but wrong: ((-) Bool) b -- gives (Bool - b). I could do: data FlipFun b -- abstract instance (f ~ FlipFun) = C Foo (f b) where ... And a type function inside the class to generate the type. But then I'd have to apply the type function for all instances, and in most places it'd be id. That's the only way to do it that I know of. -Brent ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] World's First Commercial Haskell IDE and Deployment Platform, FP Haskell Center Launches Today
This is interesting and I wish them luck, but it seems surprising that the below link doesn't have as much as a screenshot (for an IDE, you kind of expect to see what it looks like). After much browsing around on their website I finally found the Video Demo: https://www.fpcomplete.com/business/haskell-center/video-walk-through/ but the there's no video for me on Firefox (Mac OS X). In Safari shows, but when I try to play it, it reports An error occurred, please try again later. Tommy On Sep 3, 2013, at 11:16 , Natalia Muska nata...@fpcomplete.com wrote: FP Complete Has Officially Launched the World's First Commercial Haskell IDE! http://www.i-newswire.com/fp-complete-launches-fp-haskell/237230 We greatly appreciate the support we've received from the Haskell community. Natalia Muska Marketing Manager FP Complete, Inc. nata...@fpcomplete.com 865-506-6513 skype: natalia.s.muska -- Natalia Muska Marketing Manager FP Complete, Inc. nata...@fpcomplete.com 865-506-6513 skype: natalia.s.muska Official Launch PR.docx___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] World's First Commercial Haskell IDE and Deployment Platform, FP Haskell Center Launches Today
Confirm the issue. I have Firefox on Mac as well, and it does show for me, but says the same thing as Tommy's Safari On Sep 3, 2013, at 11:25 PM, Tommy Thorn tt1...@yahoo.com wrote: This is interesting and I wish them luck, but it seems surprising that the below link doesn't have as much as a screenshot (for an IDE, you kind of expect to see what it looks like). After much browsing around on their website I finally found the Video Demo: https://www.fpcomplete.com/business/haskell-center/video-walk-through/ but the there's no video for me on Firefox (Mac OS X). In Safari shows, but when I try to play it, it reports An error occurred, please try again later. Tommy On Sep 3, 2013, at 11:16 , Natalia Muska nata...@fpcomplete.com wrote: FP Complete Has Officially Launched the World's First Commercial Haskell IDE! http://www.i-newswire.com/fp-complete-launches-fp-haskell/237230 We greatly appreciate the support we've received from the Haskell community. Natalia Muska Marketing Manager FP Complete, Inc. nata...@fpcomplete.com 865-506-6513 skype: natalia.s.muska -- Natalia Muska Marketing Manager FP Complete, Inc. nata...@fpcomplete.com 865-506-6513 skype: natalia.s.muska Official Launch PR.docx___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] World's First Commercial Haskell IDE and Deployment Platform, FP Haskell Center Launches Today
OK, now video on http://www.i-newswire.com/fp-complete-launches-fp-haskell/237230 works. Seems like a youtube glitch On Sep 3, 2013, at 11:37 PM, MigMit miguelim...@yandex.ru wrote: Confirm the issue. I have Firefox on Mac as well, and it does show for me, but says the same thing as Tommy's Safari On Sep 3, 2013, at 11:25 PM, Tommy Thorn tt1...@yahoo.com wrote: This is interesting and I wish them luck, but it seems surprising that the below link doesn't have as much as a screenshot (for an IDE, you kind of expect to see what it looks like). After much browsing around on their website I finally found the Video Demo: https://www.fpcomplete.com/business/haskell-center/video-walk-through/ but the there's no video for me on Firefox (Mac OS X). In Safari shows, but when I try to play it, it reports An error occurred, please try again later. Tommy On Sep 3, 2013, at 11:16 , Natalia Muska nata...@fpcomplete.com wrote: FP Complete Has Officially Launched the World's First Commercial Haskell IDE! http://www.i-newswire.com/fp-complete-launches-fp-haskell/237230 We greatly appreciate the support we've received from the Haskell community. Natalia Muska Marketing Manager FP Complete, Inc. nata...@fpcomplete.com 865-506-6513 skype: natalia.s.muska -- Natalia Muska Marketing Manager FP Complete, Inc. nata...@fpcomplete.com 865-506-6513 skype: natalia.s.muska Official Launch PR.docx___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Reasoning about performance
I'm a Haskell beginner, and I'm baffled trying to reason about code
performance, at least with GHC. For a program I'm writing I needed to
find all pairs of elements of a list. That is, given the list ABCD
I wanted to wind up with the list
[('A','B'),('A','C'),('A','D'),('B','C'),('B','D'),('C','D')], where
the order of elements in the resulting list is immaterial, but I don't
want both ('A', 'B') and ('B', 'A'), for example.
My first attempt looked like this:
allPairs1 :: [a] - [(a, a)]
allPairs1 [] = []
allPairs1 (x:xs) = map (\a - (x, a)) xs ++ allPairs1 xs
Benchmarking with ghci's :set +s reveals the following performance
(median of three runs shown):
$ ghci
GHCi, version 7.6.3: http://www.haskell.org/ghc/ :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude :!ghc -c -O2 allpairs.hs
Prelude :load allpairs
Ok, modules loaded: AllPairs.
Prelude AllPairs :m +Control.DeepSeq
Prelude Control.DeepSeq AllPairs :show modules
AllPairs ( allpairs.hs, allpairs.o )
Prelude Control.DeepSeq AllPairs :set +s
Prelude Control.DeepSeq AllPairs deepseq (allPairs1 [1..1]) True
True
(4.85 secs, 4004173984 bytes)
A colleague suggested getting rid of the list append as follows:
allPairs2 :: [a] - [(a, a)]
allPairs2 [] = []
allPairs2 (x:xs) = allPairs2' x xs xs
where allPairs2' x [] [] = []
allPairs2' x (y:ys) zs = (x,y) : allPairs2' x ys zs
allPairs2' x [] (z:zs) = allPairs2' z zs zs
Not surprisingly, that runs faster:
Prelude Control.DeepSeq AllPairs deepseq (allPairs2 [1..1]) True
True
(2.14 secs, 4403686376 bytes)
I then figured I could do even better by rewriting the code
tail-recursively:
allPairs3 :: [a] - [(a, a)]
allPairs3 [] = []
allPairs3 (x:xs) = allPairs3' x xs xs []
where allPairs3' :: a - [a] - [a] - [(a, a)] - [(a, a)]
allPairs3' h (x:xs) ys result = allPairs3' h xs ys ((h,
x):result)
allPairs3' _ [] (y:ys) result = allPairs3' y ys ys result
allPairs3' _ [] [] result = result
This takes half the memory as the above (yay!) but runs substantially
*slower* (and appears to be thrashing my computer's memory system):
Prelude Control.DeepSeq AllPairs deepseq (allPairs3 [1..1]) True
True
(10.58 secs, 2403820152 bytes)
What gives? Why does my tail-recursive implementation run even slower
and presumably produce more garbage than my initial, naive
implementation? Is there some optimization GHC is performing for
allPairs1 and allPairs2 that it can't apply to allPairs3?
Similarly, how should I, as a newcomer who wants to write efficient
Haskell code, reason about whether a code change is likely to improve
rather than degrade performance? Guidelines like per-iteration
appends = bad and tail recursion = good are great, but the
preceding data indicate that something subtler is taking precedence
over those guidelines with respect to code performance.
Thanks in advance,
-- Scott
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Unexpected behaviour with send and send-buffer setting
On Tue, Sep 3, 2013 at 6:56 PM, Simon Yarde simonya...@me.com wrote: I've found that setting the send buffer size causes send to truncate the ByteString to the buffer size, but that successive sends continue to succeed when the buffer should be full. I see no actual flow control here. That the receiver is blocked does not mean the receiver's *kernel* has not received the packets and buffered them. Also note that send is not synchronous; it cannot know that the receiver has hit its buffer limit --- and the kernel may well have already sent the previous packet, so the send buffer is in fact empty at that point, with the pending packet either in flight or in the receiving kernel's (interrupt time or normal; they are usually distinct. Or, with a sufficiently fancy network card, its own) network buffers. In short, you have not thought through all the possible ramifications, nor considered that the kernel handles packets and buffering independently of your program, nor considered the effects of the non-instantaneous network between sender and receiver. It may or not behave differently when sender and receiver are on the same machine. Do not assume that the kernel will short-circuit here and leave out all the intermediate buffering! The only part you're guaranteed to avoid is the interface with the network hardware. The crux of my line of enquiry is this; how can my application know when to pause in generating its chunked output if send doesn't block and the current non-blocking send behaviour apparently succeeds when the send buffer should be full? I would suggest reading a book on TCP/IP networking. -- brandon s allbery kf8nh sine nomine associates allber...@gmail.com ballb...@sinenomine.net unix, openafs, kerberos, infrastructure, xmonadhttp://sinenomine.net ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] World's First Commercial Haskell IDE and Deployment Platform, FP Haskell Center Launches Today
On Tue, Sep 3, 2013 at 2:25 PM, Tommy Thorn tt1...@yahoo.com wrote: This is interesting and I wish them luck, but it seems surprising that the below link doesn't have as much as a screenshot (for an IDE, you kind of expect to see what it looks like). If you follow the link that says Product Highlights, you get to https://www.fpcomplete.com/business/haskell-center/fp-haskell-center-highlights/ , which includes links to a PDF for each highlight, which have a number of screenshots.They tend to be covered by explanatory text, or only partial shots of the window, etc. The other option is to use the Free Trial link and just see it live. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] World's First Commercial Haskell IDE and Deployment Platform, FP Haskell Center Launches Today
You can always try the attached docx! :) On Tue, Sep 3, 2013 at 9:25 PM, Tommy Thorn tt1...@yahoo.com wrote: This is interesting and I wish them luck, but it seems surprising that the below link doesn't have as much as a screenshot (for an IDE, you kind of expect to see what it looks like). After much browsing around on their website I finally found the Video Demo: https://www.fpcomplete.com/business/haskell-center/video-walk-through/ but the there's no video for me on Firefox (Mac OS X). In Safari shows, but when I try to play it, it reports An error occurred, please try again later. Tommy On Sep 3, 2013, at 11:16 , Natalia Muska nata...@fpcomplete.com wrote: FP Complete Has Officially Launched the World's First Commercial Haskell IDE! http://www.i-newswire.com/fp-complete-launches-fp-haskell/237230 We greatly appreciate the support we've received from the Haskell community. Natalia Muska Marketing Manager FP Complete, Inc. nata...@fpcomplete.com 865-506-6513 skype: natalia.s.muska -- Natalia Muska Marketing Manager FP Complete, Inc. nata...@fpcomplete.com 865-506-6513 skype: natalia.s.muska Official Launch PR.docx___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Unexpected behaviour with send and send-buffer setting
I'm new to Haskell and have reached an impasse in understanding the behaviour of sockets. I see that under the hood Network.Socket sockets are set to non-blocking. Presumably, when a non-blocking socket's buffer is full it should immediately return 0 bytes. I've found that setting the send buffer size causes send to truncate the ByteString to the buffer size, but that successive sends continue to succeed when the buffer should be full. In the server code I set the send buffer to 1, then attempted to overflow it: handleConnection conn = do setSocketOption conn SendBuffer 1 s1 - send conn abc putStrLn $ Bytes sent: ++ show s1 s2 - send conn def putStrLn $ Bytes sent: ++ show s2 s3 - send conn ghi putStrLn $ Bytes sent: ++ show s3 close conn And in the client I delay the recv by 1 second: setSocketOption sk RecvBuffer 1 threadDelay (1 * 10^6) b1 - recv sk 1 B8.putStrLn b1 b2 - recv sk 1 B8.putStrLn b2 b3 - recv sk 1 B8.putStrLn b3 The server immediately outputs: Bytes sent: 1 Bytes sent: 1 Bytes sent: 1 The client waits a for second and then outputs: a d g What's going on? I expected the second and third send operation to return 0 bytes sent, because the send buffer can only hold 1 byte. The crux of my line of enquiry is this; how can my application know when to pause in generating its chunked output if send doesn't block and the current non-blocking send behaviour apparently succeeds when the send buffer should be full? More generally, isn't polling sockets using system calls to be avoided in favour of blocking and lightweight haskell threads? Hope someone can help clear up the confusion. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] World's First Commercial Haskell IDE and Deployment Platform, FP Haskell Center Launches Today
On Tue, Sep 3, 2013 at 3:35 PM, Mathijs Kwik math...@bluescreen303.nlwrote: You can always try the attached docx! :) Which likewise showed nothing. -- brandon s allbery kf8nh sine nomine associates allber...@gmail.com ballb...@sinenomine.net unix, openafs, kerberos, infrastructure, xmonadhttp://sinenomine.net ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Reasoning about performance
Haskell's non-strict evaluation can often lead to unexpected results when
doing tail recursion if you're used to strict functional programming
languages. In order to get the desired behavior you will need to force the
accumulator (with something like Data.List's foldl', $!,
seq, BangPatterns, etc.).
One issue with the tail recursive version is that you're basically
sequencing it twice, forcing the result is going to force the whole spine
of the list, and then you're walking it again with deepseq. The overhead of
the deepseq call with that size list on my machine is 2.2 seconds, so
you're basically paying that cost twice with a tail recursive version.
allPairs2 only forces what is needed, so deepseq isn't traversing any data
structures that are already forced.
I think what's happening with allPairs2 is that GHC is throwing away the
the list during the traversal since the result of the computation isn't
used at all. I get very different timings (still fast, but no longer orders
of magnitude difference) for allPairs2 if the result is still around. You
could probably figure this out with the heap profiler.
h deepseq (allPairs2 [1..1]) True
True
(2.47 secs, 4403724176 bytes)
h let x = allPairs2 [1..1]
(0.00 secs, 510488 bytes)
h deepseq x True
True
(10.47 secs, 4401625192 bytes)
h deepseq x True
True
(2.21 secs, 1031864 bytes)
I'm no expert, but I think that allPairs2 is likely as good as you're going
to get with straightforward Haskell using lists. It doesn't build up a lot
of unevaluated computation, and if you only need to see the first n
elements it's not going to have to process the entire input. allPairs1 has
most of the good properties of allPairs2 but is a bit worse because of the
concatenation, though concatenating in this way isn't a disaster like it
would be in a strict functional programming language.
-bob
On Tue, Sep 3, 2013 at 3:28 PM, Scott Pakin pa...@lanl.gov wrote:
I'm a Haskell beginner, and I'm baffled trying to reason about code
performance, at least with GHC. For a program I'm writing I needed to
find all pairs of elements of a list. That is, given the list ABCD
I wanted to wind up with the list
[('A','B'),('A','C'),('A','D')**,('B','C'),('B','D'),('C','D')**], where
the order of elements in the resulting list is immaterial, but I don't
want both ('A', 'B') and ('B', 'A'), for example.
My first attempt looked like this:
allPairs1 :: [a] - [(a, a)]
allPairs1 [] = []
allPairs1 (x:xs) = map (\a - (x, a)) xs ++ allPairs1 xs
Benchmarking with ghci's :set +s reveals the following performance
(median of three runs shown):
$ ghci
GHCi, version 7.6.3: http://www.haskell.org/ghc/ :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude :!ghc -c -O2 allpairs.hs
Prelude :load allpairs
Ok, modules loaded: AllPairs.
Prelude AllPairs :m +Control.DeepSeq
Prelude Control.DeepSeq AllPairs :show modules
AllPairs ( allpairs.hs, allpairs.o )
Prelude Control.DeepSeq AllPairs :set +s
Prelude Control.DeepSeq AllPairs deepseq (allPairs1 [1..1]) True
True
(4.85 secs, 4004173984 bytes)
A colleague suggested getting rid of the list append as follows:
allPairs2 :: [a] - [(a, a)]
allPairs2 [] = []
allPairs2 (x:xs) = allPairs2' x xs xs
where allPairs2' x [] [] = []
allPairs2' x (y:ys) zs = (x,y) : allPairs2' x ys zs
allPairs2' x [] (z:zs) = allPairs2' z zs zs
Not surprisingly, that runs faster:
Prelude Control.DeepSeq AllPairs deepseq (allPairs2 [1..1]) True
True
(2.14 secs, 4403686376 bytes)
I then figured I could do even better by rewriting the code
tail-recursively:
allPairs3 :: [a] - [(a, a)]
allPairs3 [] = []
allPairs3 (x:xs) = allPairs3' x xs xs []
where allPairs3' :: a - [a] - [a] - [(a, a)] - [(a, a)]
allPairs3' h (x:xs) ys result = allPairs3' h xs ys ((h,
x):result)
allPairs3' _ [] (y:ys) result = allPairs3' y ys ys result
allPairs3' _ [] [] result = result
This takes half the memory as the above (yay!) but runs substantially
*slower* (and appears to be thrashing my computer's memory system):
Prelude Control.DeepSeq AllPairs deepseq (allPairs3 [1..1]) True
True
(10.58 secs, 2403820152 bytes)
What gives? Why does my tail-recursive implementation run even slower
and presumably produce more garbage than my initial, naive
implementation? Is there some optimization GHC is performing for
allPairs1 and allPairs2 that it can't apply to allPairs3?
Similarly, how should I, as a newcomer who wants to write efficient
Haskell code, reason about whether a code change is likely to improve
rather than degrade performance? Guidelines like per-iteration
appends = bad and tail recursion
Re: [Haskell-cafe] Unexpected behaviour with send and send-buffer setting
On Wed, Sep 4, 2013 at 12:56 AM, Simon Yarde simonya...@me.com wrote: What's going on? I expected the second and third send operation to return 0 bytes sent, because the send buffer can only hold 1 byte. If the underlying write operation returns EWOULDBLOCK then the send function calls into the GHC IO manager with threadWaitWrite, which registers interest in the file descriptor using epoll() and blocks the calling Haskell thread until the socket is writable. G -- Gregory Collins g...@gregorycollins.net ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Unexpected behaviour with send and send-buffer setting
On Tue, Sep 3, 2013 at 6:56 PM, Simon Yarde simonya...@me.com wrote: I'm new to Haskell and have reached an impasse in understanding the behaviour of sockets. The crux of my line of enquiry is this; how can my application know when to pause in generating its chunked output if send doesn't block and the current non-blocking send behaviour apparently succeeds when the send buffer should be full? 'send' will eventually block after enough 'send's without matching 'recv's. As Brandon explains, there is more buffering going on than the send buffer. In particular, the receiving host will accept segments until its buffer fills up. TCP implements flow control (i.e. keeps the sender from flooding the receiver) by having the receiver tell the sender how many more bytes it is currently willing to accept. This is done with the window size value in the TCP segment header [1]. [1]: http://en.wikipedia.org/wiki/Transmission_Control_Protocol#TCP_segment_structure ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Reasoning about performance
It's also worth adding that ghci does a lot less optimization than ghc.
Likewise, the best tool for doing performance benchmarking is the excellent
Criterion library.
To repeat: use compiled code for benchmarking, and use criterion. Ghci is
not as performance tuned as compiled code, except when ghci is linking in
code that's already been compiled
On Tuesday, September 3, 2013, Bob Ippolito wrote:
Haskell's non-strict evaluation can often lead to unexpected results when
doing tail recursion if you're used to strict functional programming
languages. In order to get the desired behavior you will need to force the
accumulator (with something like Data.List's foldl', $!,
seq, BangPatterns, etc.).
One issue with the tail recursive version is that you're basically
sequencing it twice, forcing the result is going to force the whole spine
of the list, and then you're walking it again with deepseq. The overhead of
the deepseq call with that size list on my machine is 2.2 seconds, so
you're basically paying that cost twice with a tail recursive version.
allPairs2 only forces what is needed, so deepseq isn't traversing any data
structures that are already forced.
I think what's happening with allPairs2 is that GHC is throwing away the
the list during the traversal since the result of the computation isn't
used at all. I get very different timings (still fast, but no longer orders
of magnitude difference) for allPairs2 if the result is still around. You
could probably figure this out with the heap profiler.
h deepseq (allPairs2 [1..1]) True
True
(2.47 secs, 4403724176 bytes)
h let x = allPairs2 [1..1]
(0.00 secs, 510488 bytes)
h deepseq x True
True
(10.47 secs, 4401625192 bytes)
h deepseq x True
True
(2.21 secs, 1031864 bytes)
I'm no expert, but I think that allPairs2 is likely as good as you're
going to get with straightforward Haskell using lists. It doesn't build up
a lot of unevaluated computation, and if you only need to see the first n
elements it's not going to have to process the entire input. allPairs1 has
most of the good properties of allPairs2 but is a bit worse because of the
concatenation, though concatenating in this way isn't a disaster like it
would be in a strict functional programming language.
-bob
On Tue, Sep 3, 2013 at 3:28 PM, Scott Pakin pa...@lanl.govjavascript:_e({},
'cvml', 'pa...@lanl.gov');
wrote:
I'm a Haskell beginner, and I'm baffled trying to reason about code
performance, at least with GHC. For a program I'm writing I needed to
find all pairs of elements of a list. That is, given the list ABCD
I wanted to wind up with the list
[('A','B'),('A','C'),('A','D')**,('B','C'),('B','D'),('C','D')**], where
the order of elements in the resulting list is immaterial, but I don't
want both ('A', 'B') and ('B', 'A'), for example.
My first attempt looked like this:
allPairs1 :: [a] - [(a, a)]
allPairs1 [] = []
allPairs1 (x:xs) = map (\a - (x, a)) xs ++ allPairs1 xs
Benchmarking with ghci's :set +s reveals the following performance
(median of three runs shown):
$ ghci
GHCi, version 7.6.3: http://www.haskell.org/ghc/ :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude :!ghc -c -O2 allpairs.hs
Prelude :load allpairs
Ok, modules loaded: AllPairs.
Prelude AllPairs :m +Control.DeepSeq
Prelude Control.DeepSeq AllPairs :show modules
AllPairs ( allpairs.hs, allpairs.o )
Prelude Control.DeepSeq AllPairs :set +s
Prelude Control.DeepSeq AllPairs deepseq (allPairs1 [1..1]) True
True
(4.85 secs, 4004173984 bytes)
A colleague suggested getting rid of the list append as follows:
allPairs2 :: [a] - [(a, a)]
allPairs2 [] = []
allPairs2 (x:xs) = allPairs2' x xs xs
where allPairs2' x [] [] = []
allPairs2' x (y:ys) zs = (x,y) : allPairs2' x ys zs
allPairs2' x [] (z:zs) = allPairs2' z zs zs
Not surprisingly, that runs faster:
Prelude Control.DeepSeq AllPairs deepseq (allPairs2 [1..1]) True
True
(2.14 secs, 4403686376 bytes)
I then figured I could do even better by rewriting the code
tail-recursively:
allPairs3 :: [a] - [(a, a)]
allPairs3 [] = []
allPairs3 (x:xs) = allPairs3' x xs xs []
where allPairs3' :: a - [a] - [a] - [(a, a)] - [(a, a)]
allPairs3' h (x:xs) ys result = allPairs3' h xs ys ((h,
x):result)
allPairs3' _ [] (y:ys) result = allPairs3' y ys ys result
allPairs3' _ [] [] result = result
This takes half the memory as the above (yay!) but runs substantially
*slower* (and appears to be thrashing my computer's memory system):
Prelude Control.DeepSeq AllPairs deepseq (allPairs3 [1..1]) True
True
(10.58 secs, 2403820152 bytes)
What
Re: [Haskell-cafe] Unexpected behaviour with send and send-buffer setting
On Tue, Sep 3, 2013 at 7:58 PM, Joey Adams joeyadams3.14...@gmail.comwrote: On Tue, Sep 3, 2013 at 6:56 PM, Simon Yarde simonya...@me.com wrote: I'm new to Haskell and have reached an impasse in understanding the behaviour of sockets. The crux of my line of enquiry is this; how can my application know when to pause in generating its chunked output if send doesn't block and the current non-blocking send behaviour apparently succeeds when the send buffer should be full? 'send' will eventually block after enough 'send's without matching 'recv's. As Brandon explains, there is more buffering going on than the send buffer. In particular, the receiving host will accept segments until its buffer fills up. TCP implements flow control (i.e. keeps the sender from flooding the receiver) by Also note that, if you're using TCP, Nagle's algorithm will be turned on unless you specifically turn it off; this is explicitly designed to avoid sending very short packets, by buffering them into larger packets in the kernel network stack up until some timeout or a minimum threshold size is reached. (Protocols such as ssh and telnet turn it off for interactivity.) And if you're using UDP, there's no flow control at all; while packets won't be aggregated á la Nagle, the network stacks on the sending and receiving ends can do pretty much whatever they want with the individual packets. And in either case the socket buffer size is only the last mile: there is no way to control what happens elsewhere, and in particular the interrupt-time received packet handling usually won't know even what socket is the target, much less what buffer size that socket has set. -- brandon s allbery kf8nh sine nomine associates allber...@gmail.com ballb...@sinenomine.net unix, openafs, kerberos, infrastructure, xmonadhttp://sinenomine.net ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Reasoning about performance
Well for one thing, note that allPairs3 produces the result in reverse
order:
allPairs1 abc
[('a','b'),('a','c'),('b','c')]
allPairs2 abc
[('a','b'),('a','c'),('b','c')]
allPairs3 abc
[('b','c'),('a','c'),('a','b')]
allPairs2 uses guarded recursion which the optimizer probably likes,
although I don't quite see why that version would use twice as much memory
as allPairs3.
See also:
http://www.haskell.org/haskellwiki/Tail_recursion
Here's a fun alternative for you to benchmark, using an old trick. I kind
of doubt that this one will optimize as nicely as the others, but I am by
no means an optimization guru:
allPairsS :: [a] - [(a, a)]
allPairsS xs = go xs [] where
go [] = id
go (y:ys) = (map (\a - (y, a)) ys ++) . go xs
Further reading:
http://www.haskell.org/haskellwiki/Difference_list
-- Dan Burton
On Tue, Sep 3, 2013 at 3:28 PM, Scott Pakin pa...@lanl.gov wrote:
I'm a Haskell beginner, and I'm baffled trying to reason about code
performance, at least with GHC. For a program I'm writing I needed to
find all pairs of elements of a list. That is, given the list ABCD
I wanted to wind up with the list
[('A','B'),('A','C'),('A','D')**,('B','C'),('B','D'),('C','D')**], where
the order of elements in the resulting list is immaterial, but I don't
want both ('A', 'B') and ('B', 'A'), for example.
My first attempt looked like this:
allPairs1 :: [a] - [(a, a)]
allPairs1 [] = []
allPairs1 (x:xs) = map (\a - (x, a)) xs ++ allPairs1 xs
Benchmarking with ghci's :set +s reveals the following performance
(median of three runs shown):
$ ghci
GHCi, version 7.6.3: http://www.haskell.org/ghc/ :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude :!ghc -c -O2 allpairs.hs
Prelude :load allpairs
Ok, modules loaded: AllPairs.
Prelude AllPairs :m +Control.DeepSeq
Prelude Control.DeepSeq AllPairs :show modules
AllPairs ( allpairs.hs, allpairs.o )
Prelude Control.DeepSeq AllPairs :set +s
Prelude Control.DeepSeq AllPairs deepseq (allPairs1 [1..1]) True
True
(4.85 secs, 4004173984 bytes)
A colleague suggested getting rid of the list append as follows:
allPairs2 :: [a] - [(a, a)]
allPairs2 [] = []
allPairs2 (x:xs) = allPairs2' x xs xs
where allPairs2' x [] [] = []
allPairs2' x (y:ys) zs = (x,y) : allPairs2' x ys zs
allPairs2' x [] (z:zs) = allPairs2' z zs zs
Not surprisingly, that runs faster:
Prelude Control.DeepSeq AllPairs deepseq (allPairs2 [1..1]) True
True
(2.14 secs, 4403686376 bytes)
I then figured I could do even better by rewriting the code
tail-recursively:
allPairs3 :: [a] - [(a, a)]
allPairs3 [] = []
allPairs3 (x:xs) = allPairs3' x xs xs []
where allPairs3' :: a - [a] - [a] - [(a, a)] - [(a, a)]
allPairs3' h (x:xs) ys result = allPairs3' h xs ys ((h,
x):result)
allPairs3' _ [] (y:ys) result = allPairs3' y ys ys result
allPairs3' _ [] [] result = result
This takes half the memory as the above (yay!) but runs substantially
*slower* (and appears to be thrashing my computer's memory system):
Prelude Control.DeepSeq AllPairs deepseq (allPairs3 [1..1]) True
True
(10.58 secs, 2403820152 bytes)
What gives? Why does my tail-recursive implementation run even slower
and presumably produce more garbage than my initial, naive
implementation? Is there some optimization GHC is performing for
allPairs1 and allPairs2 that it can't apply to allPairs3?
Similarly, how should I, as a newcomer who wants to write efficient
Haskell code, reason about whether a code change is likely to improve
rather than degrade performance? Guidelines like per-iteration
appends = bad and tail recursion = good are great, but the
preceding data indicate that something subtler is taking precedence
over those guidelines with respect to code performance.
Thanks in advance,
-- Scott
__**_
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/**mailman/listinfo/haskell-cafehttp://www.haskell.org/mailman/listinfo/haskell-cafe
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Reasoning about performance
allPairs2 can be simplified using a trick I wouldn't dare use in any language but Haskell: triangle4 xs = fused undefined [] xs where fused x (y:ys) zs = (x,y) : fused x ys zs fused _ [] (z:zs) = fused z zs zs fused _ [] [] = [] I submit this just for grins; it happens to be a touch faster but not enough to bother about. While the result _isn't_ all possible pairs of elements, making the allPairs name a bit dodgy, it _does_ have O(|xs|**2) of them... I would be surprised if the relative performance of two approaches in ghci were always the same as their relative performance in ghc. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Unexpected behaviour with send and send-buffer setting
On 4 Sep 2013, at 00:49, Gregory Collins g...@gregorycollins.net wrote: If the underlying write operation returns EWOULDBLOCK then the send function calls into the GHC IO manager with threadWaitWrite, which registers interest in the file descriptor using epoll() and blocks the calling Haskell thread until the socket is writable. If I'm following along correctly.. I was mistaken in thinking that send would never block because sockets are set to non-blocking, whereas the implementation of send re-introduces blocking behaviour through threadWaitWrite and efficient use of epoll (instead of continually polling with the attendant system call overhead). On Tue, Sep 3, 2013 at 6:56 PM, Simon Yarde simonya...@me.com wrote: The crux of my line of enquiry is this; how can my application know when to pause in generating its chunked output if send doesn't block and the current non-blocking send behaviour apparently succeeds when the send buffer should be full? Now I've learned that send *can* block the current thread to avoid overwhelming the receiver (but uses different mechanisms than send()), I understand my app need simply wait for a send to proceed before generating the next chunk. Does that sound anywhere close? On 4 Sep 2013, at 00:58, Joey Adams joeyadams3.14...@gmail.com wrote: 'send' will eventually block after enough 'send's without matching 'recv's. As Brandon explains, there is more buffering going on than the send buffer. In particular, the receiving host will accept segments until its buffer fills up. TCP implements flow control (i.e. keeps the sender from flooding the receiver) by having the receiver tell the sender how many more bytes it is currently willing to accept. This is done with the window size value in the TCP segment header [1]. [1]: http://en.wikipedia.org/wiki/Transmission_Control_Protocol#TCP_segment_structure If the receiver's buffer is full (reporting window size 0?), does send block until the receiver can accept more bytes, or return 0 bytes sent? Put another way; is there a scenario in which send could return 0 bytes sent? On 4 Sep 2013, at 00:13, Brandon Allbery allber...@gmail.com wrote: I would suggest reading a book on TCP/IP networking. I've studied Beej's Guide To Network Programming, Wikipedia entry, TCP spec, man pages.. I'll gladly take any recommendations that could help me understand system resource usage and configuration. Many thanks Brandon, Gregory, Joey. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Traversals of monomorphic containers
On 09/02/13 06:53, Nicolas Trangez wrote: # Redirected to haskell-cafe On Sun, 2013-09-01 at 14:58 +0400, Artyom Kazak wrote: Would this be an appropriate place to propose adding mapM_ (and then possibly mapM) to bytestring library? Was it suggested before? If yes, why was it rejected? This got me wondering: there are several type-classes useful for polymorphic container types, e.g. Functor, Foldable Traversable which all apply to some type of kind (* - *). Are there related things for monomorphic containers, like ByteString, Text or some newtype'd Vector with fixed element type, e.g. class MFunctor f a where mfmap :: (a - a) - f - f instance MFunctor ByteString Word8 where mfmap = ByteString.map I'm not aware of this particular class, but I have considered it. In the end I've chosen to generalize the class to FactorialMonoid instead: class Monoid m = FactorialMonoid m where ... foldMap :: Monoid n = (m → n) → m → n ByteString and Text are instances of the class, and so are lists, maps, and other containers, and Sum and Product as well. http://hackage.haskell.org/packages/archive/monoid-subclasses/0.3.2/doc/html/Data-Monoid-Factorial.html or (maybe even better) class MFunctor f where type Elem mfmap :: (Elem - Elem) - f - f instance MFunctor ByteString where type Elem = Word8 mfmap = ByteString.map and similar for other classes. Nicolas ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Traversals of monomorphic containers
These questions are exactly what Control.Lens answers. On 04/09/2013 12:50 PM, Mario Blažević blama...@acanac.net wrote: On 09/02/13 06:53, Nicolas Trangez wrote: # Redirected to haskell-cafe On Sun, 2013-09-01 at 14:58 +0400, Artyom Kazak wrote: Would this be an appropriate place to propose adding mapM_ (and then possibly mapM) to bytestring library? Was it suggested before? If yes, why was it rejected? This got me wondering: there are several type-classes useful for polymorphic container types, e.g. Functor, Foldable Traversable which all apply to some type of kind (* - *). Are there related things for monomorphic containers, like ByteString, Text or some newtype'd Vector with fixed element type, e.g. class MFunctor f a where mfmap :: (a - a) - f - f instance MFunctor ByteString Word8 where mfmap = ByteString.map I'm not aware of this particular class, but I have considered it. In the end I've chosen to generalize the class to FactorialMonoid instead: class Monoid m = FactorialMonoid m where ... foldMap :: Monoid n = (m → n) → m → n ByteString and Text are instances of the class, and so are lists, maps, and other containers, and Sum and Product as well. http://hackage.haskell.org/**packages/archive/monoid-** subclasses/0.3.2/doc/html/**Data-Monoid-Factorial.htmlhttp://hackage.haskell.org/packages/archive/monoid-subclasses/0.3.2/doc/html/Data-Monoid-Factorial.html or (maybe even better) class MFunctor f where type Elem mfmap :: (Elem - Elem) - f - f instance MFunctor ByteString where type Elem = Word8 mfmap = ByteString.map and similar for other classes. Nicolas __**_ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/**mailman/listinfo/haskell-cafehttp://www.haskell.org/mailman/listinfo/haskell-cafe __**_ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/**mailman/listinfo/haskell-cafehttp://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
