A Simple Generic Vector Container in C

I do not see much need to have a vector container in C as a vector is simply an array and array operations are all very simple. Nontheless, it might still better to implement one, for the sake of completeness. Here is the code. The library is almost as fast as the fastest code you can write in C.

#ifndef AC_KVEC_H
#define AC_KVEC_H

#include
#include

#define kv_roundup32(x) (–(x), (x)|=(x)>>1, (x)|=(x)>>2, (x)|=(x)>>4, (x)|=(x)>>8, (x)|=(x)>>16, ++(x))

#define kvec_t(type) struct { uint32_t n, m; type *a; }
#define kv_init(v) ((v).n = (v).m = 0, (v).a = 0)
#define kv_destroy(v) free((v).a)
#define kv_A(v, i) ((v).a[(i)])
#define kv_pop(v) ((v).a[–(v).n])
#define kv_size(v) ((v).n)
#define kv_max(v) ((v).m)

#define kv_resize(type, v, s) ((v).m = (s), (v).a = (type*)realloc((v).a, sizeof(type) * (v).m))

#define kv_push(type, v, x) do { \
if ((v).n == (v).m) { \
(v).m = (v).m? (v).m<<1 : 2; \ (v).a = (type*)realloc((v).a, sizeof(type) * (v).m); \ } \ (v).a[(v).n++] = (x); \ } while (0) #define kv_pushp(type, v) (((v).n == (v).m)? \ ((v).m = ((v).m? (v).m<<1 : 2), \ (v).a = (type*)realloc((v).a, sizeof(type) * (v).m), 0) \ : 0), ((v).a + ((v).n++)) #define kv_a(type, v, i) ((v).m <= (i)? \ ((v).m = (v).n = (i) + 1, kv_roundup32((v).m), \ (v).a = (type*)realloc((v).a, sizeof(type) * (v).m), 0) \ : (v).n <= (i)? (v).n = (i) \ : 0), (v).a[(i)] #endif [/sourcecode]

Thoughts on Generic Programming in C

I came across two interviews (here and here) of Alexander Stepanov, the father of STL. There are quite a lot of interesting bits. For example, he thinks C++ is the best programming language to realize his goal, but he is also strongly against OOP at the same time. In addition, he has paid a lot of efforts on efficiency, which we can see from STL. He said: “It is silly to abstract an algorithm in such a way that when you instantiate it back it becomes inefficient”. I like these two interviews because I think in the same way. The only exception is I do not use STL, although I think it is the best generic library and I like it a lot. But why?

Two reasons. Firstly, STL is written in C++, which makes it unavailable to all C projects. It is possible to only use STL and forget all the other features in C++, but people rarely do so. At least I have not seen such a project where STL is combined with procedural programming. In addition, C++ projects are usually less portable than C projects and STL makes it worse. It puts a lot of stress on C++ compilers. Even Stepanov agreeed, by the time of the interview, that “The unfortunate reality is that a lot of code in the present implementation of STL is suboptimal because of the compiler limitations and bugs of the compilers I had to use when I was developing STL”. Secondly, using STL also means much longer compiling time. I remembered I used to compile a customized Linux kernel for my old laptop in an hour. Probably I would spend more than a day to compile if it was written using C++/STL.

A generic container library would benefit a lot of C programmers, but so far I am not aware of any efficient implementation. Glib tries to achieve so, but it uses void* and this inevitably will incur overhead and complicate interfaces. And finally, I decide to write my own one. Ideally (but probably impractically) I want to achieve four goals: a) efficiency in speed and space; b) elegance in interface; c) independency between functinality and d) simplicity in codes. However, currently I am not competent enough to achieve all these goals and I am not a professional programmer at all (and so cannot invest enough time). As I said in my About page, I mainly do this to please myself.

C Array vs. C++ Vector

Here is a piece of source codes that compare C arrays and C++ vectors. It tests six scenarios: a) preallocated C array; b) dynamically growing C array; c) dynamical C vector calling kv_a macro (in my kvec.h); d) dynamical C vector calling kv_push macro (in my kvec.h); e) preallocated C++ vector and f) dynamically growing C++ vector. You can find my kvec.h on my blog.

#include
#include
#include
#include
#include “kvec.h”

