Accidentally Quadratic

Capistrano is a server automation and deployment tool written in Ruby. It provides a Ruby DSL for defining deployments and other operations on a set of servers, and executing those flows.

A Capistrano environment defines a number of servers, each of which has zero or more “roles”, which help define which of your rules should be executed on them. Servers are distinguished by their hostname and ssh ports; Two servers with the same hostname and ssh port are considered to be the same server.

Capistrano allows you to define servers using either the role helper, which attaches a role to a server (defining the server if needed), or the more explicit server method. If you define multiple roles on the same server (as in this example in the docs):

role :app, %w{example.com}
role :web, %w{example.com}
role :db,  %w{example.com}

Then Capistrano identifies that those servers are the same server, and merges the roles into a single Server:

[10] pry(main)> Capistrano::Configuration.env.servers
=> #<Capistrano::Configuration::Servers:0x00000001763eb8
 @servers=
  [#<Capistrano::Configuration::Server:0x00000001763c88
    @hostname="example.com",
    @keys=[],
    @local=false,
    @port=nil,
    @properties=#<Capistrano::Configuration::Server::Properties:0x00000001763940 @properties={}, @roles=#<Set: {:db, :app, :web}>>,
    @user=nil>]>

However, until recently, this merging and deduplication was performed by walking the list of all registered servers, comparing hostname and port. Obviously, this meant that each new server definition had to scan all previous servers, for a classic O(n²) bug.

The patch resolved the issue in the obvious way, by storing servers in a hash keyed by the (hostname, port) pair.

Thanks to Daniel Benamy for finding, fixing, and bringing this one to my attention.

The reject! method in Ruby selectively removes elements from an array in-place, based on a provided predicate (in the form of a block).

Between Ruby 1.9.3 and Ruby 2.3, reject! was accidentally quadratic.

The underlying bug was fairly straightforward. Every time the provided predicate returned true, the code immediately deleted that element:

if (RTEST(rb_yield(v))) {
    rb_ary_delete_at(ary, i);
    result = ary;
}

In an array, deleting an index necessitates shifting back all the following episodes, and so is an O(n) operation; If your predicate rejects a fixed fraction of elements, the total runtime is this O(n²).

The bug was fixed by keeping a count of accepted elements, and moving each element into its proper final position as it is scanned, and truncating the array at the end.

This bug is fairly straightforward, but the part I find most interesting was why it was introduced. The code used to be linear, but it regressed in response to bug #2545, which concerned the behavior when the block passed to reject! executed a break or otherwise exited early. Because reject! is in-place, any partial modifications it makes are still visible after an early exit, and reject! was leaving the array in a nonsensical state. The obvious fix was to ensure that the array was always in a consistent state, which is what resulted in the “delete every time” behavior.

I find this interesting as a cautionary tale of how several of Ruby’s features (here, ubiquitous mutability, blocks, and nonlocal exits) interact to create suprising edge cases that need to be addressed, and how addressing those edge cases can easily result in yet more problems (here, quadratic performance). In my mind, I’d just rather not have a reject! at all, and callers who need to mutate an array in-place can figure out how to do safely with respect to their own use cases.

(Thanks to Russell Davis for bringing this one to my attention).

The ruby parser gem is an implementation of a Ruby parser in Ruby itself, which allows for Ruby code to parse and introspect Ruby code. It’s used in a number of places, but perhaps most prominently by rubocop, a Ruby linter and style checker.

In parser versions <= 2.3.0.4, the parser is quadratic in the length of the input string, for any input containing >0 unicode codepoints outside of the ASCII range.

The problem arises initially in the lexer, which turns the source input into a sequence of tokens. The lexer is implemented using ragel, to generate a state machine that processes the input sequentially, generating tokens as it goes.

The problem comes when the lexer attempts to extract tokens and return them to its caller. As it lexes, it keeps track of character offsets, and it returns tokens via a character-range slice of the input:

def tok(s = @ts, e = @te)
  source = @source[s...e]
  return source unless @need_encode
  source.encode(@encoding)
