2009年01月25日

在本文中全部以转换为小写为例。

从推荐复用代码的角度来看，用库函数是不错的办法：

方案一：

char gc1[53] = "abcdefghigklmnopqrstuvwxyzABCDEFGHIGKLMNOPQRSTUVWXYZ";


void wayOne()
{
    strlwr(gc1);
}

优点是使用方便，别人看着也容易理解，但是效率慢的让人吐血。

extern "C" char * __cdecl _strlwr (
        char * string
        )
{
    if (__locale_changed == 0)
    {
        char * cp;

        /* validation  
section */
        _VALIDATE_RETURN(string != NULL,  
EINVAL, NULL);

        for (cp=string; *cp; ++cp)
        {
            if  
('A' <= *cp  
&& *cp <= 'Z')
                *cp  
+= 'a' \- 'A';
        }

        return(string);
    }
    else
    {
        _strlwr_s_l(string, (size_t)(-1),  
NULL);
        return string;
    }
}

循环中平均2.5次的判断，（cp一次，if的’A’<=一次，cp<=版次）加平均每次0.5次的加法，虽然这样的转换O(n)是必不可少的，但是对于这样多的操作还是慢的可怕。

例2：

char gc2[53]  
= "abcdefghigklmnopqrstuvwxyzABCDEFGHIGKLMNOPQRSTUVWXYZ";

namespace MYTEST
{
    inline char*  
strlwr(char  
*asz)
    {
       for(char*  
lp = gc2;  
*lp != 0; ++lp)
       {
           *lp |= 0x20;
       }

       return asz;
    }
}

void wayTwo()
{
    MYTEST::strlwr(gc2);
}

此例中利用了ASCII字母值的特点，一共只有一次判断（*lp！=0）,一次位或操作。算法上提高了很多：）其实已经达到了1/3的效率提升。。。。。

将原来一大堆的代码，转化成了反汇编只有4句的程序：

00401020 80 08 20         or          byte ptr [eax],20h 
00401023 83 C0 01         add         eax,1 
00401026 80 38 00         cmp         byte ptr [eax],0 
00401029 75 F5             jne         wayTwo+10h (401020h)

但是考虑到char只是1个字节，看到

00401020 80 08 20 or byte ptr [eax],20h

一句都感觉不爽，白白浪费了eax 这样4个字节的寄存器，于是可以这样优化：

namespace MYTEST2
{
    inline char*  
strlwr(char  
*asz)
    {
       long* lp  
= (long*)gc3;

       for(; *((char*)lp) != 0; ++lp)
       {
           (long)(*lp) |= 0x20202020;
       }

       for(char*  
lpc = (char*)lp;*lpc!=0; ++lpc)
       {
           *lpc |= 0x20;
       }

       return asz;
    }
}

说实话，。。。。。。。。。。。没有任何清晰性可言，没有任何可读性可言，但是优化的思想就是充分的利用4个字节的寄存器，并且以DWORD来读取内存，这是很有效率的方式。汇编代码其实比C语言代码更加清晰，原因在于C语言代码还需要处理大量与类型相关的事情，汇编代码不需要。

第一个循环汇编代码如下:

00401040 81 08 20 20 20 20 or          dword ptr [eax],20202020h 
00401046 83 C0 04         add         eax,4 
00401049 80 38 00         cmp         byte ptr [eax],0 
0040104C 75 F2            jne         wayThree+10h (401040h)

将循环次数减少了3/4。。。。所以效率的优化还是很明显的。单指令多数据操作的思想不过就是这种思想的延生罢了。。。呵呵，但是说在前面，如此影响可读性的效率优化，除非在很必要的情况下，不然慎用。。。。。

为了证实效率的优化，起码也得给出一个测试结果给大家看看吧，不然还以为我胡扯了。

void wayOne()
// Hit Count          : 1
// Time               : 5553.00
// Time with Children : 5553.00
{
       strlwr(gc1);
}

void wayTwo()
// Hit Count          : 1
// Time               : 247.00
// Time with Children : 247.00
{
       MYTEST::strlwr(gc2);
}

void wayThree()
// Hit Count          : 1
// Time               : 180.00
// Time with Children : 180.00
{
       MYTEST2::strlwr(gc3);
}

int _tmain(int argc, _TCHAR* argv[])
// Hit Count          : 1
// Time               : 6836996435.00
// Time with Children : 6837002415.00
{
       wayThree();
       wayTwo();
       wayOne();
}

测试结果为AQtime5测试数据，单位为机器周期，因为结果已经很明显了，所以没有进行多次循环的测试。并且为了排除缓存的影响，将最快的放在了最前面，那么哪怕有缓存的影响，对于wayThree也是最不利的才对。库函数的5000多的结果，说慢的可怕并不为过。在数据量很大的时候，这种优化的差异可不是一点点而已。

write by九天雁翎(JTianLing)
-- www.jtianling.com

分类: 汇编和反汇编
标签: C++

Posted By 九天雁翎 at 九天雁翎的博客 on 2009年01月25日

前一篇: 调试用Python C API 写的程序问题还真多，关于import搜索路径的，复制过来，以防忘记后一篇: 女朋友用Python实现的猜数字游戏：）

C++中字母大小写转换实现的优化

C++中字母大小写转换实现的优化