What I learned from my first C coding challenge • Hacker News Board

Re: What I learned from my first C coding challenge

#61

Post by binarycrusader » Wed, Sep 05, 2012, 1:29 AM UTC

cube13 wrote: post #49

binarycrusader wrote: post #47

Earlier 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…

Whether it was actually a bug is unclear from your description. By default, Sun Studio intentionally doesn't inline functions defined in system header files unless specifically requested.

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.

Re: What I learned from my first C coding challenge

#62

Post by icefox » Wed, Sep 05, 2012, 1:42 AM UTC

icefox wrote: post #29

Any more detailed information about the coding challenge? 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 i…

The best algorithm depends upon the data presented. What is the:

- Average number of parameters

- The % that are already sorted

- The % that don't have keys that start with same letter

Re: What I learned from my first C coding challenge

#63

Post by binarycrusader » Wed, Sep 05, 2012, 1:48 AM UTC

asveikau wrote: post #58

binarycrusader wrote: post #32

(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…

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 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=

Six of those versions are written in assembler specifically for a particular hardware platform. One is a generic C version. Furthermore, as an example, the amd64 version of memcmp alone has optimisations for at least 14 different cases. Everything from 3DNow! optimisations to optimisations based on data size and alignment.

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.

Re: What I learned from my first C coding challenge

#64

Post by asveikau » Wed, Sep 05, 2012, 1:56 AM UTC

binarycrusader wrote: post #63

asveikau wrote: post #58

Earlier 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…

> 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.

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.

Re: What I learned from my first C coding challenge

#65

Post by to3m » Wed, Sep 05, 2012, 2:19 AM UTC

spc476 wrote: post #55

tsahyt wrote: post #28

It'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 di…

There is no need to compare - ORing the register with itself will suffice to set the Z flag. This is more concise on x86 - i think it's 2 bytes to OR a 32-bit register with itself, vs 3 for a compare with a (sign-extended) 8-bit immediate zero.

Re: What I learned from my first C coding challenge

#66

Post by nitrogen » Wed, Sep 05, 2012, 2:32 AM UTC

jfasi wrote: post #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,…

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 
  #include 
  
  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;
  }

produces this result

  $ 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: 67

Re: What I learned from my first C coding challenge

#67

Post by DeepDuh » Wed, Sep 05, 2012, 3:23 AM UTC

spc476 wrote: post #56

cube13 wrote: post #49

Earlier 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?

If you are forced to implement your own implementation I would rather switch to it completely. IMO it's better to be bold and get problems detected by having a wide adoption of a function rather than hide it in an edge case where problems might hide.

Re: What I learned from my first C coding challenge

#68

Post by exDM69 » Wed, Sep 05, 2012, 5:56 AM UTC

binarycrusader wrote: post #47

exDM69 wrote: post #38

Earlier quoted context omitted.

Your advice is good but a bit too generalized here. 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 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. 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.

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?

Re: What I learned from my first C coding challenge

#69

Post by exDM69 » Wed, Sep 05, 2012, 6:11 AM UTC

binarycrusader wrote: post #63

asveikau wrote: post #58

Earlier 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…

> Six of those versions are written in assembler specifically for a particular hardware platform. One is a generic C version. Furthermore, as an example, the amd64 version of memcmp alone has optimisations for at least 14 different cases. Everything from 3DNow! optimisations to optimisations based on data size and alignment.

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.

Re: What I learned from my first C coding challenge

#70

Post by cageface » Wed, Sep 05, 2012, 6:48 AM UTC

cyberroadie wrote: post #41

I made a varnish urlsort module a while ago: https://github.com/cyberroadie/varnish-urlsort 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

Interesting. Do you have any benchmarks handy to show how much of a difference this makes? I'd wonder if the dynamic allocations necessary to build the tree might undercut the lookup advantages.