6 ms·

“Avoid multiple passes over the data when one would do.” Totally disagree. Unless performance is an issue (like I’m not dealing with a trivial number of elemen

“Avoid multiple passes over the data when one would do.” Totally disagree. Unless performance is an issue (like I’m not dealing with a trivial number of elements), 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, but it makes for readable and less error prone code. Doing the performant thing consists of writing a for loop (or multiple of them unless you unroll) and automatically result with a large custom body of code performing multiple transformations on the data. It’s just wasted mental effort when you write it and every time when you happen to read it again. Most collections/array I process have trivial number of elements (<100) and you get virtually no benefit from writing optimized code. I have also written a lot of performant code, and the lesson is always benchmark benchmark benchmark. The results do not always fit the mental model about what you think should be the fastest. In particuliar avoiding cache misses is far more important than you might think.

AstralStorm 9y ago
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.
- tigershark 9y ago
  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.
  - AstralStorm 9y ago
    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.
- lmm 9y ago
  > 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.
elcritch 9y ago
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.
- elcritch 9y ago
  Here it is: https://www.fpcomplete.com/blog/2017/07/iterators-streams-rust-haskell https://www.fpcomplete.com/blog/2017/07/iterators-streams-ru...
  - AstralStorm 9y ago
    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.
    - pjmlp 9y ago
      Which used to be a common complaint of C and Pascal compilers against manually written Assembly code.
taeric 9y ago
Performance is always an issue. That said, I fully grant it may be an issue that is worth solving later in the process.
- AstralStorm 9y ago
  The later you do it, the more expensive it gets. In this it is similar to testing.
  - taeric 9y ago
    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 http://www-cs-faculty.stanford.edu/~knuth/programs/dance.w
dullgiulio 9y ago
Performant code vs readable code is a false dichotomy.
- majikandy 9y ago
  Do you have any evidence to back that statement up?
  - dullgiulio 9y ago
    I think the proof should be on those who say that readable code cannot be performant.
    - majikandy 9y ago
      I've never heard anyone say that.
alkonaut 9y ago
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".
hvidgaard 9y ago
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.
ekr 9y ago
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-optimization-and-fusion/ https://www.stackbuilders.com/tutorials/haskell/ghc-optimiza...)
imtringued 9y ago
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.
jlg23 9y ago
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.
- lmm 9y ago
  > 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.
  - jlg23 9y ago
    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.
ssijak 9y ago
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.
srean 9y ago
> 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.

AstralStorm 9y ago

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.

tigershark 9y ago
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.
- AstralStorm 9y ago
  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.
lmm 9y ago
> 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.

elcritch 9y ago

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.

elcritch 9y ago
Here it is: https://www.fpcomplete.com/blog/2017/07/iterators-streams-rust-haskell https://www.fpcomplete.com/blog/2017/07/iterators-streams-ru...
- AstralStorm 9y ago
  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.
  - pjmlp 9y ago
    Which used to be a common complaint of C and Pascal compilers against manually written Assembly code.

taeric 9y ago

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

AstralStorm 9y ago
The later you do it, the more expensive it gets. In this it is similar to testing.
- taeric 9y ago
  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 http://www-cs-faculty.stanford.edu/~knuth/programs/dance.w

dullgiulio 9y ago

Performant code vs readable code is a false dichotomy.

majikandy 9y ago
Do you have any evidence to back that statement up?
- dullgiulio 9y ago
  I think the proof should be on those who say that readable code cannot be performant.
  - majikandy 9y ago
    I've never heard anyone say that.

alkonaut 9y ago

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".

hvidgaard 9y ago

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.

ekr 9y ago

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-optimization-and-fusion/ https://www.stackbuilders.com/tutorials/haskell/ghc-optimiza...)

imtringued 9y ago

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.

jlg23 9y ago

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.

lmm 9y ago
> 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.
- jlg23 9y ago
  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.

ssijak 9y ago

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.

srean 9y ago

> 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.