Krdytkyu

I have been discussing some code with colleagues:

for(const a of arr) {

  if(a.thing)

    continue;

  // do a thing

}

A suggestion was to filter this and use a forEach

arr.filter(a => a.thing)

  .forEach(a => /* do a thing */);

There was a discussion about iterating more than necessary. I've looked this up, and I can't find anything. I also tried to figure out how to view the optimized output, but I don't know how to do that either.

I would expect that the filter and forEach turn into code that is very much like the for of with the continue, but I don't know how to be sure.

How can I find out? The only thing I've tried so far is google.

Your first example (the for in loop) is O(n), which will execute n times (n being the size of the array).

Your second example (the filter forEach) is O(n+m), which will execute n times in the filter (n being the size of the array), and then m times (m being the size of the resulting array after the filter takes place).

As such, the first example is faster. However, in this type of example without an exceedingly large sample set the difference is probably measured in microseconds or nanoseconds.

With regards to compilation optimization, that is essentially all memory access optimization. The major interpreters and engines will all analyze issues in code relating to function, variable, and property access such as how often and what the shape of the access graph looks like; and then, with all of that information, optimize their hidden structure to be more efficient for access. Essentially no optimization so far as loop replacement or process analysis is done on the code as it for the most part is optimized while it is running (if a specific part of code does start taking an excessively long time, it may have its code optimized).

When first executing the JavaScript code, V8 leverages full-codegen which directly translates the parsed JavaScript into machine code without any transformation. This allows it to start executing machine code very fast. Note that V8 does not use intermediate bytecode representation this way removing the need for an interpreter.

When your code has run for some time, the profiler thread has gathered enough data to tell which method should be optimized.

Next, Crankshaft optimizations begin in another thread. It translates the JavaScript abstract syntax tree to a high-level static single-assignment (SSA) representation called Hydrogen and tries to optimize that Hydrogen graph. Most optimizations are done at this level.

-https://blog.sessionstack.com/how-javascript-works-inside-the-v8-engine-5-tips-on-how-to-write-optimized-code-ac089e62b12e

^_*While continue may cause the execution to go to the next iteration, it still counts as an iteration of the loop.

An easy way to see how many times each part of that statement is called would be to add log statements like so and run it in the Chrome console

var arr = [1,2,3,4];

arr.filter(a => {console.log("hit1") ;return a%2 != 0;})

   .forEach(a => {console.log("hit2")});

"Hit1" should print to the console 4 times regardless in this case. If it were to iterate too many times, we'd see "hit2" output 4 times, but after running this code it only outputs twice. So your assumption is partially correct, that the second time it iterates, it doesn't iterate over the whole set. However it does iterate over the whole set once in the .filter and then iterates again over the part of the set that matches the condition again in the .filter

Another good place to look is in the MDN developer docs here especially in the "Polyfill" section which outlines the exact equivalent algorithm and you can see that .filter() here returns the variable res, which is what .forEach would be performed upon.

So while it overall iterates over the set twice, in the .forEach section it only iterates over the part of the set that matches the .filter condition.

The right answer is "it really doesn't matter". Some previously posted answer states that the second approach is O(n+m), but I beg to differ. The same exact "m" operations will also run in the first approach. In the worst case, even if you consider the second batch of operations as "m" (which doesn't really make much sense - we're talking about the same n elements given as input - that's not how complexity analysis work), in the worst case m==n and the complexity will be O(2n), which is just O(n) in the end anyway.

To directly answer your question, yes, the second approach will iterate over the collection twice while the first one will do it only once. But that probably won't make any difference to you. In cases like these, you probably want to improve readability over efficiency. How many items does your collection have? 10? 100? It's better to write code that will be easier to maintain over time than to strive for maximum efficiency all the time - because most of the time it just doesn't make any difference.

Moreover, iterating more than once doesn't mean your code runs slower. It's all about what's inside each loop. For instance:

for (const item of arr) {

  // do A

  // do B

}

Is virtually the same as:

for (const item of arr) {

  // do A

}

for (const item of arr) {

  // do B

}

The for loop itself doesn't add any significant overhead to the CPU. Although you would probably want to write a single loop anyway, if your code readability is improved when you do two loops, go ahead and do it.

If you really need to be efficient, you don't want to iterate through the whole collection, not even once. You want some smarter way to do it: either divide and conquer (O(log n)) or use hash maps (O(1)). A hash map a day keeps the inefficiency away :-)

Now, back to your example, if I find myself iterating over and over and doing the same operation every time, I'd just run the filtering operation only once, at the beginning:

const things = ;

const notThings = ;



for (const item of arr) {

    item.thing ? things.push(item) : notThings.push(item);

}

And then you can freely iterate over notThings, knowing that unwanted items were already filtered out. Makes sense?