我的FindOneOf函数的性能问题 [英] Performance problem with my FindOneOf function

问题描述

大家好，我正在开发自己的CString类.有了使它比标准CString快得多"，易于升级以及将一些我在工作中经常使用的非标准解析函数纳入其中的想法，这些将更好地成为CFString对象本身的一部分，而不是单独的功能.
事实上，我在CFString使用的基本功能方面取得了一些显著成就:

我的copy()比strcpy()快35％！

我的lengh()比strlen()快30％.
但是请注意，优化器通常会预先计算strlen()调用，并将其替换为相应的数字！
例如int i = strlen("abc")最终将生成mov EAX，这是生成strlen()本身的asm代码的3步，这发生在硬编码的字符串上！因此，在用数字代替strlen()的情况下，我的函数快了30％

我的compare()比strcmp()快了20％.

我使用了Visual C ++编译器的内联汇编选项，通过"__asm"命令可实现此目的.

我还开发了一种均衡机制，因此当我编写str1 = str2时，"operator =实际上不会复制从str2到str1的数据仅在特定情况下才需要复制.
与CString均衡相比，该机制可以使CFString对象之间的均衡速度提高约35-40％！

到目前为止一切顺利！但是在使用FindOneOf的情况下，标准CString严重击败了我！ CString :: FindOneOf几乎比我的CFString :: FindOneOf快了三倍，而且我的FindOneOf IS也用汇编语言编写.我做了一切，但我只将时间从33000ms减少到28000ms，而CString :: FindOneOf的工作时间为18000ms，我的函数应该更快，现在我很高兴能等于CString :: FindOneOf的得分！
这是我使用的测试代码:

Hi All

I''m developing my own CString class. With the idea to make it "much" faster than the standard CString, easily upgradeable, and to include into it some non-standard parsing functions I often use in my work, those will be much better to be part of the CFString object itself, instead of being separate functions.
And in deed I have some noticeable achievements for the basic functions my CFString uses:

My copy() is 35% faster then strcpy()!

My lengh() is 30% faster than strlen().
BUT note that the optimizer often pre-calculates strlen() calls and replaces them with respective numbers!
For example int i = strlen("abc") will eventually generate mov EAX, 3 instaed of generating the asm code of strlen() itself, that happens for hardcoded strings! so in the cases when strlen() isn''t replaced by a number, my function is 30% faster

My compare() is 20% faster than strcmp().

I used the inline assembly option of the Visual C++ compiler, the "__asm" command to achieve this.

I also developed an equalizing mechanism, so when I write str1 = str2 the "operator =" actually doesn''t copy the data from str2 to str1
the copy occurs ONLY in specific cases when it''s needed.
And that mechanism provides about 35 - 40% faster equalizing betweend CFString objects in comparison to the CString equalizing!

So far so good! But in the case with FindOneOf the standard CString beated me badly! CString::FindOneOf is almost twise faster than my CFString::FindOneOf, and my FindOneOf IS written in assembly too. I did everithing I could to tweak it up, but I only reduced the time from 33000ms to 28000ms and CString::FindOneOf does the job for 18000ms, and my function suppose to be faster, now I''ll be happy just to equal the score of CString::FindOneOf!
This is the test code I use:

<br />	CString/CFString str1("abcdefghijklmnoprs0987654321");<br /><br />	int start = GetTickCount();<br />	for(int pos = 0; pos; 100000000; pos++)<br />	{<br />		index = 0;<br />		index = str1.FindOneOf("1234567890");<br />	}<br />	int time = GetTickCount() - start;<br /><br />	CString strTime;<br />	strTime.Format("%d, %d", time, index);<br />	m_editResult.SetWindowText(strTime); //this is the CEdit object I use for output<br />

我看着CString :: FindOneOf的反汇编，但是找不到单个循环，我没有什么也听不懂！有很多堆栈操作(PUSH POP)，有很多CALL，而且它们似乎很慢，我不知道该功能如何击败我！!!!
这是我写的算法C，虽然它是用汇编语言编写的，但我认为它在实际功能上已经过优化:

I looked at the disassembly of the CString::FindOneOf but couldn''t find a single loop, I didn''t understan anything! there are a lot of stack operations (PUSH POP) a lot of CALLs and they suppose to be slow, I don''t have any idea how can this function beat mine!!!
This is the algorithm I use written in C, although it''s written in assembly and I believe optimised in the actual function:

<br />        const char* pstrTBuffer = m_pstrBuffer; //the actual string<br />	const char* pstrTSeek   = pstrSeek; //the charset<br />	do<br />	{<br />		while(*pstrTSeek)<br />		{<br />			if(*pstrTBuffer == *pstrTSeek++)<br />			{<br />				return pstrTBuffer - m_pstrBuffer;<br />			}<br />		}<br />		pstrTSeek = pstrSeek;<br />	}<br />	while(*++pstrTBuffer);<br />	return -1;<br />

如果代码不够清晰，请执行以下操作:
这个想法尽可能简单，比较主字符串m_pstrBuffer中的每个字符与charset pstrSeek中的每个字符是否匹配，如果不匹配则返回其索引，否则返回-1

我认为问题不在我的编码技术范围内，通常必须在我使用的算法中！！
有人知道更好的算法来实现FindOneOf吗??? :)
我将不胜感激-谢谢！！！ :)

很抱歉，这个问题很长时间了，但是我想在我的描述中尽量保持清楚.

In case the code isn''t clear enough:
The idea is as simple as possible, compare each character in the main string m_pstrBuffer with each character in the charset pstrSeek
if there is a match return its index if not return -1

I assumed that the problem isn''t in my coding technique, it must be generally in the algorithm I use!!!
Does somebody know a better algorithm to implement FindOneOf??? :)
I will appreciate any help - thank you!!! :)

Sorry for the prolonged question, but I wanted to be as clear as I can in my description.

在2009年6月22日星期一10:20修改

modified on Monday, June 22, 2009 10:20 AM

推荐答案

成员4399131写道:

Member 4399131 wrote:

我认为问题不在我的编码技术中，它通常必须在我使用的算法中！！！

I assumed that the problem isn''t in my coding technique, it must be generally in the algorithm I use!!!

是的.

Yep.

成员4399131写道:

Member 4399131 wrote:

有人知道更好的算法来实现FindOneOf ???

Does somebody know a better algorithm to implement FindOneOf???

Microsoft看一下他们的代码(strpbrk-实际上是使用strspn实现的):)

他们建立了一个表(只有256位= = 32字节)，然后从您要查找的字符集中对要搜索的字符串的每个字符进行表查找.这意味着它们的算法为O(n)(n =搜索字符串长度)而不是O(n * m)(n =搜索字符串长度，m =您要查找的字符数).

哦，它们以汇编语言实现(x86和x64的不同实现) ).如果我是你，我会帮自己一个忙，在这种情况下使用MS C运行时功能...

Looking at their code (strpbrk - actually implemented using strspn), Microsoft do :)

They build a table (it''s only 256 bits == 32 bytes) from the set of characters you''re looking for and do a table lookup for each character of the string you''re searching in. That means that their algorithm is O(n) (n=search string length) rather than O(n*m) (n=search string length, m=number of chars you''re looking for).

Oh, and they implement that in assembly language (different implementations for x86 and x64). If I were you, I''d do myself a favour and use the MS C run-time function in this case...

不知道背后的逻辑在标准实现中，不可能知道为什么您的算法被击败.也许标准字符串存储有关特定搜索的数据，以便在您的循环中加载已知结果，而不是重新计算它们(即，您正在同一字符串中搜索同一字符集，为什么不缓存结果?).也许它意识到您输入的字符集是连续的，而不是遍历它们，而是针对范围对每个字符进行测试.也许标准实现从字符串的末尾开始并向前搜索.也许编译器意识到您可以优化循环中对FindOneOf的标准调用，因为您没有使用除最后一个方法调用之外的任何方法调用值，但是无法优化内联汇编.道德是，如果不进行更多测试，我不知道为什么您的算法较慢(或者您的测试方法不合适).我只会推荐其他测试用例，或者只做一个或多个我说过的修改，这些修改是标准代码所做的事情的可能性.您还可以尝试对循环进行重新排序，但是我怀疑您会发现这种变化会导致明显的时序差异.

