C: Why some string.h algorithms work slower than simple hand-made ones?

Question

For example, strlen() takes about 3*O(n). Why 3? I've wrote a really simple strlen-like function - it works much faster.

int string_len(char s[],int &l)
{ 
 for(l=0;s[l];l++);
return l;
}

Well, some of my friends says, nearly all of string.h algorithms are slower than they should be.

Answer 1

I seriously doubt that you have a faster implementation than glibc's version : http://sources.redhat.com/cgi-bin/cvsweb.cgi/libc/string/strlen.c?cvsroot=glibc&rev=1.1.2.1

Answer 2

There's no such thing as 3*O(n) - the three in that is a constant factor, and asymptotic notation explicitly excludes all the constant factors.

So - back at you - why 3, where did you get this 3 from?

The standard strlen function in a typical compilers standard library will be written pretty much exactly the same as yours, and will probably have identical performance - unless your compiler has a hand-optimised machine code version, which is probably rare these days.

Answer 3

I performed a quick test and your assertion was false

First custom strlen as described by you

  1 #include <string.h>
  2 
  3 
  4 int main(){
  5 int i=0;
  6 int j=0;
  7 
  8 char * my_string = "HHHHHHHHHHHHHHHHHHHHHH";
  9 for(i=0; i< 10000000;i++) {
 10   for(j=0; my_string[j]; j++);
 11 }
 12 }
 13 
 14 

The results where

0.60s real     0.60s user     0.00s system

Now using the strlen from strings.h

   1 #include <string.h>
  2 
  3 
  4 int main(){
  5 int i=0;
  6 int j=0;
  7 
  8 char * my_string = "HHHHHHHHHHHHHHHHHHHHHH";
  9 for(i=0; i< 10000000;i++) {
 10  strlen(my_string);
 11 }
 12 }

I get

   0.14s real     0.14s user     0.00s system

Which is 4 times faster

This is on i386 linux.

What platform are you on?

Answer 4

Reconsider your timing algorithm :-)

In some cases you may be able to write some code that is "faster" than a library function, but only if you cut corners that the library function does not. If you write code that has exactly the same behaviour as a library function, it is virtually guaranteed that your code will be equal at best, and probably slower, than the library function.

Answer 5

Library functions are generally faster. if not, they are more general than your functions. if not, they are more secure than your.

3O*(n) is a completely wrong expression.

I think all you need is a knowledge base of algorithm analysis, Asymptotic theory and Asymptotic analysis.

also this book will be helpful:

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7.

you can find it in: McGraw-Hill - Introduction to algorithms or Amazon.com - Introduction to Algorithms, Third Edition

Answer 6

Hey It might be faster for very short strings (if you test was for a string with length 1 for example, but how does it perform with a variaty of string lengths including longer ones. If you look at the implementations for strlen in library code you see it tries to perform opreations on lonmgwords and not on separate bytes. Setting this up takes a few cycles and that is exactly what bites it for very short strings.

As to the general assumption: do you really think that you (and your friends) can do better than thousands of other programmers on all those functions in string.h??

Perhaps you can do better on your small testset for your computer in your controlled environment but the general case... I doubt it.

Answer 7

You're funny, honestly!!! Can't understand why it got downvoted. Are you all so dull not noticing the humour?!