开发者

How to avoid writing multiple versions of the same loop

Inside a large loop, I currently have a statement similar to

if (ptr == NULL || ptr->calculate() > 5) 
  {do something} 

where ptr is an object pointer set before the loop and never changed.

I would like to avoid comparing ptr to NULL in every iteration of the loop. (The current final program does that, right?) A simple solution would be to write the loop code once for (ptr == NULL) and once for (ptr != NULL). But this would increase the amount of code making it more difficult to maintain, plus it looks silly if the same 开发者_如何转开发large loop appears twice with only one or two lines changed.

What can I do? Use dynamically-valued constants maybe and hope the compiler is smart? How?

Many thanks!

EDIT by Luther Blissett. The OP wants to know if there is a better way to remove the pointer check here:

loop {
 A; 
 if (ptr==0 || ptr->calculate()>5) B;
 C;
}

than duplicating the loop as shown here:

if (ptr==0) 
loop {
 A; 
 B;
 C;
} 
else loop {
 A;
 if (ptr->calculate()>5) B;
 C;
}


I just wanted to inform you, that apparently GCC can do this requested hoisting in the optimizer. Here's a model loop (in C):

struct C
{
 int (*calculate)();
};

void sideeffect1();
void sideeffect2();
void sideeffect3();

void foo(struct C *ptr) 
{
    int i;
    for (i=0;i<1000;i++) 
    {
        sideeffect1();
        if (ptr == 0 || ptr->calculate()>5) sideeffect2(); 
        sideeffect3();
    }
}

Compiling this with gcc 4.5 and -O3 gives:

.globl foo
    .type   foo, @function
foo:
.LFB0:
    pushq   %rbp
.LCFI0:
    movq    %rdi, %rbp
    pushq   %rbx
.LCFI1:
    subq    $8, %rsp
.LCFI2:
    testq   %rdi, %rdi        # ptr==0? -> .L2, see below
    je  .L2
    movl    $1000, %ebx
    .p2align 4,,10
    .p2align 3
.L4:
    xorl    %eax, %eax
    call    sideeffect1      # sideeffect1
    xorl    %eax, %eax
    call    *0(%rbp)         # call p->calculate, no check for ptr==0
    cmpl    $5, %eax
    jle .L3
    xorl    %eax, %eax
    call    sideeffect2      # ok, call sideeffect2
.L3:
    xorl    %eax, %eax
    call    sideeffect3
    subl    $1, %ebx
    jne .L4
    addq    $8, %rsp
.LCFI3:
    xorl    %eax, %eax
    popq    %rbx
.LCFI4:
    popq    %rbp
.LCFI5:
    ret
.L2:                       # here's the loop with ptr==0
.LCFI6:
    movl    $1000, %ebx
    .p2align 4,,10
    .p2align 3
.L6:
    xorl    %eax, %eax
    call    sideeffect1    # does not try to call ptr->calculate() anymore
    xorl    %eax, %eax
    call    sideeffect2    
    xorl    %eax, %eax
    call    sideeffect3
    subl    $1, %ebx
    jne .L6
    addq    $8, %rsp
.LCFI7:
    xorl    %eax, %eax
    popq    %rbx
.LCFI8:
    popq    %rbp
.LCFI9:
    ret

And so does clang 2.7 (-O3):

foo:
.Leh_func_begin1:
    pushq   %rbp
.Llabel1:
    movq    %rsp, %rbp
.Llabel2:
    pushq   %r14
    pushq   %rbx
.Llabel3:
    testq   %rdi, %rdi        # ptr==NULL -> .LBB1_5
    je  .LBB1_5
    movq    %rdi, %rbx   
    movl    $1000, %r14d
    .align  16, 0x90
.LBB1_2:
    xorb    %al, %al          # here's the loop with the ptr->calculate check()
    callq   sideeffect1
    xorb    %al, %al
    callq   *(%rbx)     
    cmpl    $6, %eax
    jl  .LBB1_4
    xorb    %al, %al
    callq   sideeffect2
.LBB1_4:
    xorb    %al, %al
    callq   sideeffect3
    decl    %r14d
    jne .LBB1_2
    jmp .LBB1_7
.LBB1_5:
    movl    $1000, %r14d      
    .align  16, 0x90
.LBB1_6:
    xorb    %al, %al        # and here's the loop for the ptr==NULL case
    callq   sideeffect1
    xorb    %al, %al
    callq   sideeffect2
    xorb    %al, %al
    callq   sideeffect3
    decl    %r14d
    jne .LBB1_6
.LBB1_7:
    popq    %rbx
    popq    %r14
    popq    %rbp
    ret


In C++, although completely overkill you can put the loop in a function and use a template. This will generate twice the body of the function, but eliminate the extra check which will be optimized out. While I certainly don't recommend it, here is the code:

template<bool ptr_is_null>
void loop() {
    for(int i = x; i != y; ++i) {
       /**/
       if(ptr_is_null || ptr->calculate() > 5) {
          /**/
       }
       /**/
    }
}

You call it with:

if (ptr==NULL) loop<true>(); else loop<false>();

You are better off without this "optimization", the compiler will probably do the RightThing(TM) for you.


Why do you want to avoid comparing to NULL?

Creating a variant for each of the NULL and non-NULL cases just gives you almost twice as much code to write, test and more importantly maintain.


A 'large loop' smells like an opportunity to refactor the loop into separate functions, in order to make the code easier to maintain. Then you can easily have two variants of the loop, one for ptr == null and one for ptr != null, calling different functions, with just a rough similarity in the overall structure of the loop.


Since

ptr is an object pointer set before the loop and never changed

can't you just check if it is null before the loop and not check again... since you don't change it.


If it is not valid for your pointer to be NULL, you could use a reference instead.

If it is valid for your pointer to be NULL, but if so then you skip all processing, then you could either wrap your code with one check at the beginning, or return early from your function:

if (ptr != NULL)
{
  // your function
}

or

if (ptr == NULL) { return; }

If it is valid for your pointer to be NULL, but only some processing is skipped, then keep it like it is.


if (ptr == NULL || ptr->calculate() > 5) 
  {do something} 

I would simply think in terms of what is done if the condition is true.

If "do something" is really the exact same stuff for (ptr == NULL) or (ptr->calculate() > 5), then I hardly see a reason to split up anything.

If "do something" contains particular cases for either condition, then I would consider to refactor into separate loops to get rid of extra special case checking. Depends on the special cases involved.

Eliminating code duplication is good up to a point. You should not care too much about optimizing until your program does what it should do and until performance becomes a problem.

[...] Premature optimization is the root of all evil

http://en.wikipedia.org/wiki/Program_optimization

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