Accidentally Quadratic

Neal Gafter writes:

godoc is Go's tool for extracting doc comments from source code and rendering HTML documentation (loosely parallel Java's "javadoc").

godoc processes Go struct definitions in two passes. First, it runs over the AST recursively building rendering documentation and declarations into a textual output buffer containing an HTML fragment. The walker for this pass is shared with the rest of godoc's documentation rendering (so that e.g. top-level definitions and struct fields share the bulk of their rendering code).

Then, it performs a second pass, modifying the HTML to add anchors to field names, so that e.g. https://golang.org/pkg/net/http/#Response.Header links specifically to the Header field in the Response struct.

Unfortunately, previously, godoc implemented this with nested loops over the struct fields and over the rendered text:

for _, f := range st.Fields.List { foreachLine(buf.Bytes(), func(line []byte) { … } }

Since each struct field added at least one line to the output, this turned into an O(n²) loop.

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.

Elasticsearch is a distributed search engine. One can store “documents” within “indices”, which are collections of documents. One common pattern for storing time based data is to use one index per day. E.g.: tweets-2017-01-01, tweets-2017-02-01 and so on. This makes having many indices decently common, and it also makes searching across many indices common in a single search.

Elasticsearch has a query type called IndicesQuery, which lets you (among other things) optimise your query path by knowing which index to search in. For example, say that you have one index pattern for tweets (tweets-YYYY-MM-DD) and one for Reddit posts (reddit-YYYY-MM-DD). Say that someone searches for “hashtag: kittens OR subreddit: awww”. You know that you don’t have to execute the hashtag query in the Reddit indices and that you do not have to execute the subreddit query in the tweet indices. This is done by specifying to only execute the hashtag in indices that match tweets-*.

When executing the query, Elasticsearch will consider each shard (of an index) separately. Usually one has 2-5 shards per index. For each shard, it will check if the index name matches the pattern given by the IndicesQuery. This is where we find our performance bug.

The algorithm in the 1.X and 2.X versions of ES work by first expanding a pattern into the list of all matching indices – tweets-* becomes ["tweets-2017-01-01", "tweets-2017-01-02", …]. Then, for each index being considered, it checks for membership in that list:

protected boolean matchesIndices(String currentIndex, String... indices) { final String[] concreteIndices = indexNameExpressionResolver.concreteIndices(clusterService.state(), IndicesOptions.lenientExpandOpen(), indices); for (String index : concreteIndices) { if (Regex.simpleMatch(index, currentIndex)) { return true; } } return false; }

(Here, indices is a list of patterns, and the concreteIndices() method applies the wildcard internally to the list of all indices)

This means that the time complexity per shard is O(n), where n is the number of indices in your cluster. Since we consider at least one shard per index, the overall search complexity then goes to O(n^2). Furthermore, this expansion (and Elasticsearch’s Regex.simpleMatch pattern matcher) generate a lot of garbage, stressing the garbage collector and making the process even slower.

(For those of you arriving here via Russ’s blog, you’ll be chagrined to note that ES implements an exponential-time backtracking glob matcher, although that fact isn’t implicated in the bug in question.)

We used this query in our not-too-shabby production cluster. At the time, it had a total of 1152 cores and we searched over roughly 150 TB of data in about 8500 indices. We discovered that we spent almost half of our CPU time in the Regex.simpleMatch method. We patched the algorithm to instead directly check if the current index matches any of the specified indices, making it O(m), where m is the number of index patterns specified in the query (we usually had 2-3). On top of the saved CPU, this also had the benefit of making us spent about 1/3 as much time in Garbage Collection pauses, due to the fewer allocations of Strings.

This seems to have been fixed in the ‘Great Query Rewrite’ for Elasticsearch 5. I do not know if this was explicitly targeted as a performance fix, if it was by accident or if someone just thought 'oh this might be slow’.

A tags file is a classic UNIX format for storing an index of where symbols are defined in a source tree, for ease of finding a symbol definition from within an editor. Both vim and emacs have native support for loading TAGS files and using them to jump to symbol definitions.

When performing tags lookups, vim deduplicates results, to suppress identical matches (perhaps in case you've concatenated multiple tags files? I'll admit to not fully understanding the intent here).

However, historically, it stored the matches in an array, which meant that looking up tags was accidentally quadratic in the number of returned matches. Presumably this escaped notice in part because usually most symbols have only a few definitions, but it was a problem for programmatic use, or in some edge cases of manual search or pathological code bases.

The fix, as it often is on this blog, was to store the results in a hash table, providing duplicate-merging for free.

Interestingly, some earlier developer had noticed that this code could be slow, but instead of fixing it, had added code to check for ^C and abort the entire match, so as to return use of the editor to the user! We may never know if that author didn't realize there was a relatively-easy fast solution, or just thought it was too much work in C (as of the fix, vim did have a built-in hash table type, but it needed to be extended to support non-NULL-terminated strings).

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.

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.

Server-sent events are a standard for web servers to stream a sequence of events to a browser over a single HTTP connection. You can view them as a simpler, unidirectional, alternative to websockets (that doesn't require support from any middleboxes), or as an optimization over one-event-per-request longpolling.

The wire format for an event consists of a number of newline-separated key-value pairs, in a simple key: value format. For instance, the documentation provides the example event:

event: userconnect data: {"username": "bobby", "time": "02:33:48"}

Until recently, Chrome's parser for this format worked strictly line-at-a-time, maintaining no additional state. When it received data from the server, it appended the data to its buffer, and then attempted to parse a k-v pair off the first line:

void EventSource::didReceiveData(const char* data, unsigned length) { append(m_receiveBuf, m_decoder->decode(data, length)); parseEventStream(); }

If it didn't find a complete event (e.g. missing newline), the parser just stopped, waiting for the next batch of data to arrive.

This works well as long each line arrives in a relatively small number of packets. However, if you have a very long line (e.g. a 16MB data field), it will (of necessity) be chunked into many smaller packets on the wire, which will end up getting passed to didReceiveData separately. In response to each packet, the parser will scan the entire line to the end, note the lack of newline, and then abort. Thus, we will do N/chunk-size scans of our line, each one scanning more and more bytes, resulting in an overall quadratic blowup!

The fix makes the new parser more stateful, so that it keeps track of its progress in the parse across each new packet, and avoids scanning the buffer O(N) times.

It was recently discovered that some surprising operations on Rust’s standard hash table types could go quadratic.

Perhaps the simplest illustration is this snippet from a comment, here simplified even further:

use std::collections::hash_set::HashSet; fn main() { println!("populating..."); let mut one = HashSet::new(); for i in 1..5000000 { one.insert(i); } println!("cloning..."); let mut two = HashSet::new(); for v in one { two.insert(v); } }

In this example, the first loop (populating one) finishes fairly quickly, as you would expect, but the second loop (copying into two) takes much, much longer.

I enjoy this bug for at least two reasons: One, it’s fun technically, allowing us to take a brief deep dive into hash-table implementation – something most of us are normally able to treat as a solved problem – and two, it’s a great example of subtle quadratic behavior in a system specifically designed by smart and well-informed developers to avoid the possibility of accidental quadratic behavior!

Robin-Hood hashing

To understand the bug, we’re going to need to understand the hash table strategy used by Rust’s standard hash tables. A major challenge in any general-purpose hash table implementation is how to handle hash collisions; If you have a table with N buckets, eventually you’ll get two elements with the same value of hashcode%N, and what do you do?

Rust uses Robin Hood hashing, a relatively old technique that’s recently received new attention. Robin Hood hashing is a variation on good old open addressing with linear probing, with a small twist.

First, let’s refresh our memory:

In hash tables, “open addressing” refers to the technique of, upon encountering a collision, somehow selecting an alternate location in the hash table. It’s most commonly contrasted with “chaining”, in which you store multiple entries in a single hash bucket, typically using a linked list.

Linear probing, in particular, means that select alternate buckets by scanning forward from the natural bucket. If you try to insert an element with hash code H into a table with N buckets, and bucket H%N is full, you try (H+1)%N, (H+2)%N and so on, until you find an empty bucket. On lookup, you start at H%N and scan forward until you find your element or an empty bucket.

Open addressing with linear probing is arguably the simplest possible general-purpose hash table implementation, and it can work fine (assuming a good hash function) as long as you don’t let your load factor get too high (reminder: the load factor is the number of elements stored in the table, divided by the number of buckets in the hash table. A load factor of 0.5 means that half the buckets are in use). If your load factor gets too high, then elements can end up extremely far from their natural hash bucket, necessitating a lot of scanning on inserts and lookups.

Robin Hood hashing improves on linear probing with a simple trick: When you’re scanning forward from H%N, look at each element you encounter. If the inserting element is further from its “natural” bucket than the element in the bucket you’re considering, then swap the new element and the element in that bucket, and continue scanning with the other element.

Let’s consider an example. Imagine this is a subset of a hash table; I’ve labeled each bucket below it with its index, and inside the bucket I’ve placed hashcode%N, what I’ve been calling the “natural” index of an element:

+---+---+---+---+---+ | 0 | 0 | 2 | 1 | | ... +---+---+---+---+---+ 0 1 2 3 4

Now suppose we want to insert an element with hash%N == 1. We start at bucket 1, and find it full. The element in that bucket is at index 1 and wants to be at index 0, so it’s further from home than our new element is. We keep looking. At index 2 we find an element with natural index of 2. It is a distance 0 from home, and we’re a distance 1, which is further. So we place our new element at index 2, and pick up whatever element used to be there, and continue. Eventually, we end up with:

+---+---+---+---+---+ | 0 | 0 | 1 | 1 | 2 | ... +---+---+---+---+---+ 0 1 2 3 4

The net result of this process is to reduce the variance of how far out-of-position elements are. Reducing variance means we have much more predictable insert and lookup times, which is strongly desirable. When we employ robin hood hashing, we can safely load a table up to a load factor of 90% or even 95%. We can even prove (as the author of the original paper did) fairly tight bounds on the expected maximum probe distance.

The Problem

Rust’s problem arises when you iterate over one table and insert the resulting entries into another table. The problem occurs because iteration over a hash table procedes by walking the backing array of the hash table directly. This results in yielding entries approximately in hash order, which turns out to be fatal when combined with the other elements of Rust’s implemention.

The final detail we need to know in order to understand the bug is Rust’s table-sizing algorithm. Rust uses power-of-two sized tables (a common technique, since it means you can use bitmasks instead of more-expensive modulus), and grows tables when they reach a 90% load factor.

Now, let’s consider what happens when we execute the above example. For simplicity, we’ll pretend that two starts out with a table size of half of one’s. In reality it will start out extremely small and grow through powers of two, but the half-size case exhibits the necessary behavior and is simpler for illustration. We can modify the above example to initialize two as let two = HashSet::with_capacity(one.capacity()/2); to verify that this still exhibits quadratic behavior.

So, let’s consider what happens as we start copying one into a two half its size. Things procede uneventually for the first half of the table; Because two has half as many buckets as one, hash%two.raw_capacity() == hash%one.raw_capacity() for the first half of the table, and elements are inserted into two in approximately the same indexes as they had in one. Because elements have been reordered slightly in one by the insertion process we occasionally have to search slightly, but never far, because most of the space to the right is still free. So, as we go, the picture looks something like (where Xs are filled buckets, and dots are empty):

one: |XX.XX.XXXX.XXXXXX.XXX..XXX| ^-- cursor two: |X.XXXX.XX....|

However, eventually we reach the midpoint of one’s table. At this point, indexes in two’s half-sized table wrap around, and we start searching for openings beginning near the start of two once again.

At this point, two’s load factor is approximately equal to that of one; it has half as many buckets, and approximately half as many elements. Because Rust resizes tables at a 90% load factor, we know one’s load factor to be between 45% and 90%. If we suppose by way of example that one is at a 70% factor, two can absorb 20% of its capacity past one’s half-way point until it will resize.

During the insertion of that additional 20% of two’s capacity (constituting something like 70% * 10% = 7% of one’s elements), we run into trouble.

We begin inserting at the beginning of two. two is 70% full, so as we insert we search to the right until we find an empty bucket.

However, “immediately to the right” is also where our future inserts will land, since we’re walking two in bucket order. And so, as we go, the position at which we attempt an insertion marches forward at a rate of one bucket per bucket in one; But the insertions all “stack up”, pushing the distance-until-empty forward at greater than one bucket per bucket, since we must also contend with the 70% of buckets already full. The situation rapidly looks something more like:

one: |XX.XX.XXXX.XXXXXX.XXX..XXX| ^-- cursor two: |XXXXXXX.X.....| ^-- cursor/2

With each element we insert, we must search further and further to the right to find the empty spaces in two. This is, essentially, a classic triangular pattern, and definitely quadratic.

This pattern continues until we fill up two to 90% capacity; At that point, two will be resized, and performance will go back to something reasonable. However, even though the quadratic regime covers only a small fraction of the middle of the loop, it’s an approximately-constant fraction, and so the quadratic behavior is still quadratic.

We can demonstrate this, visually. If we augment the above program to measure the cumulative time to insert N elements into two, we observe the above behavior:

We can see the exact behavior I described – efficient performance for the first half, a quadratic explosion, and then a return to efficiency.

If we don’t preallocate capacity/2 elements, we can see the full picture:

It is an essentially similar picture, except that the quadratic breakdown happens prior to each resize of the underlying table.

The Fix

Rust is working around the issue by reseeding the underlying SipHash hashing algorithm on a per-table basis. This solves the problem very thoroughly, by ensuring that the order of elements in two different tables has no correlation to each other, restoring all the nice assumptions about independence that make Robin Hood hashing work. They’re also speculating about a more fundamental fix to the hash table implementation, so that users who drop in a different hash algorithm are not again vulnerable. One proposal is that hash tables ought to retain their insertion order, since this bug is much less likely to happen if tables do not leak their hash order.

Concluding Thoughts

This was a subtle bug. Rust’s hash tables were very carefully thought by experienced developers well-versed in the literature and practice of deliberate quadratic attacks on hash tables. They selected an algorithm, a hashing algorithm (SipHash) and developed an implementation specifically to avoid such anomalies. But quadratics are sneaky creatures, and unexpected correlations can bite any algorithm based on statistical independence.

For my part, this was one of the harder bugs I’ve written up to understand. When the ticket was initially linked to me, I had to read it several times and read up on robin hood hashing and try several approaches to developing intuitions about the system before it began to make sense to me. But even then, when I sat down to write this post, I realized I had oversimplified it in my head and my explanation was wrong! I had to resort to a lot of experimentation with the above test case before I was confident I understood the dynamics.

Surprisingly to me, the specific dynamics of Robin Hood hashing end up being relatively unimportant here; I believe that vanilla linear probing would exhibit similar behaviors. The key effect of Robin Hood hashing is just that it gives you confidence and/or hubris to push a table to 90% capacity, which greatly exacerbates the problem.

Go's text/template package implements a templating system for Go. Like many templating systems, when it loads a template it parses it into an AST, which can then be walked to render the template against one or more inputs.

AST nodes in the template AST hold the line number from which that element was parsed, primarily for better error-reporting.

In go1.7.3 and earlier, as the AST is walked, the line number field of each element is filled in by counting the newlines since the start of the file.

Of course, this means that for an N-line file containing roughly a template directive every few lines, we have to count through O(N²) newlines, making template parsing quadratic in file line count!

go1.8 will update the lexer to count the line number as it lexes and sees newlines, restoring linear-time behavior.

They wrote a really nice postmortem, analyzing, explaining the problem, and a linear time fix:

http://stackstatus.net/post/147710624694/outage-postmortem-july-20-2016

I see quadratic time regular expressions all the time, and there have been multiple submitted that I haven’t posted just because they’re so common. This one is noteworthy because of the scale of impact it had.

A few days ago, Benjamin Encz blogged an excellent writeup of disassembling and reverse engineering UIKit to track down an incident of accidentally quadratic behavior in Apple's UIKit when adding subviews.

[Ed note: This post was contributed by Dougall Johnson via email, and edited by me, with permission]

Dolphin is a Wii/GameCube emulator. A few years back, it had a bug where it was crashing with the error "Trampoline cache full" during the "Super Smash Bros. Brawl" character selection screen.

Dolphin uses a JIT compiler that translates blocks of PowerPC code from Wii or GameCube games into x86-64 instructions as the game runs. It generally uses a feature called "fastmem", to quickly emulate the Wii’s memory management unit by leveraging the host’s memory management. Fastmem configures a 4GB range of memory to match the Wii’s address space, and PPC memory accesses are translated directly to x86 memory accesses into this region. Certain parts of memory are special and require more complex handling: for example, the FIFO address which sends all data written to it to the GPU. Fastmem doesn’t map these parts of memory, so when JIT code tries to write to the FIFO a fault occurs. Dolphin handles these faults, and simulates the behaviour of special areas of memory (in the FIFO write example, by buffering the data and sending it to the emulated GPU).

However fault handling is extremely slow, so Dolphin also “back patches” the faulting instruction to call directly into the full memory-write code (implemented in C). This requires saving registers and setting up the arguments for the C function, which is much bigger than a single “write” instruction, so Dolphin generates some “trampoline” code to invoke the C code, and patches the write instruction with a call instruction in the original JIT code.

4MB of JIT memory is allocated for trampoline generation (the “trampoline cache”) and this was somehow being exceeded, even though each trampoline is very small and there couldn’t have been more than a few thousand write instructions needing patching in the game code.

However, it turns out that writing to the FIFO is slightly more complicated than it looks. Whenever a write overflows the FIFO buffer, Dolphin adds the address to an internal table (jit->js.fifoWriteAddresses) and triggers a recompilation of the faulting address, which will cause additional exception-handling code to be compiled in. The code that handles this looks like:

void CompileExceptionCheck() { std::unordered_set<u32> *exception_addresses; exception_addresses = &jit->js.fifoWriteAddresses; if (PC != 0 && (exception_addresses->find(PC) == exception_addresses->end())) { int optype = GetOpInfo(Memory::ReadUnchecked_U32(PC))->type; if (optype == OPTYPE_STORE || optype == OPTYPE_STOREFP || optype == OPTYPE_STOREPS) { exception_addresses->insert(PC); // Invalidate the JIT block so that it gets recompiled // with the external exception check included. jit->GetBlockCache()->InvalidateICache(PC, 4); } } }

The key detail here is InvalidateICache(PC, 4), which invalidates the compiled code for the entire basic block containing PC (since code is JIT'ed a basic block at a time, there's no way to invalidate a smaller range).

When the block is next invoked, the JIT compiler re-compiles the code, adding an external exception check because the instruction is in jit->js.fifoWriteAddresses (which is the whole point of the recompilation). Recompiling inadvertently has the side effect of removing any back-patches from the code. Because of the exception_addresses->find(PC) check in the above function, this recompilation can only occur once per distinct instruction that writes to the FIFO.

It turns out that there is a single block of code in Super Smash Bros. Brawl which contains 216 FIFO write instructions. You can see the PPC assembly code here: http://codepad.org/XMRCtzaG .

JITing and then executing this block will generate 216 faults (one for each write), 216 back-patches, and 216 trampolines.

However, as the code runs, eventually each of those 216 FIFO writes will happen to be the write that overflows the FIFO. When that happens, it will trigger a recompilation of the entire block, meaning the next execution will result in an additional 216 faults, backpatches, and trampolines.

In the limit, this can lead to 217 compilations of this block (the initial one, plus one per write), each of which results in 216 backpatches, for a theoretical limit of 46872 trampolines! This accidentally-quadratic trampoline generation was more than sufficient to blow the 4MB cache.

The bug was initially fixed by adding a map lookup to find and reuse existing trampolines. Later, the constant propagation was improved to detect all the FIFO writes ahead of time, avoiding all back patching in this case.

Confusingly, the bug first appeared in Dolphin 4.0-140, which was a tiny patch, that introduced the following code, just before generating each write instruction:

// Helps external systems know which instruction triggered the write MOV(32, M(&PC), Imm32(jit->js.compilerPC));

Prior to this commit, the PC wasn't updated within the block (only at the start/end), so each block would only have been recompiled once, preventing the excessive trampoline generation. At that time, the character selection screen in Super Smash Bros. Brawl would work with only 1500 trampolines generated. After that commit, the trampoline count would start at around 4000 and quickly grow to over 20000.

For more interesting Dolphin stories, see the Dolphin Progress Reports (https://dolphin-emu.org/blog/), and “Gekko the Dolphin” by Fiora in PoC||GTFO 0x06 (https://www.alchemistowl.org/pocorgtfo/pocorgtfo06.pdf — 97MB PDF).

Apache Spark is a cluster computing engine, essentially an alternative computation model to MapReduce for executing jobs across large clusters.

Spark's scheduler stores pending work on a number of arrays, to keep track of which work is available to be executed where in the cluster.

In Spark 1.6, a bug was introduced, that meant that any time Spark added a new task to one of these arrays, it would first exhaustively search the array to ensure it wasn't re-adding a duplicate.

Since the array search is O(n), this resulted in O(n²) behavior to schedule n tasks.

Like all good accidentallyquadratic bugs, this went unnoticed until some poor user tried to submit 200k jobs to their Spark install in one go, and observed it hanging for effectively forever.

It turns out that the code didn't actually require the uniqueness guarantee in the array, so the fix was simply to remove the check. (Of course, if they had needed the check, keeping a secondary hash map, or turning the array into an ordered hash map, would likely have worked just as well).

If you’re a programmer, there’s a good chance you noticed the node.js left-pad fiasco of a few weeks back that temporarily broke most of the npm ecosystem.

This blog doesn’t have an opinion on any of that. However, in the ensuing kerfluffle, several people observed that left-pad appears to be quadratic, and that is definitely this blog’s concern.

If we look at the code, we see that the main loop looks like so:

while (++i < len) { str = ch + str; }

In most languages’ string implementations, this would be definitely quadratic — + copies the entire string (of size O(len)) on each iteration, and this loop runs O(len) times.

However, I happen to know that modern JS implementations have a whole pile of complex String optimizations, including rope-like data structures. And this is an evidence-driven blog, so I decided to take a deeper look. And what I found is fascinating and bizarre and I honestly can’t explain it yet.

The benchmarks

But let’s start with something easy. I ran a benchmark in rhino, which I judged to be the javascript implementation that I had easy access to least likely to have super-advanced string optimizations. We can clearly see the telltale quadratic curve:

But now let’s try something a bit more sophisticated, which also happens to be my primary browser: Chrome. Running a left-pad benchmark in Chrome yields the following result:

There’s bit of anomalous behavior, especially at small sizes, but it makes a compelling case for being linear out through the 1MB limit I ran the test over!

(I’m running Chrome Version 50.0.2661.57 beta (64-bit); your results may well vary with Chrome version!)

And in fact, the Chrome developer tools will let us see the rope structure that Chrome has used to make these concatenations efficient! If we leftpad('hi', 100000, 'x') in a Chrome console and then take a heap snapshot, we can see that the string is a “concatenated string” made up of a huge number of chunks linked together:

(The downside of this optimization, as you can also see from that screenshot, is that our 100kb string now consumes 4MB of RAM…)

Moving on, we can also try Safari, another modern browser with an incredibly-sophisticated Javascript engine. In Safari, we see this odd behavior:

It’s a bit hard to be sure, but the data appears to fit two linear fits, with a cutover somewhere around 350k. This pattern was reproducible across multiple experiments, but I don’t have an explanation.

I also decided to try node, since that is the actual runtime that NPM primarily targets, after all. node runs the same v8 engine as Chrome, so we’d expect similar behavior, but version skew, configuration, or who knows what could cause divergence. And in fact, we see:

Oddly, it also seems to exhibit two separate linear regimes!

At this point, I’m out of energy for what was meant to be a short post, but if anyone can follow-up and explain what’s happening, I’d be terribly curious.

In Conclusion

The /proc/ filesystem, if you're not familiar with it, is a magical place full of all kinds of useful debugging tools for introspecting (and modifying) the state of a Linux machine – especially for inspecting other processes.

/proc/<pid>/maps shows, for any process on the system, a list of all of the memory mappings in its address space. For a simple cat execution on my machine, it looks like:

[nelhage@nelhage:~]$ cat /proc/self/maps 00400000-0040b000 r-xp 00000000 09:01 254164 /bin/cat 0060a000-0060b000 r--p 0000a000 09:01 254164 /bin/cat 0060b000-0060c000 rw-p 0000b000 09:01 254164 /bin/cat 007dc000-007fd000 rw-p 00000000 00:00 0 [heap] 7fc8e702b000-7fc8e72f4000 r--p 00000000 fc:00 4861 /usr/lib/locale/locale-archive 7fc8e72f4000-7fc8e74af000 r-xp 00000000 09:01 223514 /lib/x86_64-linux-gnu/libc-2.19.so 7fc8e74af000-7fc8e76ae000 ---p 001bb000 09:01 223514 /lib/x86_64-linux-gnu/libc-2.19.so 7fc8e76ae000-7fc8e76b2000 r--p 001ba000 09:01 223514 /lib/x86_64-linux-gnu/libc-2.19.so 7fc8e76b2000-7fc8e76b4000 rw-p 001be000 09:01 223514 /lib/x86_64-linux-gnu/libc-2.19.so 7fc8e76b4000-7fc8e76b9000 rw-p 00000000 00:00 0 7fc8e76b9000-7fc8e76dc000 r-xp 00000000 09:01 221267 /lib/x86_64-linux-gnu/ld-2.19.so 7fc8e78cc000-7fc8e78cf000 rw-p 00000000 00:00 0 7fc8e78d9000-7fc8e78db000 rw-p 00000000 00:00 0 7fc8e78db000-7fc8e78dc000 r--p 00022000 09:01 221267 /lib/x86_64-linux-gnu/ld-2.19.so 7fc8e78dc000-7fc8e78dd000 rw-p 00023000 09:01 221267 /lib/x86_64-linux-gnu/ld-2.19.so 7fc8e78dd000-7fc8e78de000 rw-p 00000000 00:00 0 7fffd912a000-7fffd914b000 rw-p 00000000 00:00 0 [stack] 7fffd91a9000-7fffd91ab000 r-xp 00000000 00:00 0 [vdso] ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0 [vsyscall]

Notably, /proc/$pid/maps attempts to label each mapping with information about its provenance. For regions that map files, the kernel has to track this information directly, anyways, but for regions like the [heap] and [stack] maps, it's more heuristic.

As of kernel 3.3, the kernel attempts to mark stacks of any thread that is part of that process, as [stack:<thread-id>].

However, the code that checks if a mapping is a stack does so by looping over each thread in the process, to check if its stack pointer points into that mapping.

Since each thread will typically have its own stack, and each stack is typically its own mapping, this means that enumerating /proc/$pid/maps is quadratic in the number of threads in a process. For most applications this isn't a big deal, but if we consider, say, a database that uses a thread per connection, and has 10s of thousands of connections, we can rapidly get very sad…

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.