a glob, not a blog ...

Hi, and welcome to my little space on the Internet ...

  • Diff and Longest Common Subsquence (LCS) with Hunt/Szymanski and Kuo/Cross algorithms

    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).

    Read on →

  • Re-engineering a qsort function (part 5)

    Comparison with some other sorts

    Read on →

  • Re-engineering a qsort function (part 4)

    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:

    Read on →

  • Re-engineering a qsort function (part 3)

    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.

    Read on →

  • Re-engineering a qsort function (part 2)

    (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.

    Read on →