PUBLIC OBJECT

Optimization is Specialization

One aspect of programming that’s more art-than-science is making things efficient. I love finding shortcuts that make a system work better! It’s particularly satisfying to gather insights that we can exploit! I’ll illustrate with an example.

Optimal for Today

HttpUrl is a class I wrote that implements URL parsing and resolution. It knows that ../../index.html goes up two directories to the index file. It also knows that %2e and %2E are both equivalent to . when percent-encoded. Here’s a function to decide whether a path segment is equivalent to ..:

  fun String.isDotDot(): Boolean {
    var dotCount = 0
    var pos = 0
    while (pos < length) {
      when {
        regionMatches(pos, ".", 0, 1) -> {
          dotCount++
          pos++
        }
        regionMatches(pos, "%2e", 0, 3, ignoreCase = true) -> {
          dotCount++
          pos += 3
        }
        else -> return false
      }
    }
    return dotCount == 2
  }

We could also do it with regex:

  fun String.isDotDot(): Boolean {
    return matches(Regex("(?i)(\\.|%2e){2}"))
  }

But I made two insights to inform OkHttp’s implementation:

  • Regexes aren’t as fast as equality checks on current Androids and JVMs.
  • Using the %2e encoding for . is rare.

So OkHttp’s implementation is asymmetric:

    fun String.isDotDot(): Boolean {
      return this == ".." ||
        equals("%2e.", ignoreCase = true) ||
        equals(".%2e", ignoreCase = true) ||
        equals("%2e%2e", ignoreCase = true)
    }

It’s optimized to prefer .. and to avoid regex. But I also claim that it’s specialized to the currently most-common input, and to the current platforms. If either the data or the runtime changes this optimization stops fitting.

Worn-out Optimizations

The world does change in ways that turn optimizations into pessimizations. Much of the current work on OpenJDK is specifically interested in doing this:

I’ve spent much of my career trying to optimize code for the JVM. But unfortunately I’ve just been specializing my code the limitations of the current JVMs, and making it clumsier to fit the platform’s future.

Optimizing for People

Attempting to optimize something and actually just specializing it is not just a problem for software.

Were you building a product in the booming economy of 2019? Specializations for that environment might hurt your product for the current economy!

There’s a lot of changes happening now: to the climate, the economy, and global trade. I’ll forgo optimization and efficiency in order to stay flexible and adaptable.