Efficient idiom for fastest code

IntegratedDimensions IntegratedDimensions at gmail.com
Wed May 23 02:24:08 UTC 2018


Many times in expensive loops one must make decisions. Decisions 
must be determined and the determination costs.

for(int i = 0; i < N; i++)
{
     if(decision(i)) A; else B;
}

the if statement costs N times the cycle cost.

In some cases the decision holds for continuous ranges. For some 
0 <= n <= N the decision is constant, but n is 
arbitrary(determined by unknown factors at compile time).

One can speed up the routine by using something akin to a 
simplified strategy pattern where one uses 
functions/delegates/lambdas to code a faster version without the 
test:


for(int i = 0; i < N; i++)
{
     d = (){ if(decision(i)) A; else d = () { B; };
     d();
}

this code basically reduces to

for(int i = 0; i < N; i++)
{
     B;
}

Once the decision fails, which we assume once it fails it always 
fails in this particular case.

Therefor, once the decision fails it kicks in the "faster" code. 
Suppose decision is very slow.

The cycle cost is then n times rather than N times.

In general, such techniques can be used to speed up code, 
sometimes significantly, but are difficult to implement using a 
standard pattern and for more complex decision functions.


Does anyone see any way to use some some of D's power to help 
simplify such things but not using something like a strategy 
pattern or complexifying the overall design(using advanced 
techniques such as templates, mixins is not making the code more 
complex).
















More information about the Digitalmars-d-learn mailing list