Re: [tortoisesvn] r21435 committed - Speed up FindScreenLineForViewLine using binary search

On 2011-05-21 17:40, Stefan Küng wrote:
> On 21.05.2011 17:25, tortoisesvn_at_googlecode.com wrote:
>> Revision: 21435
>> Author: htcotik
>> Date: Sat May 21 08:25:03 2011
>> Log: Speed up FindScreenLineForViewLine using binary search
>> http://code.google.com/p/tortoisesvn/source/detail?r=21435
>>
>> Modified:
>> /trunk/src/TortoiseMerge/BaseView.cpp
>>
>> =======================================
>> --- /trunk/src/TortoiseMerge/BaseView.cpp Fri May 20 14:59:09 2011
>> +++ /trunk/src/TortoiseMerge/BaseView.cpp Sat May 21 08:25:03 2011
>> @@ -4404,15 +4404,47 @@
>> {
>> RebuildIfNecessary();
>>
>> - int ScreenLine = 0;
>> - for (std::vector<TScreenLineInfo>::const_iterator it =
>> m_Screen2View.begin(); it != m_Screen2View.end(); ++it)
>> - {
>> - if (it->nViewLine>= viewLine)
>> - return ScreenLine;
>> - ScreenLine++;
>> + __int32 nScreenLineCount = (__int32)m_Screen2View.size();
>> +
>> + int nPos = 0;
>> + if (nScreenLineCount>16)
>> + {
>> + // for enougth long data use binary search
>> + __int32 nTestBit = 0x40000000; // simply max value
>> +#define _USE_ASM
>> +#ifdef _USE_ASM
>> + //GetMostSignificantBitValue
>> + __asm {
>> + mov eax, 1
>> + bsr ecx, nScreenLineCount
>> + shl eax, cl
>> + mov nTestBit, eax
>> + }
> Please do not use assembler. It's not supported for x64 builds, it's
ok
> hard to read and with todays optimizing compilers not necessary.
I don't know any optimizer to be able use single instruction for
FindMostSignificatBit. If you know how to write it let me know. There is
other alternative in code though (20 instruction).
Will remove ASM way.
>> +#else
>> + nTestBit = nScreenLineCount;
>> + nTestBit |= nTestBit>>1;
>> + nTestBit |= nTestBit>>2;
>> + nTestBit |= nTestBit>>4;
>> + nTestBit |= nTestBit>>8;
>> + nTestBit |= nTestBit>>16;
>> + nTestBit ^= (nTestBit>>1);
>> +#endif
>> + while (nTestBit)
>> + {
>> + int nTestPos = nPos | nTestBit;
>> + if (nTestPos< nScreenLineCount&&
>> m_Screen2View.operator[](nTestPos).nViewLine< viewLine)
>> + {
>> + nPos = nTestPos;
>> + }
>> + nTestBit>>= 1;
>> + }
>> + }
>> + while (nPos< nScreenLineCount&&
>> m_Screen2View.operator[](nPos).nViewLine< viewLine)
>> + {
>> + nPos++;
>> }
> I don't understand how this works. Is there some documentation
> available? Because it's definitely *not* a binary search:
> http://en.wikipedia.org/wiki/Binary_search_algorithm
It is just binary search which does not start at (Count/2)half, but
minimal 2**n>=Count/2 thus MSB. And thus optimized for machines using
binary code, also bypasses division and rounding issues. Quite common
one I think.
> Please, if you're using such 'tricks', you have to document them properly.
Only 'trick' is that we dont finish at find (==), but 'one' before as we
have to find first (not just any) equal or greater
> Stefan

-- 
Oto BREZINA, Printflow s.r.o., EU
+421 903 653470 skype: ot_ik_
------------------------------------------------------
http://tortoisesvn.tigris.org/ds/viewMessage.do?dsForumId=757&dsMessageId=2743365
To unsubscribe from this discussion, e-mail: [dev-unsubscribe_at_tortoisesvn.tigris.org].