5 ms·

So the original line of code has apparently been present since the very first import by Sigbjørn Finne in https://github.com/nominolo/HTTP/blob/c4765e822eb92196

by zvrba 13y ago

So the original line of code has apparently been present since the very first import by Sigbjørn Finne in https://github.com/nominolo/HTTP/blob/c4765e822eb92196fec95560f8f640018d18737f/Network/HTTP/Base.hs https://github.com/nominolo/HTTP/blob/c4765e822eb92196fec955... (check line 443). If a Haskell expert (e.g., he authored hdirect -- an IDL compiler and interface with Win32 COM -- sadly defunct now) makes this kind of mistake, how are mere mortals supposed to reason about algorithmic efficiency?

sjtgraham 13y ago
Humans occasionally make mistakes, including expert ones.
- vanderZwan 13y ago
  Exactly. Isn't it comforting to know that making mistakes is only human? And isn't this a wonderful practical example of why you want to be open source?
6d0debc071 13y ago
Advantage in focus - maybe he wrote it once and didn't look back at it. Low hanging fruit elsewhere for typical use case?
velis_vel 13y ago
I don't think this was an 'oh my god we're trying to track down why cabal update is so slow and we just can't find it' issue like you make it out to be. edit: http://www.reddit.com/r/haskell/comments/1sh67u/the_reason_why_cabal_update_takes_so_long/cdxnr5l http://www.reddit.com/r/haskell/comments/1sh67u/the_reason_w... This comment by the patch author indicates that actually tracking it down was a fairly straightforward profiling job.
- zvrba 13y ago
  I didn't try to imply that it was difficult to find the performance problem. It's an observation on something else: Haskell is often mentioned for its equational reasoning. I find it interesting that correct equational reasoning in this case lead to a correct program, but one with absymal performance. It'd be interesting to think how one could encode performance characteristics into equations.
  - jjaredsimpson 13y ago
    Its known that postpending to a linked list is slow. It's just a property of the data type.
  - deleted 13y ago
    [deleted]
  - Peaker 13y ago
    I think having simple and direct denotational semantics necessarily means having relatively complex, indirect operational semantics (e.g: Haskell). Having a simple and direct operational semantics necessarily means having complex and indirect denotational semantics (e.g: C). C makes performance easy and correctness hard. Haskell makes correctness easy and performance hard. The trick is, in most programs, you only need performance for a tiny subset of the program. You need correctness throughout the whole program.
    - zvrba 13y ago
      Why do you think that there must be a tradeoff between simplicity of denotational and operational semantics?
      - Peaker 13y ago
        Because operational semantics (of contemporary computers, at least) are very different from a simple denotational semantics. We have to bridge that gap: 1) Either use a compiler that hides away the operational details 2) Or use a language that directly maps to the operational semantics, but then is necessarily far away from the denotational ones
  - velis_vel 13y ago
    > I find it interesting that correct equational reasoning in this case lead to a correct program, but one with absymal performance. That's not really an interesting property of Haskell, though. You can always write correct but slow code in any language. > It'd be interesting to think how one could encode performance characteristics into equations. I've seen the concept of encoding performance in types played around with, but I can't find actual work (if any) that's been done on it.
microtherion 13y ago
I suppose what Alan Perlis said about LISP programmers—that they know the value of everything and the cost of nothing—is true for Haskell programmers as well.
- kovalkos 13y ago
  This is a bad application of the quote. Most of the Lisp hackers are usually knowledgeable about analysis of algorithm complexity. Alan Perlis comment talks about inefficiency of Lisp programs due to a lot of (meta) abstraction and indirect mapping of abstract software to hardware.
  - microtherion 13y ago
    Admittedly, this particular case seems amenable to fairly straightforward algorithmic complexity analysis, but it seems to me that the lazy nature of Haskell seems to make it even harder to get a good grasp of costs involved than in a language like Lisp.
