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

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
hard to read and with todays optimizing compilers not necessary.

> +#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

Please, if you're using such 'tricks', you have to document them properly.

Stefan

-- 
        ___
   oo  // \\      "De Chelonian Mobile"
  (_,\/ \_/ \     TortoiseSVN
    \ \_/_\_/>    The coolest Interface to (Sub)Version Control
    /_/   \_\     http://tortoisesvn.net
------------------------------------------------------
http://tortoisesvn.tigris.org/ds/viewMessage.do?dsForumId=757&dsMessageId=2743359
To unsubscribe from this discussion, e-mail: [dev-unsubscribe_at_tortoisesvn.tigris.org].