Your insertion sort scans downwards from the highest populated index, bumping elements up as it goes. Given that you have space on both sides, I'm surprised that you didn't start in the middle and pick a scan direction based on the comparison result there.
What I learned from my first C coding challenge
71–80 of 85 posts
Re: What I learned from my first C coding challenge
#72Good 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…
Awesome code review. Thank you.
[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 );
}
static inline int str_compare( const char *a, const char *b )
{
while( ( *a == *b ) && *a )
{
a++; b++;
}
return( *a - *b );
}
Re: What I learned from my first C coding challenge
#73Earlier quoted context omitted.
Awesome code review. Thank you.
[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…
How 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...
Re: What I learned from my first C coding challenge
#74Earlier quoted context omitted.
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…
Except we're not talking about any old library function here. We're talking about standard library functions such as memcpy, etc. Those functions are optimised specifically for different hardware platforms on every major operating system. For example, Solaris, Linux, and Windows all feature versions of memcpy that are specifically optimised for different hardware platforms. Intel in particular supplies these optimisa…
While I agree ont he general sentiment of your post, I remember in the case of memcpy that at least the GCC implementation is a "most general case" implementation which tries to have good performance in average usage.
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.
Re: What I learned from my first C coding challenge
#75Earlier quoted context omitted.
[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…
How 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...
Both 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"
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.
Re: What I learned from my first C coding challenge
#76Earlier 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. 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?
SPARC is pretty much a lost cause for us. I believe that we have had better performance with the system memcpy over anything we've written.
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.
Re: What I learned from my first C coding challenge
#77Earlier quoted context omitted.
Awesome code review. Thank you.
[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…
Hey thanks for the suggestions. One thing that I found is that testing both strings for null actually performs faster because you may have parameters of different lengths and bailing on the null character of the shortest is ideal. And actually testing for an ampersand would probably bail even earlier in cases of duplicate params.
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?
Re: What I learned from my first C coding challenge
#78(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…
I think this is a valid point. I usually try to rely on the optimizations that are already done for me. I think in this case the strcmp function may be doing some extra work based on locale/collation that I don't need to consider in my code which is making my code faster. But point well taken.
Re: What I learned from my first C coding challenge
#79Good read. Reminds me of the oldie but goodie http://ridiculousfish.com/blog/posts/old-age-and-treachery.h...
Interesting find.
Re: What I learned from my first C coding challenge
#80Nice, i remember my first coding challenge in c. Nice result for first attempt.
Thanks!