Another Look at my old Benchmark

This is a follow-up of my previous post. Here I change the table to several charts. Hope it seems more friendly to readers. You can find the links to these libraries in that table. Their source codes, including my testing code, are available here. You may also want to see my previous posts in the [...]

Read Full Post »

Futher Discussion on Search Trees

Over the weekend, I have done a more comprehensive benchmark of various libraries on search trees. Two AVL, seven red-black tree, one Splay tree, two treap implementations are involved, together with seven hash table libraries. As I need to present a big table, I have to write it in a free-style HTML page. You can [...]

Read Full Post »

B-tree vs. Binary Search Tree

When talking about in-memory search tree, we usually think of various binary search trees: red-black tree, AVL tree, treap, splay tree and so on. We do not often think of B-tree, as B-tree is commonly introduced as an on-disk data structure rather than in-memory one. Is B-tree also a good data structure for in-memory ordered [...]

Read Full Post »

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 [...]

Read Full Post »

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 [...]

Read Full Post »

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 [...]

Read Full Post »

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 [...]

Read Full Post »

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);
kh_value(h, k) = 10;
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, [...]

Read Full Post »

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 [...]

Read Full Post »

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 [...]

Read Full Post »