Category Archives: C

Benchmarking string hash tables

So first let’s try the Google farmhash hash function, using a few fast hash table implementations.

We will do a similar benchmark as the one we did for integers a while back, but with strings. Actually, let’s add an integer version as well.

Continue reading Benchmarking string hash tables

Advertisements

Benchmarking dynamic array implementations

Continuing looking at the performance of data structures and different implementations and languages, let’s look at a simpler but very common container, the dynamic array.

The interesting performance properties of a dynamic array is constant, O(1), lookup time and amortized constant insertion and deletion at the end of the array. Random insertion on the other hand is linear, O(n), and typically something you want to avoid.

Continue reading Benchmarking dynamic array implementations

libdynamic – vector

I think the lack of simple and basic dynamic data structures is a major reason why people sometimes struggle with programming in C.

To take a simple example the naive task of splitting a string into words is near trivial in C++ using the standard library, while in C you are challenged with how to dimension the resulting array. In most cases likely the solution here would be to declare a fixed size array with a MAX_WORDS constant size, and later when the parsing is done and you know the number of words, declare a new array into which you copy the result, and then return. Hardly an elegant solution, and you end up with making difficult assumptions regarding how many words a line realistically can contain.

Continue reading libdynamic – vector