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).

On Wednesday, 23 May 2018 at 02:24:08 UTC, IntegratedDimensions wrote:
>
> 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();
> }
>

assuming you meant
> auto d = (int i){ if(decision(i)) A; else d = (int i) { B; };};
> for(int i = 0; i < N; i++)
> {
>     d(i);
> }
>

> 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).

If decision is pure, consider using static foreach (iota(N).map!decision) { ... }to unroll it at compile time. even if it isn't the compiler may still be able to factor out parts of repeated calls to decision, look at the assembly/IR to confirm this.

Otherwise PROFILE!!!!! (and use profile guided optimisation! this implies using a compiler other than DMD which if you care about performance you should be doing anyway)

Blindly trying to optimise is just as likely to hurt performance.
in particular don't underestimate the branch predictor. Even if decision is complex, if there is a pattern in evaluating iota(n).map!decision the branch predictor will pick up on it.

In terms of exploiting knowledge of decision a priori that the compiler somehow lacks you really don't have much option but to do it yourself.

On Wednesday, 23 May 2018 at 03:00:17 UTC, Nicholas Wilson wrote:
> On Wednesday, 23 May 2018 at 02:24:08 UTC, IntegratedDimensions wrote:
>>
>> 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();
>> }
>>
>
> assuming you meant
>> auto d = (int i){ if(decision(i)) A; else d = (int i) { B; };};
>> for(int i = 0; i < N; i++)
>> {
>>     d(i);
>> }
>>
>
>> 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).
>
> If decision is pure, consider using static foreach (iota(N).map!decision) { ... }to unroll it at compile time. even if it isn't the compiler may still be able to factor out parts of repeated calls to decision, look at the assembly/IR to confirm this.
>
> Otherwise PROFILE!!!!! (and use profile guided optimisation! this implies using a compiler other than DMD which if you care about performance you should be doing anyway)
>
> Blindly trying to optimise is just as likely to hurt performance.
> in particular don't underestimate the branch predictor. Even if decision is complex, if there is a pattern in evaluating iota(n).map!decision the branch predictor will pick up on it.
>
> In terms of exploiting knowledge of decision a priori that the compiler somehow lacks you really don't have much option but to do it yourself.

I knew someone was going to say that and I forgot to say DON'T!

Saying to profile when I clearly said these ARE cases where they are slow is just moronic. Please don't use default answers to arguments.

This was a general question about cases on how to attack a problem WHEN profiling says I need to optimize. Your SO 101 answer sucks! Sorry!

To prove to you that your answer is invalid:

I profile my code, it says that it is very slow and shows that it is do to the decision checking... I then I have to come here and write up a post trying to explain how to solve the problem. I then get a post telling me I should profile. I then respond I did profile and that this is my problem. A lot of wasted energy when it is better to know a general attack strategy. Yes, some of us can judge if code is needed to be optimized before profiling. It is not difficult. Giving a generic answer that always does not apply and is obvious to anyone trying to do optimization is not helpful. Everyone today pretty must does not even optimize code anymore... this isn't 1979. It's not ok to keep repeating the same mantra. I guess we should turn this in to a meme?

The reason I'm getting on to you is that the "profile before optimization" sounds a bit grade school, specially since I wasn't talking anything about profiling but a general programming pattern speed up code, which is always valid but not always useful(and hence that is when profiling comes in).

On Wednesday, 23 May 2018 at 02:24:08 UTC, IntegratedDimensions wrote:
> 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.

I would just do
>int i=0;
>for(;decision(i) && i < N; i++)
>{
>    A;
>}
>for(;i < N; i++)
>{
>    B;
>}

This could be turned to a mixin template with something like this:
>mixin template forSplit(alias condition, alias A, alias B)
>{
>    void execute()
>    {
>        int i = 0;
>        for (; condition(i) && i < N; i++)
>        {
>            A();
>        }
>        for (; i < N; i++)
>        {
>            B();
>        }
>    }
>}

and to use it in code (assuming N is defined in the scope)
>mixin forSplit!((int i)=>(decision(i)), {A;}, {B;}) loop;
>loop.execute();

I have't measured anything, but I would assume that delegates come with an overhead that you just don't need here. In fact when trying to use
> auto d = (int i) {};
> d = (int i){ if(decision(i)) A; else d = (int i) { B; };};
> for(int i = 0; i < N; i++)
> {
>     d(i);
> }
All I got was "cannot access frame of function D main" which sums up my experiences with lambdas in D so far.

