Accidentally Quadratic

Mercurial (sometimes called “hg”, the name of its command-line tool, named after the elemental symbol for mercury) is a distributed version-control system.

When applying a “change group” (a group of changes applied as a unit, e.g. in a single hg push), Mercurial tracks the heads before and after the changeset. Previously, it stored the “oldheads” list of pre-changeset heads as a Python list, and computed the newly-created heads post-changeset with:

newheads = [h for h in repo.heads() if h not in oldheads]

Since h not in oldheads is O(n) on a list, a large repository would incur an O(N²) cost with respect to the number of heads in the repository.

What’s perhaps remarkable about this change is the size of the fix, which I think is the smallest diff in Accidentally Quadratic’s history: Wrapping a simple set(…) around the instantiation of the list.

In my judgment this fix is notable for a few reasons:

• It’s a testament to Python’s expressiveness and consistency of APIs, that swapping out a set for a list can very often be a 5-character change.
• It’s a vote in favor of all languages having a readily-available set type in their standard libraries along side lists and mapping types, so that fixes of this type are easy, and also hopefully less-often necessary in the first place.
• My first point notwithstanding, it’s an argument against having a polymorphic in or contains method that silently degrades to O(n) behavior on lists or similar containers. Wherever practical, asymptotics should be clear from the call site!