Looping vs. Functional Transformations - GlenKPeterson/Paguro GitHub Wiki
Looping code is vulnerable to errors:
- "off-by-one" boundary overflow/underflow
- improper initialization
- accidental exit
- infinite loops
- forgetting to update a counter
- updating the wrong counter
- etc....
Loops generally require setting up accumulators, then running a gamut of if
, break
, continue
, and return
statements, like some kind of mad obstacle race that involves as many state changes as possible. Different kinds of collections require different looping constructs - which adds more complexity. None of that has anything to do with why the loop was created in the first place which is to transform the underlying data in a collection (or array).
With functional transformations, all those concerns disappear. Instead of thinking, “Oh, I need to process that stuff, I'll add an inner loop!” I'm thinking “What data structure would have the best performance characteristics for that transformation?” I can only think about a limited number of things at once. Each unnecessary concern takes precious thought power away from a more important one. Choosing data structures for their performance characteristics is my #2 priority, right below correctness.
In Michael Abrash's book, "Zen of Assembly" he says:
- Optimize the design before worrying about the implementation
- Measure optimizations with actual timings because they often run contrary to the best laid theories of what will be fast.
This is incredible advice that has served me well over the years. But I think there's a 1.5 available in higher-level languages and that's "leverage the performance characteristics of collections."
Also known as "Big 'O' Notation" provides a rough notation to describe how different algorithms scale. This is a sea change from how people think about speed today. The web is plastered with statements like, "I made a 10% performance improvement", or "It runs 3 times faster." But these are small beans - only useful when the design is ideal, and you are using the right algorithm. Because, making a process that takes a million years 3x faster, still leaves you with a process that's totally worthless. Asymptotic complexity is about orders of magnitude at scale. It's about the curve of y = x^2 vs. y = x vs. y = log x. Type some of these into Google and you'll see the difference right away.
In a recent study, it was found that the most common collection on GitHub was List<String>
. That's really sad when you think about it. It suggests that 1. People aren't using Maps and Sets as much as they might and 2. people are passing Strings around instead of modeling data. But #2 is a topic for a separate article.
It's sad because choosing the right collection has more to do with performance than any amount of loop-oriented thinking. Georges I. Gurdjieff's thoughts on spirituality apply equally well to looping in programming:
You are in Prison. If you are to get out of prison, the first thing you must do is realize that you are in prison. If you think you're free, you can't escape.
- List: O(1) lookup by index, O(n) for contains()
- HashSet/HashMap: O(1) (or similar) for contains()
- TreeSet/TreeMap: O(log n) for contains()
If you're looping through a collection or an array, that's O(n). If you loop within a loop, that's O(n^2). Consider the case of the java.util.List.containsAll(Collection c). This method probably shouldn't be there because a List is not suitable for the contains() operation. The naive implementation would be:
boolean containsAll(Collection<?> as) {
// Iterate through each item that must be contained.
for (Object a : as) {
// Check to see if we contain it.
boolean containsItem = false;
for (E b : this) {
if (Objects.equals(a, b)) {
containsItem = true;
break; // out of the inner loop
}
}
// If any item was not found, then we don't contain all.
if (!containsItem) {
return false;
}
}
// All items were found.
return true;
}
But as stated before, that's O(n^2). But what if we did this instead:
boolean containsAll(Collection<?> c) {
return this.toMutableSet().containsAll(c);
}
Not only is this a huge reduction in code, but it's O(n). How much of an improvement is that? Well, if the two lists have 1000 items each, it's roughly a 1000 times improvement, because however long this improved algorithm takes, the naive one takes roughly the square of that amount of time.
What do you have to know to use this benefit in your code? Only the Big O notation for the common methods on the 5 or so common collections. Well, that and you have to actually think about Big O and collections when you're coding. How do you do that?
If you're thinking about arrays, primitives, checked exceptions in lambdas, and all those complexities of looping, you probably aren't thinking about the Big O performance of your algorithms or leveraging collections to bring about miraculous performance improvements where your software needs it the most. This is where simple, clean functional transformations can radically speed up your code, even as they make it simpler to read and understand.
Whether you use Paguro's Transforms, or Clojure's Transducers, there is a potential for a simultaneous readability and performance revolution in most code bases. Java 8 streams can do this as well for the price of a little more complexity (see: Comparison with Streams and Lambdas in JDK8).
There are timings on the web that show that a for-loop iterates an array three times faster than Java 8's forEach. But as we just learned, 3x is nothing. 3x is the wrong way of talking about performance. If you put 100 items in your 3x O(n^2) algorithm it takes the speed from 10,000 down to 3,000 operations. But going from n^2 to n brings it down to 100 operations. You keep your 3x, I'll take the Big O difference!
Using the right collection typically results in a performance gain from O(n^2) to O(n), or O(n) to O(log n) or similar. This isn't about writing slower code. It's about writing faster, safer code on the first pass. See the Transformable usage example.