I’m sure you may have come across some post in LinkedIn comparing junior vs senior code. They are unmistakable, with that fresh morning smell of heated arguments and even holy wars, with endless comments arguing why some option is better than another option or how something runs 1% faster.
Sometimes they favour highly performant code, other times they favour much shorter code, usually including some nerdy or obscure feature of the language being used. These snippets of code are shared to show you how senior the original poster is, seniority being directly proportional to the amount of those obscure features they know and inversely proportional to the length of their code.
Some other times they discuss functional vs imperative approaches, arguing about the time and space complexity of the different solutions. These discussions offer endless insights about the vast knowledge of the senior developers involved in the discussion.
Calculating the price of discounted products#
One of those posts showed the following snippets of code, comparing functional and imperative versions of the same functionality, apparently calculating the cost of certain discounted products, that you would only buy if they are more expensive than a certain amount of money. I have adapted the code to Scala from the original Javascript version.
Let’s assume you have the following data:
// Note to really senior developers, I'm aware that Double is not an
// appropriate data type for prices, just using it for the sake of simplicity
case class Product(name: String, price: Double)
val products = List(
Product("Apple", 50),
Product("Banana", 21),
Product("Orange", 70)
)Here you have the functional version of the code (with the curried functions that weren’t included in the original example):
def applyDiscount(discount: Double)(product: Product) =
product.price * (1 - discount)
def priceGreaterThan(limit: Double)(price: Double) =
price > limit
def calculateTotalPrice(firstPrice: Double, secondPrice: Double) =
firstPrice + secondPrice
val totalPrice = products
.map(applyDiscount(0.1))
.filter(priceGreaterThan(20))
.reduce(calculateTotalPrice)And here you have the imperative version:
var totalPrice = 0.0
for product <- products do
val discountedPrice = product.price * 0.9
if discountedPrice > 20 then
totalPrice += discountedPriceThe original poster, blatantly ignoring the Hic sunt dracones annotation, candidly asked which option looked better, stating his mild preference for the functional version of the code for its improved readability and intention conveying.
Of course the obvious happened: hell rained upon Earth.
Are you crazy? Functional code is O(3n)!#
One of the main discussions around the merits of each version came down to the performance of the code, with some senior developers arguing that the functional code had O(3n) time complexity.
Why O(3n) isn’t worse than O(n)#
First of all, let me clearly state this:
O(3n)is not a thing. Period.
The reasoning behind this was that the functional code iterates three times through the products collection, one for map, another for filter, and a last one for reduce. Meanwhile the imperative code only had one loop, iterating only once through the collection. So according to these senior developers, the functional code had O(3n) time complexity, while the imperative code had O(n) time complexity.
First of all, I won’t go into the nitty-gritty details of the mathematical definition of the Big-O notation, but suffice to say that this notation is usually used to define an asymptotic behaviour when the input size tends to infinite. In the case of O(n) we are saying that the time spent by the algorithm grows linearly based on the size of the input (again this is a simplification). So it doesn’t matter if the time function of your algorithm is n/150, n, 3n, or 12500000n, they all grow linearly, so they all are O(n).
Duh, but functional code still runs three times slower#
Really? Again, to keep things simple we won’t take into account the nuances associated with modern computing and memory layering. Even without taking into account this, dereferencing a memory position in an array is usually a much quicker operation than anything that you do with that data inside the loop. If those operations are an order of magnitude greater than the dereferencing, the dereferencing operations become negligible.
You don’t believe me? Let’s do some basic maths:
- Let’s say that you do three operations per loop, which take
a,bandc - Let’s say dereferencing a position in the input array takes
d
The total time of the operation will be, for an input of size n:
- In the case of three loops:
3dn + an + bn + cn = (3d + l)n, wherel = a + b + c - In the case on one loop:
dn + an + bn + cn = (d + l)n
So, the ratio between them will be (3d + l)/(d + l). When will the code with three loops be three times slower? When you spend zero time inside the loop. And what if the operations in the loop are quite feasibly just one order of magnitude greater than loop itself? If l = 10d then the ratio becomes 13/11, just a 18% increase, not a triple increase in time. So no, going over the collection three times doesn’t make the code three times slower.
But you have the cost of invoking those curried functions#
Yes, but those curried functions are improving the legibility of the code clearly conveying its intention. And if you want to stop comparing apples to oranges, you can still use similar operations in the functional code just including some anonymous functions (and even replacing reduce with sum):
val totalPrice = products
.map(_.price * 0.9)
.filter(_ > 20)
.sumAnyway, you create lot of useless structures#
Ok, here you may have a fair point. When you perform functional transformations, each transformation creates an intermediate structure which is discarded once its results are used in the next step of the functional pipeline.
So in this case map would create a structure of size n, which is consumed by filter which creates another structure of at most n (because it may filter out some results), which in turn is processed by sum to compute the final result. So we have an O(2n) space complexity solution (just kidding, O(n), I wanted to check if you were still paying attention).
In any case, unless we are doing some kind of nested transformations, we will have a solution whose space grows linearly with the size of the input, and arguably worsened by the number of steps in the pipeline.
Why this is a pointless discussion: strict vs lazy evaluation#
Once reached this point I would just include a method invocation in the functional code to finally settle the question:
val totalPrice = products.view
.map(_.price * 0.9)
.filter(_ > 20)
.sumDo you see that .view method there? That’s the Scala way of switching to lazy evaluation in collections, with the use of Views. In contrast to strict evaluation, where all the transformations are eagerly applied — hence producing new structures — when you use lazy evaluation, computations are delayed until they are strictly needed.
In our case this would mean that map and filter, instead of returning a concrete collection, would be returning another View (wrapping the underlying view and remembering the closure needed to compute values in that new view), but without performing any actual operation.
Once we reach sum, which needs to access the elements to produce its output, we do the real computation. But thanks to the magic of lazy evaluation, we loop through the original input only once without creating any intermediate structure, making this functional code effectively equivalent to the single-loop imperative code we saw in the beginning.
Of course lazy evaluation comes with its costs, in this case creating the intermediate view structures, and creating and storing those intermediate closures, which for small input sizes may be even more costly than simply performing the “loop” several times and creating intermediate collections.
In the case of functional languages, some of them are lazy (or non-strict) by default, as Haskell, and others are strict by default offering mechanisms to switch to lazy evaluation, as Scala.
Why this discussion is even more pointless: legibility and maintainability#
As I said in the beginning of this article, it seems that seniority is considered to be directly proportional to the number of features you know of a given language and inversely proportional to the length of the code you generate. It also seems to be related with your ability to micro-optimise your code, so it has O(n) performance instead of O(3n) performance (kidding again).
I would argue that in a business environment the senior developer (or the valuable developer) is that who manages to lower the total cost of ownership of a software product as much as possible. Or simply said, the one who saves more company’s money. But how can we know where to focus when trying to save money?
According to some people who know much more than me (I won’t be the one disagreeing with an O’Reilly’s published author):
Fully 60% of the life cycle costs of software systems come from maintenance […]. During maintenance, 60% of the costs on average relate to user-generated enhancements (changing requirements), […], and 17% to bug fixes.
So it seems that maintenance costs are much greater than operational costs (those related to the infrastructure needed to run the software). This means that unless you are Google — and an improvement in performance has an impact on millions of machines — you better focus on making your software much more maintainable and bug free. And that means stopping micro-optimising your code for measly performance gains and instead focus on making your code tell a beautiful story, one that other fellow developers and your future self are delighted to read and evolve. I would argue that functional programming has an edge here, but that is probably the topic for another post.
Anyway I hope that you, as Martin Golding asked,
Always code as if the guy who ends up maintaining your code will be a violent psychopath who knows where you live.
