Speeding up string compare and sorting (compared to vanilla strcmp)

Motivation

Strcmp and its variants are crucial part of nearly every software project ever made. Unless the project is written in C, the useage of strcmp is implicit i.e. it is used by the standard library or the platform underneath (for example Python, it is used by the interpreter). Usually the string comparing functions are not questioned and are taken as given when designing systems. When optimizing the system performace it is easy to neglect strcmp & co. and because of this, a faster implementation of strcmp yields unexpected gains even on a somewhat highly optimized systems.

A large amount of effort is put into devising more and more efficient string sorting algorithms etc. These optimizations reduce the computational complexity of the sorting and therefore make it faster especially when the amount of sorted strings is very large. Making the underlying string comparing faster doesn't give such far-reaching results, but it increases the speed of current highly optimized algorithms without touching the algorithm itself.

This is why even a modest increase in strcmp speed is useful, because it speeds up the system in various places and situations and because it can be put to use without greatly modifying the current codebase.

The Code

The proposed simple algorithm is:

There is nothing new in this algorithm, it is only engineered to be faster than the out-of-the-box strncmp from GNU libc library.

Comparing strings

A set of test runs against the strncmp was done using a C program that generated a set of random strings and the compare functions were timed when an all-to-all compare loop was executed. Results reported here are averages over 512 runs. All programs were complied using gcc version 4.4.6 and with -O3 flag.

Results from 32bit EC2 instance: 

Test 1: Comparing 20000 strings (20 chars each) against each other
fast_compare: 1.19 s
strncmp:      3.58 s

fastcmp vs strncmp: 3.0x


Test 2: Comparing 20000 strings (2000 chars each) against each other
fast_compare: 18.15 s
strncmp:      187.74 s

fastcmp vs strncmp: 10.3x

Result from 64bit Intel Pentium 4 @ 3.4Ghz

Test 1: Comparing 20000 strings (20 chars each) against each other
fast_compare: 2.44 s
strncmp:      7.47 s

fastcmp vs strncmp: 3.1x


Test 2: Comparing 20000 strings (2000 chars each) against each other
fast_compare: 29.20 s
strncmp:      45.31 s

fastcmp vs strncmp: 1.6x



Sorting strings

A common application where string comparing is used is sorting strings (for example in alphabetical order, database indexing). A set of test runs were conducted with a C program that sortes randomly generated strings (same set for each compare function) and libc's qsort was used as the sorting function. Same compiler options and averages were used as in the previous test setup.

Results from 32bit EC2 instance: 

Test 1: Sorting 16384 strings (8192 chars each)
fast_compare: 5.956 ms
strncmp:      9.977 ms

fastcmp vs strncmp: 1.68x

Test 2: Sorting 32768 strings (1024 chars each)
fast_compare: 12.715 ms
strncmp:      21.470 ms

fastcmp vs strncmp: 1.69x

Result from 64bit Intel Pentium 4 @ 3.4Ghz

Test 1: Sorting 32768 strings (20 chars each)
fast_compare: 19.193 ms
strncmp:      25.704 ms

fastcmp vs strncmp: 1.34x



Results from sorting are not as dramatic as in raw string compare mainly because the actual amount of string compares is quite low as (almost) all sorting algorithms try to do as little compares as possible (lower algorithmic complexity).

Markus Grönholm, Alshain ltd., 2014