SECRET OF CSS

Algorithms and their impact on performance


How to choose the right algorithm?

Website loading optimization page speed (Image licensed to the author)
Website loading optimisation (Image licensed to the author)

“Hi, Héla! Can you help me check why my code is taking so long?”, “Hi Héla! Can you help me check why my code is consuming a lot of memory?”, “When I test my code locally everything is fine, but in production, my code hangs!”

These are my daily problems, and I love them! Why? Because it gives me the opportunity to be close to the machine (computer) and low-level execution. To understand a machine, it is necessary to understand its inner workings, like a mechanic or a doctor!

Motherboard City (Image licensed to the author)

I’m convinced that if I want to write a performance code, I have to start from the low level:

  • the required steps (instructions) to run the algorithm
  • the amount of memory required to hold the algorithm code
  • the amount of memory required for input data
  • the amount of memory required for all output data

In computer jargon, the required steps reflect Time Complexity and the required amount of memory reflects Space Complexity.

By reducing the temporal and spatial complexities we gain resources and money. We cannot respond to the lack of performance and resources by increasing and modifying the hardware each time.

The software we write should be effective and efficient!

Well, gorgeous! But, let’s stop a bit to simplify what I mean!

Let’s say you are an airplane pilot and you need to fly from France to Istanbul. You have a limited amount of kerosene because the plane’s fuel tank is limited. What are you going to do? Yeah, good! You will choose the short trajectory! As a result, you will save time and consumption!

The same goes for code: in order for it to consume fewer resources (CPU, memory, GPU), we should always choose the optimal path.

If the software was a car, then we can say that the design and the architecture make it possible to have a good and beautiful carcass: resilient, scalable, extensible, maintainable, etc. On the other hand, the low level makes it possible to have a high-performance car that’s efficient. Aha, external beauty is not enough. The code must also be beautiful from the inside!

Note that in this article, when I talk about performance, I talk about the execution speed and when I talk about consumption, I talk about the allocated memory.

Well, how are code instructions executed internally? Let’s take a look at this illustration:

1*8O8rXh8rZE3fjElVpwbRMQ
The life of an instruction (Image by the author)
  • The CPU executes a program that is stored as a sequence of machine language instructions in the main memory.
  • It does this by repeatedly reading or retrieving an instruction from memory and then executing that instruction.
  • When finished, the result will be saved back into memory.

That’s all, folks!

You can see that we need memory to store the program and the final and intermediate results.

Now is the time to give you my magic recipe for solving algorithm-related performance and memory issues!

My recipe includes:

  • choosing the right algorithm
  • choosing the right data structures
  • some techniques to analyze and validate our choices

In this article, I will focus on choosing the right algorithm with some techniques to analyze and validate our choices. In my future articles, I will explain the other parts. Enough talking, let’s start!

Just wait, what’s Big O?

Let’s take a look at this graph:

1*9QZNKa85t ul FG1YqOCyA
Limits of Algorithm Variation (Image by the author)
min: when we have a reduced number of input data (usually locally).
max: when we have a lot of input data (usually in production).
f(min) = minimum required steps to execute the code.
f(max) = maximum required steps to execute the code.

In the computer world, we call:

  • f(max): O(N), Big O of N.
  • f(min): Ω(N), Big Omega of N.
  • Big O is used to describe the worst-case running time for an algorithm.
  • Big Ω is used to describe the best-case running time for a given algorithm.

Aha, magic!

In this article, I’ll focus on the Big O (the nightmare).

“Big O tells you about the proportional relationship between the data and the algorithm’s efficiency. It describes exactly how the number of steps increase as the data increases.” — A Common-Sense Guide to Data Structures and Algorithms, Second Edition, Jay Wengrow

In short, the Big O shows how the performance of an algorithm changes as the data changes? If there are N data items, how many steps will the algorithm take?

Big O will be our metric to measure the speed of an algorithm.

An algorithm is considered fast if it requires a reduced number of instructions (or steps) to execute. Noted!

Wait, what about memory?

Do you know we can also use Big O for space complexity? Aha, we just need to rephrase the notions and the questions.

For memory consumption, we have to say: if there are N data elements, how many memory units will the algorithm consume? Ta-da!

How will Big O help us then?

Let’s wrap up:

  • Performance: If there are N data elements, how many steps will the algorithm take?
  • Memory: If there are N data elements, how many memory units will the algorithm consume?

Big O helps us predict the performance and consumption of an algorithm even before it is executed!

Let’s see the power of Big O in action!

Bubble sort

Bubble sort is a simple sorting algorithm that compares a pair of adjacent elements in a list. If an element is not in the right order, we swap the element with the one before. Otherwise, the element remains in the same place. Whoa, touchy algorithm for large data!

Here’s some code:

Vintage Bubble sort

Execution steps:

"data input : ", [89, 13, 57, 44, 71, 51]
"data i : ", [89, 13, 57, 44, 71, 51]
"data i : ", [13, 57, 44, 71, 51, 89]
"data i : ", [13, 44, 57, 51, 71, 89]
"data i : ", [13, 44, 51, 57, 71, 89]
"data i : ", [13, 44, 51, 57, 71, 89]
"data i : ", [13, 44, 51, 57, 71, 89]
"sortedTab : ", [13, 44, 51, 57, 71, 89]