int main()
{
int M = 10, N = 20000000, i, j;
clock_t t;
t = clock();
for (i = 0; i < M; ++i) { int *array = (int*)malloc(N * sizeof(int)); for (j = 0; j < N; ++j) array[j] = j; free(array); } printf("C array, preallocated: %.3f sec\n", (float)(clock() - t) / CLOCKS_PER_SEC); t = clock(); for (i = 0; i < M; ++i) { int *array = 0, max = 0; for (j = 0; j < N; ++j) { if (j == max) { max = !max? 1 : max << 1; array = (int*)realloc(array, sizeof(int)*max); } array[j] = j; } free(array); } printf("C array, dynamic: %.3f sec\n", (float)(clock() - t) / CLOCKS_PER_SEC); t = clock(); for (i = 0; i < M; ++i) { kvec_t(int) array; kv_init(array); kv_resize(int, array, N); for (j = 0; j < N; ++j) kv_a(int, array, j) = j; kv_destroy(array); } printf("C vector, dynamic (kv_a): %.3f sec\n", (float)(clock() - t) / CLOCKS_PER_SEC); t = clock(); for (i = 0; i < M; ++i) { kvec_t(int) array; kv_init(array); for (j = 0; j < N; ++j) kv_push(int, array, j); kv_destroy(array); } printf("C vector, dynamic (kv_push): %.3f sec\n", (float)(clock() - t) / CLOCKS_PER_SEC); t = clock(); for (i = 0; i < M; ++i) { std::vector array;
array.reserve(N);
for (j = 0; j < N; ++j) array[j] = j; } printf("C++ vector, preallocated: %.3f sec\n", (float)(clock() - t) / CLOCKS_PER_SEC); t = clock(); for (i = 0; i < M; ++i) { std::vector array;
for (j = 0; j < N; ++j) array.push_back(j); } printf("C++ vector, dynamic: %.3f sec\n", (float)(clock() - t) / CLOCKS_PER_SEC); return 0; } [/sourcecode] Here is the result on two machines (compiled with g++ -O2 -fomit-frame-pointer -finline-functions):

type	MacIntel	LinuxIntel
C array, preallocated	1.589	1.180
C array, dynamic	2.064	1.340
C vector, dynamic (kv_a)	2.051	1.600
C vector, dynamic (kv_push)	1.932	1.250
C++ vector, preallocated	2.119	1.590
C++ vector, dynamic	5.095	3.770

Such result may vary with different machines/compilers, but not much.

Update: My example passed valgrind check on a Linux (Debian etch, g++-4.1), but Tom_ pointed out that it did not pass VC++’s debugger as vector::operator[] writes outside vector::size(). Anyway, it is good not to use operator[] in my way. You can replace reserve()+[] with resize()+[] or reserve()+push_back(). On my machine, the replacement gives a little bit slower speed, but it is safer/more portable in that way. Thanks for all the comments.

Calculating Median

Here is an example that google does not give me the result in the first page. I want to know how to calculate median efficiently, and so I search “c calculate median”. In the first result page, google brings me to several forums which only show very naive implementations. The 11th result, this page, is the truely invaluable one which should be favoured by most programmers. I do not want to replicate that website. I just want to show you a function that is adapted from quickselect.c on the website. This function calculates the k-smallest (0<=k<n) element in an array. Its time complexity is linear to the size of the array and in practice it runs much faster than sorting and then locating the k-smallest element.

type_t ks_ksmall(size_t n, type_t arr[], size_t kk)
{
	type_t *low, *high, *k, *ll, *hh, *middle;
	low = arr; high = arr + n - 1; k = arr + kk;
	for (;;) {
		if (high <= low) return *k;
		if (high == low + 1) {
			if (cmp(*high, *low)) swap(type_t, *low, *high);
			return *k;
		}
		middle = low + (high - low) / 2;
		if (lt(*high, *middle)) swap(type_t, *middle, *high);
		if (lt(*high, *low)) swap(type_t, *low, *high);
		if (lt(*low, *middle)) swap(type_t, *middle, *low);
		swap(type_t, *middle, *(low+1)) ;
		ll = low + 1; hh = high;
		for (;;) {
			do ++ll; while (lt(*ll, *low));
			do --hh; while (lt(*low, *hh));
			if (hh < ll) break;
			swap(type_t, *ll, *hh);
		}
		swap(type_t, *low, *hh);
		if (hh <= k) low = ll;
		if (hh >= k) high = hh - 1;
	}
}

