When writing software (or living life, really) you frequently have to make trade offs. And it’s often the case that these trade offs will be made whether you think about it or not; you can’t avoid making the trade off, but you will not have any say in the matter if you don’t pay attention.
This post is concerned with one of the more common trade offs software engineers are called on to make – optimizing time/space use against maintainability. These decisions are easy to make on the extremes. If you can get a 100x improvement in time or space complexity at the expense of having to add some comments to deal with the decrease in readability then you should take it. Or, if your system is performing well enough and the improvement in performance you could get would render the code completely unreadable, then you should not make that trade off.
It’s the middle bit that is tricky. If you can get a modest improvement in performance for a slight reduction in maintainability, what should you do?
I tend to optimize for maintainability. It’s a well-known saying that code is written once and read many times. The time you can save the reader of your code (including future you) is multiplied. Of course, if your system would be unusable below a certain performance metric then you need to ensure that performance remains above that threshold, even at the expense of maintainability.
To illustrate the tradeoff between optimization and maintainability let’s look at problem 1 from projecteuler.net. The fine folk at Project Euler have stated that they’re ok with public discussion of the first 100 of their problems. This first problem asks us to add all the multiples of 3 or 5 below 1000 together. A direct (to my mind) translation of this into code would look something like this pseudo-code:
total = 0
for each i in the range
if i is a multiple of 3 or 5
add i to the total
I’d like to introduce two definitions:
The Problem Domain is the set of concepts that are found in the problem you are trying to solve. In this case, “multiple” and “total” and “number” are concepts from the problem domain. When talking to a customer who wants you to make them a house perhaps things like “square footage”, “bedroom” and “electrical outlets” would be concepts from the problem domain.
The Solution Space (I really wanted to call this Solution Domain for symmetry, but that’s not really what I call it) is the set of concepts that are found in the solution you are trying to develop. In this case the same concepts from the problem domain are found in the solution space. To me this is a hallmark of readable, understandable code. When building a house for a customer you might have concepts like “tensile strength”, “drainage field” and “residential building code” in your solution space.
As we look at this initial solution, we note that it does not appear to be optimal. It looks at all numbers in the range. This seems sub-optimal. After looking at the numbers we wish to sum up one notices that the list of those numbers can be generated by starting at 3 and successively adding 2,1,3,1,2,3,3. This leads to this solution:
differences = [2,1,3,1,2,3,3]
number = 3
total = 0
index = -1
MAX_VALUE = 1000
#
# Generate numbers from 3 to strictly less than MAX_VALUE
# And add them to total
# We generate the number by adding the next entry in our first order differences list
#
while number < MAX_VALUE:
total = total + number
index = (index + 1) % len(differences)
number = number + differences[index]
print(total)
Note that we still have the concept of a total, but no other concepts from the problem domain exist in the solution space. And we’ve introduced concepts like “differences” and the index into the differences array. This seems more optimal as we only consider items which need to be summed (there is no “if” here). However, we have traded understandability for optimization. Was it worth it? Likely not. We arrived at the values for “differences” by direct observation, we have no idea why those numbers are what they are and thus we could not explain it to future readers of this code. A future reader of this code will be hard-pressed to map the problem domain to the solution space, and thus will spend extra time trying to understand what they are looking at. This extra time is multiplied by the number of readers of this code and thus likely dwarfs the cycles you save by making this optimization.
Here I would like to post Donald Knuth’s quote on optimization:
The real problem is that programmers have spent far too much time worrying about efficiency in the wrong places and at the wrong times; premature optimization is the root of all evil (or at least most of it) in programming
Donald Knuth
This is applicable here, because I ran timing tests on the above two implementations and the first version; the one I labeled sub-optimal, outperformed the second version by ~10% on average. Shows what I know.
Of course, everything we do exists in a larger context. We can get caught up in making local optimizations that are not the global optimal. An optimization might appear to have too small of an impact to warrant the decrease to readability, but if looked at in context – perhaps this code is called inside a tight loop and the milliseconds saved here are multiplied by many orders of magnitude – the change is indeed warranted.
developerly.info 