In last two post I gathered the probe statistics in various scenarios. How does it impact the actual performance? I wrote some benchmarks this weekend and got useful results.
In the last post I demonstrated probe distributions under six insertion schemes: linear probing, quadratic probing, double hashing, and their robin hood hashing variants. Knowing the probe distribution of insertion is useful for static hash tables, but does not model the hash table with frequent updates. Therefore I made some experiments for such scenario, and found the results are very interesting.
In the last 4 months I’ve been working on how to implement a good hash table for OPIC (Object Persistence in C). During the development, I made a lot of experiments. Not only for getting better performance, but also knowing deeper on what’s happening inside the hash table. Many of these findings are very surprising and inspiring. Since my project is getting mature, I’d get a pause and start writing a hash table deep dive series. There was a lot of fun while discovering these properties. Hope you enjoy it as I do.
In my last post, I briefly introduced OPIC (Object Persistance in C), which is a general serialization framework that can serialize any object without knowing its internal layout. In this post, I’ll give a deeper dive on how it works.
Hash table is probably the most commonly used data structure in software industry. Most implementations focus on its speed instead of memory usage, yet small memory footprint has significant impact on large in-memory tables and database hash indexes.
In this post, I”ll provide a step by step guide for writing a modern hash table that optimize for both speed and memory efficiency. I’ll also give some mathematical bounds on how well the hash table could achieve, and shows how close we are to the optimal.
In this post I’ll show an example of how to write a cross-plaform OpenGL
program. We’ll explore more autoconf features, including
config.h, third party
libraries, and many more.
This is the second post of the autoconf tutorial series. In this post I’ll cover some fundamental units in autoconf and automake, and an example cross platform X11 program that uses the concepts in this post. After reading this post, you should be able to write your own build script for small scope projects.
It’s been more than a year since my last update to my blog. I learnt a lot new stuffs in last year, but was too busy on work to write down what I’ve learnt. Luckily I got some breaks recently, and I’ll pick up some of the posts that I’ve wanted to write about. First I’ll start with a autoconf tutorial series. This is one of the difficult material to learn, but I’ll try to re-bottle it to make it more accessible to everyone.
Many assembly tutorials and books doesn’t cover how to write a simple assembly program on the Mac OS X. Here are some baby steps that can help people who are also interested in assembly to get started easier.
It’s been a while since I wrote my last article. I recently read an old book Expert C Programming and found there are many C langauge details that I never think about. Review and rethink what C integer promotion rules meant to C is one of the interesting topic that I want to share with you.