What I learned from my first C coding challenge

I've never come across the Duff's Device previously and after staring at it for a few minutes it made horrifying sense. I can't tell whether it's a piece of true evil or true genius.

(Just as a note, the count-down condition is normally (i = NUMBER; i--; ), the condition you have gives different results: i is 1 larger than one expects.)

> Without optimizations turned on, gcc translates both of them to cmpl operations followed by a jne

Why would you expect anything different? It isn't doing any optimisations, so it is doing the naive method of transliterating the C to ASM.

The actual test is when one turns optimisations on. The code generated by GCC -O3 for your two conditions is (respectively):

  .L21:
        addl    $1, %eax
        cmpl    %edx, %eax
        jne     .L21

and

  .L13:
        subl    $1, %eax
        jne     .L13

And for the condition I gave above

  .L7:
        subl    $1, %eax
        cmpl    $-1, %eax
        jne     .L7

You can make your own conclusions from that, but clearly your count-down method uses fewer instructions.

(Also, one can test for 0 extremely quickly: just check that all the bits are 0.)

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.

More like evil genius… Variations of this trick are a common optimization in embedded systems for years. (Stuff like this is why “premature optimization” is considered such a bad thing.)

On that note, I find it interesting that the article writer wanted to see more languages support pointer arithmetic. Language mechanics like that have developed a reputation of being “unsafe” due to they enabling common programming errors like buffer overflows and the like. Depending on the level of abstraction between the language and underlying iron, it might not even be possible to do stuff like this anymore. (Some modern languages/VMs/compilers use the more abstract concept of “references” over “pointers.” Even Apple’s flavor of Objective C, which AFAICT is still using pointers as an implementation detail, prefers to couch documentation and API conventions in the more abstract convention to deter some of the direct memory access abuses that were discovered during the Classic-to-Carbon Mac migration way back when…)

Awesome code review. Thank you.