13 ms·
Turn O(n^2) reverse into O(n)
- seliopou 13y agoI for one prefer the more "algebraic" implementation. Why worry about performance when you get theorems for free?! Monads.
- dinkumthinkum 13y agoYour users might care ...
- deleted 13y ago[deleted]
- 10098 13y agohttp://imgur.com/QIVtdxM.jpg http://imgur.com/QIVtdxM.jpg
- adamnemecek 13y agoYou would fit right in at http://reddit.com/r/programmingcirclejerk http://reddit.com/r/programmingcirclejerk :-)
- oakwhiz 13y agoWhy not upgrade the compiler to detect the algebraic implementation and optimize it to the buffer implementation?
- cliffbean 13y agoBecause if it's a common pattern, then it's nice to put it in a common library anyway, instead of having everyone write it out by hand. It makes the code cleaner and more efficient. Win win!
- tikhonj 13y agoIt actually does this in a bunch of cases; see Haskell's stream fusion[1] and rewrite rules in general[2] for examples. However, there aren't any rewrite rules for list-based code, at least with the standard library. Rewrite rules are generally used for libraries designed explicitly with performance in mind like Vector and Bytestring; the standard String type and the Prelude don't fall into this category. [1]: http://stackoverflow.com/questions/578063/what-is-haskells-stream-fusion http://stackoverflow.com/questions/578063/what-is-haskells-s... [2]: http://www.haskell.org/ghc/docs/7.0.1/html/users_guide/rewrite-rules.html http://www.haskell.org/ghc/docs/7.0.1/html/users_guide/rewri...
- lmm 13y agoObvious follow-up question: why does cabal not use more performance-oriented libraries? Does it have to avoid depending on anything because it's the dependency manager?
- kenko 13y agoI for one prefer the (appropriately) unthinking anti-intellectualism. Hacker News.
- coherentpony 13y agoI think (s)he was being sarcastic.
- mintplant 13y agoAnd that's the anti-intellectualism.
- hdevalence 13y ago"And make no mistake: irony tyrannizes us. The reason why our pervasive cultural irony is at once so powerful and so unsatisfying is that an ironist is impossible to pin down. All irony is a variation on a sort of existential poker-face. All U.S. irony is based on an implicit "I don't really mean what I say." So what does irony as a cultural norm mean to say? That it's impossible to mean what you say? That maybe it's too bad it's impossible, but wake up and smell the coffee already? Most likely, I think, today's irony ends up saying: "How very banal to ask what I mean." Anyone with the heretical gall to ask an ironist what he actually stands for ends up looking like a hysteric or a prig. And herein lies the oppressiveness of institutionalized irony, the too-successful rebel: the ability to interdict the question without attending to its content is tyranny. It is the new junta, using the very tool that exposed its enemy to insulate itself." From David Foster Wallace's "E Unibus Pluram".
- haberman 13y agoOnly if you believe that "intellectualism" means "favoring more abstract approaches regardless of practical concerns."
- tibbon 13y agoMy Haskell skills still are growing. Can someone explain?
- seliopou 13y agoThe original line was something like this: acc = ""; for (var i = 0; i < strings.length; i++) { acc += strings[i] } The new version is something like this: strings.join("") The second version can pre-allocate a string and copy characters into that string under the hood. The first version has to allocate a new string and recopy the characters on every iteration.
- fekberg 13y agoI recall when I studied algorithms and data structures, but just swapping to using references/pointers instead of copying memory, I could speed up my algorithms ridiculously. Correct me if I am wrong. "Small" things like these (as we just saw) can be really beneficial!
- eru 13y agoAs an aside, immutability (ie purity) in Haskell allows refercences everywhere, and thus less copying. (They call it `sharing' in Haskell land.)
- thinkpad20 13y agoIt's worth noting, though, that immutability doesn't always mean less copying. Immutable arrays, where the entire array must be copied with the change of one element, are an example of that. And by extension, hash tables, etc. Of course there are lots of tricks that can be employed to get around this, to a degree.
- eru 13y agoYes. The right data structure for the right job. If your array only has one future---ie there are no references to the unchanged array around---you can re-use the old array. That means you get to mutate in place but still pretend you have immutability.
- thinkpad20 13y agoI'd definitely like to see an explanation of what's going on, both at a high level and the specifics of the code. As a Haskell beginner-intermediate, I don't really know what most of those functions are doing (much less the context of what that function's purpose is), but I feel I could probably understand an explanation if it were given.
- MBCook 13y agoI think I know enough Haskell to explain. Old version: foldr (flip (buf_append bufOps)) (buf_empty bufOps) strs foldr is a combination map/reduce in one. It takes a value (the accumulator), runs a function on the rightmost value in a list called str (that's why it's 'foldr'), and combines the two together into a new accumulator value. Let's say we have a list of numbers, the addition operator, and an accumulator of 0. foldr op acc list foldr + 0 [1, 2, 3, 4] a = 0, list = [1, 2, 3, 4] a = 0 + 4, list = [1, 2, 3] a = 4 + 3, list = [1, 2] a = 7 + 1, list = [1] a = 8, list = [] Result is 8 One thing to note is that this walks the list 'backward', and in Haskell it's a singly linked list. That means that each time it has to walk the full list. I believe this is why it's O(n^2). It looks like the accumulator starts with (buf_empty bufOps), which from context I assume is an empty buffer structure. The operator is (flip (but_append bufOps)), which looks like it adds values onto the bufOps structure when called. Each time it goes through this process, it appends one element. Because they're using foldr and the list is walked 'backward', this has the natural side effect that the order of the items in strs is reversed as it's added to bufOps. New version: buf_concat bufOps $ reverse strs The $ is a way of controlling precedence in Haskell, you can replace it with parenthesis. So we get: buf_concat bufOps ( reverse strs ) So reverse just reverses the order of a list, getting things in the order the code wants them. Then it calls buf_concat with the current structure and the items it wants added. So instead of taking one existing list and adding 6 new elements at the end one at a time, it takes one existing list and adds a list of 6 elements to the end once. It seems like a relatively simple change. I wonder if using foldl or foldl' to avoid having to rewalk the list every time would have performance similar to the new line. I find the new line simpler and cleaner either way, but was the choice of a right-fold the cause of the performance problem?
- anonymouscowar1 13y agoDo people try and optimize Haskell programs? This is a part of Haskell that terrifies me.
- fekberg 13y agoShouldn't we optimize all our programs?
- cliffbean 13y agoSure they do! Optimizing is more than just low-level efficiency. It's also about using appropriate data structures and algorithms, and using advantageous APIs (like buf_concat here) when they're applicable.
- seliopou 13y agoLook. I love Haskell. I usually formulate solutions to programming problems in my head in Haskell before I write code in whatever language I have to deal with. Constructing programs using combinators? Great. Assuming referential transparency everywhere? Great. It's a great language. But there comes a point in time where you have to project that stuff all away and get down to the brass tacks of what's happening in your system, leaving behind the Platonic heaven you've constructed for yourself. As the patch proves without a doubt, this is very possible to do in Haskell. But sadly, the general ethos of the Haskell community does not bend in that direction. I am a lover of the language, but at the same time a vocal critic of the community in that respect.
- jberryman 13y agoHere is the context http://www.reddit.com/r/haskell/comments/1sh67u/the_reason_why_cabal_update_takes_so_long/ http://www.reddit.com/r/haskell/comments/1sh67u/the_reason_w...
- djulius 13y agoI guess nobody ever got upvoted for using StringBuffer/StringBuilder instead of String concatenation in Java.
- drostie 13y agoExplanation: bufOps is a dictionary which holds a bunch of functions accessed with the getters on it. For the sake of this comment, we can concretize and use (buf_empty bufOps) as [] and (buf_append bufOps) as ++. This code then essentially performs: foldr (flip (++)) [] xs Which, if you look up the definition of foldr, is: ((([] ++ xN) ++ ... ) ++ x2) ++ x1 And a definition of ++ is of course: [] ++ ys = ys (x:xs) ++ ys = x : (xs ++ ys) This means that for lists of this sort a ++ b runs in time O(length a), because it has to descend down the leftmost list to find the empty list -- only once it finds [] can it "work its way backwards" to append elements from a onto b. If each of the x1, x2, ... xN has m elements, then we do 0 + m + 2m + ... + N m = m * N * (N + 1) / 2 operations. Each ++ will do about N operations and we'll do about N of them; it's O(N^2). The new algorithm, `concat (reverse xs)`, works because `xs` is just a list which can be reversed by traversing down it in O(N) time, then those can be merged together in O(N * m) time.
- zvrba 13y agoSo 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 agoHumans occasionally make mistakes, including expert ones.
- vanderZwan 13y agoExactly. 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 agoAdvantage 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 agoI 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 agoI 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.
- thomasahle 13y agoDoesn't hlint catch stuff like this?
- gwern 13y agoHow would hlint catch this? The offending line is foldr (flip (buf_append bufOps)) (buf_empty bufOps) strs hlint doesn't know what 'buf_append bufOps' is, or 'buf_empty bufOps' or 'strs'. If you saw 'foldr (flip (u v)) (x y) z', would you immediately go 'ah, n^2! better throw a warning'? If not, why do you expect hlint to warn?
- taybin 13y agoYep, this can also bite you in Erlang.