Hi, and welcome to my little space on the Internet ...
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
qsortfunctions have been based on the code and/or the ideas in that paper.
qsortin 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
qsortimplementation. I also downloaded a number of
qsortimplementations from various sources. Several were from
libcand related implementations, including NetBSD, FreeBSD, OpenBSD, dietlibc, u-boot, μClibc and uclibc-ng, Newlib, picolibc, klibc, Bionic, and musl.
I’ve been working on better (at least faster) implementations of
qsortfor 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.
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…
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.