While PGO and branch predictor are good, they don't help much here. Not executing an expression is out of scope for them. All they do is prevent pipeline flushes.
Also I think you overestimate what the compiler can do. My decision function to do some testing was this:
>bool decision(int a) pure
>out (result) {
>    	assert(result == (a < 10));
>} do {
>    import std.algorithm, std.range;
> 
>    // stolen from https://dlang.org/library/std/parallelism.html
>    enum n = 1_000_000;
>    enum delta = 1.0 / n;
>    alias getTerm = (int i)
>    {
>        immutable x = ( i - 0.5 ) * delta;
>        return delta / ( 1.0 + x * x ) ;
>    };
>    immutable pi = 4.0 * reduce!"a + b"(n.iota.map!getTerm);
> 
>    return a < 3*pi;
>}
With N=100 I got a speedup of ~10 (ldc -O3 -release). Even though this function is pure and could be optimized a lot. It calculated pi for every single call. And optimizing the decision function isn't even the point of that question.

On Wednesday, 23 May 2018 at 10:55:02 UTC, Malte wrote:
> On Wednesday, 23 May 2018 at 02:24:08 UTC, IntegratedDimensions wrote:
>> [...]
>
> I would just do
>>[...]
>
> [...]


Thanks, I didn't think about using a for loop like that. While it is not the most general it does solve the specific case for a simple step/toggled decision.

On Wednesday, 23 May 2018 at 03:12:52 UTC, IntegratedDimensions wrote:
> I knew someone was going to say that and I forgot to say DON'T!
>
> Saying to profile when I clearly said these ARE cases where they are slow is just moronic. Please don't use default answers to arguments.
>
> This was a general question about cases on how to attack a problem WHEN profiling says I need to optimize. Your SO 101 answer sucks! Sorry!
>
> To prove to you that your answer is invalid:
>
> I profile my code, it says that it is very slow and shows that it is do to the decision checking... I then I have to come here and write up a post trying to explain how to solve the problem. I then get a post telling me I should profile. I then respond I did profile and that this is my problem. A lot of wasted energy when it is better to know a general attack strategy. Yes, some of us can judge if code is needed to be optimized before profiling. It is not difficult. Giving a generic answer that always does not apply and is obvious to anyone trying to do optimization is not helpful. Everyone today pretty must does not even optimize code anymore... this isn't 1979. It's not ok to keep repeating the same mantra. I guess we should turn this in to a meme?
>
> The reason I'm getting on to you is that the "profile before optimization" sounds a bit grade school, specially since I wasn't talking anything about profiling but a general programming pattern speed up code, which is always valid but not always useful(and hence that is when profiling comes in).

I'm going to ignore the tone of your response, but I am going to say that responding like that isn't going to get you very far. Don't expect others to do likewise.

Assuming that your decision function is indeed the bottleneck, you'll see I did actually provide some hints as to how to optimise the case where decision is pure. even if you can't convince the compiler to inline and expression combine, as in the case for the other answer, you can memoize it (look in std.functional).

One of the great things about D is that you can force lots of computation to happen at compile time, so in the case where decision is impure, factoring it into pure and impure parts and `enum x = pureFunc(args);`ing the part that can be can make a large difference if you can't convince the optimiser to do it for you.

If you still can't do that consider Jitting it  (https://github.com/ldc-developers/druntime/blob/e3bfc5fb780967f1b6807039ff00b2ccaf4b03d9/src/ldc/attributes.d#L78 ) with `-enable-dynamic-compile` or running the loop in parallel with std.parallelism.

On Wednesday, 23 May 2018 at 03:12:52 UTC, IntegratedDimensions wrote:
> On Wednesday, 23 May 2018 at 03:00:17 UTC, Nicholas Wilson wrote:
>> [...]
>
> I knew someone was going to say that and I forgot to say DON'T!
>
> Saying to profile when I clearly said these ARE cases where they are slow is just moronic. Please don't use default answers to arguments.
>
> This was a general question about cases on how to attack a problem WHEN profiling says I need to optimize. Your SO 101 answer sucks! Sorry!
>
> To prove to you that your answer is invalid:
>
> I profile my code, it says that it is very slow and shows that it is do to the decision checking... I then I have to come here and write up a post trying to explain how to solve the problem. I then get a post telling me I should profile. I then respond I did profile and that this is my problem. A lot of wasted energy when it is better to know a general attack strategy. Yes, some of us can judge if code is needed to be optimized before profiling. It is not difficult. Giving a generic answer that always does not apply and is obvious to anyone trying to do optimization is not helpful. Everyone today pretty must does not even optimize code anymore... this isn't 1979. It's not ok to keep repeating the same mantra. I guess we should turn this in to a meme?
>
> The reason I'm getting on to you is that the "profile before optimization" sounds a bit grade school, specially since I wasn't talking anything about profiling but a general programming pattern speed up code, which is always valid but not always useful(and hence that is when profiling comes in).

Very challenging. Wish I could help you out with the tough work. People don't share the same context, especially via online, so it is necessary to clarify the  problem so other can understand and help. I've been beaten on stackoverflow many times for not providing sufficient information for my questions. It seems like one can do the reverse here at forum.dlang.org.

With that said, I think you know what you are doing, and you can do it. Just relax and give it more time and experimentation.