0xFEE1C001

Where there is a shell, there is a way

strlen的实现方法

感谢John Smith来稿,笔风太有趣了,能当本博的专栏作家吗?

    size_t strlen(const char* str)
    {
        size_t len = 0;
        while (*str++)
            len++;
        return len;
    }

这大概是通常的写法,或者是像C语言程序设计的示例

    int strlen(char* s)
    {
        char *p = s;
        while(*p++)
            ;
        return p - s;
    }

和某B偶然说到这个函数,那B说面试的时候老大问了strlen的写法,他当时用了一种 比较快速的方法。第一反应这货还有快速实现?怎么搞都得遍历完这个字符串,O(n)没跑了,你丫忽悠我。

答曰不是,然后上网去搜了一个glibc的strlen实现。大概如下:

    size_t strlen (const char *str)
    {
        const char *char_ptr;
        const unsigned long int *longword_ptr;
        unsigned long int longword, magic_bits, himagic, lomagic;

        for (char_ptr = str; ((unsigned long int) char_ptr
                & (sizeof (longword) - 1)) != 0;
                    ++char_ptr)
            if (*char_ptr == '\0')
                return char_ptr - str;

        longword_ptr = (unsigned long int *) char_ptr;

        magic_bits = 0x7efefeffL;
        himagic = 0x80808080L;
        lomagic = 0x01010101L;
        if (sizeof (longword) > 4)
        {
            magic_bits = ((0x7efefefeL << 16) << 16) | 0xfefefeffL;
            himagic = ((himagic << 16) << 16) | himagic;
            lomagic = ((lomagic << 16) << 16) | lomagic;
        }
        if (sizeof (longword) > 8)
            abort ();

        for (;;)
        {
            longword = *longword_ptr++;

            if (((longword - lomagic) & himagic) != 0)
            {
                const char *cp = (const char *) (longword_ptr - 1);

                if (cp[0] == 0)
                    return cp - str;
                if (cp[1] == 0)
                    return cp - str + 1;
                if (cp[2] == 0)
                    return cp - str + 2;
                if (cp[3] == 0)
                    return cp - str + 3;
                if (sizeof (longword) > 4)
                {
                    if (cp[4] == 0)
                        return cp - str + 4;
                    if (cp[5] == 0)
                        return cp - str + 5;
                    if (cp[6] == 0)
                        return cp - str + 6;
                    if (cp[7] == 0)
                        return cp - str + 7;
                }
            }
        }
    }

艹,这么长(你这么想了,你一定这么想了)。

大概看了下,主要思想是一次取4/8个字节的数据进行判断。减少了将数据从内存搬到寄存器的指令次数。碉堡了,简直碉堡了。

以32位机器为例。

第一步地址4字节对齐。将地址与上0x03,抹掉前面的bits,留下最后两位,检查是否为0,为0则地址是4字节对齐的退出循环,否则地址+1。

第二步4字节作步长,检查取到的4字节中是否有\0,有的话,return 长度,没有继续往后走。检查是否有\0,是通过 (x - 0x01010101L) & 0x80808080L != 0来做的。至于为啥可以这么做,自行列竖式试验下就知道了。如果有\0,遍历那4个字节,看具体是哪个字节是\0

至此,实现方式已经清楚了。

但是这种方式实际上对于非ascii字符串是有问题的,会误判。所谓步子迈大了容易扯着tama。 unicode,GBK啥的,虽然函数不会出错,但是效率退化到和普通遍历一样了。 GBK是这样编码的好像,比如两字节表示一个字,这种情况下第一个字节肯定是大于等于128。就是说第一个字节最高位是1,这样 (x - 0x01010101L) & 0x80808080L != 0判断是否有\0就失效了,就算上面的判断为true,那4个字节也没有\0,代码会遍历那4个字节,发现实际上没有\0,不退出,继续往后走直到找到\0

理论上对于ascii字符串,glibc的实现可以达到3X的效率提升,仔细想想 Is it worthwhile?

who knows? ╮(╯_╰)╭, it all depends.

现在的电脑,内存带宽大概在5GB/s(我胡邹的),mov VAR, %eax这条指令大约消耗十几到几十个时钟周期(这也是胡诌的)。做这样的优化是否有意义不太好说,真是超级无所谓的事情。对程序员来说,就知道大概有这么一种思想,可以这么做,聊以自慰罢了。

----喂喂,你是认真的么

----我错了,我说谎了,最大作用是可以和别人拿来zhuangbility。。。

顺便说一下,CRC32算法也用到这种的思想了(同上)。一次取4字节数据进行计算 + 打表。可以达到原本计算方法几十倍速度的提升吧,大概。。。有兴趣自行wikipedia。

以上

john_smith,2013-12-07,一边听着柿姐的<虎视眈眈>,一边看里番,一边想着中午吃什么,一边写这个。

无所谓,真是超级无所谓的事情。

评论