www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Use of templates to avoid redudancy of code

reply Mael <mael.primet gmail.com> writes:
Hello,

I'm writing an algorithm that has, say, too possible behaviour depending on a
switch. Since there are many imbricated loops, and the behaviour change is
inside the loop, testing for the flag is time-consuming

for( ....)
for( .... )
for( ... )
{
  if( flag ) action_1 ;
  else action_2 ;
}

is there a clean way to use templates to generate the duplicate of the code like

if( flag )
{
  for(...) .... action1 ;
}
else
{
  for(...) .... action2 ;
}
Jun 03 2008
next sibling parent Lutger <lutger.blijdestin gmail.com> writes:
Mael wrote:

 Hello,
 
 I'm writing an algorithm that has, say, too possible behaviour depending
 on a switch. Since there are many imbricated loops, and the behaviour
 change is inside the loop, testing for the flag is time-consuming
 
 for( ....)
 for( .... )
 for( ... )
 {
   if( flag ) action_1 ;
   else action_2 ;
 }
 
 is there a clean way to use templates to generate the duplicate of the
 code like
 
 if( flag )
 {
   for(...) .... action1 ;
 }
 else
 {
   for(...) .... action2 ;
 }

If flag is a compile time constant, then you don't need no templates, just this: static if (flag) action_1 else action_2 The if is evaluated only at compile time. If behavior is changed at runtime, it would depend a little on the rest of the code, there are some different ways to implement if. For example as a helper function: void func(bool flag) { if (flag) helper!(true)(); else helper!(false)(); } void helper(bool flag)() { for( ....) for( .... ) for( ... ) { static if( flag ) action_1 ; else action_2 ; } }
Jun 03 2008
prev sibling next sibling parent Chris Wright <dhasenan gmail.com> writes:
Mael wrote:
 Hello,
 
 I'm writing an algorithm that has, say, too possible behaviour depending on a
switch. Since there are many imbricated loops, and the behaviour change is
inside the loop, testing for the flag is time-consuming

You've profiled and you've determined that checking that bool is expensive. One option is checking it at compile time: void action1(args); void action2(args); template action(bool isActionOne) { static if (isActionOne) alias action1 action; else alias action2 action; } for (...) action!(flag); // Or the same, but instead just hoping for inlining: // global const bool flag; void action(args) { static if (flag) action1(args); else action2(args); } If the flag changes at runtime... Change your functions from: void foo(args) { for (i = 0; i < some_really_huge_number; i++) if (flag) action1(args); else action2(args); } void foo(alias fn)(args) { for (i = 0; i < some_really_huge_number; i++) fn(args); } The vast majority of your methods would just pass on the alias template parameter. You'll still have to know about the flag and the functions wherever the flag might change, though.
Jun 03 2008
prev sibling next sibling parent reply Fawzi Mohamed <fmohamed mac.com> writes:
On 2008-06-03 11:39:24 +0200, Mael <mael.primet gmail.com> said:

 Hello,
 
 I'm writing an algorithm that has, say, too possible behaviour 
 depending on a switch. Since there are many imbricated loops, and the 
 behaviour change is inside the loop, testing for the flag is 
 time-consuming

I trust you really profiled the code to see this (never optimize before testing)
 for( ....)
 for( .... )
 for( ... )
 {
   if( flag ) action_1 ;
   else action_2 ;
 }
 
 is there a clean way to use templates to generate the duplicate of the 
 code like
 
 if( flag )
 {
   for(...) .... action1 ;
 }
 else
 {
   for(...) .... action2 ;
 }

a simple compile time solution is to make the looping construct a template, and the action a template parameter (either alias or char[] to mixin if you need). I used it extensively in my multidimensional array lib...
Jun 03 2008
next sibling parent reply Fawzi Mohamed <fmohamed mac.com> writes:
On 2008-06-03 15:19:33 +0200, Fawzi Mohamed <fmohamed mac.com> said:

 On 2008-06-03 11:39:24 +0200, Mael <mael.primet gmail.com> said:
 
 Hello,
 
 I'm writing an algorithm that has, say, too possible behaviour 
 depending on a switch. Since there are many imbricated loops, and the 
 behaviour change is inside the loop, testing for the flag is 
 time-consuming

I trust you really profiled the code to see this (never optimize before testing)

In case the issue is actually cleaning up the code, I would consider making the action a delegate that you pass in to your algorithm (and execute there).
Jun 03 2008
parent reply Mael <mael.primet gmail.com> writes:
 In case the issue is actually cleaning up the code, I would consider 
 making the action a delegate that you pass in to your algorithm (and 
 execute there).

