Code: Select all
for(i=0; i<MAX; i++) if(Condition(i)) Action(i);
Code: Select all
int todo[MAX];
int n=0;
for(i=0; i<MAX; i++) { todo[n] = i; n += (Condition(i) != 0); }
for(i=0; i<n; i++) Action(todo[i]);
Moderators: hgm, Rebel, chrisw
Code: Select all
for(i=0; i<MAX; i++) if(Condition(i)) Action(i);
Code: Select all
int todo[MAX];
int n=0;
for(i=0; i<MAX; i++) { todo[n] = i; n += (Condition(i) != 0); }
for(i=0; i<n; i++) Action(todo[i]);
Code: Select all
for(i=0; i<MAX; i++) { todo[n] = i; n += (Condition(i) ? 1 : 0); }
Yes, but only if you assume that Action() is trivial without side effects and the compiler can see its guts.dragontamer5788 wrote: ↑Mon Dec 09, 2019 11:25 pm Comment: For some reason, I couldn't grok your code in the first pass. My brain understands the following more:
Condition(i) ? 1 : 0 will probably compile into a cmov instruction, so you won't have any branches either. In fact, you probably can use the if() else {} code and rely upon compiler optimizations to use cmov instead of a branch.Code: Select all
for(i=0; i<MAX; i++) { todo[n] = i; n += (Condition(i) ? 1 : 0); }
EDIT: Godbolt says that GCC uses sete flag, which is still branchless.
--------
I see the theory, and I think it could be useful! Interesting food for thought.
I think that (A != 0) used as an operand by definition means (A ? 1 : 0), so the compiler will consider it equivalent, and generate the same code for it.dragontamer5788 wrote: ↑Mon Dec 09, 2019 11:25 pm Comment: For some reason, I couldn't grok your code in the first pass. My brain understands the following more:
Code: Select all
for(i=0; i<MAX; i++) { todo[n] = i; n += (Condition(i) ? 1 : 0); }
Indeed, I used the function calls only as a means to write compact pseudo-code; they were supposed to be simple code sections. BTW, all calls to Action are done in the same order as they would be in the original code. So side effects there are not dangerous per se. But Condition and Action should not have side effects on each other's behavior.
I use something similar but with different motivation. I often extract elements/pointers based on a condition into a (thread)local array for further processing.hgm wrote: ↑Mon Dec 09, 2019 10:36 pmCode: Select all
int todo[MAX]; int n=0; for(i=0; i<MAX; i++) { todo[n] = i; n += (Condition(i) != 0); } for(i=0; i<n; i++) Action(todo[i]);
hgm wrote: ↑Tue Dec 10, 2019 9:47 amCode: Select all
for(i=0; i<MAX; i++) { todo[n] = i; n += (Condition(i) ? 1 : 0); }
Code: Select all
for(i=0; i<MAX; i++) { todo[n] = i; n += !!Condition(i); }
If this simplicity can be assured, then we open up SIMD-compute capabilities. Wait, wait wait... don't run away. I'm not talking GPUs here, just pointing out that the compiler will autovectorize the loop.hgm wrote: ↑Tue Dec 10, 2019 9:47 amIndeed, I used the function calls only as a means to write compact pseudo-code; they were supposed to be simple code sections. BTW, all calls to Action are done in the same order as they would be in the original code. So side effects there are not dangerous per se. But Condition and Action should not have side effects on each other's behavior.
Code: Select all
void Action(int& x){
x = x+10;
}
...
#pragma omp simd
for(int i=0; i<n; i++) Action(todo[i]);
why? the code you posted is auto-vectorized by gcc regardless of any pragma, clang even unrolls the loop as well as mscdragontamer5788 wrote: ↑Tue Dec 10, 2019 4:05 pmGCC still needs the #pragma omp simd to see that this loop is vectorizable for some reason
Interesting. I stand corrected. I tested it earlier, but maybe I herp-derp'd and messed up my reading of the assembly earlier.mar wrote: ↑Tue Dec 10, 2019 4:34 pmwhy? the code you posted is auto-vectorized by gcc regardless of any pragma, clang even unrolls the loop as well as mscdragontamer5788 wrote: ↑Tue Dec 10, 2019 4:05 pmGCC still needs the #pragma omp simd to see that this loop is vectorizable for some reason