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)

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)

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)

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)

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)

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)