Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Linear search faster than binary search
71 views
Skip to first unread message
Bonita Montero
Jan 6, 2022, 3:21:31 AM1/6/22
to
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 !
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 !
Marcel Mueller
Jan 6, 2022, 6:42:21 AM1/6/22
to
Am 06.01.22 um 09:21 schrieb Bonita Montero:
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
> 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.
> 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:
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
Bonita Montero
Jan 7, 2022, 9:49:31 AM1/7/22
to
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
> 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.
likely to fit in a cacheline. Then the key-comparison cost is also
low because it wouldn't binary search would becom favourable.
Andrey Tarasevich
Jan 7, 2022, 3:28:22 PM1/7/22
to
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
>
> The code with the linear search is about 17% faster !
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
Bonita Montero
Jan 7, 2022, 10:15:34 PM1/7/22
to
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". ...
> For one, you binary search version does not attamtp to take advantage
Show me the code where a "lucky hit" is sufficient.
Öö Tiib
Jan 8, 2022, 9:01:09 PM1/8/22
to
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.
0 new messages