[TUHS] Bell Labs sed performance

[John P. Linderman via TUHS]

Russ Cox has written extensively <https://swtch.com/~rsc/regexp/> about
regular expression matching, and why some "features", like backtracking,
may not be a good idea. -- jpl

On Mon, Mar 23, 2026 at 5:05 AM Diomidis Spinellis via TUHS <tuhs at tuhs.org>
wrote:

> Over the past year I ported the (now {Free,Net,Open})BSD version of
> sed(1) I implemented in C in the 1990s into Rust as part of the uutils
> initiative.  I've described the process in a series of four IEEE
> Software "Adventures in Code" [2] columns.  In this March's column [3] I
> compare the performance of the Rust implementation against that of GNU,
> FreeBSD, and the original 1970s Bell Labs Seventh Research Edition one
> [6].  Amazingly, in four benchmarks the Bell Labs implementation is
> still the fastest.  At 1850 lines of code (including a regular
> expression engine) it's also the smallest one (FreeBSD, 2672 LoC; GNU
> 5462; Rust, 8946).  Admittedly, modern sed versions have more features.
> Still, one can only admire the design and craftsmanship that went into
> the original implementation.
>
> [1] https://github.com/uutils/sed
> [2] https://www.spinellis.gr/adventures-in-code.html
> [3] https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=11433192
> [4] https://github.com/dspinellis/sed-research-v7
>