5 ms·
Good work, one obvious speed up is, if possible, removing the use of dynamic memory. Simply supply a static output buffer to url_sort so that it doesn't have to
by alexkus 14y ago
Good work, one obvious speed up is, if possible, removing the use of dynamic memory. Simply supply a static output buffer to url_sort so that it doesn't have to allocate/free memory for the resulting URL.
That took my execution for 5M lines of (not really representative but it's all I could be bothered to sort out at 11pm):
/test.php?b=b&c=bb&a=3&a=4
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.
- jasonmoo 14y agoAwesome code review. Thank you.
- alexkus 14y ago[EDIT - Fix unintentional italics] 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.
- gsg 14y agoHow is testing for a terminator the right approach? The comparator is only supposed to look at a single parameter, and the only null byte in the url string is at the end...
- alexkus 14y agoBoth implementations have exactly the same outcome for all inputs, it's just one has less code (well, code that is less complex) inside the loop and therefore is more pipeline friendly and/or just executes faster. 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.