In this funcion, type_t is a type, swap() swaps two values, and lt() is a macro or a function that returns true if and only if the first value is smaller.

The Google Dense Hashtable Library

Google dense hash table (google-dense) implements an open addressing hash table with quardric probing. It requires users to set an empty element and a deleted element which are distinct from all the other valid keys in the hash table. Google-dense tests whether a bucket is empty or deleted by performing key comparisons. It is fast for integer keys where comparisons are cheap but will have overhead for string keys. In contrast, khash uses a bit vector to record which bucket is empty or deleted. On string keys, it avoids overhead for additional string comparisons, but will incur a potential cache miss when it is checking the bit vector. It seems that this cache miss costs a little less than one or two string comparisons. As a consequence, google dense hash is more efficient for simple keys and khash is more efficient for complex keys. This is what we see from my hash table benchmark.

Another difference between google-map (plus almost all the other hash map implementations I am aware of) and khash-map is that google-map keeps key-value pair in one array while khash-map keeps keys and values in two separate arrays. Keeping one array helps cache efficiency because we will not incur a cache miss when we have located the bucket via a key. However, putting a key and a value in one struct/class will waste memory when the key type and the value type are not aligned. For example, on 64-bit systems, if the key type is “const char*” and the value type is “int”, 25% of memory is wasted on memory alignment. Keeping two separate arrays like khash will not have this problem, but this strategy will cost one additional cache miss when we retrieve a value. Khash was initially designed for a huge hash table with 64-bit integers as keys and 8-bit integers as values. 44% of memory would be wasted on memory alignment if I put key-value pair in a struct. This was unacceptable for that application. Whether to separate keys and values is a tradeoff between memory and speed.

Where to Find Good Programmers?

It is always good to learn from good programmers, but where are they? Do they write blogs, join forums or discuss in some mailing lists? It seems to me that most of them do not. The few who do so only write posts or send emails very occassionally. I guess most good programmers are busy with programming in computer languages instead of writing in natural languages, which in fact is why they become good programmers.

In finding good programmers, I have checked quite a few blogs. Most of the bloggers (including me unfortunately) act as good programmers. They are presenting their thoughts on some concepts or quarrelling over what is better. But they do not present source codes, or just give elementary pieces of codes, from which no one can ever tell their abilities. What is the meaning to hear the thought of a bad programmer? If I cannot tell, I would simply ignore their words.

I have also joined comp.lang.c for a few days. It also disappoints me, at least up to now. Again, most people argue over details of concepts or show off their knowledges which I do not think necessary in a lot of cases. A lot of people here like to ignore the central issue and to extend the discussions on mediocre points to nowhere. Few present high-quality source codes and again I do not know who are really good programmers or who are just good lecturers on C. Probably good programmers in this list do not have the time to show their abilities. I need to wait a bit longer.

Then where to find good programmers? I would suggest searching for good codes first and then for the authors behind those codes. Here is an example that how I found a good programmer. I came across jemalloc written by Jason Evans and then I noticed his implementation of red-black tree. Further search brought me to his blog. Only a few posts there but you can quickly know he is a good programmer. I would say his thoughts on programming weight much more than the most emails I have seen on the newsgroup or the blogs I have read there several days. Always remember: before reading one’s thoughts, read his/her codes first.

Implementing Generic Hash Library in C

Synopsis

Here is an simple example showing how to use khash.h library:

#include "khash.h"
KHASH_MAP_INIT_INT(32, char)
int main() {
	int ret, is_missing;
	khiter_t k;
	khash_t(32) *h = kh_init(32);
	k = kh_put(32, h, 5, &ret);
	if (!ret) kh_del(32, h, k);
	k = kh_get(32, h, 10);
	is_missing = (k == kh_end(h));
	k = kh_get(32, h, 5);
	kh_del(32, h, k);
	for (k = kh_begin(h); k != kh_end(h); ++k)
		if (kh_exist(h, k)) kh_value(h, k) = 1;
	kh_destroy(32, h);
	return 0;
}

