Neal Gafter writes: I just fixed a bug in the implementation of constant folding in the C# and VB.Net compilers. They used to require O(n^2) space. Now they require O(n) space. The naive approach to implementing string concatenation for an expression such as "S1" + "S2" + "S3" is to recursively visit the left-hand and right-hand operands and compute their constant string values, and then concatenate these strings to produce the constant string for the concatenation. It seems obviously ...| Accidentally Quadratic
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...| 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.head...| Accidentally Quadratic
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 pa...| Accidentally Quadratic
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, historic...| 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. ...| Accidentally Quadratic
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, ...| Accidentally Quadratic
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: ev...| Accidentally Quadratic
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...| Accidentally Quadratic
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 fi...| Accidentally Quadratic
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. As Rob Pike points out, linking to Russ Cox’s excellent post these bugs are all the more tragic for being utterly ...| Accidentally Quadratic
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. I don’t have much to add, but readers of this blog would almost certainly enjoy his post!| Accidentally Quadratic
[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 quick...| Accidentally Quadratic
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 arra...| Accidentally Quadratic
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, severalpeopleobservedthat 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 implementati...| Accidentally Quadratic
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 0...| Accidentally Quadratic
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...| Accidentally Quadratic
(Boy is there a lot of Haskell here now. What’s up with that?) This one comes by way of Shachaf Ben-Kiki, who found it originally and mentioned it to me. Data.Traversable and Data.Foldable are two Haskell typeclasses that express related notions of a data structure being “list-like” in the sense that it contains zero or more elements, and an externally-provided function can be mapped over those elements in some way. GHC provides support (as a language extension) for automatically “der...| Accidentally Quadratic
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 start...| Accidentally Quadratic
I spent a while talking with Greg Price about the Haskell Network.HTTP issue previously featured here, and he was unconvinced I had the whole story. He spent a while reading some source and thinking...| Tumblr