Drill Bits

RSS
Sort By:

Efficient Graph Search

Welcome to Drill Bits, a new column about programming. This inaugural episode shows how graph search algorithms can avoid unnecessary work. A simple modification to classic breadth-first search improves the lower bound on its running time: Whereas classic BFS always requires time proportional to the number of vertices plus the number of edges, the improved "Efficient BFS" sometimes runs in time proportional to the number of vertices alone. Both asymptotic analysis and experiments show that Efficient BFS can be much faster than classic BFS.

September 13, 2020

Topic: Visualization

0 comments

Decentralized Computing

Feeding all relevant inputs to a central solver is the obvious way to tackle a problem, but it's not always the only way. Decentralized methods that make do with only local communication and local computation are sometimes the best way. This episode of Drill Bits reviews an elegant protocol for self-organizing wireless networks that can also solve a seemingly impossible social networking problem. The protocol preserves privacy among participants and is so simple that it can be implemented with pencil, paper, and postcards. Example software implements both the decentralized protocol and a centralized solver.

November 16, 2020

Topic: Distributed Computing

0 comments

Offline Algorithms in Low-Frequency Trading:
Clearing Combinatorial Auctions

Expectations run high for software that makes real-world decisions, particularly when money hangs in the balance. This third episode of the Drill Bits column shows how well-designed software can effectively create wealth by optimizing gains from trade in combinatorial auctions. We'll unveil a deep connection between auctions and a classic textbook problem, we'll see that clearing an auction resembles a high-stakes mutant Tetris, we'll learn to stop worrying and love an NP-hard problem that's far from intractable in practice, and we'll contrast the deliberative business of combinatorial auctions with the near-real-time hustle of high-frequency trading.

January 27, 2021

Topic: Development

0 comments

Schrödinger's Code:
Undefined behavior in theory and practice

Undefined behavior ranks among the most baffling and perilous aspects of popular programming languages. This installment of Drill Bits clears up widespread misconceptions and presents practical techniques to banish undefined behavior from your own code and pinpoint meaningless operations in any software—techniques that reveal alarming faults in software supporting business-critical applications at Fortune 500 companies.

May 26, 2021

Topic: Development

0 comments

Crashproofing the Original NoSQL Key-Value Store

Fortifying software to protect persistent data from crashes can be remarkably easy if a modern file system handles the heavy lifting. This episode of Drill Bits unveils a new crash-tolerance mechanism that vaults the venerable gdbm database into the league of transactional NoSQL data stores. We'll motivate this upgrade by tracing gdbm's history. We'll survey the subtle science of crashproofing, navigating a minefield of traps for the unwary. We'll arrive at a compact and rugged design that leverages modern file-system features, and we'll tour the production-ready implementation of this design and its ergonomic interface.

September 19, 2021

Topic: Databases

0 comments

Steampunk Machine Learning:
Victorian contrivances for modern data science

Fitting models to data is all the rage nowadays but has long been an essential skill of engineers. Veterans know that real-world systems foil textbook techniques by interleaving routine operating conditions with bouts of overload and failure; to be practical, a method must model the former without distortion by the latter. Surprisingly effective aid comes from an unlikely quarter: a simple and intuitive model-fitting approach that predates the Babbage Engine. The foundation of industrial-strength decision support and anomaly detection for production datacenters, this approach yields accurate yet intelligible models without hand-holding or fuss.

January 18, 2022

Topic: AI

0 comments

Persistent Memory Allocation:
Leverage to move a world of software

A lever multiplies the force of a light touch, and the right software interfaces provide formidable leverage in multiple layers of code: A familiar interface enables a new persistent memory allocator to breathe new life into an enormous installed base of software and hardware. Compatibility allows a persistent heap to slide easily beneath a widely used scripting-language interpreter, thereby endowing all scripts with effortless on-demand persistence.

May 11, 2022

Topic: Data

0 comments