Coffee Space

Profiling

I haven’t tried profiling with C before, but it’s genuinely pretty good. During compiling with gcc, you can add a -pg flag to allow for profiling. Next you need to run your program, which will generate a gmon.out file. After this you can the convert it into something human readable with:

0001 gprof -b <BINARY> gmon.out > analysis.out

For uDatabase, analysis.out looks like so (I have cut it to the first section of the output):

0002 Flat profile:
0003 
0004 Each sample counts as 0.01 seconds.
0005   %   cumulative   self              self     total           
0006  time   seconds   seconds    calls  ms/call  ms/call  name    
0007  71.43      0.05     0.05   245388     0.00     0.00  udatabase_search
0008  28.57      0.07     0.02        5     4.00     4.00  udatabase_service
0009   0.00      0.07     0.00   245388     0.00     0.00  udatabase_shash
0010   0.00      0.07     0.00   163592     0.00     0.00  udatabase_remove
0011   0.00      0.07     0.00    81796     0.00     0.00  udatabase_get
0012   0.00      0.07     0.00    81796     0.00     0.00  udatabase_put
0013   0.00      0.07     0.00       54     0.00     0.00  currentTimeMillis
0014   0.00      0.07     0.00        1     0.00     0.00  udatabase_close
0015   0.00      0.07     0.00        1     0.00     0.00  udatabase_signal

Here you can see how much time is spent in each function, how many calls to each function and other cool stuff. This is a great way to benchmark your improvements when speeding up functions!

Hashing

During profiling, I realised that udatabase_service() got called often - in fact, way too often. The function is responsible for expanding the lookup table, but we were doing it insanely often. It’s a very heavy function as it also cleans up the database on disk at the same time.

I initially used __unint128_t, but this is both not compiler portable or even system portable. I ended up switching to a char* as all we were essentially doing was byte matching.

After some time, it occurred to me that we were getting tonnes of hash collisions, causing udatabase_service() to get called to expand the lookup table, and then pay massive overheads from this function.

My initial hash function was as follows:

0016 /**
0017  * udatabase_shash() Convert a string to a hash.
0018  * Source: http://www.cse.yorku.ca/~oz/hash.html
0019  * @param s The NULL terminated string to be hashed.
0020  * @return The hashed number.
0021  **/
0022 __uint128_t udatabase_shash(char* s){
0023   __uint128_t h = 0;
0024   int c;
0025   while(c = *s++) h = c + (h << 6) + (h << 16) - h;
0026   return h;
0027 }

This worked well, except I no longer wanted to rely on the __uint128_t type.

Next I implemented string-based hashing and cooked up the following:

0028 /**
0029  * udatabase_shash() Convert a string to a hash.
0030  * @param s The NULL terminated string to be hashed.
0031  * @param d The target pre-allocated string of hash length for the result.
0032  * @param n The length of the hash to be created.
0033  * @return A pointer to the hashed string stored in d.
0034  **/
0035 char* udatabase_shash(char* s, char* d, int n){
0036   int x = -1;
0037   while(s[++x]) d[x % n] = s[x] ^ (x < n ? '\0' : d[x % n] << 2);
0038   while(x < n) d[x++] = '\0';
0039   return d;
0040 }

It worked fine during small test cases, but absolutely sucked in the larger tests… I got a little better performance with:

0041   while(s[++x]) d[x % n] = s[x] ^ (s[x + 1] << 3);

But it still sucked for large scale tests…

Then it hit me! Out of the result of this function (which we’ll call hash), we pull out the first two bytes and use it as a short hash like so: *(uint16_t*)hash. We then use this short form for our initial testing for matches and our lookup table acceleration.

The problem is, with the previous version of the hashing function, the first two bytes are really low entropy! What of there was a way to force high entropy onto the first two bytes… There is!

0042 /**
0043  * udatabase_shash() Convert a string to a hash.
0044  * @param s The NULL terminated string to be hashed.
0045  * @param d The target pre-allocated string of hash length for the result.
0046  * @param n The length of the hash to be created.
0047  * @return A pointer to the hashed string stored in d.
0048  **/
0049 char* udatabase_shash(char* s, char* d, int n){
0050   int x = -1;
0051   while(s[++x]){
0052     d[x % n] = s[x];
0053     d[x % sizeof(uint16_t)] ^= s[x] << 3;
0054   }
0055   while(x < n) d[x++] = '\0';
0056   return d;
0057 }

This works extremely well! I’m not away of any other C (or other language) string->string hash function, and certainly of nothing that prioritizes entropy in the first bits in order for a simple shortening cast to take advantage of.

memcmp()

Holy moly I wish I had known about this function sooner! My initial string comparison looked like this:

0058 /**
0059  * udatabase_cmp() Compare two binary strings of equal length.
0060  * @param a The first string to be compared.
0061  * @param b The second string to be compared.
0062  * @param n The length of the strings to be compared.
0063  * @return If strings are equal return 0, otherwise not equal.
0064  **/
0065 int udatabase_cmp(char* a, char* b, int n){
0066   while(n-->0) if(*a++ != *b++) break;
0067   return n + 1;
0068 }

It’s ‘okay’, but there’s a lot of checking going on in there. I did some checking online and in theory it is possible to do zero-branching string compare for fixed-length strings… But someone (cannot remember who) suggested just to forget that and checkout memcmp() instead! It’s super speedy!

Another plus is it has example the same definition and meant that I could delete my comparison function entirely!

Signal Handling

Okay, this was a stroke of genius. There are a few great points with this code:

1. All signals of interest exist between SIGHUP and SIGKILL, and all implementations I could find number these roughly between 1 to 9, in that order. All the signal in between were also pretty interesting, so with a single line, we can register our interest in them all!
2. We access our file pointer FILE* to close the database. This is stored in a database struct uDB. Our close() function should be able to be called by anybody, including the signal handler. So the question is, how do we give the function udatabase_signal() a reference to db when parameters are not supported for the signal handler? Check this out…

0069   for(int x = SIGHUP; x < SIGKILL; x++) signal(x, (void (*)(int))udatabase_signal);
0070   udatabase_signal(0, db);

After setting up the signals of interest, we hand over a fake signal with access to our db struct.

0071 /**
0072  * udatabase_signal() Handle a given signal and close gracefully.
0073  * @param db The database description.
0074  * @param signum The signal number indicating
0075  * @param ptr The raw pointer to the database structure.
0076  **/
0077 void udatabase_signal(int signum, void* ptr){
0078   static struct uDB* db = NULL;
0079   if((db = db != NULL ? db : ptr) != NULL && signum >= SIGHUP && signum <= SIGKILL)
0080     udatabase_close(db); // NOTE: Remains locked.
0081 }

We then read this into a static variable if we detect we have not already stored it! I still need to see exactly how this will work with multiple databases opened though… I suspect it won’t work.