deleted 13y ago
[deleted]
hesselink 13y ago
I think back then, the 'n' just wasn't very large, so O(n) versus O(n^2) didn't make much of a difference.
nilkn 13y ago
Mistakes of this sort have been made in many languages. I don't see what this has to do with Haskell specifically.
eru 13y ago
> [...] how are mere mortals supposed to reason about algorithmic efficiency? You profile, and then you look at the suspicious parts.

by zvrba 13y ago

sjtgraham 13y ago

Humans occasionally make mistakes, including expert ones.

vanderZwan 13y ago
Exactly. Isn't it comforting to know that making mistakes is only human? And isn't this a wonderful practical example of why you want to be open source?

6d0debc071 13y ago

Advantage in focus - maybe he wrote it once and didn't look back at it. Low hanging fruit elsewhere for typical use case?

velis_vel 13y ago

I don't think this was an 'oh my god we're trying to track down why cabal update is so slow and we just can't find it' issue like you make it out to be. edit: http://www.reddit.com/r/haskell/comments/1sh67u/the_reason_why_cabal_update_takes_so_long/cdxnr5l http://www.reddit.com/r/haskell/comments/1sh67u/the_reason_w... This comment by the patch author indicates that actually tracking it down was a fairly straightforward profiling job.

zvrba 13y ago
I didn't try to imply that it was difficult to find the performance problem. It's an observation on something else: Haskell is often mentioned for its equational reasoning. I find it interesting that correct equational reasoning in this case lead to a correct program, but one with absymal performance. It'd be interesting to think how one could encode performance characteristics into equations.
- jjaredsimpson 13y ago
  Its known that postpending to a linked list is slow. It's just a property of the data type.
- deleted 13y ago
  [deleted]
- Peaker 13y ago
  I think having simple and direct denotational semantics necessarily means having relatively complex, indirect operational semantics (e.g: Haskell). Having a simple and direct operational semantics necessarily means having complex and indirect denotational semantics (e.g: C). C makes performance easy and correctness hard. Haskell makes correctness easy and performance hard. The trick is, in most programs, you only need performance for a tiny subset of the program. You need correctness throughout the whole program.
  - zvrba 13y ago
    Why do you think that there must be a tradeoff between simplicity of denotational and operational semantics?
    - Peaker 13y ago
      Because operational semantics (of contemporary computers, at least) are very different from a simple denotational semantics. We have to bridge that gap: 1) Either use a compiler that hides away the operational details 2) Or use a language that directly maps to the operational semantics, but then is necessarily far away from the denotational ones
- velis_vel 13y ago
  > I find it interesting that correct equational reasoning in this case lead to a correct program, but one with absymal performance. That's not really an interesting property of Haskell, though. You can always write correct but slow code in any language. > It'd be interesting to think how one could encode performance characteristics into equations. I've seen the concept of encoding performance in types played around with, but I can't find actual work (if any) that's been done on it.

microtherion 13y ago

I suppose what Alan Perlis said about LISP programmers—that they know the value of everything and the cost of nothing—is true for Haskell programmers as well.

kovalkos 13y ago
This is a bad application of the quote. Most of the Lisp hackers are usually knowledgeable about analysis of algorithm complexity. Alan Perlis comment talks about inefficiency of Lisp programs due to a lot of (meta) abstraction and indirect mapping of abstract software to hardware.
- microtherion 13y ago
  Admittedly, this particular case seems amenable to fairly straightforward algorithmic complexity analysis, but it seems to me that the lazy nature of Haskell seems to make it even harder to get a good grasp of costs involved than in a language like Lisp.

deleted 13y ago

[deleted]

hesselink 13y ago

I think back then, the 'n' just wasn't very large, so O(n) versus O(n^2) didn't make much of a difference.

nilkn 13y ago

Mistakes of this sort have been made in many languages. I don't see what this has to do with Haskell specifically.

eru 13y ago

> [...] how are mere mortals supposed to reason about algorithmic efficiency? You profile, and then you look at the suspicious parts.