Algorithms in Everyday Tasks

Originally published on TechBullion.

I often hear from front-end developers, that the ability to solve algorithmic problems, which are frequently assessed in interviews, is completely unnecessary for regular developers. They believe the same applies to the algorithms and data structures used in these tasks.

I completely disagree. Firstly, these challenges greatly enhance attention, concentration, problem-solving skills, and teach the importance of carefully considering architecture before implementation. Secondly, understanding algorithms and data structures — even if you rarely encounter them directly — helps to better grasp how everything in IT operates under the hood.

Below, I will illustrate with several examples how closely related some well-known algorithms and data structures are to the everyday tasks of a front-end developer, and how they can be beneficial in these contexts.

Storage

An Array is a data structure representing a collection of a predefined number of elements of the same type, with each element corresponding to an index. Array elements are stored in memory consecutively as a single contiguous block.

Reading and writing occur in constant time (the access time does not depend on the size of the array). This is achieved by calculating the offset in memory from the start of the array based on the data type and the index of the sought element.

Front-end development is closely tied to the use of arrays for data storage, and it seems straightforward. However, one of the most interesting examples of how algorithms can enhance life is that the V8 engine, responsible for executing JavaScript in Google Chrome and applications built on Node.js and Electron, does not always store arrays as described above.

JavaScript Arrays

Unlike classical arrays, JavaScript arrays are dynamic (not of fixed length) and can store mixed data types. V8 employs various optimizations to make working with JavaScript arrays convenient and fast. Here are some of them:

• When a new empty array is created, only a small amount of memory for a couple of elements is reserved. Each time more memory is needed, the engine increases the allocated space by 1.5 times, reassigning the entire array. This means developers don’t need to specify the size themselves.

• When adding elements to an array, their types are tracked. Depending on the type, the engine selects the most speed-efficient storage strategy. For instance, arrays containing fixed-size data types (integers, floats, or booleans) are stored as classical arrays with very fast access through calculated memory offsets. However, once a string is added, the array is forced to convert into an array of references to separate data objects, making it slightly slower.

• For arrays with gaps in the data (for example, when a new array is created and values are written while skipping indexes), V8 stops treating them as arrays altogether and begins to use a HashMap. This significantly saves memory but slightly slows down code execution.

A HashMap is a data structure that represents a collection of elements with unordered keys (including strings), functioning as an associative array. It is implemented based on a standard array.

To obtain an ordered index from an unordered key, the key undergoes a hash function, yielding a number. The remainder of this number divided by the maximum number of elements in the array becomes the ordered index. Two or more different keys can hash to the same index (this is called a collision) and are placed there as a linked list. If there are many collisions, the size of the array increases, and the keys are recalculated based on the new length and relocated.

Thanks to this structure, reading and writing also occur in constant time (but with more operations compared to reading/writing from an array).

With these optimizations, you truly don’t need to worry about the underlying data structures, but understanding their principles can help you write faster code: avoid mixing different data types in arrays, refrain from creating arrays with many gaps, and try to specify the array size in advance.

An example of reduced read speed from a sparse array due to its deoptimization into a HashMap.

You can read more about how V8 handles different data formats and organizes their storage in the official blog.

Sorting

Front-end tasks often include sorting challenges. If you’ve ever prepared for a technical interview, the term “sorting” likely brings to mind the QuickSort algorithm. This is one of the most well-known and widely used general sorting algorithms. Interestingly, QuickSort, despite its name, is not the fastest.

There are general algorithms with better time complexity, like MergeSort or HeapSort, which operate at n log n at worst. However, unlike them, QuickSort performs much better in practice, has a simpler structure, uses less additional memory during execution, and requires fewer accesses to memory.

In the V8 engine, QuickSort was used for sorting until the engine switched to TimSort, developed in 2002 for Python (and later adopted in Swift and Rust). TimSort is a general algorithm that can sometimes operate in linear time by analyzing input data and identifying previously sorted segments to eliminate unnecessary work.

A TimSort example clearly demonstrates how crucial it is to leverage knowledge about the input data. If you know what you want to sort, you can gain speed in the sorting process. Here are some examples.

TypedArray

In JavaScript, the default sorting method sorts lexicographically, comparing array elements as strings in alphabetical order.

If you want to sort an array of numbers (which is usually the case), you need to provide a comparator function like (a, b) => a – b to inform the engine how to compare the elements. However, invoking your function for each pair of elements slows down the sorting process.

A better option is to use typed arrays. In this case, the engine will clearly know the type of the data being sorted and can sort the contents in ascending order without a comparator.

RadixSort

If you, unlike V8 (which always allows specifying a comparator), are willing to sacrifice versatility, you can achieve stable linear sorting time, resulting in significant speed gains. This is made possible by the Radix Sort algorithm.

RadixSort is a sorting algorithm that does not use comparisons of the elements being sorted. During the sorting process, elements are distributed into buckets based on their digits starting from the most significant. For elements with multiple digits, this distribution process repeats cyclically for each subsequent digit.

This achieves a linear runtime of m + n, where n is the number of elements and m is the maximum number of digits.

A comparison of standard, typed, and radix sorting of integers in ascending order (radix sort based on the hpc-algorithms package).

Searching

In front-end development, situations often arise where you need to quickly find something in data. Here, trees come into play, as their main purpose is to reduce search time from linear to logarithmic by discarding unsuitable options.

One simple example of a search task is quickly retrieving either the minimum or maximum element from a periodically updated collection, essentially organizing a priority queue.

Solving such a task with standard or even Radix sorting would be too costly, as it would require re-sorting the array after every possible update. Instead, a binary heap can be used.

A BinaryHeap is a binary tree where each node contains a value greater than any of its descendants (MaxHeap) or vice versa (MinHeap).

The order of the children at the same level does not depend on their values and is not important. Every layer of the tree, except the last, must be fully filled, and the last can be partially filled but must be filled strictly from left to right. This structure can be easily accommodated in an array. If you sketch a heap on paper as a tree (with the root on top), you will notice that every path from the root to the leaf is a correctly sorted sequence.

Adding a new element takes logarithmic time, as it requires not a full re-sort but a partial rearrangement of one of the sequences from root to leaf. Retrieving the maximum (for MaxHeap) or the minimum (for MinHeap) is performed in constant time.

You have likely reaped the benefits of this approach many times in terms of front-end speed. This is because heaps are used in React to organize the task scheduler for rendering.

In web development, trees are ubiquitous: Trie (prefix tree) helps implement autocomplete in input fields, tree structures store JS objects in V8, layered linked trees speed up the process of applying changes in the virtual DOM in React, and even the DOM and CSSOM are trees.

Conclusion

Data structures and algorithms are used everywhere, and if they aren’t immediately visible, they are often hidden behind familiar native methods and functions of libraries and frameworks.

By being aware of them, you can write efficient code that unlocks the potential of the algorithmic approaches behind them. In some cases, thanks to the specialized algorithms you apply, your interpreted JS code may outperform optimized standard solutions of your runtime environment.