Hacker News Reader

Comment by tsimionescu | Hacker News Reader

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.

View on HN

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

Result:

   process1: 2s 251.327833ms
   process2: 1s 537.721625ms

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)
  }

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/

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

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++)

Array.prototype.reduce can basically do almost anything a for loop can do, since it gives you access to state from one iteration to the next. The only reason I didn't remove the flatMap in my original example and convert it all to reduce, is because there's no longer any method chaining which was the point of the original comparison between the Go and JS examples.

> dont ask me why but for(a of b) is slower than for(i=0;i<b.length;i++)

Probably because for of loops use the iterator protocol. So I'm assuming under the hood the JS engine is actually invoking the Symbol.iterator method (which is slower).

  #! /usr/bin/env node --experimental-strip-types
  
  function processIterator(input: number[]) {
    let sum = 0
    for (let i = input[Symbol.iterator](), r; (r = i.next()); ) {
      if (r.done) return sum
      if (r.value % 2 === 0) sum += r.value * 2
    }
  }
  
  function processfor(input: number[]) {
    let sum = 0
    for (let i = 0; i < input.length; i++) {
      const value = input[i]
      if (value % 2 === 0) sum += value * 2
    }
    return sum
  }
  
  
  const input = Array.from({ length: 1_000_000 }, (_, i) => i)
  
  console.time('normal for loop')
  console.log(processfor(input))
  console.timeEnd('normal for loop')
  
  console.time('iterator for loop')
  console.log(processIterator(input))
  console.timeEnd('iterator for loop')

But this is apples and oranges. Process 1 creates and calls lambdas, etc.

A proper comparison could be:

  # Case 1.
  for n in range(len(data)):
    data[n] = transform1(data[n])
    data[n] = transform2(data[n])

  # Case 2.
  for n in range(len(data)):
    data[n] = transform1(data[n])
  for n in range(len(data)):
    data[n] = transform2(data[n])

It illustrates how this kind of code is used in the wild - array functions vs a for loop. What you did is not even a fruit, if I go along with your metaphor.

Funny enough, the iterator version is much faster in rust because the compiler can more easily optimize iterator chains than custom for loops:

https://play.rust-lang.org/?version=stable&mode=release&edit...

(I'd recommend running it on your own machine as the rust playground limits memory and will likely kill this program)

Output from my machine:

    $ cargo run --release
        Finished `release` profile [optimized] target(s) in 0.05s
         Running `target/release/iterator`
    Process 1 returned 18270843109002848788 and took 64.58175ms
    Process 2 returned 18270843109002848788 and took 308.969083ms

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!

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.

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.

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.

There's no way to do this (a single instruction loop vs 10 loops with a single instruction) in JS or Golang.

I don't mean assembly-level instructions, just general instructions in the language:

  for i := range arr {
    foo1(arr[i])
    ...
    foo10(arr[i])
  }

  for i := range arr {
    foo1(arr[i])
  }
  ... 
  for i := range arr {
    foo10(arr[i])
  }

Until the array no longer fits in your cache :)

https://en.m.wikipedia.org/wiki/Loop_fission_and_fusion

Reply on news.ycombinator.com