九天雁翎的博客
如果你想在软件业获得成功,就使用你知道的最强大的语言,用它解决你知道的最难的问题,并且等待竞争对手的经理做出自甘平庸的选择。 -- Paul Graham

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

 

 

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

write by 九天雁翎(JTianLing) --
blog.csdn.net/vagrxie

讨论新闻组及文件

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

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

方案一:

 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一次,ifA<=一次,*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实现的猜数字游戏:)