A great read. I am curious about your double-wide insertion sort algorithm.
Thanks. I haven't seen it anywhere else, but can't really be sure I came up with it. Just seemed like a good optimization.
What I learned from my first C coding challenge
51–60 of 85 posts
Re: What I learned from my first C coding challenge
#52Good read. Reminds me of the oldie but goodie http://ridiculousfish.com/blog/posts/old-age-and-treachery.h...
Re: What I learned from my first C coding challenge
#53(I realise the poster came up with a different solution ultimately, but this bears repeating.) 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…
Implementing something using as little foreign code as reasonably possible can actually be a good way to make it correct an secure.
You write it once and prove it's correct. After that, you're done, no matter how libraries around you change. If a library function gets a bug or gets slower, your code is unaffected. And your code likely won't get significantly slower as you update the compiler (it's more likely it will get faster).
Re: What I learned from my first C coding challenge
#54(I realise the poster came up with a different solution ultimately, but this bears repeating.) 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…
Also note that only the most basic library functions are likely to be optimized specifically for your platform (e.g. assembly). Mostly basic memory stuff like memcpy, strcpy, memcmp, strcmp, strchr,... Anything more complex can be usually be made very fast with just pure C code, comparable to implementations that come with your compiler.
Re: What I learned from my first C coding challenge
#55It's interesting that he points out that testing for zero is cheaper than comparing two numbers. Interesting because this might not always be the case. For a quick test I used the conditions (i=0; i 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…
It depends on the architecture. I know that a register load on the Motorola 68k CPU will set the flags (Z for zero, N for negative) while a register load on the Intel x86 line doesn't change the flags and thus, a comparison needs to be made.
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).
Re: What I learned from my first C coding challenge
#56Earlier quoted context omitted.
But that's sort of my point; today's optimisation can be tomorrow's performance regression, security bug, or be outdone by an update by the OS vendor. 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.
> But that's sort of my point; today's optimisation can be tomorrow's performance regression, security bug, or be outdone by an update by the OS vendor. >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…
How about, "use the standard library function unless proven guilty"? Sure, if compiling with Solaris Sun Studio 12 on x86 is a loss, but what about SPARC? Or Linux GCC?
Re: What I learned from my first C coding challenge
#57Good 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 Linu…
// comments and mid-function variables are C99 standard. The platforms that don't support them are probably not worth supporting yourself, and are not likely to be seen running varnish. This is the same mindset that held mozilla back for ages and ages because the hpux compiler from 1987 didn't support some c++ feature, so therefore nobody was allowed to use it even in 1997.
Re: What I learned from my first C coding challenge
#58(I realise the poster came up with a different solution ultimately, but this bears repeating.) 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…
This is good advice for a novice, but I have to say from my experience I pretty vehemently disagree.
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.
Re: What I learned from my first C coding challenge
#59> Pointer arithmetic
I have always heard of pointer arithmetic but now I understand why it’s so useful. Taking a pointer to the first element in an array and incrementing it to iterate through it’s elements is elegant and more efficient than taking an integer i and using it as an array index. I wish more languages afforded this.
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.
Re: What I learned from my first C coding challenge
#60> Pointer arithmetic I have always heard of pointer arithmetic but now I understand why it’s so useful. Taking a pointer to the first element in an array and incrementing it to iterate through it’s elements is elegant and more efficient than taking an integer i and using it as an array index. I wish more languages afforded this. Trust me, no you don't. Pointer arithmetic is one of the easiest things to screw up in C,…
You are correct, of course. But he is correct in saying that this method is elegant. Thus, iterators, which, in a much safer form, can be found in Java and Python and many other places.