• Linear search faster than binary search

    From Bonita Montero@21:1/5 to All on Thu Jan 6 09:21:14 2022
    I've written some code that resembles FileTimeToSystemTime from Win32.
    In that code I did needed to get the month and the day from a FILETIME (100ns-intervals) offset within a year. I did this with a binary search
    on a table, but although the code isn't performance-critical I asked
    myself if a linear search would be faster because there would be less
    branch misspredictions than with the binary search - there are only a
    few elements so that the linear search might be faster:

    static
    uint64_t const alignas(CL_SIZE) monthOffsets[2][12 + 1] =
    {
    { 0 * DAY, 31 * DAY, 59 * DAY, 90 * DAY, 120 * DAY, 151 * DAY, 181 *
    DAY, 212 * DAY, 243 * DAY, 273 * DAY, 304 * DAY, 334 * DAY, 999 * DAY },
    { 0 * DAY, 31 * DAY, 60 * DAY, 91 * DAY, 121 * DAY, 152 * DAY, 182 *
    DAY, 213 * DAY, 244 * DAY, 274 * DAY, 305 * DAY, 335 * DAY, 999 * DAY }
    };
    uint64_t const *pMonthOffsets = monthOffsets[leapYear];
    #if defined(BINARY_SEARCH)
    size_t lower = 0, upper = 12, hit = -1, mid;
    do
    {
    mid = (lower + upper) / 2;
    if( pMonthOffsets[mid] <= tsCalc )
    hit = mid,
    lower = mid + 1;
    else
    upper = mid;
    } while( lower != upper );
    #else
    size_t hit;
    for( hit = 0; tsCalc >= pMonthOffsets[hit + 1]; ++hit );
    #endif

    The code with the linear search is about 17% faster !

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Marcel Mueller@21:1/5 to All on Thu Jan 6 12:41:54 2022
    Am 06.01.22 um 09:21 schrieb Bonita Montero:
    I've written some code that resembles FileTimeToSystemTime from Win32.
    In that code I did needed to get the month and the day from a FILETIME (100ns-intervals) offset within a year. I did this with a binary search
    on a table, but although the code isn't performance-critical I asked
    myself if a linear search would be faster because there would be less
    branch misspredictions than with the binary search - there are only a
    few elements so that the linear search might be faster:

    This is typical.

    1. The branch prediction you already mentioned.
    2. Random memory access is slower than linear memory access.
    Details highly depend on cache line size and object size, of course. As
    long as the entire fable fits into a single cache line there is no
    difference.

    Some frameworks have hybrid dictionaries for this purpose that switch
    between different strategies depending on the number of elements:
    unordered list, sorted list, hash table.


    Marcel

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Bonita Montero@21:1/5 to All on Fri Jan 7 15:49:17 2022
    Am 06.01.2022 um 12:41 schrieb Marcel Mueller:
    Am 06.01.22 um 09:21 schrieb Bonita Montero:
    I've written some code that resembles FileTimeToSystemTime from Win32.
    In that code I did needed to get the month and the day from a FILETIME
    (100ns-intervals) offset within a year. I did this with a binary search
    on a table, but although the code isn't performance-critical I asked
    myself if a linear search would be faster because there would be less
    branch misspredictions than with the binary search - there are only a
    few elements so that the linear search might be faster:

    This is typical.

    1. The branch prediction you already mentioned.
    2. Random memory access is slower than linear memory access.
    Details highly depend on cache line size and object size, of course. As
    long as the entire fable fits into a single cache line there is no difference.

    If the array is that small that linear search is favourable it's
    likely to fit in a cacheline. Then the key-comparison cost is also
    low because it wouldn't binary search would becom favourable.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Andrey Tarasevich@21:1/5 to Bonita Montero on Fri Jan 7 12:28:05 2022
    On 1/6/2022 12:21 AM, Bonita Montero wrote:

    The code with the linear search is about 17% faster !

    For one, you binary search version does not attamtp to take advantage of
    a possible "lucky hit". It insists on waiting for 'lower'/'upper'
    convergence even if the interval in question has already been found. Asymptotically this might not mean much, but in the context of the
    practical experiment (small array, searching for intervals, not exact
    values) this might make a difference.

    --
    Best regards,
    Andrey Tarasevich

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Bonita Montero@21:1/5 to All on Sat Jan 8 04:15:21 2022
    Am 07.01.2022 um 21:28 schrieb Andrey Tarasevich:

    For one, you binary search version does not attamtp to take advantage
    of a possible "lucky hit". ...

    Show me the code where a "lucky hit" is sufficient.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From =?UTF-8?B?w5bDtiBUaWli?=@21:1/5 to Bonita Montero on Sat Jan 8 18:00:56 2022
    On Saturday, 8 January 2022 at 05:15:34 UTC+2, Bonita Montero wrote:
    Am 07.01.2022 um 21:28 schrieb Andrey Tarasevich:

    For one, you binary search version does not attamtp to take advantage
    of a possible "lucky hit". ...

    Show me the code where a "lucky hit" is sufficient.

    It is hard to read your code as it is random slice of real thing. That is perhaps
    why you can't write lucky code. Ok ... code:

    constexpr auto YEAR = DAY * 365;
    size_t lucky_hit = (tsCalc * 12) / YEAR;

    One multiplication, one division and we have "lucky_hit". Now the homework
    for you is to verify if it is precisely the month index or is next to it.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)