High Performance JavaScript: Build Faster Web Application Interfaces

by Nicholas C. Zakas

Of the four loop types provided by JavaScript, only one of them is significantly slower than the others: the for-in loop. Since each iteration through the loop results in a property lookup either on the instance or on a prototype, the for-in loop has considerably more overhead per iteration and is therefore slower than the other loops. For the same number of loop iterations, a for-in loop can end up as much as seven times slower than the other loop types. For this reason, it’s recommended to avoid the for-in loop unless your intent is to iterate over an unknown number of object properties. If you have a finite, known list of properties to iterate over, it is faster to use one of the other loop types

If loop type doesn’t contribute to loop performance, then what does? There are actually just two factors: Work done per iteration Number of iterations By decreasing either or both of these, you can positively impact the overall performance of the loop.

See Sections below for details on how to approach each.

You can also increase the performance of loops by reversing their order. Frequently, the order in which array items are processed is irrelevant to the task, and so starting at the last item and processing toward the first item is an acceptable alternative. Reversing loop order is a common performance optimization in programming languages but generally isn’t very well understood. In JavaScript, reversing a loop does result in a small performance improvement for loops, provided that you eliminate extra operations as a result:

i.e if you can then do a singular lookup like "while(i--)" which only checks whether or not the iterator is positive. It avoids another variable lookup each pass.

The loops in this example are reversed and combine the control condition with the decrement operation. Each control condition is now simply a comparison against zero. Control conditions are compared against the value true, and any nonzero number is automatically coerced to true, making zero the equivalent of false. Effectively, the control condition has been changed from two comparisons (is the iterator less than the total and is that equal to true?) to just a single comparison (is the value true?). Cutting down from two comparisons per iteration to one speeds up the loops even further. By reversing loops and minimizing property lookups, you can see execution times that are up to 50%–60% faster than the original.

Decreasing the work done per iteration is most effective when the loop has a complexity of O(n). When the loop is more complex than O(n), it is advisable to focus your attention on decreasing the number of iterations.

Whether or not it’s worthwhile to use Duff’s Device, either the original or the modified version, depends largely on the number of iterations you’re already doing. In cases where the loop iterations are less than 1,000, you’re likely to see only an insignificant amount of performance improvement over using a regular loop construct. As the number of iterations increases past 1,000, however, the efficacy of Duff’s Device increases significantly. At 500,000 iterations, for instance, the execution time is up to 70% less than a regular loop.

Even though function-based iteration represents a more convenient method of iteration, it is also quite a bit slower than loop-based iteration. The slowdown can be accounted for by the overhead associated with an extra method being called on each array item. In all cases, function-based iteration takes up to eight times as long as loop-based iteration and therefore isn’t a suitable approach when execution time is a significant concern.

i.e array.forEach(() => {});

As it turns out, the switch statement is faster in most cases when compared to if-else, but significantly faster only when the number of conditions is large. The primary difference in performance between the two is that the incremental cost of an additional condition is larger for if-else than it is for switch. Therefore, our natural inclination to use if-else for a small number of conditions and a switch statement for a larger number of conditions is exactly the right advice when considering performance. Generally speaking, if-else is best used when there are two discrete values or a few different ranges of values for which to test. When there are more than two discrete values for which to test, the switch statement is the most optimal choice.

When optimizing if-else, the goal is always to minimize the number of conditions to evaluate before taking the correct path. The easiest optimization is therefore to ensure that the most common conditions are first.

Sometimes the best approach to conditionals is to avoid using if-else and switch altogether. When there are a large number of discrete values for which to test, both if-else and switch are significantly slower than using a lookup table. Lookup tables can be created using arrays or regular objects in JavaScript, and accessing data from a lookup table is much faster than using if-else or switch, especially when the number of conditions is large

Lookup tables are most useful when there is logical mapping between a single key and a single value (as in the previous example). A switch statement is more appropriate when each key requires a unique action or set of actions to take place. High Performance JavaScript: Build Faster Web Application Interfaces (p. 113). O'Reilly Media. Kindle Edition.

Any algorithm that can be implemented using recursion can also be implemented using iteration. Iterative algorithms typically consist of several different loops performing different aspects of the process, and thus introduce their own performance issues. However, using optimized loops in place of long-running recursive functions can result in performance improvements due to the lower overhead of loops versus that of executing a function.

Work avoidance is the best performance optimization technique. The less work your code has to do, the faster it executes. Along those lines, it also makes sense to avoid work repetition. Performing the same task multiple times is a waste of execution time. Memoization is an approach to avoid work repetition by caching previous calculations for later reuse, which makes memoization a useful technique for recursive algorithms. When recursive functions are called multiple times during code execution, there tends to be a lot of work duplication.

Generic memoization of this type is less optimal than manually updating the algorithm for a given function because the memoize() function caches the result of a function call with specific arguments. Recursive calls, therefore, are saved only when the shell function is called multiple times with the same arguments. For this reason, it’s better to manually implement memoization in those functions that have significant performance issues rather than apply a generic memoization solution.

The for, while, and do-while loops all have similar performance characteristics, and so no one loop type is significantly faster or slower than the others. Avoid the for-in loop unless you need to iterate over a number of unknown object properties. The best ways to improve loop performance are to decrease the amount of work done per iteration and decrease the number of loop iterations. Generally speaking, switch is always faster than if-else, but isn’t always the best solution. Lookup tables are a faster alternative to multiple condition evaluation using if-else or switch. Browser call stack size limits the amount of recursion that JavaScript is allowed to perform; stack overflow errors prevent the rest of the code from executing. If you run into a stack overflow error, change the method to an iterative algorithm or make use of memoization to avoid work repetition.