The efficiency of Bubble Sort:

The first loop needs data.length steps:

for (let i = 0; i < data.length; i++) {

The second loop also needs data.length steps:

for (let j = 0; j < data.length; j++) {

If data.length = n, then the Bubble sort algorithm has a worst-case time complexity of O(n²). OMG!

Since we are modifying the array in place without creating copies or temporary arrays, the Bubble sort has a space complexity of O(1).

When the array elements are few and the array is nearly sorted, bubble sort is effective and efficient.

Insertion sort

The idea behind Insertion Sort is that the array is virtually split into a sorted part and an unsorted part. The values of the unsorted part are selected and placed in the correct position in the sorted part.

It’s like sorting playing cards:

  • It is assumed that the first card is already sorted in the card game.
  • Then we select an unsorted card.
  • If the selected unsorted card is greater than the first card, it will be placed on the right side.
  • Otherwise, it will be placed on the left side.
  • Similarly, all unsorted cards are taken and put in their exact place.
1*A72MRZllItOB0HmkaYhSYA
Ordered cards (Image licensed to the author)

Whoa, another touchy algorithm for large data!

Four types of steps occur in Insertion Sort: removals, comparisons, shifts, and insertions.

Here’s some more code:

Vintage Insertion Sort

Here’s some execution steps:

"data input : ", [89, 13, 57, 44, 71, 51]"data i : ", [89, 13, 57, 44, 71, 51]
"data i : ", [13, 89, 57, 44, 71, 51]
"data i : ", [13, 57, 89, 44, 71, 51]
"data i : ", [13, 44, 57, 89, 71, 51]
"data i : ", [13, 44, 57, 71, 89, 51]
[13, 44, 51, 57, 71, 89]

The efficiency of Insertion Sort:

The bubble sort algorithm has a worst-case time complexity of O(n²) and a space complexity of O(1). OMG!

Linear search

This is the simplest, most native, and intuitive algorithm:

  • Linear search will accept an array and a target value.
  • Start searching from the beginning of the array.
  • Check if that value equals the target.
  • If so, stop and return that value’s index.
  • If not, move on to the next element.

Whoa. Simple but expensive and greedy especially for large data!

Here’s even more code:

Vintage Linear Search

The efficiency of Linear Search:

  • If the target value is at the beginning, the algorithm will always run at constant time, O(1).
  • If the target is the last element in the array, then the algorithm will make n comparisons (n being the length of the input data).
  • If the target element is somewhere in the middle of the array, then the time complexity will be approximately O(n/2).

Linear Search has a time complexity of 1 — linear time complexity.

Linear Search has a space complexity of O(1) — constant space. It uses no auxiliary data structures to find the target value.

Whoa, a touchy search algorithm for large data!

Binary search

The idea behind binary search is to search over a sorted array by repeatedly dividing the search interval in half. I have a special love for this algorithm because it reminds me of our games to guess a number: lower, upper, and more!

More code for you:

Vintage Binary Search

The efficiency of Binary Sort:

The time complexity of the binary search algorithm is O(log n).

  • The best-case time complexity would be O(1) when the central index would directly match the desired value.
  • The worst-case scenario could be the values at either extremity of the list or values not in the list.

In the iterative method, the space complexity would be O(1). While in the recursive method, the space complexity would be O(log n).

Not bad! We can still improve, see!

Merge sort

If you want to see the “Divide and Conquer” strategy in real life, this algorithm will be the best example.

Here’s how Merge sort works:

  • it divides the complete list into sublists or into “n” sublists.
  • it continues this process recursively until each sub-list has one element.
  • once this “divide and conquer” process is completed, it starts merging each sub-list to create a sorted list.

Break down the problem into smaller subproblems until they become simple enough to solve directly. I love it!

Here’s even more code for you:

Merge sort

Now, let’s see the code step by step:

Consider this input data :
[5, 7, 1, 4, 6, 3, 2]
Divide the array into two sub-arrays :
[5, 7, 1] and [4, 6, 3, 2]
Again each array will be divided into two subarrays :
[5], [7, 1] and [4, 6], [3, 2]
Continue over and over :
[5], [7], [1], [4], [6], [3], [2]
[5, 7], [1, 4], [3, 6], [2]
[1, 4, 5, 7] [2, 3, 6]
[5], [7], [1], [4], [6], [3], [2]
Now the first step is complete as each array has only one item in it.Now we will compare the array elements and merge these single item arrays into pairs :
[5, 7], [1, 4], [3, 6], [2]
[1, 4, 5, 7] [2, 3, 6]
[1, 2, 3, 4, 5, 6, 7]

Efficiency of Merge Sort:

Time Complexity of Merge Sort is O(n log(n)).

The space complexity of Merge Sort is O(n).

Merge Sort is very fast for a sorting algorithm, but the gains in speed come with the cost of taking up more space in memory. The larger the array, the more arrays that have to be stored in memory (from dividing them up). Ops!

The quick Sort algorithm also follows the Divide and Conquer approach. It divides elements into smaller parts based on some condition and performs the sort operations on those divided smaller parts. Aha, it works well for large datasets!

Yes, more code for you:

Quick sort

Here’s more explanations of what we’re working on:

1*OYA9J1pj WhhWeURDFfXXQ
Quick Sort Execution Steps (Image by the author)

The efficiency of Quick Sort:

  • The average case time complexity of Quick Sort is O(n log (n)) which is the same as Merge Sort. Even with a large input array, it performs very well. It provides high performance and is comparatively easy to code.
  • It doesn’t require any additional memory.
  • The main disadvantage of Quick Sort is that a bad choice of pivot element can decrease the time complexity of the algorithm down to O(n²).

Whoa, it’s not a stable sorting algorithm!

Tim Sort

Tim Sort is a hybrid stable sorting algorithm, derived from Merge sort and Insertion sort, designed to perform well on many kinds of real-world data. Whoa!

It was developed by Tim Peters in 2002 to replace Python’s previous sorting algorithm. It has since been adopted in Java’s OpenJDK, the V8 JavaScript engine, and the Swift and Rust languages. Aha, this is a testament that Tim Sort is a performant sort!

For the curious:

Tim Sort Python Definition

Tim Sort Python Implementation

Before we continue, let me say that if you don’t know Tim Sort’s algorithm, you are really missing an important and interesting part of computer science!

Here’s an open source implementation example (JavaScript):

Efficiency of Tim Sort:

  • Tim Sort is an adaptive sorting algorithm that needs O(n log n) comparisons to sort an array of n elements.
  • The space complexity of Tim Sort is O(n).

It’s time to sum up what we’ve seen so far!

1*PZ93ikmhhMYoqpXnPSFnAw
Comparisons of sorting algorithms (Image by the author)

Change array in-place

By default, I adopt the functional approach in my code. No mutations are allowed and all functions are pure. However, before I create copies, especially for large amounts of data, I have to make sure that the language offers concepts like shallow copies, structural sharing or copy-on-write (we’ll see them right after). If not, I opt for the “change array in-place” strategy.

The above function changes input data in place:

const inPlaceChange = (data) => {
for (let i in data) {
data[i] = data[i] * 2;
}
}
const tab = [1, 2, 3, 4];console.log(tab) // [1, 2, 3, 4]inPlaceChange(tab);console.log(tab) // [2, 4, 6, 8]

The above function creates a copy before mutating the array:

const copyChange = (data) => {
const dataCopy = [
...data
]
for (let i in dataCopy) {
dataCopy[i] = dataCopy[i] * 2;
}
return dataCopy;
}
const tab = [1, 2, 3, 4];console.log(tab) // [1, 2, 3, 4]const newTab = copyChange(tab);console.log(tab) // [1, 2, 3, 4]
console.log(newTab) // [2, 4, 6, 8]

Be careful before creating copies. We generally avoid deep copying for big data and instead use shallow copying or some techniques like structural sharing and copy-on-write. Let’s see!

Structural sharing

When we adopt a functional style and data immutability, we handle data changes by creating a copy (new version) of the data instead of mutating the data in place, without impacting performance.

Structural sharing provides an efficient way to share data between multiple versions of it, instead of copying the entire data. This is similar to how git works. Whoa!

0*FRra15 wWdtN7XVF
Wikipedia — Persistent data structure

In the above schema, ys shares the structure of xs.

Copy-On-Write (cow)

“Copy-on-write” means that everyone has a single shared copy of the same data until it’s written, and then a copy is made. Copying large and complicated data can be an expensive operation. If the copy is never modified, then there’s no need to incur this cost. Super!

More details below:

Timsort is available starting with V8 v7.0 and Chrome 70!

Well, it was more or less a long journey inside the algorithms.

It is clear that the choice of the algorithm has a direct impact on the performances and the used resources in particular the memory.

Thanks to the inventors and mathematicians who provided us with a metric to predict more or less exactly the behaviour of an algorithm before its real execution.

At this level some will ask me: why do we have to study and know this part if the programming languages already provide native methods for sorting, searching, etc.? That’s a good question, and here’s my answer.

First, we need to know what we use in case of a problem in production or in case of debugging. If the internal algorithm of the native method implements a Quick Sort or a Tim Sort, we are reassured. Otherwise, we must raise an alert and improve.

Then, sometimes some languages do not natively implement optimal methods.

It’s very good to know and master the Big O concept to be able to predict problems before they appear. Everything was well calculated and chosen before the execution.

To improve performances and resources consumption you should be close to low level. Big O, time complexity and space complexity offer a good abstraction between soft and hard parts.

Aha, do you now know how to choose the right algorithm? Yeah, good, and you know how according to “Big O” !

The Big O is not just for sorting and searching algorithms, but it is a general concept applicable to all types of algorithms. Sort and research are usually used as a simple example to show the application of the Big O.

Finally, I wish you a good trip in the world of algorithm optimisation and in the universe of the Big O. O! O! Big O!

See you soon in a future article!



News Credit

%d bloggers like this: