Long time ago I saw a pull request in which two developers were arguing about the loop performance. The argument turned into a long discussion. Everyone spammed links to threads on Github and articles to prove their point. Honestly, it was quite hilarious.
This got me curious... I have never had time to check which of the available options is the best. The articles that covered this topic were superficial. Therefore, I decided to educate myself from the inside out. Let's discuss this in today's post.
Experience and knowledge work wonders 🚀.
I have proven to you that time varies. Now, we need to determine how we can figure out which loop is faster. We will use a technique that is called sampling. Instead of calling the function once and comparing it with the result of another program, we will run it a thousand/million times and calculate the total time.
Run the given code on your computer and check how running programs affects the result of any 💻 function.
2. We're sampling and collecting
We have a function measure(), so now we need to run it n times.
3. Displaying the results
At this stage we have clean data, but who wants to go through it manually. We need to sum the values and round them to four decimal places. If something lasts 0.00001532 seconds then - let's agree - the user is unlikely to notice it.
What do we have here? We called the sum function three times and passed to it six numbers from 1 to 6. The total duration of these calculations was 0.0101 seconds.
JS is weird. Run the code three times and see that the values are different.
4. Loops and recurrence
We need a several implementations of sum numbers function. Later we'll compare the result with a ready-made tool for checking optimization and we will draw conclusions.
Now we transfer the same data set to each of them.
I assume you were suprised by the absence of the recursiveSum call. It is intentional. Here a small spoiler - this implementation will have the worst result. Bad enough to cause a stack overflow 💥.
5. Let's check the results
When there is little data (100-1000) then you can't see much difference. It even looks like the results are random (it takes such a short time that there is no difference which implementation we used). Everything changes when there is more data. Suddenly, it turns out that the for loop always appears in the first place, and the difference between the rest is significant.
Tests in our mini app
Why is this happening? Modern processors are very fast. If they are not overloaded then there isn't much difference among times. When increasing the set of numbers the processor begins to "tire" (or rather the browser). That's why we see differences.
One more point. Why then the methods built into prototype Array are slower if they use a for loop inside? This is due to the additional operations that we as developers agree to, gaining on the code clarity and losing on its speed (according to the principle of something for something). Used abstractions like forEach and reduce performs additional operations at each iteration, so this accounted for their inferior performance.
Check specification and you'll see that there is additional if statement.
Special thanks to Paweł Wolak for help here.
6. What was the result of the battle-tested tool?
There are really a lot of them on the Internet, and I decided to choose the prettiest one, that is perf.link (such an affliction of a front-end developer). I dropped the earlier examples and came up with exactly the same verdict. Loop for led the way with larger sets of numbers, and with smaller ones it was impossible to judge which is the best. I also checked the recursive function. Just as before, it stood off from the very beginning.
As you can see, recursion doesn't work.
Result for 100000 numbers
There are still nice libraries available. I have used Benchmark.js, which in my opinion is great and similar to writing regular unit tests.
After this post you already know that measuring computational complexity can be "tricky." It turns out that it's hard to tell which loop is fastest.
The syntax of language is important, but not as much as algorithm and skills of programmer on side of which stands answer to the question - which solution is faster?
Remember that memory complexity is also important and sometimes even more important. I think we'll go through it another time.
If you enjoyed it, be sure to visit us on Linkedin where we regularly upload content from programming.
"A human learns all life and usually does it by reinventing the wheel. From childhood to the end of his days." - a quote from a book, may you know of which one?