Optimization Fever!!!

What is Premature Optimization?

You may have heard this term before, but what does it actually mean? After all, optimization is a good thing that should be incorporated into everything that software engineers do, right? In a purely academic sense, this is absolutely true.

However, in real-world situations, we have to maintain code. As code complexity increases, maintenance costs increase as well as risk. Are we building a system for processing millions of financial transactions a second? Or are we building a system that will search for a really sweet deal on concert tickets? This question can have a profound impact on just where the balance lies.

Even within the context of these vastly different scenarios, there will be parts of the system that require more or less optimization than others. One may need to go crazy optimizing the system that is filtering out a customer's transactions from all of the bank's records, but do we really need to go that far to switch the sorting from date to amount?

Case Study: Prime Numbers

Prime numbers are whole numbers that are only evenly divisible by 1 and itself. These numbers play an important role in many areas of computer science. Why they are so important is beyond the scope of this writing, but they are an interesting case study when dealing with complex algorithms. We will compare a couple of approaches for finding all of the prime numbers up to a given ceiling. All examples are written in Kotlin, and example times are measured by averaging 10 runs in a unit test.

Brute Force

In this exercise, we will literally iterate through every number up to the given ceiling and determine whether or not it is prime. We will do this by stepping through every potential factor up to and including the square root of the potential prime number (anything above the square root cannot possibly be a factor). If no factors are found, we stick it into an array. We stop once we've reached the ceiling, and we have all of the prime numbers we were looking for. In a nutshell, we are walking through every single number and trying every possible factor of that number to find the primes. Not very efficient, right?

We can add a little intelligence to the isPrime check, and we will see what it does to the numbers later. With this (slightly more complex) algorithm, we simply return false if the value is 1, otherwise we automatically return true if the value is 2 or 3. Once it gets past this point, it rules out any that are divisible by 2 or 3. Then, it does get a little more interesting as it starts at the next "well-known prime" of 5 and as long as the test value squared does not exceed n, we test it for divisibility, increment it to the next odd value, and repeat. If we find any factors, we return false. If we get through the loop, we return true.

fun isPrime(n: Int): Boolean {

    val max = Math.sqrt(n.toDouble()).toInt()

    for (factor in 2..max) {
        if (n % factor == 0) {
            return false
        }
    }

    return true
}

fun isPrimeWithSmartCheck(n: Int): Boolean {

    if (n == 1) {
        return false
    } else if (n <= 3) {
        return true
    } else if (n % 2 == 0 || n % 3 == 0) {
        return false
    }

    var testValue: Int = 5

    while (testValue * testValue <= n) {
        if (n % testValue == 0) {
            return false
        }
        testValue += 2
    }

    return true
}

fun findPrimes(n: Int): List<Int> {

    var primes: MutableList<Int> = ArrayList()

    for (i in 2..n) {
        if (isPrime(i)) {
            primes.add(i)
        }
    }

    return primes
}

Sieve of Eratosthenes

The Eratosthenes was a Greek mathematician (among other things). He was a pioneer in number theory and introduced the Sieve of Eratosthenes. This is a fairly well known efficient method for finding prime numbers.

We start by creating a list of Boolean values with a length of n and default values of true. We set the size to n + 1 to account for zero. We immediately rule out zero and one by setting them to false since these do not count as prime numbers.

Next, we iterate through the list of possibilities as tracked by the Boolean array. For each number, starting with 2, we check to see if the Boolean for that index is true. If it is, we add it to the list of prime numbers. We then walk through all multiples of that number up to the end of the Boolean array, marking any multiples to false. This means that the next true value we find is a prime, so we add it to the prime list and repeat. The beauty of this approach is that every time we find a prime, we shrink the quantity of values remaining to be checked. When we get to the end of the Boolean list, we have our final list of primes.

fun sieveOfEratosthenes(n: Int): List<Int> {

    var primes: MutableList<Int> = ArrayList()
    var list = MutableList(n + 1, {i -> true})

    list[0] = false
    list[1] = false

    for (i in list.indices) {
        if (list[i]) {

            primes.add(i)
            var j = i

            while (j < list.count()) {
                list[j] = false
                j += i
            }
        }
    }

    return primes
}

The Hard Numbers

So just how much more efficient is the Sieve of Eratosthenes than the brute force method? Well, it depends. While it performs very well dealing with large n values, the brute force approach is actually faster than the sieve dealing with smaller numbers. We can even squeeze out a little more competitiveness in the brute force method by adding the smart check, but even this is beat out by the raw hammer-like approach until n passes 1000.

            average time in milliseconds
 n       |     sieve    |  brute force |  w/smart check
 --------------------------------------------------------
     10  |    0.649766  |    0.006483  |    0.496988
    100  |    0.639629  |    0.025545  |    0.579207
   1000  |    1.038445  |    0.235613  |    0.653132
  10000  |    3.082918  |    1.784386  |    1.767561
  50000  |    6.192984  |   11.570596  |    5.937535
 100000  |   12.807858  |   29.364065  |   14.411587
1000000  |  103.172073  |  622.648549  |  377.154029
2000000  |  329.524157  |  1673.22857  |  888.082857

As we can see in the data above, the Sieve of Eratosthenes easily takes the crown after n hits 50,000. But interestingly enough, the raw brute force approach that uses the least amount of code leaves the sieve in the dust while n is below that threshold. Furthermore, by adding just a little bit of complexity by switching the isPrime check to use the smarter approach, that threshold moves closer to 100,000, but the simple brute force approach beats the smart check out while n is below 10,000. And while the gains at the 2 million-mark are as high as 4-fold, the gains of the simpler approach at smaller scales are up to 100 times faster!

The Moral of the Story

Intuition is a powerful manifestation of the human brain making many calculations under the hood on our behalf and filtering it down to a "gut" feeling. When it comes to identifying bottlenecks or inefficiencies in code, developers will often fall back on this mechanism. Unfortunately, as illustrated above, the optimal way of doing something can be very counterintuitive. I am in no way suggesting we disregard intuition in our decision process. By all means, trust your gut, but we can do ourselves a huge favor by consulting metrics before blindly overcomplicating code in the name of optimization.