Accidentally Quadratic
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...
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...
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...
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...
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...
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...
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...
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...
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() {...
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...
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...
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....
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,...
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, several people observed that left-pad appears to be...
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...
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...
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...
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...
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 about folds, and pointed out today that my analysis was incomplete, and flat-out wrong for the...