The self-indulgent ramblings of a Danish hacker.

Ok, I am a lazy bastard…

I have never really spent the time to create myself a good, simple gcc Makefile template. I always end up hacking something together at the last minute. So… yesterday I took some time to do a simple, reusable, cross-platform Makefile to be used with my small C projects:

# Executable, object names and library/linker flags
EXECUTABLE  = program
OBJECTS     = program.o other.o stuff.o

# Common compiler and linker flags
CFLAGS  = -Wall -Werror -m64
LDFLAGS = -lpthread

# OS-specific stuff
OS = $(shell uname -s)
ifeq ($(OS), Darwin)
	STRIP_OPTIONS = -u -r -arch all
endif
ifeq ($(OS), Linux)
	STRIP_OPTIONS = -s
endif

# release/all: Set additional flags, build and strip executable
all: CFLAGS += -O3 -fomit-frame-pointer -funroll-loops
all: $(EXECUTABLE)
	strip $(EXECUTABLE) $(STRIP_OPTIONS)

# debug: Set additional flags and build executable
debug: CFLAGS += -O0 -g -DGX_DEBUG
debug: $(EXECUTABLE)

# clean: Remove executable and object files (rarely needs to be changed)
clean:
	rm -f $(EXECUTABLE) $(OBJECTS)

# Complete compiler string
CC = gcc $(CFLAGS)

# Link objects into executable (rarely needs to be changed)
$(EXECUTABLE): $(OBJECTS)
	$(CC) -o $@ $^ $(LDFLAGS)

# Compile all files to objects (rarely needs to be changed)
%.o: %.c
	$(CC) -c $<

This will allow you to use “make” to do a release build, “make debug” to build a debug build, and finally “make clean” to remove all produced files. Suggestions are welcome!

{ 6 comments }

Thought I would share another little code gem. This one is really cool.

Suppose you have a sorted array of integers, and you want to find the index of a particular element, if it’s in there, or the closest match.

The naïve way of doing it is by linear search, which may be the fastest thing for very small arrays (less than 10 elements). For larger arrays you are much better off using binary search. To those of you, who are unfamiliar with binary search methods, the idea is very simple.

Compare your needle (number you are looking for) to the central element of the haystack (the array you are searching). If the needle is smaller than the central element, you continue your search by repeating the procedure on the left part of the array (and vice versa).

This allows you to find the element you are looking for in O(log n) time, meaning that for n elements, you only need to do about log n comparisons, eg. if n is 1024, you only need to do 10 comparisons. This is of course much better than doing a simple, linear search, which, for random array and needle, would need 512 comparisons on average!

What I want to show you is a very elegant way of doing a binary search of an array of fixed size – in this case 256 integers.

int unrolled_binary_search(int *haystack, int needle)
{
  int i = 0;

  if (haystack[    128] <= needle) i += 128;
  if (haystack[i +  64] <= needle) i +=  64;
  if (haystack[i +  32] <= needle) i +=  32;
  if (haystack[i +  16] <= needle) i +=  16;
  if (haystack[i +   8] <= needle) i +=   8;
  if (haystack[i +   4] <= needle) i +=   4;
  if (haystack[i +   2] <= needle) i +=   2;
  if (haystack[i +   1] <= needle) i +=   1;

  return i;
}

This little piece of code is not only beautiful. It is also very, very fast. Instead of having a loop, such as a “for” statement, we have unrolled the loop, which eliminates some CPU instructions when it… comes out the other end. There are a few other optimizations, that can be done, but that would spoil the simplicity of the code. Enjoy.

{ 0 comments }

As a follow-up to my last post, I thought, I would provide you with an unsigned version of the same algorithm. The last algorithm, that I provided you with, will underflow, if you plug in unsigned variables.

Here is a more robust version.

void ternary_quicksort(unsigned int *a, unsigned int begin, unsigned int end)
{
  unsigned int i, j, k, p, x;

  if (begin < end) {

    i = j = begin;
    k = end;

    // Calculate median pivot
    p = median(a[i], a[k], a[(i + k) >> 1]);

    // Partition
    do {
      if      (a[j] < p) swap(a, i++, j++);
      else if (a[j] > p) swap(a, j, --k);
      else j++;
    } while (j < k);

    // Recurse
    ternary_quicksort(a, begin, i);
    ternary_quicksort(a, k, end);
  }
}

Note, that I have changed “end” to mean, not the last element, but the first element not in the array. This is more compatible with other range specifications and leads to less confusing code.

{ 0 comments }

Hi guys, it’s code sharing time!

This weekend, I started a new pet project. I produced a lot of code, and thought I would share a tiny bit, that turned out surprisingly fast, clean and simple.

The code is a ternary, or three-way, quicksort. It is an extension of Hoare’s original quicksort, that is both faster and more useful, i.e. we have a win-win situation on our hands.

In the original quicksort algorithm, you sort a set by going through the following three steps:

1. Pick a pivot value from the set. This can be done in several ways.
2. Partition the set into two subsets – one containing elements smaller and one containing elements larger than the pivot.
3. Recurse on these two smaller subsets, i.e. invoke this function successively on the two subsets.

A ternary quicksort splits each set into three subsets instead – one smaller, one larger and one with values equal to the pivot. Sounds like more work, right? Wrong!

Let us sum up the algorithm to compare it with the standard quicksort:

1. Pick a pivot value from the set.
2. Partition the set into the three subsets.
3. Recurse on the smaller and the larger one.

At this point, you can begin to see the performance benefit. We are no longer recursing over two half sets (excluding the pivot). Instead, we fix the elements that equal the pivot in the center. This way, we avoid shuffling these “equal” elements around in subsequent calls/rounds. Another benefit is, that should be apparent from the code below is, that we keep track of the middle part as well, which is quite useful if you are doing string (or similar multikey) sorting – maybe I will write more on this in a later post.

Here is the code:

void ternary_quicksort(int *a, int begin, int end)
{
  int i, j, k, p;

  if (begin < end) {

    i = begin;
    k = end;

    // Calculate median pivot
    p = median(a[i], a[k], a[(i + k) >> 1]);

    // Partition
    j = i;
    while (j <= k) {
      if      (a[j] < p) swap(a, i++, j++);
      else if (a[j] > p) swap(a, j, k--);
      else j++;
    }

    // Recurse
    ternary_quicksort(a, begin, i - 1);
    ternary_quicksort(a, k + 1, end);
  }
}

Note, that we are using the median of the first, last and central element as our pivot. The median is simply the element, that has the “middle value” of the set, eg. median(3, 7, 2) = median(2, 3, 7) = 3.

inline int median(int vi, int vj, int vk)
{
  if (vi <= vj) {
    if (vj <= vk) return vj;
    else if (vi <= vk) return vk;
    else return vi;
  } else {
    if (vi <= vk) return vi;
    else if (vk <= vj) return vj;
    else return vk;
  }
}

The swap method is just a trivial swap of the elements in the array:

inline void swap(int *a, int i, int j)
{
  register int k;
  register int l;

  k     = a[i];
  l     = a[j];
  a[i]  = l;
  a[j]  = k;
}

Here be dragons! Note, that this is not a classic implementation of the algorithm. I have done away with the pivot element, as the only thing, we really need, is a pivot value to group around. Hopefully, it still works.

{ 0 comments }