end

The problem arises because the input, at this point, has been UTF-8-encoded. Because UTF-8 is a variable-length encoding, finding the nth character requires a linear traversal to skip over one codepoint at a time. Therefore, @source[s...e] is linear in the end position. Since the input contains O(n) tokens, and each one requires an O(n) scan to extract, just extracting the tokens requires quadratic time.

The fix, which I implemented after discussion with the authors, was to re-encode any non-ASCII input into UTF-32 before processing. UTF-32 imposes a significant memory overhead, but it obviously admits O(1) character indexing, and the tradeoff is well worth avoiding quadratic behavior – on a 1500-line test case from the Stripe codebase, the change dropped parsing from about 2.5s to about 900ms.

I’m fond of this one because of how subtle it was. I’m obviously well-attuned to being on the lookout for these issues, but even after my profiler showed 50% of the parser’s time in tok, it took my a long time to realize what was happening. I eventually had to run it under Linux perf, and see a large amount of time in str_utf8_nth, before it clicked.

And it’s subtle, too, because of Ruby’s “clever” handling of strings: Even if a string is marked as UTF-8-encoded, Ruby knows internally if it happens to only contain 7-bit codepoints, and optimizes access to O(1) in that case. And so the exact same code, on the exact same “shape” of data (a UTF-8-encoded string) could change dramatically in time complexity by the modification of a single character anywhere in the input!

puppet is a popular configuration-management tool. Puppet’s basic model is declarative: You define a set of “resources” and the state they should be in. A “resource” can be basically anything that might be managed on a server: file on disk, a user account, a provisioned database instance, a running service, …

Puppet compiles the input puppet configuration into a “catalog” with all the defined resources, and creates a dependency graph: e.g. before the MySQL service can be started, the MySQL package has to be created.

Applying a puppet catalog involves walking the catalog in dependency order, analyzing each resource in turn and modifying the running system to reflect the desired state (creating or removing a user, starting or stopping a service, …).

As with most problems in engineering, puppet has to deal with the ever-present possibility of failures or errors: What happens if a resource node cannot be applied correctly? Permission errors, insufficient disk space, being asked to install a typoed package, …

If a resource fails, puppet records this fact and then continues applying the catalog, attempting to apply as much of the catalog as it can. Since it maintains a dependency graph, it can selectively skip only the resources that depend on a failed resource.

However, until recently, puppet implemented this skipping by, for each node, visiting each recursive-dependency and checking if that failed

It performed this check regardless of whether any failures had happened or not, for every node. This trivially leads to O(n²) behavior for a depth-N dependency chain!

My fix, scheduled for release with Puppet 4.2, attaches a list of failed recursive-dependencies to each node. When visiting a node, the list is computed for that node by directly unioning the lists of the immediate dependencies.

To demonstrate the fix I constructed a series of puppet manifest that just included N notify resources in a linear chain, and compared runtime before and after my patch:

[edited to add]: The above graph is plotted to an artificially large N to make the quadratic behavior extremely obvious to visible inspection; I don’t mean to imply that real manifests will have depth-6000 dependency trees. However, the patch is also a significant improvement on real-life manifests: As noted in the PR, it cut puppet runtime nearly in half on many real servers at Stripe.

This one was discovered by Greg Price, a friend and former coworker: http://blog.solanolabs.com/profiling-ruby/

Ruby provides a require helper, which loads a file exactly once, no matter how many times the same file is required. It implements this by maintaining a cache, in $LOADED_FEATURES, of which files have already been loaded by require, and skipping files already present in that array.

Prior to Ruby 1.9, Ruby implemented this cache by directly scanning $LOADED_FEATURES each time require was called. Loading n files thus entailed n require calls, each of which did an O(n) scan of all loaded features – O(n²) in all.

Greg’s patch, which was ultimately accepted into Ruby 2.0, adds a hash-table cache for $LOADED_FEATURES, allowing O(1) querying of whether a given file has already been loaded.