The second line says we want to use a hash map with int as key and char as value. khash_t(int) is a type. kh_get() and kh_put() returns an iterator, or the position in the hash table. kh_del() erases the key-value in the bucket pointed by the iterator. kh_begin() and kh_end() return the begin and the end of iterator, respectively. And kh_exist() tests whether the bucket at the iterator is filled with a key-value. The APIs are not so concise in comparison to C++ template, but are very straightforward and flexible. How can this be done?

Achieving generic programming in C

The core part of khash.h is:

#define KH_INIT(name, key_t, val_t, is_map, _hashf, _hasheq) \
  typedef struct { \
    int n_buckets, size, n_occupied, upper_bound; \
    unsigned *flags; \
    key_t *keys; \
    val_t *vals; \
  } kh_##name##_t; \
  static inline kh_##name##_t *init_##name() { \
    return (kh_##name##_t*)calloc(1, sizeof(kh_##name##_t)); \
  } \
  static inline int get_##name(kh_##name##_t *h, key_t k) \
  ... \
  static inline void destroy_##name(kh_##name##_t *h) { \
    if (h) { \
      free(h->keys); free(h->flags); free(h->vals); free(h); \
    } \
  }

#define _int_hf(key) (unsigned)(key)
#define _int_heq(a, b) (a == b)
#define khash_t(name) kh_##name##_t
#define kh_init(name) init_##name()
#define kh_get(name, h, k) get_##name(h, k)
#define kh_destroy(name, h) destroy_##name(h)
...
#define KHASH_MAP_INIT_INT(name, val_t) \
	KH_INIT(name, unsigned, val_t, is_map, _int_hf, _int_heq)

In macro ‘KH_INIT’, name is a unique symbol that distinguishes hash tables of different types, key_t the type of key, val_t the type of value, is_map is 0 or 1 indicating whether to allocate memory for vals, _hashf is a hash function/macro and _hasheq the comparison function/macro. Macro ‘KHASH_MAP_INIT_INT’ is a convenient interface to hash with integer keys.

When ‘KHASH_MAP_INIT_INT(32, char)’ is used in a C source code file the following codes will be inserted:

  typedef struct {
    int n_buckets, size, n_occupied, upper_bound;
    unsigned *flags;
    unsigned *keys;
    char *vals;
  } kh_int_t;
  static inline kh_int_t *init_int() {
    return (kh_int_t*)calloc(1, sizeof(kh_int_t));
  }
  static inline int get_int(kh_int_t *h, unsigned k)
  ...
  static inline void destroy_int(kh_int_t *h) {
    if (h) {
      free(h->keys); free(h->flags); free(h->vals); free(h);
    }
  }

And when we call: ‘kh_get(int, h, 5)’, we are calling ‘get_int(h, 5)’ which is defined by calling KH_INIT(int) macro. In this way, we can effectively achieve generic programming with simple interfaces. As we use inline and macros throughout, the efficiency is not affected at all. In my hash table benchmark, it is as fast and light-weighted as the C++ implementation.

Other technical concerns

• Solving collisions. I have discussed this in my previous post. I more like to achieve smaller memory and therefore I choose open addressing.
• Grouping key-value pairs or not. In the current implementation, keys and values are kept in separated arrays. This strategy will cause additional cache misses when keys and values are retrieved twice. Grouping key-value in a struct is more cache efficient. However, the good side of separating keys and values is this avoids waste of memory when key type and value type cannot be aligned well (e.g. key is an integer while value is a character). I would rather trade speed a bit for smaller memory. In addition, it is not hard to use a struct has a key in the current framework.
• Space efficient rehashing. Traditional rehashing requires to allocate one addition hash and move elements in the old hash to the new one. For most hash implementations, this means we need 50% extra working space to enlarge a hash. This is not necessary. In khash.h, only a new flags array is allocated on rehashing. Array keys and values are enlarged with realloc which does not claim more memory than the new hash. Keys and values are move from old positions to new positions in the same memory space. This strategy also helps to clear all buckets marked as deleted without changing the size of a hash.

Generic Programming in C

