#1 2023-04-28 08:57:46

Junior/RO
Member
Registered: 2011-05-13
Posts: 207

"Branchless binary search" can be done in Pascal?

Offline

#2 2023-04-28 09:53:24

ab
Administrator
From: France
Registered: 2010-06-21
Posts: 14,128
Website

Re: "Branchless binary search" can be done in Pascal?

We already do something similar with mORMot.

The asm of Compare*() or SortDynArray*() functions use branchless comparisons.

And since FPC is able to generate some CMOV on properly written code, other pascal functions do it.
Just search for "branchless" comment in the mORMot source code and you will see a lot of places when this is available.
Last time I checked, Delphi did not generate the CMOV asm opcodes as FPC does - but perhaps latest Delphi versions do (even if I doubt it).

Of course, we don't use this "Shar" algorithm, because we did not find our binary search routines to be a bottleneck on production yet.
Cache pollution is likely to be more a problem on production code.
On microbenchmarks, the "Shar" optimization may have an effect, but I am not sure it would be on production code, where most of the time is done putting the data into L1 cache.

Offline

#3 2023-04-29 13:04:43

Junior/RO
Member
Registered: 2011-05-13
Posts: 207

Re: "Branchless binary search" can be done in Pascal?

ab wrote:

We already do something similar with mORMot.

Just search for "branchless" comment in the mORMot source code and you will see a lot of places when this is available.

16 comments in SynCommons.pas, I will read everyone. Thank you.

Offline

#4 2023-04-29 13:47:27

ab
Administrator
From: France
Registered: 2010-06-21
Posts: 14,128
Website

Re: "Branchless binary search" can be done in Pascal?

And even more in mormot 2. wink

Offline

Board footer

Powered by FluxBB