What I learned from my first C coding challenge
blog.jasonmooberry.com
blog.jasonmooberry.com
Don't hand-roll standard library functions. You'll very likely regret it later.
In particular, as hardware advances, OS vendors often update their implementations with optimisations specific to new hardware platforms. This both allows improvements for all programs that consume those interfaces, and prevention of regressions when hardware changes in some cases.
In addition, you really don't want to be the one that introduces a security bug into your program because it turns out your optimisation work didn't account for a scenario that the standard library function does.
I'm aware that there may be cases where some believe it's appropriate; don't give into temptation. It's a bad idea to duplicate the standard library.
The reason why the standard library functions, qsort in particular, were performing worse in this case is not related to the implementation to the functions themselves. Instead, it is because adding a function call to a foreign function will practically inhibit all compiler optimizations that can happen around the call site. So the "overhead" of the function call itself is a lot more expensive than differences in the function implementation itself. In the case of qsort with function pointer callbacks, the effect is especially devastating. Benchmark qsort vs. C++ std::sort to see how much (a lot).
So when writing performance critical C code, it's a perfectly good option to re-write a standard library function, especially a simple one like this. Make it an inline function in a header file to make sure the compiler can optimize.
If your compiler can do link time optimization to these function calls, then you don't have to re-write them. Before LTO becomes mainstream, sometimes you might have to.
It's very rare that a program's performance is being held back by a standard library function (speaking of libc here). I remain highly skeptical that the algorithm isn't the real issue instead of the implementation of standard library functions.
It's just not worth it.
>It's very rare that a program's performance is being held back by a standard library function (speaking of libc here). I remain highly skeptical that the algorithm isn't the real issue instead of the implementation of standard library functions.
In the last year, we encountered a bug with Solaris Sun Studio 12 on x64 where memcpy wasn't automatically inlined, forcing a full function jump every time it was invoked. That was a major performance hit, and forced us to switch to an internal implementation(that normally is worse on Solaris). IIRC, we didn't have much luck getting a patch out of Oracle for the issue.
So no, this really isn't true. In an ideal world, it would be.
Linux GCC was all over the place, depending on the Red Hat Enterprise version. IIRC, RHEL 4 and above, our internal code worked better, but with 5 and 6, the included memcpy is generally better.
If you're writing code that has serious performance requirements, experimentation is key. There's absolutely no guarantee that the system call will be better than a hand rolled call.
It's also at the discretion of the compiler whether to permit some functions to be inlined. The compiler man page outlines this caveat, and mentions that inlining standard library functions is discouraged as it can cause errno to become unreliable.
Finally, there's also a question as to whether (again) there was a bad algorithm being used as opposed to the fault being with a standard library function. Yes, it's possible there was a performance pathology with the particular use case you have, but there's almost always a better way to resolve an issue like that than hand-rolling a standard library function which inevitably causes unexpected issues.
Code should be written for today, not for tomorrow. Sure, link time optimization may cure the issue but it's not mainstream yet.
Software has to be maintained, it can be changed later if a performance regression or a bug is found.
> It's very rare that a program's performance is being held back by a standard library function (speaking of libc here). I remain highly skeptical that the algorithm isn't the real issue instead of the implementation of standard library functions.
Benchmark it and see. I've done several benchmarks like this and in general proper function calls can be surprisingly costly. Not because the function itself would be expensive but the function call also inhibits compiler optimizations in the call sites.
Any libc function is probably faster than a hand written naive implementation, but that only applies when you have large inputs, like megabytes worth of almost equal strings. A good optimizing compiler can (and in this case, will) make a naive loop implementation perform better.
> It's just not worth it.
The benchmark says it is worth it. Why argue against?
I suppose there's a sort of spectrum of programmer personality types that may help to explain the disagreement. Please forgive me of I am prone to hyperbole in my description.
One type of programmer says "never rewrite a function if it exists in a library". They do this in part because they are not confident in their own abilities (see disclaimer about hyperbole), and generally trust code if it's written by somebody else.
Another type is more of a cowboy. The cowboy wants to write everything from scratch, for the opposite reasons - because they don't trust code not written by them.
Someone who reliably adheres to only one of these extremes at all times is probably not a good person to work with. However, both of these motivations do have some basis in fact and practicality. On the one hand, use of libraries gets the job done quickly and can save you some headaches. On the other hand, there are some pretty bad to horrible libraries out there, many of them quite popular; introducing dependency on the library can add considerable complexity, code size, and weaken your own "whole-program" understanding of what's going on. I'd say that being distrustful of dubious library dependencies is a good thing.
In practice, even your libc is not necessarily going to be as well maintained as you suggest. The people who maintain such libraries might not have the motivation to do the sort of periodic performance tweaks and updating for the current era that you ascribe to them. They might have a working implementation and decide to stick with it as long as possible. (In my experience this is more common than your rosy picture.) That's fine for them but it doesn't mean the library will work for you, or help you meet your performance goals. One problem with your side of the spectrum is that the people who write the libraries aren't always perfect or even good authorities. You have to know when to let go of your trust in them.
And especially, if I really need something to be faster and it's something that I can spend a few hours on, benchmark, and either decide to take or maybe just revert and go back to the library... Well then yes, I'm going to take a crack at it. One can always revert it later.
For example, Solaris, Linux, and Windows all feature versions of memcpy that are specifically optimised for different hardware platforms. Intel in particular supplies these optimisation for a number of operating systems directly to the OS vendors.
My advice only applies to the standard library (really, just libc). It's not intended to be nor applicable to anything else for the purpose of this discussion.
For example, in Solaris alone (older version of OpenSolaris actually, but it gets the point across), there are seven easily found versions of memcmp alone:
http://src.opensolaris.org/source/search?q=&project=onnv&defs=memcmp&refs=&path=libc&hist=
Also, as for your concerns that OS vendors don't update the standard library functions as often as you think -- you're wrong. I know for certain that Linux, Windows, and Solaris all receive continual updates for new hardware platforms for their standard library. There's a reason you hear these vendors constantly talking about their SPEC benchmark numbers or the like.
So again, as far as standard libraries are concerned -- don't do it; it's not worth it.
Well I was actually speaking from experience here. I might be more willing to believe you for something like memcpy(), but as an example (and the one I was thinking of), the Windows CRT is generally in pretty poor shape. I've also seen some crufty things in libc trees from some of the *BSDs.
None of those optimizations matter in this case because the average query string parameter name is only a few characters in length and an inlined naive loop with compiler optimizations will be faster.
I remember reading about this some time ago when I was doing some tinkering. I read that for example, John Carmack decided to implement his own memcpy tailored for the games they programmed. Additionally, I read about different alternative implementations o memcpy which were better than the standard for specific domains. I even experimented using Microsoft detours to replace the vanilla memcpy with a faster version.
For a quick test I used the conditions (i=0; i < NUMBER; i++) and (i=NUMBER;i != 0; i--). Without optimizations turned on, gcc translates both of them to cmpl (compare long) operations followed by a jne (jump not equal). So on an assembly level, they're absolutely identical except that in the one case you're testing against zero whilst in the other you're testing against the number. Fine, so we'll have to dig deeper.
And this is where it gets complicated. This optimization depends entirely on the inner workings of the ALU. Theoretically one can test against zero with just one subtraction, because 0-n == n-0 is always true, whereas a-b == b-a iff a == b, otherwise the two sides will differ in sign. On a hardware level such operations might be parallelized inside of the ALU though, so a comparison of two numbers might actually take exactly as many clock cycles as the comparison against zero.
It's however an interesting excursion into how such basic things work. And concerning my test: They're both about equally fast on my machine. I've done multiple runs with no clear winner.
The most straightforward implementation of first loop would be "add i,1" followed by "cmp i,NUMBER" followed by "jb top" (or "jl top" if i is signed). It's an extra instruction which may be even slower, depending on specific CPU and surrounding code, if NUMBER is a literal or memory access (as opposed to register value).
My guess is that your compiler will produce code that takes advantage of the savings if you turn on optimizations, but you might have to actually do something in the body of the loop to keep the compiler from optimizing the loop completely out (or tweak flags to enable/disable specific optimization techniques). Adding a loop body will make the timing difference less noticeable, as the single-instruction savings of the zero-test version becomes a smaller percentage of the total time per iteration.
Disclaimer: This is how I'd write assembly by hand. A compiler could conceivably do something quite different, depending on the specific application code, compiler, version and flags. I also haven't yet taught myself 64-bit x86 assembly code, although I understand it's rather similar to 32-bit x86 with more registers available.
That said, it's very likely that the compiler will make sense of such an optimization and produce the quicker assembly code like you just wrote it.
What I wanted to say with my post was really that things like these are heavily depended on architecture and that comparisons could be optimized in hardware.
Use a non-constant value for the loop and put a dummy load inside to stop compiler from doing loop unrolling and/or dead code elimination.
I often use time(), rand() or even argc to get dummy values when looking at assembly from compiler optimizations.
for (..; ..; ..) asm("");
> 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
.L13:
subl $1, %eax
jne .L13
.L7:
subl $1, %eax
cmpl $-1, %eax
jne .L7
(Also, one can test for 0 extremely quickly: just check that all the bits are 0.)
You have to add these suffixes "l" or "w" to all your instructions to tell the compiler how big they are, but of course if you're using EAX you're talking about a 32-bit register; if you wanted to talk about a 16-bit register, you'd say AX, or AL (or even AH) for 8-bit. An assembler that isn't smart enough to figure out something that simple and obvious is a sorry tool indeed.
And then there's the fact that operands are backwards. "subl $1,eax" translates to "eax -= 1" in C-like syntax. Why switch the order of operands? It's completely unnecessary and confusing. It's like someone inventing a programming language where integer literals were negative if specified with no sign, and only positive if you put a + on them -- technically possible, but the sort of thing that serves no useful purpose and defies all prior conventions, common sense, and sanity.
And putting dollar signs on constants and percent signs on registers? I can't even imagine any possible explanation for that, other than a lazy parser author who didn't care about making extra work for their users. It's the type of corner-cutting that you'd expect to find in some prototype thrown together by a single person in a single evening.
Please, for the sake of your own sanity and those around you, use Intel syntax instead!
Both architectures, however, include special instructions to handle numeric loops (for instance for (i = S ; i != E ; i += step) that count downwards, but they have a slightly different ending condition (Intel ends on 0, Motorola ends on -1) and is really specialized on the Intel (it requires the use of the CX (ECX, RCX) register; on the Motorola you can use any of the data registers) so it makes it kind of hard to use in portable C code (your best bet---don't use the for index in the body of the loop and hope the compiler can transform it to use the specialized instructions).
If speed is really critical, you need to check the output from the compiler, and make sure you always measure twice (and keep the original code around as a reference when the hardware changes).
For example the repo references a 5Murls.txt file, but it isn't part of the repo and the blog says it needs to "output in a standardized format:", but doesn't specify what "standardized" means nor does the current code actually output anything (the printf is disabled). Does it specifically need to go to stdout or just that it exists somewhere in memory? Does it require a char* or will this char* be instantly hashed and tossed away? Does the challenge forbid the use of threads/cpus/workers? In the blog it says: "In this particular context the plugin architecture we were writing against allowed for returning the original string or a new malloc’d string" Are you allowed to muck with the original string? In the code on github it has a function that takes a const char* forcing a malloc, but it could easily just re-write the string in place if allowed.
edit: As for sorting the params, (based upon your comments about the common usage) pretty sure there is a way to do this without any string comparisons at all. Post a sanitized 5Murls.txt file and give it a go to make a patch.
- Average number of parameters
- The % that are already sorted
- The % that don't have keys that start with same letter
- Do we have to validate the URL strings in any way?
- What do we need to do with duplicate names?
- Are cases with small parameter names and/or small numbers of parameters common?
- How common are parameters with lengthy common prefixes?
- Is there a bound on the length of the longest common prefix of two different parameter names?
Tuning or special-casing with common cases in mind can often produce big wins.
Here my blog post about it: http://cyberroadie.wordpress.com/2012/01/05/varnish-reorderi...
It parses the url and every token gets added to a binary tree which than gets traversed in order to get the parameters alphabetically
It's been used in production in several companies I worked for, so tried and tested :-)
Olivier
Alternatively, keeping them in separate arrays removes the alignment overhead, and each pair of values will consume 10 bytes. That's a substantial savings when you're trying to fit into something like a 32KB L1 data cache.
Another technique that can help you fit as much useful data as possible into L1/L2 cache is to store offsets rather than raw pointers. Using a 2-byte unsigned short for an offset rather than an 8-byte pointer would save another 6 bytes of cache per entry, assuming you're happy limiting your URL size to 64 kilobytes. The extra address arithmetic should be essentially free on a modern pipeline.
Trust me, no you don't. Pointer arithmetic is one of the easiest things to screw up in C, and the raw form can be very dangerous to work with.
For sure, treating a pointer as an integer and incrementing by a fixed number of bytes each time is fine, but more often than not languages have this implemented, just as a JIT or compiler optimization.
And here, you've inadvertently pointed out one of the major pitfalls (and amazing virtues) of pointer arithmetic: in C, pointers increment by the size of their data type. You don't add some number of bytes to the pointer, you add the number of elements by which to increment.
In other words, incrementing a uint8_t* will add one byte to the pointer address, but a uint32_t* will add four bytes, and a pointer to a 64-byte struct will add 64 bytes.
Here's an example. This code:
#include <stdio.h>
#include <inttypes.h>
struct foo {
char bar[67];
};
int main()
{
struct foo monkey[60];
struct foo *zoochild;
printf("sizeof foo: %zu\n", sizeof(struct foo));
printf("sizeof monkey: %zu\n", sizeof(monkey));
zoochild = monkey; // child points at first monkey
zoochild++; // child points at second monkey
printf("(monkey + 1) - monkey: %zd\n", zoochild - monkey);
printf("(bytes) (monkey + 1) - monkey: %zd\n", (uint8_t *)zoochild - (uint8_t *)monkey);
return 0;
}
$ gcc -O4 -Wall -Wextra -pedantic -std=c99 ptr.c -o ptr
$ ./ptr
sizeof foo: 67
sizeof monkey: 4020
(monkey + 1) - monkey: 1
(bytes) (monkey + 1) - monkey: 67One clever trick is assigning a prime to each card value. By multiplying the values together you get a unique number representing each hand without needing to sort.
There's a great description of an algorithm at http://www.suffecool.net/poker/evaluator.html.
Depending on exactly what type of hashing they are doing, the normalization could be a significant fraction of the lookup time.
If you are going to get all micro-optimized, you should probably combine the normalization and hash steps, as there is likely some string parsing / building that could be eliminated.
Also: it's a pretty fun exercise.
Depends also if there's pre validation (even with C you're never sure, so for example, reading that he used strcpy makes my head go "security hole", but this is a proof-of-concept so it's ok)
The best thing to keep in mind is that "There is no such thing as the fastest code"
Edit: strcmp to strcpy (or any str C function)
Moral of the story, if you're going to use C strings, use the strn* variants.
If passed an unterminated string, the function will fail at least. How much you could exploit from that, I guess I exaggerated.
This whole subthread of picking on the guy's implementation because of "strcmp" is pretty silly. There are times where strcpy() is safe to use, but most of the time it's a red flag. There are conceivably times when strcmp() is unsafe to use, but to a professional reviewer, it is very rarely a red flag.
I should have just come right out and said that, rather than begging for the rationale for picking on strcmp().
Timing attacks aren't a flaw in memcmp or strcmp. Touching every byte of a string is stupid behavior in the overwhelming majority of cases.
Point your string function to a non-null terminated byte buffer for example. At the very least you can crash the app
What's recommended (one of the recommendations) is to use the 'n' functions like strncmp that takes a maximum size.
Using strncmp in this situation makes very little sense and is probably more dangerous. The lengths given to strncmp() are inevitably going to be derived from something else that requires a NUL terminator. Meanwhile, strncmp() leaves you open to logic flaws where you compare too few bytes.
Perhaps also consider using a radix sort?
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
(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.
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 );
}
static inline int str_compare( const char *a, const char *b )
{
while( ( *a == *b ) && *a )
{
a++; b++;
}
return( *a - *b );
}
Yes the string comparator is comparing items like:
"a=3&a=4" and "a=4"
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.
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?
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.
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…)