Template in C++ is the single reason that I still keep using it. Previously, I thought generic programming in C is nothing but ugly and painful. Now I have changed my mind a bit, in the light of tree.h written by Niels Provos. Generic programming in C can be done without much pain and with just slightly less elegance in comparison to C++ implementations. How can this be done? Macros, of course. But in what form macros are used is where all the tricks come in.

The first way to achieve generic programming is to pass a type to macros. Jason Evans‘ rb.h is an example. Each operation on an RB tree is a macro. Users have to provide the type of the data in the tree and a comparison function with each macro. It is not hard to think of this way, but we can do better.

In tree.h, Niels gives a better solution: to use token concatenation. The key macro is SPLAY_PROTOTYPE(name, type, field, cmp). It is a huge macro that defines several operations, in the form of “static inline” functions, on the splay tree. These functions will be inserted to the C source code which uses the macro. Using SPLAY_PROTOTYPE() with different “name”s will insert different functions. For example, when “SPLAY_PROTOTYPE(int32, int, data, intcmp)” is invoked, the insertion function will be “int32_SPLAY_INSERT()”. Splay trees with different “name”s can coexist in one C source code because their operations have different names. At the end of tree.h, Niels further defines “#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y)”. Then In the C source code, we can call insertion with “RB_INSERT(int32, x, y)”. In comparison to a C++ template implementation, the only line you need to add is SPLAY_PROTOTYPE(). Calling operations is as easy.

I will further explain this idea when I present my khash implementation in C.

Comparison of Hash Table Libraries

As a Perl programmer, I enjoy a lot using hash tables. I keep this habit in C/C++ programming. Then what C/C++ hash libraries are available? How are they compared to each other? In this post, I will give a brief review of hash libraries and present a small benchmark showing their practical performance.

Hash table libraries

In C++, the most widely used hash table implementation is hash_map/set in SGI STL, which is part of the GCC compiler. Note that hash_map/set is SGI’s extention to STL, but is not part of STL. TR1 (technical report 1) tries to standardize hash tables. It provides unordered_map/set with similar API to hash_map/set. Most of TR1 routines are available since gcc-4.0. Google sparse hash is another C++ hash table template library with similar API to hash_map/set. It provides two implementations, one is efficient in speed and the other is in memory.

In contrast, there are few good C libraries around. I have tried SunriseDD, uthash, glibc hash table, hashit, Christopher Clark’s hashtable, glib hash table and ghthash. SunriseDD sounds a great library that implements a lock-free hash table. However, I am not sure how to install it or use it, although the code itself is well documented. Uthash is a single header file. It is quite complex to use and incompatiable with C++. It also lacks basic APIs such as counting how many elements in the hash table. Glibc hash and hashit seem to only implement static hash tables. Glibc hash even does not have deletion operation. Only glib hash, CC’s hashtable and ghthash implement most of common operations. And they still have their weakness in comparison to C++ implementations (see below).

Design of the benchmark

The benchmark is comprised of two experiments. In the first experiment, a random integer array of 5 million elements is generated with about 1.25 million distinct keys. Each element is then tested whether it is present in the hash. If the element is in the hash, it will be removed; otherwise, it will be inserted. 625,792 distinct keys will be in the hash after this process. To test performance on string input, I convert integers to strings with sprintf().

The second experiment is designed by Craig Silverstein, the author of sparsehash. I am using his source codes. This experiment tests the performance of insertion from zero sized hash, insertion from preallocated hash, replacement, query, query of empty hash, and removal.

Results

The following table gives the results in the first experiment:

Library	Mac-intCPU (sec)	Mac-strCPU (sec)	Mac PeakMem (MB)	Linux-intCPU (sec)	Linux-strCPU (sec)	Linux PeakMem (MB)
glib	1.904	2.436	11.192	3.490	4.720	24.968
ghthash	2.593	2.869	29.0/39.0	3.260	3.460	61.232
CC’s hashtable	2.740	3.424	59.756	3.040	4.050	129.020
TR1	1.371	2.571	16.140	1.750	3.300	28.648
STL hash_set	1.631	2.698	14.592	2.070	3.430	25.764
google-sparse	2.957	6.098	4.800	2.560	6.930	5.42/8.54
google-dense	0.700	2.833	24.616	0.550	2.820	24.7/49.3
khash (C++)	1.089	2.372	6.772	1.100	2.900	6.88/13.1
khash (C)	0.987	2.294	6.780	1.140	2.940	6.91/13.1
STL set (RB)	5.898	12.978	19.868	7.840	18.620	29.388
kbtree (C)	3.080	13.413	3.268	4.260	17.620	4.86/9.59
NP’s splaytree	8.455	23.369	8.936	11.180	27.610	19.024

