-
Notifications
You must be signed in to change notification settings - Fork 0
Complexity
Inside every large program is a small program struggling to get out.
-- Tony Hoare
In the beginning of your programming journey, you will take complex programs for granted. You will assume that your code is complex because the real-life problem it attempts to solve is complex. This is almost never the case. The vast majority of problems you will solve with code are embarrassingly simple. The intrinsic complexity required to solve the problem may only be a small fraction of your program's total complexity compared to the unnecessary (i.e. accidental) complexity that arises from your code wrestling with itself.
Most people use complexity in the general sense, because it's not easy to pin down what we really mean. Something that's simple for a human to understand might be complex for a computer to process, and vice-versa. But there is surprising overlap: rarely do I come across a situation where we can reduce some expression into an informationally simpler form that is now harder for a human to understand. Humans can only store so many things in their head so the fewer things that need to be stored, the easier the comprehension.
There are point based systems out there that allocate points to certain constructs so you can get a feel for when a chunk of code is particularly complex, but the main culprits are unnecessary duplication and unnecessary conditionals (if statements and switch statements). Many of the language constructs we use directly address these problems (for example, duplication can often be extracted out into functions, and subtype polymorphism is often a good substitute for switch statements)
Complexity in your code has two main costs:
- cognitive overhead
- bugs
Cognitive overhead slows down development time and creates a vicious cycle where you work around complexity by adding more complexity rather than stripping things down to what's necessary. This complexity gives rise to bugs which cost you even more time because instead of refining your code you're scouring it for bugs.
So how does code become unnecessarily complex?
There are many ways to express the same thing, but some are simpler than others. For example, consider the following code:
if value {
return value
} else {
return fallback
}
This says that if value is falsey we'll return it, otherwise we'll return fallback. But another way of writing the same thing is:
return value || fallback
The second approach is simpler than the first in part because it removes duplication. The first approach contains value twice whereas the second only contains it once. This duplication increases the cognitive cost because you have more code to read before you understand what it's doing, and it increases the chance of bugs because as you write the code you have more locations to accidentally type the wrong variable name.
Duplication is bad but sometimes the abstraction that replaces the duplication is worse. If removing duplication comes at the cost of introducing a new abstraction (for example, a function), you need to consider whether the new abstraction actually introduces more complexity on net. Replacing the following:
foo = a + b - c
bar = b + c - d
with
function plusMinus(a, b, c) {
return a + b - c
}
foo = plusMinus(a, b, c)
bar = plusMinus(b, c, d)
Doesn't really reduce the complexity. You've removed the duplication of the +/- expression but you've introduced a new function and two function calls. Not only have you increased the complexity of the code that needs to be run, you've increased the cognitive load on the reader.
Whether you remove or retain duplication should ultimately come down to the question: is this duplication essential or coincidental? With the above case, the chances are it's only a coincidence that you have an 'a + b - c' type expression for both foo and bar. That means that as new requirements come in, the two expressions will not evolve in lockstep and will instead diverge. If you clutch onto your abstraction beyond that point, that's when things really start to get complex. More on that here.
The 'problem domain' is the real-life stuff that your program is trying to encode in order to solve some problem. Consider the contrived example where a person can either be stationary or walking, and we want to keep track of that for the sake of animating that person. You might encode the possible states as a single boolean variable: isMoving. If isMoving is false then the person is standing still, otherwise they're walking.
What happens if you need to now handle a new state: the person is running? One approach is to introduce a new boolean variable: isRunning, which we only care about if isMoving is true. Only two variables into our program and we have already introduced unnecessary complexity. Two boolean variables means four possible permutations:
!isMoving && !isRunning
isMoving && !isRunning
isMoving && isRunning
!isMoving && isRunning
But we said we would only care about our isRunning variable if isMoving is true! Easier said than done. Do you trust yourself to remember to type isMoving && isRunning every time you want to check if a person is running? I certainly don't. By using two booleans to model three possible states, we have allowed for an impossible state (a person is running without moving) to be represented in our program. This complexity increases the cognitive burden on the developer and increases the chance of bugs.
Another approach is to use an enum:
enum State {
Stationary,
Walking,
Running,
}
Now we have three possible states in our code to match the three possible states in our problem domain. This is far better. But even this approach can prove problematic if we later need to introduce a new form of movement. Say we wanted to add a 'Crawling' state:
enum State {
Stationary,
Walking,
Running,
Crawling,
}
Notice how Walking, Running, and Crawling are all more closely related to eachother than they are to Stationary. You will probably want to know at some point whether a person is moving or not, and you could determine this with the following function:
function isMoving(person) {
person.state == State::Walking ||
person.state == State::Running ||
person.state == State::Crawling
}
But now we're duplicating some of our enum definition in a separate function. What happens if we add Sprinting to the enum but forget to add it to our function? Another bug.
Some languages will allow you to capture extra information within an enum value like so:
enum MotionType {
Walking,
Running,
Crawling,
Sprinting,
}
enum State {
Stationary,
Moving(MotionType),
}
Now we don't need to maintain a whitelist of motion types in our isMoving function, because that information is now embedded right into our enum. Our hypothetical language might allow us to directly check if person.state == State::Moving, without caring about how we're moving:
// hypothetical syntax
function isMoving(person) {
return person.state == State::Moving
}
The important thing is that we're no longer forced to update our isMoving function each time we add a new type of motion.
All of this to say that every time we fail to faithfully map the problem domain into our program, we will pay for it in unnecessary complexity. We can't avoid the intrinsic complexity of the problem domain, but intrinsic complexity is often the minority of the total complexity in a program.
The above example also demonstrates that one approach to modelling a problem may be fine given the current requirements, but as requirements change, a failure to rethink the modelling can cost us in unnecessary complexity.
Some languages are more expressive than others, meaning you may find yourself in a language that does not provide the tools to faithfully fit your code to the problem domain. The less expressive the language, the more boilerplate you'll need to write in order to solve a problem, and much of that boilerplate is a breeding ground for bugs. If you're not in a position to switch to a more expressive language, you'll need to make do with the tools available.
But even the most expressive language still produces code that needs to be executed by a computer, and that alone means there will be some limit to how you closely you can fit your code to the problem domain.
Above I stated that rarely will a drop in informational complexity correspond to an increase in cognitive complexity. The main exception to this rule is when there are inconsistencies in the codebase.
Sometimes consistency is more important than correctness. If your codebase has one small section that, for no particular reason, uses hardcore functional paradigms while the rest of the codebase is written idiomatically, that increases cognitive complexity. If the codebase's idioms loaded into your brain need to be thrown out the window whenever you come across that hardcore functional file, it will only serve to slow you down and increase the chance of bugs. Even if an oracle told you that that one file in your codebase using ultra-functional paradigms is in its simplest possible form, given the context switching required to understand it, it's not worth the cost.
Consider the following program:
books = get_books()
books.each { |book|
author = authors.find { |author| author.name == book.author_name }
puts "book #{book.id} has author #{author.id}"
}This has a time complexity of O(b*a) where b is the number of books and a is the number of authors. The reason we're multiplying b and a is because in the worst case scenario, for every book we'll need to scan the entire list of authors to find a match so we're looking at a authors b times.
Compare that to the following:
books = get_books()
authors_by_name = authors.index_by { |author| author.name }
books.each { |book|
author = authors_by_name[book.author_name]
puts "book #{book.id} has author #{author.id}"
}This only has a time complexity of O(b+a) because we make a single pass through the authors to obtain our authors_by_name variable, and then we make a single pass through our books, with a constant-time (i.e. O(1)) hash lookup on our authors_by_name variable for each book.
So we've optimised our code to reduce the time complexity, but we've paid for it in code complexity. Whether such an optimisation is premature depends on the context. If you expect your books and authors database to grow to contain millions of records, then the optimisation is worth it. On the other hand if you know your database will never go beyond a hundred books because it's a pet project, there's no need for the extra complexity.