How to make generics in C: an adventure in sorting

*
Accepted Session
Short Form
Intermediate
Scheduled: Tuesday, June 24, 2014 from 4:45 – 5:30pm in B201

Excerpt

This will be a talk on how to hack C to get generics-like support,
which we used to make a super-fast C sorting library, all in headers.
We'll also talk about sorting in general, and the various kinds of
sorting algorithms, and why this hack helps so much.

Description

Sorting is hard, but it’s a rich, fun topic. It turns out that the C
standard sorting library is actually quite slow, but a very simple C
trick (token pasting) can let us easily get a 10x speed improvement.

I’m the author and primary contributor to sort.h, a simple, small, and
powerful sorting library based on this trick
(https://github.com/swenson/sort).

We’ll explain how the trick works, and what other kinds of uses you
can use it for (a lot!). For instance, I’ve also used this trick to build fast, simple, library-less vector and hash tables in C.

We’ll also go into detail on the various sorting algorithms, how they
work, and why and when this hack works.

Also, sorting algorithms are fun and actually fairly straightforward! Knowing how the tools in your coding toolbox work can help you use them more effectively. We’ll discuss some popular sorting algorithms, like quicksort, heapsort, mergesort, and timsort.

Tags

sorting, C, C++, timsort, quicksort, optimization, python, java, beginner, intermediate

Speaking experience

I've spoken at PyCon 2012 and OSCON 2012, and
numerous meetups and organizations (PDX Git in 2013, PDX Python in
2013, DC PyLadies, PyLadies PDX, ...).

http://pyvideo.org/video/652/sage-open-source-math-in-python

Speaker