Notes:

• Please be aware that changing the size of input data may change the ranking of speed and memory. The speed of a library may vary up to 10% in two different runs.
• CPU time is measured in seconds. Memory denotes the peak memory, measured in MB.
• For string hash, only the pointer to a string is inserted. Memory in the table does not count the space used by strings.
• If two numbers are given for memory, the first is for integer keys and the second for string keys.
• For all C++ libraries and khash.h, one operation is needed to achieve “insert if absent; delete otherwise”. Glib and ghthash require two operations, which does not favour these two libraries.
• The speed may also be influenced by the efficiency of hash funtions. Khash and Glib use the same hash function. TR1/SGI-STL/google-hash use another hash function. Fortunately, to my experiment, the two string hash functions have quite similar performance and so the benchmark reflects the performance of the overall hash libraries instead of just hash functions.
• For glib and ghthash, what is inserted is the pointer to the integer instead of the integer itself.
• Ghthash supports dynamic hash table. However, the results do not seem correct when this is switched on. I am using fixed-size hash table. This favours ghthash.
• CC’s hashtable will force to free a key, which is not implemented in all the other libraries. This behaviour will add overhead on both speed and memory in my benchmark (but probably not in other applications). The memory is measured for integer keys.
• This simple benchmark does not test the strength and weakness of splay tree.

And here is the result of the second experiment:

Library	grow	pred/grow	replace	fetch	fetchnull	remove	Memory
TR1	194.2	183.9	30.7	15.6	15.2	83.4	224.6
STL hash_map	149.0	110.5	35.6	11.5	14.0	87.2	204.2
STL map	289.9	289.9	141.3	134.3	7.0	288.6	236.8
google-sparse	417.2	237.6	89.5	84.0	12.1	100.4	85.4
google-dense	108.4	39.4	17.8	8.3	2.8	18.0	256.0
khash (C++)	111.2	99.2	26.1	11.5	3.0	17.4	198.0

Notes:

• CPU time is measured in nanosecond for each operation. Memory is measured by TCmalloc. It is the memory difference before and after the allocation of the hash table, instead of the peak memory.
• In this experiment, integers are inserted in order and there are no collisions in the hash table.
• All these libraries provide similar API.

Discussions

• Speed and memory. The larger the hash table, the fewer collisions may occur and the faster the speed. For the same hash library, increasing memory always increases speed. When we compare two libraries, both speed and memory should be considered.
• C vs. C++. All C++ implementations have similar API. It is also very easy to use for any type of keys. Both C libraries, ghthash and glib, can only keep pointers to the keys, which complicates API and increases memory especially for 64-bit systems where a pointer takes 8 bytes. In general, C++ libraries is perferred over C ones. Surprisingly, on 32-bit Mac OS X, glib outperforms TR1 and STL for string input. This might indicate that the glib implementation itself is very efficient, but just the lack of functionality in C affects the performance.
• Generic programming in C. Except my khash.h, all the other C hash libraries use (void*) to achieve generic typing. Using void* is okey for strings, but will cause overhead for integers. This is why all C libraries, except khash.h, is slower than C++ libraries on integer keys, but close to on string keys.
• Open addressing vs. chaining hash. Khash and google hash implement open addressing hash while the remaining implement chaining hash. In open addressing hash, the size of each bucket equals the size of a key plus 0.25 byte. Google sparsehash further compresses unused bucket to 1 bit, achieving high memory efficiency. In chaining hash, the memory overhead of each bucket is at least 4 bytes on 32bit machines, or 8 bytes on 64bit machines. However, chaining hash is less affected when the hash table is nearly full. In practice, both open addressing and chaining hash occupy similar memory under similar speed. Khash takes less peak memory mainly due to its advanced technique in rehashing which reduces memory usage. So far as speed is concerned, chaining hash may have fewer comparison between keys. We can see this from the fact that the speed of chaining hash approaches that of open addressing hash on string keys but much slower on integer keys.
• Memory usage of search trees. B-tree is the winner here. Each element in the B-tree only needs one additional pointer. When there are enough elements, a B-tree is at least halfly full; on average it should be around 75% full. And so on 64-bit systems, for a B-tree with N elements, we need additional N*8/0.75=10N bytes memory. Splay tree will need N*8*2=16N extra space. RB tree is the worst.
• Other issues. a) Google hash becomes unbearably slow when I try to put a lot of strings in the hash table. All the other libraries do not have this problem. b) Google hash performs more comparisons than khash. This is obvious because google-dense is clearly faster on integer keys but comparable to khash on string keys.

