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.

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.