I just know how much work there is to do, at short notice, when a customer comes along offering $$$ for a version of your product on an architecture that you hadn't originally considered. It was definitely worth the hassle of porting and cleaning up to code to provide them with it, but it would have been so much easier if we'd kept it clean from the start.
Another ~5% off by getting rid of the branch inside the str_compare() loop. Here was your original:-
static inline int str_compare( const char *a, const char *b )
{
for(;*a == *b; ++a, ++b)
{
if (*a == '\0' || *b == '\0')
{
return( 0 );
}
}
return( *a - *b );
}
Inside the loop, if *a is a NUL then so will *b, so you don't need to test for both to be NUL. Also, if *a is NUL and *b is NUL then ( *a - *b ) will be 0. You can just iterate through the string when *a are equal and non-NUL, and then return the difference between the two characters so:-
static inline int str_compare( const char *a, const char *b )
{
for(; (*a == *b) && *a; ++a, ++b);
return( *a - *b );
}
[ C-Holy-War ] Personal style preferences; I prefer while loops, so much so that it has been years since I've purposely written a for loop in C and writing C is what I do for my job. For loops likes that end up looking like line noise, I'd find the following much easier on the eye and, more importantly, more immediately obvious to anyone else reading the code as to what it does:- static inline int str_compare( const char *a, const char *b )
{
while( ( *a == *b ) && *a )
{
a++; b++;
}
return( *a - *b );
}
But, as I said, that's my own style preference. There's nothing wrong about using for loops, perfect acceptable implementation.And maybe you can shed some light on this. I am a fan of the while loop too, but I found the for loop to be more performant. Is it possible that there are optimizations for variables touched in the for(;;) definition that do not exist for the while() definition?
Yes the string comparator is comparing items like:
"a=3&a=4" and "a=4"
but it doesn't really matter since it'll never put such items in the wrong order. It's a quirk of passing the original url as 'const char *' so that it can't be modified (to temporarily replace the & symbols with NULs) and the OP was trying to avoid the cost of copying the input string except when creating the output string.You should only look at the next byte in either string if both of the current bytes are non-NUL. If both are equal, and one is non-NUL then the other is non-NUL and so you can continue.
If they're non-equal then you stop and return the difference between the two which will be +ve or -ve.
If they're equal and one is NUL then you stop and return the difference which will be 0 since they are equal.
Consider the (admittedly perverse) input "test.php?a=1&a=1&a=1&a=1&a=1". At each comparison, the comparator you suggest will look at the entire remaining part of the string.
Maybe duplicate elements are considered invalid input and aren't a concern, I'm not sure. But fixing it is not hard and doesn't require fiddling about with copying strings or adding terminating nulls: just find and remember the parameter length once, and use a length-based comparator.
The other two improvements I'd be looking to do are:
1) try to rework the insertion sort to make it use a binary search (if over a certain threshold that is yet to be determined by experimentation). Should be faster than looping through each element each time.
2) Not automatically extend the tail each time (where insertion somewhere between head and tail is required). The element being added may be one from the head so it's best to work out where it goes first and then pick the extension direction that requires the fewest number of elements to be shuffled up. Also the shuffling can be done in bulk using memmove() (can't use memcpy since the areas of memory will overlap when shuffling up by more than one position); this should also be faster than doing them one at a time.
Anyway, i'm off on holiday so I've got about another 15 minutes to look at this so I'm not going to get far. If I remember I'll try and check up on the status of it in github when I get back.
That took my execution for 5M lines of (not really representative but it's all I could be bothered to sort out at 11pm):
down from 5.05s to 4.49s (so down 10%) on an old 1.5GHz Athlon Linux box that whirrs away in the corner of my flat. (Down to 2.81s when compiled with -O4).(I assume you're compiling with -O4 as that's the only way I could make it worthwhile using your str_compare() function over libc's strcmp().
The only other thing I can think of that may speed it up more is a kind of binary search on the insertion as that is currently just a flat loop that does a comparison against each param; and therefore O(n).
In a pessimal case where you've already got 30 params and your 31st is going just before the tail (but not as the tail so you can't short cut straight to adding it as the tail) then it'll do a whole bunch of string comparisons on entries 1, 2, 3, ..., 30 before finding the right place. It'd be better to do them on, say, 1, 15, 23, 27, 29, 30. (This will only be beneficial when you have more than a certain number of params). An O(log n) algorithm will hopefully outweigh the slight expense of having to compute the midpoints.)
But, given you've got to 2M urls/sec, do you really need to eek out any more performance? That's an awful lot of traffic if you think each HTTP request will be about 500 bytes (including TCP headers, HTTP headers, etc). 2M * 500 bytes * 8bits = ~8Gbps, and that's just the incoming traffic from established connections.
For the binary search suggestion I get to point out the minor nitpicks:-
* Not all C compilers accept C++ style comments (gcc is way too lenient by default)
* Not all C compilers accept local variables to be defined mid-function
* unsigned long is not the same as size_t (fun fun fun when porting to different word sizes)
* If you ever have to port this code to work on a different CPU you may find yourself spending time adding lots of casts to (ptrdiff_t) to avoid it breaking due to unexpected sign extensions/etc.
These may seem OTT for a project like this, but it's not trivial when you've continued those practicises for years (and new devs have copied the house style) and have a bunch of projects totalling 20MLOC+ that you then need to port to a new compiler on a new architecture (with a different word size) and the code is riddled with assumptions about the old compilers and the architectures. Some things can be automated but spending days moving variable definitions to the top of functions and fixing types of variables that hold return values of strlen() in an seemingly endless list of thousands of files gets boring after a very short period. Me? Bitter?
"gcc -Wall -ansi -pedantic" and lint should be your friends.