[BEGIN EDIT]
查找表的主意对于ASCII字符串而言是一个很好的主意. ..我只是在考虑Unicode.
[END EDIT]

Without knowing the logic behind the standard implementation, it is impossible to know why your algorithm is being beat. Perhaps the standard string stores data about specific searches so that, in your loop, it loads known results instead of recalculating them (ie, you are searching the same string for the same charset, so why not cache the result?). Perhaps it realized that your set of input characters is consecutive, and instead of iterating through them it tests each character against a range. Perhaps the standard implementation starts from the end of the string and searches forward. Perhaps the compiler realized that the standard call to FindOneOf in your loop could be optimized away since you are not using any values of that method call except the final one, but your inline-assembly could not be optimized away. The moral is, without doing more testing I have no idea why your algorithm is slower (or your test method is inappropriate). I would only recommend additional test cases, or to make one or more of the modifications that I said were possibilities of what the standard code does. You could also try reordering the loops, but I doubt you are going to see significant timing differences resulting from such a change.

[BEGIN EDIT]
The lookup table idea is a great one for ASCII strings... I was only thinking in terms of unicode.
[END EDIT]

我认为Stuart建议在这种情况下使用C运行时是最好的选择.

算法可以针对不同的目的进行优化，并且在某些情况下也可以更好或更坏.我猜标准的C运行时实现是相当通用且可预测的.

尝试以下算法，您将明白我的意思.
使用您的字符串，它的速度是CString::FindOneOf()的两倍发行后用于测试和测量.另一方面，在搜索字符串中添加"u"会使算法比CString::FindOneOf()慢50％.当然，您可以进一步优化它，但是它仍然有其缺点.
下面算法的关键是尽可能少地处理要搜索的字符串中的每个字符.

I think Stuart''s advice to use the C runtime in this case is the best alternative.

An algorithm can be optimized for different purposes and can also be better or worse in some scenarios. I guess the standard C runtime implementation is rather generic and predictable.

Try out the following algorithm and you''ll see what I mean.
It is twice as fast as CString::FindOneOf() with the strings you''re using for testing and measurement when it''s release-built. On the other hand, adding a ''u'' in the search string will make the algorithm 50% slower than CString::FindOneOf(). Surely you can optimize it further, but it will still have its weaknesses.
The key in the algorithm below is to do as little as possible with each char in the string to be searched.

int FindOneOf( const char* pString, const char* pSearch )<br />{<br />    register char cMask = -1;<br />    register char cPattern = *pSearch;<br />    register int nPos;<br />    int nSPos;<br />    int nRet = -1;<br /><br />    for( nPos = 1; pSearch[nPos]; ++nPos )<br />    {<br />        cMask &= ~(pSearch[nPos - 1] ^ pSearch[nPos]);<br />        cPattern |= pSearch[nPos];<br />    }<br />    // cMask now contains ''1''s in bits that have the same value for every char in pSearch string<br /><br />    // Check each char in pString<br />    for( nPos = 0; pString[nPos]; ++nPos )<br />    {<br />        // Find out which bits have the same values by ''~(pString[nPos] ^ cPattern)''<br />        // Mask the bits of interest and compare with the mask<br />        if( (~(pString[nPos] ^ cPattern) & cMask) == cMask )<br />        {<br />            // We have a possible match, now walk through the search string<br />            for( nSPos = 0; pSearch[nSPos]; ++nSPos )<br />            {<br />                if( pString[nPos] == pSearch[nSPos] )<br />                {<br />                    // A match was found, update return value and get out<br />                    nRet = nPos;<br />                    break;<br />                }<br />            }<br />            if( nRet != -1 )<br />            {<br />                break;<br />            }<br />        }<br />    }<br /><br />    return nRet;<br />}

当心！以上只是我脑海中的一个例子！ ;-)

Beware! The above is just an example at the top of my head! ;-)

这篇关于我的FindOneOf函数的性能问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！