5 Code Optimization Techniques To Speed Up Your Programs
Make it work first, then make it fast. This is one common principle many professional programmers go by. At first, you may write your code using whichever approach seems the most intuitive to save development time on the draft. After you got a working implementation, you may want to optimize it by carefully choosing which techniques data structures work best in your specific case.
In this article, we'll explore five language-agnostic methods you can use to improve your code runtime. The following concepts are generic and can be applied to any programming language.
Loop-invariant extraction
Consider the following Python code that checks a list of strings against a regular expression to find all the matches:
import regex as re
# Get some strings as input
strings = get_strings()
# List to store all the matches
matches = []
# Iterate over the input strings
for string in strings:
# Compile the regex
rex = re.compile(r'[a-z]+')
# Check the string against the regex
matches = rex.findall(string)
# Finally, append the matches to the list
matches.extend(matches)Loops repeatedly apply a set of instructions to a varying input. With this in mind, can you spot any operation that doesn't change in the code above?
The statement rex = re.compile(r'[a-z]+') operates on a constant input: the regex string. For every iteration of the loop, this statement does exactly the same thing, independently from the loop's input. If we were to extract this invariant statement and execute it once before the loop, the code would still have the same overall behavior while saving some CPU cycles.
import regex as re
# Get some strings as input
strings = get_strings()
# List to store all the matches
matches = []
# Compile the regex only once before the loop
rex = re.compile(r'[a-z]+')
# Iterate over the input strings
for string in strings:
# Check the string against the regex
matches = rex.findall(string)
# Finally, append the matches to the list
matches.extend(matches)As a rule of thumb, every variable or operation that is loop-invariant (doesn't depend on the loop's input or state) should be extracted out of the loop as long as the code logic remains the same.
Sometimes, compilers will apply this kind of Optimization to your code automatically. However, they are not guaranteed to always detect redundant statements, and interpreted languages don't have the privilege of ahead-of-time optimization, so you should keep an eye on loop-invariant code.
Enum states and types
When representing a variable object state, beginner programmers might think of using a string. Consider the following Rust code:
struct Door {
pub state: &'static str,
}
impl Door {
fn new() -> Door {
Door { state: "closed" }
}
}
fn main() {
// Create a new door objetc
let mut door = Door::new();
// Set the door state to open
door.state = "open";
// Check if the door is open
if door.state == "open" {
println!("The door is open!");
}
// Set the door to another state
door.state = "semi-closed";
// Commit a typing mistake
if door.state == "semi-clsed" {
println!("This won't get printed!");
}
}While strings are an intuitive solution, there are a few problems with that. First, string states are vulnerable to typing errors, as shown by the last if statement. Also, which are the possible states?
Anyway, we're here to talk optimization. String comparison is terribly slow, as you have to check every single character to know whether they are equal. Also, strings require significantly more bytes to store than other alternatives. For example, you can use an enum to represent the object state and not worry about typing mistakes while harnessing the speed of integer comparison.
struct Door {
pub state: DoorState
}
impl Door {
fn new() -> Door {
Door {
state: DoorState::Closed
}
}
}
enum DoorState {
Open,
Closed,
SemiClosed,
Locked,
}
fn main() {
// Create a new door object
let mut door = Door::new();
// Set the door state to open
door.state = DoorState::Open;
// Check the door state
if matches!(door.state, DoorState::Open) {
println!("The door is open!");
}
// Match all possible states
match door.state {
DoorState::Open => println!("The door is open!"),
DoorState::Closed => println!("The door is closed!"),
DoorState::SemiClosed => println!("The door is semi-closed!"),
DoorState::Locked => println!("The door is locked!"),
}
}Enums are an abstraction based on integers and require very little memory to store. On top of that, enums are usually passed by value, thus avoiding the dereferencing overhead during operations like comparison. Many languages support enums natively, and most allow for such a pattern.
Algebraic and boolean operations
Consider the following code snippets that include conditional statements:
def is_zero(number):
if number == 0:
return True
else:
return False
def count():
counter = 0
MAX = 10
for i in range(100):
counter += 1
# Reset the counter when it reaches MAX
if counter == MAX:
counter = 0If-statements are compiled into conditional jump instructions, which can make your code notably slower when compared to linear branch execution. Sometimes, conditional statements can be substituted with an equivalent expression that is usually faster, depending on its length and operations.
Here are the previous functions optimized using boolean and arithmetic expressions instead of conditionals:
def is_zero_algebra(number):
# The result of comparison is already a boolean
return number == 0
def count_algebra():
counter = 0
MAX = 10
for i in range(100):
# Use the remainder operator to reset the counter
# when it reaches MAX
counter = (counter + 1) % MAXHowever, you should always perform a benchmark on any supposedly optimized alternative to check whether it's actually faster.
Memoization
No, it's not a spelling mistake. Memoization is an algorithm optimization technique that consists of memorizing the output of a function along with its input. When dealing with resource-intensive functions that are going to be called multiple times, you can store the input and result in a map data structure so that you don't have to compute the function again if the input is the same.
A classic example of a function that can be improved with memoization is computing the Fibonacci sequence. Consider the following code that calculates the nth number of the Fibonacci sequence:
def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n-1) + fibonacci(n-2)
R = 30
for i in range(R):
fibonacci(i)For small inputs n, the function doesn't take much time to execute. However, due to its time complexity of O(2ⁿ), larger input values will result in a significantly longer runtime.
Consider now this other approach that takes advantage of memorization:
# Use a class to implement the memoization technique
class MemoizedFibonacci:
def __init__(self):
# When the object is created, initialize a map
self.memo = {}
def fibonacci(self, n):
if n <= 1:
return n
elif n not in self.memo:
# Store the input-output pair in a map data structure
self.memo[n] = self.fibonacci(n-1) + self.fibonacci(n-2)
# Return the stored output value that corresponds to the given input
return self.memo[n]
memoized_fibonacci = MemoizedFibonacci()
for i in range(R):
memoized_fibonacci.fibonacci(i)As you can see from the graph below, memoization greatly improves the function runtime:
This is because this memoized function's time complexity is roughly linear.
Use a case-specific data structure
One common example of data structure choice is the ubiquitous linked list vs array dilemma. Do you need the O(1) insertion time of linked lists or do you need the fast random indexing of arrays? When it comes to the choice of data structure, you have to compare the pros and cons of each option to find what fits your case best. Sometimes, you may even want to implement a custom-made data structure to fit exactly your requirements.
Here are a few other examples of common data structure choices for optimization:
- Copy-on-write implementations (COW). Structures that implement COW allow you to efficiently and safely pass data around via a shared immutable reference. The data gets copied only if you actually try to mutate it, thus saving time on pointless operations.
- Circular buffers are a common alternative to traditional arrays when implementing queue-like behavior or for caching data.
- Lookup tables and hash tables are used for fast indexing of data or handling different cases efficiently without branching.
- Parsing tables are a combination of lookup and hash tables nested in a tree-like fashion that allows you to efficiently and concisely parse structured data without having to write intricated and error-prone code. They are extensively used in compilers and classification algorithms.
Key takeaways
Optimizing code is not a simple job. You have to find the relevant bottlenecks first. Then, check carefully whether there are any redundant operations or a more direct approach to solve a problem. You may need to sketch your ideas out onto a piece of paper to better visualize algorithms, memory layouts, and data structures. Lastly, perform benchmarks and tests to see if you actually made your code any better or you broke something.
I hope you enjoyed this article. If you have any thoughts, please share them in a comment. Thanks for reading!
If you're interested in learning more about code optimization, check out the following article about lookup tables and hash tables:
Get Rid of Excessive If-Else Statements With Lookup and Hash Tables
