Thursday, March 12, 2009

strlen implementation

I was reading Hacker news and found one very interesting web page link: Glibc's strlen implementation: Probably not what you'd guess. Out of curiosity I have compared Glibc’s strlen implementation with two most simple implementation’s. Here are benchmark results (my4bytes_strlen is still so far away from Glibc’s strlen in term of performance): code:
size_t my_strlen(const char* str)
{
    const char* ptr = str;
    
    size_t size = 0;
    while(*ptr != '\0')
    {
        ptr++, size++;
    }
    return size;
}
    
size_t my4bytes_strlen(const char* str)
{
    const int32_t* ptr = (int32_t*)str;
    size_t size = 0;
    for (;;){
        if (!(*ptr & 0x000000ff)) return size;
        if (!(*ptr & 0x0000ff00)) return size + 1;
        if (!(*ptr & 0x00ff0000)) return size + 2;
        if (!(*ptr & 0xff000000)) return size + 3;

        size += 4;
        ptr++;
    }
}

int main(char* argv[], int argc)
{
    const char* str = "test this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long stringtest this long string";

    Timer t1, t2, t3, t4;
    
    t1.start();
    size_t len = my_strlen(str);
    t1.stop();

    t2.start();
    size_t len1 = glibc_strlen(str);
    t2.stop();
    
    t3.start();
    size_t len3 = strlen(str);
    t3.stop();

    t4.start();
    size_t len4 = my4bytes_strlen(str);
    t4.stop();

    std::cout << " my_strlen size: " << len << " time: " << t1.getElapsedTimeInMilliSec() << std::endl
        << " my4bytes_strlen size: " << len4 << " time: " << t4.getElapsedTimeInMilliSec() << std::endl
        << " glibc size:  " << len1 << " time: " << t2.getElapsedTimeInMilliSec() << std::endl
        << " strlen:  " << len3 << " time: " << t3.getElapsedTimeInMilliSec() << std::endl;

return 0;
}
Time count utilities from http://www.songho.ca/misc/timer/timer.html