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

Literate Executables

Literate executables redefine the relationship between compiled binaries and source code to be that of chicken and egg, so it's easy to derive either from the other. This episode of Drill Bits provides a general-purpose literacy tool and showcases the advantages of literacy by retrofitting it onto everyone's favorite command-line utility.

November 15, 2022

Topic: Data

0 comments

Catch-23: The New C Standard Sets the World on Fire

A new major revision of the C programming language standard is nearly upon us. C23 introduces pleasant conveniences, retains venerable traps for the unwary, and innovates a gratuitous catastrophe. A few steps forward, much sideways shuffling, and a drunken backward stumble into the fireplace come together in the official dance of C standardization, the Whiskey Tango Foxtrot.

March 29, 2023

Topic: Programming Languages

0 comments

Protecting Secrets from Computers

Bob is in prison and Alice is dead; they trusted computers with secrets. Review time-tested tricks that can help you avoid the grim fate of the old crypto couple.

September 20, 2023

Topic: Security

0 comments

Programmer Job Interviews: The Hidden Agenda

Top tech interviews test coding and CS knowledge overtly, but they also evaluate a deeper technical instinct so subtly that candidates seldom notice the appraisal. We'll learn how interviewers create questions to covertly measure a skill that sets the best programmers above the rest. Equipped with empathy for the interviewer, you can prepare to shine on the job market by seizing camouflaged opportunities.

January 15, 2024

Topic: Business/Management

0 comments

Zero Tolerance for Bias

From gambling to military conscription, randomization makes crucial real-world decisions. With blood and treasure at stake, fairness is not negotiable. Unfortunately, bad advice and biased methods abound. We'll learn how to navigate around misinformation, develop sound methods, and compile checklists for design and code reviews.

May 29, 2024

Topic: Development

0 comments