Hacker News Reader

Generally, performance is something you worry about when it becomes an issue. Otherwise you spend waaaay too much time on "performance" that have 0 benefit.

That said “Avoid multiple passes over the data when one would do", while true, often profound performance gains comes from insight into the domain, where the first pass is structuring it such that the subsequent queries and transformations are simple and quick.

Luckily for haskellers, GHC does a thing called fusion, which is an optimization that pipes together different operations on data, and avoids allocating intermediate results.

(https://www.stackbuilders.com/tutorials/haskell/ghc-optimiza...)

Ever heard of streams/iterators? Where data from the collection pass as a stream through all transformations only once. Code is readable and functional, and it only passes once through your collection.

I think the idea is: think about what you are doing. Choose the correct level of simplicity vs performance What I find is that it's rarely massive amounts of data that kills you, it's the polynomial effects that do. For example, if you have 3 collections of <100 and you do for-each-class of students, then for each class check which rooms are available, and for each room available see if the course can be in the room, you may have 100^3 tests though your data was trivially small. People benchmark and it looks fine (because they took 10 items each for their O(MNK) algorithm, and perhaps even tried (1001010) but when things later hit 100^3 in production everything grinds to a halt. This is why benchmarking is not always helpful in the early phase. Estimate the relations between the data sizes just slightly wrong and your estimate of performance might be 1000% off.

I work on a program with dozens of parts being fundamentally quadratic and several even NP, and I'm perpetually angry at my fellow developers for tackling O(N^k) things as O(N^(k+1)). Typically this is by the use of "subtly polynomial" things such as things.First(x => otherThings.Contains(...)) etc.

I'm all for the nice high level constructs, I just think tthat it needs to be carefully considered. And I don't agree with the "make the simple one first, and only optimize after benchmarking" because that just keeps proving useless (Pick too small dataset and benchmark is OK, and unless the algorithm is linear or better, it's trivial to choose N such that the performance is unacceptable in the benchmark. And whatever N you choose, customers will demand 2N tomorrow). I prefer a simpler solution, e.g. "in parts X and Y of the application we write the fastest things possible from the start, while in the remaining 80% of the app we write the clearest thing possible and don't optimize until we are certain it's needed".

Readable and less error prone? As opposed as to proven to be correct for example? Recursive functional code is a pain to prove to be right and not blow up stack. Multiple passes (when interspersed with other accesses) can blow up cache.

Even calling through a lambda is a cost compilers cannot easily optimize away unless you help them. (Even in C++.)

You do get the benefit of optimizing all the "trivial data size" code when it is all the functions being written in such silly way. Difference of 10% in one function as opposed to across whole application.

Benchmarking is often even harder to do right than writing good tests. (In fact is tied to it.) Instead of benchmarking, be a real computer scientist and prove bounds and memory allocations.

How is it difficult to prove if a recursive call is tail-recursive or not? If it's tail-recursive and your language supports tail-call optimisation then you proved that there will be no stack blow-up.

For simple calls, not. For something more involved? (Dependent functions, corecursion, partially stateful code.) Very which is why compilers fail to optimize it in general.

> Recursive functional code is a pain to prove to be right and not blow up stack.

Much easier to prove recursion correct than to prove a loop always terminates, since the recursion makes the way the state changes between steps much more explicit. If you're really worried about this you can use Idris and require all your functions to be total.

Plus some functional languages can combine those steps at compile, giving you the best of both worlds. Rust for example elides away many lambda's in map operations. I don't have the link handy, but a post a few months back showed Rust and Haskell functional patterns could almost match their hard coded imperative style implementations and C/C++ cousins.

Here it is: https://www.fpcomplete.com/blog/2017/07/iterators-streams-ru...

The key word is "often". Which means not always, which means you cannot rely on it unless you check all your code in Godbolt or equivalent.

Which used to be a common complaint of C and Pascal compilers against manually written Assembly code.

Performance is always an issue.

That said, I fully grant it may be an issue that is worth solving later in the process.

The later you do it, the more expensive it gets. In this it is similar to testing.

Fully agreed, though optimization is something that should come later. Otherwise, folks will spend too much time making a really tight loop that isn't actually run in a loop. :)

I also agree that folks should try to avoid poor habits. However, I'll note that even Knuth uses brute force for some parts of his programs. Quoting, "Brute force is the rule in this part of the program."[1] Sometimes, it really isn't the bottleneck. :)

[1] http://www-cs-faculty.stanford.edu/~knuth/programs/dance.w

Performant code vs readable code is a false dichotomy.

Do you have any evidence to back that statement up?

I think the proof should be on those who say that readable code cannot be performant.

I've never heard anyone say that.

> Totally disagree.

Hmm, I see....

> Most collections/array I process have trivial number of elements (<100)

Ah! ok that explains it.

> I would rather use functional programming approaches to sort data into shape (think map/filter/reduce). These approaches typically result in passing over the data multiple times, and often performing multiple copies,

That's a good recommendation. If you tend to write in a deforestable style (whether deforested automatically by the compiler or, by you manually) you can mitigate some gratuitous copying and multiple passes.

The vast majority of programming languages return an iterator when you use map, filter, etc. There is usually only one eager evaluation pass at the end that conerts the iterator to a list.

Most languages are capabale of inlining the "next" function of the iterator to generate almost the same code as a regular for loop.

The advice you quoted is the most valuable of all, in my opinion.

You give "map/filter/reduce" as an example and claim that theses approaches "typically result in passing over the data multiple times". No, since reduce can behave like map and filter, with a proper reduction function you only have to pass over the data once.

> Most collections/array I process have trivial number of elements (<100) and you get virtually no benefit from writing optimized code.

That is true for all other advice given in the original article, but not for this: A reduction function only needs one input element and the aggregate/result so far. This function then does not care whether it is called in the context of list or vector iteration, it will happily work with elements read from a stream or any other potentially destructive iterator. The benefit is obvious: Write & debug once, document and never touch the code again until the actual algorithm implemented there changes.

> No, since reduce can behave like map and filter, with a proper reduction function you only have to pass over the data once.

You can indeed - which is why reduce is relatively opaque and unmaintainable, and should be a last resort. Any given map/filter pipeline could be rewritten to reduce, and it quite possibly would perform better - but at the cost of not being able to test individual pipeline stages, nor inspect the intermediate results in a debugger. Most of the time that's a bad tradeoff.

I disagree. I does not have to be unmaintainable. The difference between chaining map/filter and a single reduce is mostly a syntax transformation plus a little bit of thinking upfront:

   ;; N.B.: Code was written here in a comment and never tested. 
   ;; It might need some of those: ')))))'
   (flet ((filter-element (element bucket)
            ;; all (filter...)s of your chain here
           )
          (mutate-element (element bucket)
            ;; apply all your (map...)s here
           ))
     (defun distill-magic (essence element)
        (if (not (filter-element element essence))
            essence
            (cons (mutate-element element essence) 
                   essence))))

The hard part is sometimes to reformulate the chain in a way that you only filter on either pre- or post-mutation data. If you can't, your most probably using the wrong algorithm. But fixing that, if it requires serious thinking, is something I defer to the moment it actually matters. I now can, because it is neatly encapsulated in a single, local function definition.

And yes, of course I can inspect intermediate results in a debugger: Just trace distill-magic or set a break point.