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.

Improved qsort implementations

I’ve been working on better (at least faster) implementations of qsort for the C standard library. A long time ago I wrote an implementation of the C standard library function qsort. I thought it was pretty good, but recently I’ve made much better versions.

I have recently made my first contribution to a major (?) open source project.

The Python Imaging Library (PIL), now known as Pillow, is probably the best-known library for image processing in Python. (See documentation and source.)

I had a need to handle GIF files in Python, and I noticed some time ago that they were not compressed very well. The library was originally written by Fredrik Lundh starting in the late 1990s. Fredrik is a brilliant programmer (also created the ElementTree system for handling XML in Python, among other projects). But when he created PIL, GIFs were under a bit of a cloud.

Maybe I’m wrong, but it seems many blogs start with a post about what was involved in getting the blog going. This isn’t really a blog, but anyway…

This site is hosted on GitHub at https://raygard.github.io/, but using a custom domain https://raygard.net.

I had already done a little with Jekyll and GitHub Pages using the Just the Docs theme. I wanted to set up a site or page where I could put any sort of stuff, initially planning to point to some work I’ve put up in GitHub repositories and some open source contributions I’ve made or will make. Just the Docs is aimed at documentation and it seemed fine for some work I’ve done so far (more about that in the next post). I needed something better suited for blogging.