4 ms·

I think the killer case for this is not hiding the computational complexity of mapping/reversing/etc. I write a lot of typescript and golang and I often notice

I think the killer case for this is not hiding the computational complexity of mapping/reversing/etc. I write a lot of typescript and golang and I often notice in typescript my chains end up iterating the same array N times when it couldbe been done in one smarter iteration. I don't think I care though -- both styles are way more than performant enough. You can be more careful about it in cases it is not.

tsimionescu 2y ago
Iterating an array 10 times doing 1 operation on each element each time is equivalent to iterating it 1 time while doing 10 operations on each element.
- parhamn 2y ago
  This isn't true outside the theoretical best case. Definitely not true in most interpreted languages. Consider the performance difference of .reverse() (in-place or copy) vs using a descending for loop. Generally with interpreter chaining there are more "hidden" allocations/operations.
  - tsimionescu 2y ago
    You're comparing apples and oranges. Of course modifying an array or copying it takes way more time than looping. The comparison was not about that, it's about one loop with 10 instructions VS 10 loops each with a single instruction, for the exact same instructions.
    - thrww120956 2y ago
      There's no way to do this (a single instruction loop vs 10 loops with a single instruction) in JS or Golang.
      - tsimionescu 2y ago
        I don't mean assembly-level instructions, just general instructions in the language: for i := range arr { foo1(arr[i]) ... foo10(arr[i]) } Vs for i := range arr { foo1(arr[i]) } ... for i := range arr { foo10(arr[i]) }
- thrww120956 2y ago
  Found the theoretical informatician... Nope, not in real world software engineering. Especially not in JIT runtimes like V8. Try it! I tried it, code: https://pastebin.com/cA8YkE8R https://pastebin.com/cA8YkE8R Result: process1: 2s 251.327833ms process2: 1s 537.721625ms
  - throwitaway1123 2y ago
    It's a little bit faster (on my machine at least) if you combine the filter and map into a flatMap (it's still not as performant as the imperative solution though). function process3(input) { return input .flatMap((n) => (n % 2 === 0 ? n * 2 : [])) .reduce((a, b) => a + b, 0) }
    - 6510 2y ago
      If it needs to be fast use oldskool for() loops. function processfor(input){ let sum = 0 for (let i = 0; i < input.length; i++){ if (input[i] % 2 !== 0){ continue } sum += input[i] * 2 } return sum } https://jsfiddle.net/gaby_de_wilde/y7a39r15/5/ https://jsfiddle.net/gaby_de_wilde/y7a39r15/5/
      - throwitaway1123 2y ago
        Yeah the comment I was originally responding to included a for loop (in the Pastebin link). My point is that if you're set on going down the functional route you don't need separate map and filter steps, you can just use flatMap which is effectively a filter and map combined (returning an empty array filters out the current value, since an empty array gets flattened into nothing). Of course, if you want the most performant solution an imperative for loop is faster (which is what I said in my last comment).
        6510 2y ago
        input.reduce((a, b) => b % 2 !== 0 ? a : a + (b * 2), 0) or if you want it really silly. input.reduce((a, b) => a + (b % 2 && b * 2), 0) dont ask me why but for(a of b) is slower than for(i=0;i<b.length;i++)
- nick__m 2y ago
  In an ideal machine you are absolutely correct! But when executed by a real physical CPU, if the array doesn't fit I the cache, iteration strategies matters!
  - tsimionescu 2y ago
    Not in this way, not significantly. At worse, for each new loop through the array you have an extra cache miss. If the array is large enough, 10 extra cache misses will barely even be measurable. It's only for small arrays actually that the cost of the loop infra and the extra cache miss per loop matters.
- gpderetta 2y ago
  https://en.m.wikipedia.org/wiki/Loop_fission_and_fusion https://en.m.wikipedia.org/wiki/Loop_fission_and_fusion
- ehaliewicz2 2y ago
  Until the array no longer fits in your cache :)