Concluding remarks

• C++ hash library is much easier to use than C libraries. This is definitely where C++ is preferred over C.
• TR1 hash implementation is no faster than STL implementation. They may outperform one another under certain input or settings.
• SGI hash_map is faster and takes less memory than STL map. Unless ordering is important, hash_map is a better container than map.
• Google hash is a worthy choice when we understand why it is slow for many string keys.
• My khash library, which is a single-file C++ template header, achieves good balance between speed and memory. All my source codes are available at the Programs page.

Update

1. C interface can be elegant, too, if we implement it cleverly. See this post.
2. I realize that we just need one lookup to achieve “insert if absent; delete otherwise”. This further improves the speed for all C++ libraries.
3. I have analyzed google dense hash table in this post which explains why it is faster than khash on integer keys but close to or slower than on string keys.
4. This thread directed me to gcc hashtable, and cocom hashtable. They are more or less independent of other source codes, but it would still take time to separate the source codes. So, I have not benchmarked them. Just keep a record.
5. Python dictionary is in fact a hash table. The dictnotes.txt in that directory gives some quite interesting discussion about how to implement hash efficiently.
6. hashlib library. A bit hard to use and I cannot get it running correctly. Possibly I have not provided a proper second hash function for rehashing.
7. Added results for STL set (based on red-black tree) and John-Mark Gurney’s B-tree implementation (JG’s btree). Both libraries are considerably slower than hash tables. Of course search trees provide more functionality than hash tables, and every nice thing comes with a price. I have also tried Jason Evans’s and Niels Provos’ red-black tree implementations. On integer keys, JE’s takes 6.110 seconds on Mac-Intel using 18.884 MB memory and NP’s taks 6.611 seconds using the same amount of memory. This performance is close to that of STL set. They appear to be slower mainly due to the additional malloc/free calls I have to made under their APIs. Unlike hash table which have a variety of ways to implement it, red-black tree usually has one way (well, can be more. See also Jason’s blog.). And so I only show the performance of STL set as a representitive.
8. Replaced JG’s B-tree with a modified version. The new version is both faster and more light-weighted.

Comparison of Internal Sorting Algorithms

Sorting algorithm

Given an array of size N, sorting can be done in O(N log(N)) in average. The most frequently used sorting algorithms that can achieve this time complexity are quicksort, heapsort and mergesort. They usually require O(log(N)), O(1) and O(N) working space, respectively (the space complexity of mergesort can be improved at the cost of speed). Most people believe quicksort is the fastest sorting algorithm. However, the fact is quicksort is only fast in terms of the number of swaps. When comparison is expensive, mergesort is faster than quicksort because mergesort uses less comparisons. GNU sort uses mergesort. Replacing it with a quicksort reduces the speed on typical text input. In addition, of the three algorithms, only mergesort is a stable sort. Stability is sometimes useful for a general tool like GNU sort.

The worst-case time complexity of quicksort is O(N^2). In practice, we combine quicksort and heapsort to avoid worst-case performance while retaining the fast average speed. The resulting algorithm is called introsort (introspective sort).

Implementation

The two most widely used implementations are glibc qsort and STL (unstable) introsort. Libc qsort calls a function for comparison. For simple comparison, a function call is expensive, which may greatly hurt the efficiency of qsort. STL sort does not have this problem. It is one of the fastest implementations I am aware of. My own implementation of introsort is similar but not as fast as STL introsort.