The good news is that all other modern browsers (including IE8) perform far better in this test and do not exhibit the quadratic complexity that is the real killer here. However, this demonstrates the impact that seemingly simple string concatenation can have; 226 milliseconds for 5,000 concatenations is already a significant performance hit that would be nice to reduce as much as possible, but locking up a user’s browser for more than 32 seconds in order to concatenate 20,000 short strings is unacceptable for nearly any application.

This dramatic improvement results from avoiding repeatedly allocating memory for and copying progressively larger and larger strings. When joining an array, the browser allocates enough memory to hold the complete string, and never copies the same part of the final string more than once.

Unfortunately, concat is a little slower than simple + and += operators in most cases, and can be substantially slower in IE, Opera, and Chrome. Moreover, although using concat to merge all strings in an array appears similar to the array joining approach discussed previously, it’s usually slower (except in Opera), and it suffers from the same potentially catastrophic performance problem as + and += when building large strings in IE7 and earlier.

there is a lot you can do to improve regex efficiency. Just because two regexes match the same text doesn’t mean they do so at the same speed. Many factors affect a regex’s efficiency. For starters, the text a regex is applied to makes a big difference because regexes spend more time on partial matches than obvious nonmatches. Each browser’s regex engine also has different internal optimizations.[4]

When you create a regex object (using a regex literal or the RegExp constructor), the browser checks your pattern for errors and then converts it into a native code routine that is used to actually perform matches. If you assign your regex to a variable, you can avoid performing this step more than once for a given pattern.

In most modern regex implementations (including those required by JavaScript), backtracking is a fundamental component of the matching process. It’s also a big part of what makes regular expressions so expressive and powerful. However, backtracking is computationally expensive and can easily get out of hand if you’re not careful. Although backtracking is only part of the overall performance equation, understanding how it works and how to minimize its use is perhaps the most important key to writing efficient regexes.

Here, the regex starts by matching the three literal characters <p> at the start of the string. Next up is .*. The dot matches any character except line breaks, and the greedy asterisk quantifier repeats it zero or more times — as many times as possible. Since there are no line breaks in the target string, this gobbles up the rest of the string! There’s still more to match in the regex pattern, though, so the regex tries to match <. This doesn’t work at the end of the string, so the regex backtracks one character at a time, continually trying to match <, until it gets back to the < at the beginning of the </div> tag. It then tries to match \/ (an escaped forward slash), which works, followed by p, which doesn’t. The regex backtracks again, repeating this process until it eventually matches the </p> at the end of the second paragraph. The match is returned successfully, spanning from the start of the first paragraph until the end of the last one, which is probably not what you wanted. You can change the regex to match individual paragraphs by replacing the greedy * quantifier with the lazy (aka nongreedy) *?. Backtracking for lazy quantifiers works in the opposite way. When the regex /<p>.*?<\/p>/ comes to the .*?, it first tries to skip this altogether and move on to matching <\/p>. It does so because *? repeats its preceding element zero or more times, as few times as possible, and the fewest possible times it can repeat is zero. However, when the following < fails to mat...

Slow regex processing is usually caused by slow failure rather than slow matching. This is compounded by the fact that if you’re using a regex to match small parts of a large string, the regex will fail at many more positions than it will succeed. A change that makes a regex match faster but fail slower (e.g., by increasing the number of backtracking steps needed to try all regex permutations) is usually a losing trade.

Alternation using the | vertical bar may require that all alternation options be tested at every position in a string. You can often reduce the need for alternation by using character classes and optional components, or by pushing the alternation further back into the regex (allowing some match attempts to fail before reaching the alternation). The following table shows examples of these techniques.

This is just a bit faster than the regex-based test with small target strings, but, more importantly, the string’s length no longer affects the time needed to perform the test. This example used the charAt method to read the character at a specific position. The string methods slice, substr, and substring work well when you want to extract and check the value of more than one character at a specific position. Additionally, the indexOf and lastIndexOf methods are great for finding the position of literal strings or checking for their presence. All of these string methods are fast and can help you avoid invoking the overhead of regular expressions when searching for literal strings that don’t rely on fancy regex features.

Intensive string operations and incautiously crafted regexes can be major performance obstructions, but the advice in this chapter helps you avoid common pitfalls. When concatenating numerous or large strings, array joining is the only method with reasonable performance in IE7 and earlier. If you don’t need to worry about IE7 and earlier, array joining is one of the slowest ways to concatenate strings. Use simple + and += operators instead, and avoid unnecessary intermediate strings. Backtracking is both a fundamental component of regex matching and a frequent source of regex inefficiency. Runaway backtracking can cause a regex that usually finds matches quickly to run slowly or even crash your browser when applied to partially matching strings. Techniques for avoiding this problem include making adjacent tokens mutually exclusive, avoiding nested quantifiers that allow matching the same part of a string more than one way, and eliminating needless backtracking by repurposing the atomic nature of lookahead.

A variety of techniques exist for improving regex efficiency by helping regexes find matches faster and spend less time considering nonmatching positions (see More Ways to Improve Regular Expression Efficiency). Regexes are not always the best tool for the job, especially when you are merely searching for literal strings. Although there are many ways to trim a string, using two simple regexes (one to remove leading whitespace and another for trailing whitespace) offers a good mix of brevity and cross-browser efficiency with varying string contents and lengths. Looping from the end of the string in search of the first nonwhitespace characters, or combining this technique with regexes in a hybrid approach, offers a good alternative that is less affected by overall string length.