amarshall 2y ago
By that logic, calling any function with a loop or recursion should be forbidden, as it hides computational complexity at the call site. I.e. should we get rid of `slices.Sort` (etc.) because it hides computational complexity?

tsimionescu 2y ago

Iterating an array 10 times doing 1 operation on each element each time is equivalent to iterating it 1 time while doing 10 operations on each element.

parhamn 2y ago
This isn't true outside the theoretical best case. Definitely not true in most interpreted languages. Consider the performance difference of .reverse() (in-place or copy) vs using a descending for loop. Generally with interpreter chaining there are more "hidden" allocations/operations.
- tsimionescu 2y ago
  You're comparing apples and oranges. Of course modifying an array or copying it takes way more time than looping. The comparison was not about that, it's about one loop with 10 instructions VS 10 loops each with a single instruction, for the exact same instructions.
  - thrww120956 2y ago
    There's no way to do this (a single instruction loop vs 10 loops with a single instruction) in JS or Golang.
    - tsimionescu 2y ago
      I don't mean assembly-level instructions, just general instructions in the language: for i := range arr { foo1(arr[i]) ... foo10(arr[i]) } Vs for i := range arr { foo1(arr[i]) } ... for i := range arr { foo10(arr[i]) }
thrww120956 2y ago
Found the theoretical informatician... Nope, not in real world software engineering. Especially not in JIT runtimes like V8. Try it! I tried it, code: https://pastebin.com/cA8YkE8R https://pastebin.com/cA8YkE8R Result: process1: 2s 251.327833ms process2: 1s 537.721625ms
- throwitaway1123 2y ago
  It's a little bit faster (on my machine at least) if you combine the filter and map into a flatMap (it's still not as performant as the imperative solution though). function process3(input) { return input .flatMap((n) => (n % 2 === 0 ? n * 2 : [])) .reduce((a, b) => a + b, 0) }
  - 6510 2y ago
    If it needs to be fast use oldskool for() loops. function processfor(input){ let sum = 0 for (let i = 0; i < input.length; i++){ if (input[i] % 2 !== 0){ continue } sum += input[i] * 2 } return sum } https://jsfiddle.net/gaby_de_wilde/y7a39r15/5/ https://jsfiddle.net/gaby_de_wilde/y7a39r15/5/
    - throwitaway1123 2y ago
      Yeah the comment I was originally responding to included a for loop (in the Pastebin link). My point is that if you're set on going down the functional route you don't need separate map and filter steps, you can just use flatMap which is effectively a filter and map combined (returning an empty array filters out the current value, since an empty array gets flattened into nothing). Of course, if you want the most performant solution an imperative for loop is faster (which is what I said in my last comment).
      - 6510 2y ago
        input.reduce((a, b) => b % 2 !== 0 ? a : a + (b * 2), 0) or if you want it really silly. input.reduce((a, b) => a + (b % 2 && b * 2), 0) dont ask me why but for(a of b) is slower than for(i=0;i<b.length;i++)
nick__m 2y ago
In an ideal machine you are absolutely correct! But when executed by a real physical CPU, if the array doesn't fit I the cache, iteration strategies matters!
- tsimionescu 2y ago
  Not in this way, not significantly. At worse, for each new loop through the array you have an extra cache miss. If the array is large enough, 10 extra cache misses will barely even be measurable. It's only for small arrays actually that the cost of the loop infra and the extra cache miss per loop matters.
gpderetta 2y ago
https://en.m.wikipedia.org/wiki/Loop_fission_and_fusion https://en.m.wikipedia.org/wiki/Loop_fission_and_fusion
ehaliewicz2 2y ago
Until the array no longer fits in your cache :)

amarshall 2y ago

By that logic, calling any function with a loop or recursion should be forbidden, as it hides computational complexity at the call site. I.e. should we get rid of `slices.Sort` (etc.) because it hides computational complexity?