This doesn't incur a penalty on the execution time ? Does it unfold the delegate as an inline function, or will there be calls to the delegate ?
Jun 03 2008
parent Fawzi Mohamed <fmohamed mac.com> writes:
On 2008-06-03 20:17:16 +0200, Mael <mael.primet gmail.com> said:

 In case the issue is actually cleaning up the code, I would consider
 making the action a delegate that you pass in to your algorithm (and
 execute there).

This doesn't incur a penalty on the execution time ? Does it unfold the delegate as an inline function, or will there be calls to the delegate ?

yes this incurs a penalty if the delegate doesn't get inlined, and even if it does there might still be some small penalty. So I said *if* you just need to clean up the code, then that is probably the best solution.
Jun 03 2008
prev sibling parent reply Mael <mael.primet gmail.com> writes:
 a simple compile time solution is to make the looping construct a 
 template, and the action a template parameter (either alias or char[] 
 to mixin if you need).

Jun 03 2008
parent reply Fawzi Mohamed <fmohamed mac.com> writes:
On 2008-06-03 20:20:16 +0200, Mael <mael.primet gmail.com> said:

 a simple compile time solution is to make the looping construct a
 template, and the action a template parameter (either alias or char[]
 to mixin if you need).


this approach is like the delegate approach only that it is potentially faster. An alias parameter to a template is a symbol that you pass to the template. This symbol should be the delegate or function that executes the action. void myAlgorithm(alias op)(args for the algorithm){ for.. for .. op(); } the mixin is similar only that you pass a string and the string has access to all variables in the algorithm. This is less safe, bur (form my experience with gdc) also potentially faster for very simple operations. void myAlgorithm(char[] op_str)(args for the algorithm){ for.. for .. mixin(op_str); } op_str must be one (or more) complete statement (you need even the ";") and needs to be a string known at compile time. Fawzi
Jun 03 2008
parent reply Mael <mael.primet gmail.Com> writes:
okay thanks for the explanations,
the D language never specifies whether a function or template argument is
inlined or not ?
It's left up to the compiler to choose what to do ?
Jun 03 2008
next sibling parent Robert Fraser <fraserofthenight gmail.com> writes:
Mael wrote:
 okay thanks for the explanations,
 the D language never specifies whether a function or template argument is
inlined or not ?
 It's left up to the compiler to choose what to do ?

Template arguments are always inlined. (since the template is generated by the compiler). There's a way to specify a function should NOT be inlined (use a .di w/o the function body and link in the final code), but there's little reason you'd want to do that if you had access to the code. I don't think DMD inlines any functions which accept delegate parameters, but I may be wrong (and I think in another thread someone showed GDC does).
Jun 04 2008
prev sibling parent janderson <askme me.com> writes:
Mael wrote:
 okay thanks for the explanations,
 the D language never specifies whether a function or template argument is
inlined or not ?
 It's left up to the compiler to choose what to do ?

Template is likely to inline. Even if it doesn't it will be one less pointer indirection then a delegate. Basically imagine as a copy past operation. That's the easiest thing for the compiler to do, copy in your arguments. The reason it may decide not to is due to template code reuse and yes that could be implementation specific. -Joel
Jun 04 2008
prev sibling parent janderson <askme me.com> writes:
Mael wrote:
 Hello,
 
 I'm writing an algorithm that has, say, too possible behaviour depending on a
switch. Since there are many imbricated loops, and the behaviour change is
inside the loop, testing for the flag is time-consuming
 
 for( ....)
 for( .... )
 for( ... )
 {
   if( flag ) action_1 ;
   else action_2 ;
 }

If the flag is dependent on something in the loop, you could try storing your stuff in buckets (maps, arrays, sorted array or whatever works). That way you know what is in each group to begin with.
 
 is there a clean way to use templates to generate the duplicate of the code
like
 
 if( flag )
 {
   for(...) .... action1 ;
 }
 else
 {
   for(...) .... action2 ;
 }
 

Ok, so you've created some sort of bucket thing, great! Assuming that flag is not an object with a very expensive compare. If you've profiled it and found its a problem (based on algorithm 1) then it means that action_1 and/or action_2 are doing very, very little work and you are traversing many items. I'm imagining its either an assignment or comparison. In fact you would likely get more of a speedup by unrolling the loop then anything else. Note that for does a comparison and a ++ each iteration. Anyway hope that helps explain why other people in the NG immediately raised the pink premature optimisation warning flags. Ok down to my thoughts on optimizing this: Given that action_1 and action_2 are probably small ops; If you want optim performance you could take advantage of SIMD or futures (parallel processing) or there may be a function already that's ASM optimized to do what you want (memcopy, memset etc...) Another possibility is to change the array your iterating over: array = (flag) ? array1 : array2; for (auto value; array) { } Note you save a branch that way, but that would very likely be insignificant. I hope this has been helpful.
Jun 04 2008