GNU sort implements a top-down recursive sort. On integer sorting, it is twice slower than introsort (see below). Iterative top-down mergesort is hard to implement. Iterative bottom-up mergesort is much easier. My implementation is a bottom-up one.

Paul Hsieh has also implemented quicksort, heapsort and mergesort. His implementation should be very efficient from what I can tell. To see whether my implementation is good enough, I copied and pasted his codes in my program, and applied “inline” where necessary.

Comparison

I designed a small benchmark on sorting 50 million random integers. As comparison is cheap in this case, the number of swaps dominate the performance. I compiled and run the program on three machines: MacIntel (Core2-2G/Mac/g++-4.2.1), LinuxIntel (Xeon-1.86G/Linux/g++-4.1.2) and LinuxAMD (Opteron-2G/Linux/g++-3.4.4). On all the three platforms, the program was compiled with “-O2 -fomit-frame-pointer”. The time (in seconds) spent on sorting is showed in the following table:

Algorithm	MacIntel	LinuxIntel	LinuxAMD	Linux_icc
STL sort	7.749	8.260	7.170	8.400
STL stable_sort	9.684	11.990	10.270	10.770
libc qsort	16.579	81.190	30.490	81.120
introsort	7.887	8.880	7.670	9.320
iterative mergesort	10.371	12.480	10.110	10.130
binary heapsort	36.651	45.710	42.460	40.820
combsort11	18.131	19.290	19.370	19.490
isort (func call)	16.760	17.380	13.390	16.740
isort (template func)	7.902	8.800	7.690	9.010
Paul’s heapsort	34.790	43.680	40.740	39.060
Paul’s quicksort	8.410	8.940	7.810	9.450
Paul’s mergesort	11.103	13.390	10.680	13.030

As for the algorithm itself, we can see that introsort is the fastest and heapsort is the slowest. Mergesort is also very fast. Combsort11 is claimed to approach quicksort, but I do not see this in sorting large integer arrays. As for the implementation of quicksort/introsort, STL is the best, with my implementation following very closely. Paul’s implmentation is also very efficient. Libc qsort is clearly slower, which cannot simply attribute to the use of function calls. My implementation with function calls, although slower than without function calls, outperforms libc qsort on both Linux machines. As for the implementation of mergesort, my version has similar performance to STL stable_sort. Note that stable_sort uses buffered recursive mergesort when a temporary array can be allocated. When memory is insufficient, it will use in-place mergesort which is not evaluated here.

Availability and alternative benchmarks

My implementation is available here as a single C++ template header file. The program for benchmark is also available. Programs in plain text can be acquired by chopping .html in the two links.

Paul Hsieh’s benchmark is here, including the original source codes. He also discussed how algorithms perform when the initial array is not completely random (I am one of “naive people” in his standard). Please note that in his benchmark, he was sorting an array of size 60,000 for 10000 times, while in my benchmark I more focus on very large arrays. Notably, heapsort approaches introsort on small arrays, but far slower on large arrays. Presumably this is because the bad cache performance of heapsort. Both quicksort and mergesort are very cache efficient.

In addition to Paul’s benchmark, you can also find alternative ones here and here. They seem to be more interested in the theoretical issues rather than efficient practical implementations.

If you search “benchmark sorting algorithms” in google, the first result is this page, which was implemented in D by Stewart Gordon. This benchmark aims to evaluate the performance on small arrays. It also tests the speed when the array is sorted or reverse sorted. However, the implementation is not optimized enough at least for quicksort. Using insertion sort when the array is nearly sorted is always preferred. You can also find this report from google search, but the implementation of quicksort is too naive to be efficient.

Concluding remarks

Although in the table introsort performs the best, we may want to use mergesort if we want to perform stable sorting, or the comparison is very expensive. Mergesort is also faster than introsort if the array is nearly sorted. STL sort seems to take particular care in this case, which makes it still fast when the array is sorted.

In common cases when comparison is cheap, introsort is the best choice. Of the various implementations, STL is the fastest. If you do not use STL or you just want to use C, you can use/adapt my implmentation which is very close to STL sort in speed. Do not use libc qsort, especially on Linux. It is not well implemented.

Update

1. This website gives severl good implementations of sorting algorithms. I also believe the programmer behind is very capable. Highly recommended.