Diff and Longest Common Subsequence (LCS)

If you’ve used a diff program, you probably used a solution to the longest common subsequence (LCS) problem. The most well-known diff implementations, the original Unix diff and GNU diff, are both based on LCS solutions, but use different algorithms. Here, I’ll try to explain two related LCS algorithms informally (or less formally than in the original technical papers).

Comparison with some other sorts

Aliasing concerns

While looking at commit logs for various BSD qsort versions, I noticed this:

*   libc qsort(3): stop aliasing.   Konstantin Belousov 2018-06-10  1   -44/+17

Which led to some details:

The qsort optimization that wasn’t

In 1993, Jon Bentley and Doug McIlroy published a paper Engineering a Sort Function (also here) (Software–Practice and Experience, vol. 23 no. 11, Nov. 1993, pp 1249-1265). Since then, most C stdlib qsort functions have been based on the code and/or the ideas in that paper.

The qsort in the BSD variants and descendants have followed the code in that paper. But someone in 1994 attempted to “improve” on Bentley and McIlroy, with potentially disastrous results.

(Continued from part 1.)

I was starting to feel pretty good about my qsort implementation. I also downloaded a number of qsort implementations from various sources. Several were from libc and related implementations, including NetBSD, FreeBSD, OpenBSD, dietlibc, u-boot, μClibc and uclibc-ng, Newlib, picolibc, klibc, Bionic, and musl.