You are not logged in.
- Topics: Active | Unanswered
#1 2023-04-28 08:57:46
- Junior/RO
- Member
- Registered: 2011-05-13
- Posts: 207
"Branchless binary search" can be done in Pascal?
Well this is interesting
Offline
#2 2023-04-28 09:53:24
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?
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
