tags:

views:

96

answers:

5
wraparound_counter & operator ++() {
    m_count = (m_count + 1) % upper_limit;
    /*if (upper == m_count)
        m_count = lower;
    ++m_count;*/
    return *this;
}

It is my understanding that on some systems using the remainder operator trick will be faster, but on others the conditional will be faster. Is there any way to figure out which will be faster at compile-time (or run-time)?

+1  A: 

run it million times in a loop?

Nice and practical. You could mention pitfalls such as optimizations etc.
Matt Joiner
yeah to avoid distortion due to compiler optimalization, you could trymaking the loop around a bigger part of the program.
+1  A: 

You'll need to benchmark it.

Conditionals can be expensive because of branch misprediction.

On the other had, division is more expensive than simple comparison on many processors.

It could go either way based on the platform you are running on, what kind of a loop it is running in, how big upper limit is, what optimizations your compiler is performing etc. etc.

mikera
+2  A: 

Unless you need your program to be cross-compilable, you could include a benchmark test as part of your build process. Depending on the results you could select a specific implementation and continue compiling your application.

sellibitze
Yes. Measuring > guessing
Brian S
+2  A: 

For most platforms, you can assume that the conditional will be faster. This is because most modern architecture where branch mispredictions are expensive have some form of conditional move instruction, which the compiler will utilize to perform the requested check & assignment. For example, my gcc translates this:

n++; if (n==1234) n=0;

into this for x86_64 (and x86):

    addl    $1, %esi  ; %esi=n
    cmpl    $1234, %esi
    cmove   %edx, %esi ; %edx contains 0

(cmove is available since PentiumPro.)

This comes out for ARM-thumb:

    add     r3, r3, #1
    cmp     r3, r1
    moveq   r3, #0 ; <- conditional move

All ARMs have conditional execution.

And so. To wrap it up: You'd need an architecture with

  • Very fast division/modulo
  • Expensive branch mispredictions
  • no conditional move

to end up with the modulo trick as being the fastest. *If there is such an architecture, then please tell me about it. I'm always interested in such things.

Luther Blissett
IIRC SPARCv9 and PowerPC/POWER do not have conditional moves.
Dummy00001
+1  A: 

Technically it is not possible to determine which is faster without doing them both. In terms of the code being called to do the work, by the time you need to execute one of the options, it's too late. You could have a routine that benchmarks two sample routines during application initialization stage and then sets a flag. But that introduces a whole new test which adds overhead for each target call. It boils down to:

  1. specialized code to select appropriate routine at build time
  2. run-time benchmarking (increases overhead)
  3. targeting your platform and studying the instruction set implementation details
  4. let the compiler do all this work for you

Unless you're building an embedded system or have very specific performance tuning requirements, #4 is your best bet.

Kelly French