Wednesday, August 14, 2013

Destroying Performance with Strictness

Summary: New versions of unordered-containers cause a massive performance regression in uniplate (10x slower is typical), which I have fixed in uniplate-1.6.11.

I've just uploaded uniplate-1.6.11, which fixes a severe performance regression introduced by unordered-containers-0.2.3.0 and above. As an example, the time to run HLint on the HLint source code (my standard benchmark) jumped from 1.7 seconds to 18.6 seconds, more than ten times slower. I strongly recommend anyone using Uniplate/HLint to upgrade.

The problem is caused by the lookupDefault function from the Data.HashMap.Strict module:

lookupDefault :: (Eq k, Hashable k) => v -> k -> HashMap k v -> v
lookupDefault def k mp = ...

This function looks up k in mp, but if k is not found, returns def. There has been discussion over whether def should be evaluated even if k is present in mp, and since unordered-containers-0.2.3.0 lookupDefault always evaluates def. There are many legitimate discussions on semantics in the Haskell community, but I do not consider this discussion to be one of them - lookupDefault should not pointlessly evaluate def. As John Hughes elegantly argues in "Why Functional Programming Matters", laziness lets you write functions that composable properly. I have spent several days debugging two problems caused by the excessive strictness in lookupDefault:

Problem 1: Error Defaults

uniplate-1.6.9 contained the following code:

lookupDefault (error "Uniplate internal error: Report to Neil Mitchell, couldn't grab in follower") x mp

Uniplate uses a very complex and highly tuned algorithm to determine which values can be recursively contained by a type. The algorithm relies on subtle invariants, in particular that x must be a member of mp at this particular point. If that fails for certain data types, I want users to submit a bug report, rather than wonder if they called Uniplate incorrectly. The simplest way to achieve that goal is using a default value of error that is only evaluated if x is not present in mp. Unfortunately, by making lookupDefault strict, this error message was always triggered. People have argued that passing error as the default is only to work around the absence of stack traces in GHC - an argument disproven by the example above. The error message provides information that would not be provided by a stack trace - the error is not merely an error, but an error that is my fault. I fixed this bug in uniplate-1.6.10 by switching to:

fromMaybe (error "Uniplate internal error: Report to Neil Mitchell, couldn't grab in follower") $ lookup x mp

Problem 2: Expensive Defaults

uniplate-1.6.10 contained the following code:

lookupDefault (hit ! x) x mp

In this example I look up x in mp, but if that fails, look up x in hit. By forcing the default to be evaluated this code always performs the lookup in hit, resulting in a slowdown of more than 10 times in HLint, and more than 20 times in Uniplate microbenchmarks. I fixed this bug in February by changing all instances of lookupDefault to use fromMaybe after finding out lookupDefault was incorrect, but was unaware of the significant performance impact until earlier today.

Counterarguments

There are various arguments for making lookupDefault strict in the default argument:

  • "You are using Data.HashMap.Strict" - the Strict module for a data structure should provide a data structure containing strict values, not a module of functions which are unnecessarily strict - values which are never stored in the data structure should never be evaluated. As another example consider the Control.Monad.State.Strict module, which provides a strict state monad. In that module, the state is strict, but functions like return are not needlessly strict.
  • "We don't support using undefined values" - I expect all Haskell libraries to work with undefined values where sensible, not be corrupted in the presence of exceptions and be multithread safe. These are some of the attributes that are essential to allow libraries to be used predictably and reused in situations the authors did not consider.
  • "Strictness is faster" - a strict lookupDefault may occasionally shave nanoseconds off a program, but can make a program arbitrarily slower, and in the case of HLint makes a commonly used program 10 times slower.
  • "It is what people expect" - I didn't expect lookupDefault to be strict, despite being one of a handful of Haskell programmers to program in a strict variant of Haskell all day long.