Alternatives to if/else jump conditions

[Nusa]

Code: [Select]

uint16_t next_output_current[8]={0x0403,0x0408,0x0409,0x040C,0x0400,0x0400,0x0400,0x0400};

ad7124_regs[AD7124_IOCon1].value=next_output_current[sample & 0x07];

Also, it will be faster if, instead of using "ad7124_regs[AD7124_IOCon1]" you create a variable holding a single element of it. I think it might be possible to simplify it further if we knew what the elements of "ad7124_regs" look like.

https://github.com/analogdevicesinc/no-OS/blob/master/drivers/ad7124/AD7124.h

AD7124_IOCon1 is a constant declared in an enum statement, so it'll be evaluated at compile time. No speed advantage to making it look different.

[NorthGuy]

https://github.com/analogdevicesinc/no-OS/blob/master/drivers/ad7124/AD7124.h

AD7124_IOCon1 is a constant declared in an enum statement, so it'll be evaluated at compile time. No speed advantage to making it look different.

This is true. Besides, even if it wasn't, the function being called does so much stuff that saving few cycles while calling it simply wouldn't matter.

[sokoloff]

I would also reject the number '5'.

I agree that magical numbers are a no go.
With a for statement or simple iteration i personally feel  it is a grey area but better in this case would be to define the arraysize with a #define and use the same define in the if statement. At least it is clear that hey belong together.

At a prior company, we had a fairly hopeless programmer. At one code review, we suggested that he not use a magic constant, but should rather make a #define and use that instead.

His code came back, and I kid you not at all, with this:

Code: [Select]

#define SEVENTEEN 17
and dutifully used SEVENTEEN in the subsequent comparisons. 

[John Coloccia]

I would also reject the number '5'.

I agree that magical numbers are a no go.
With a for statement or simple iteration i personally feel  it is a grey area but better in this case would be to define the arraysize with a #define and use the same define in the if statement. At least it is clear that hey belong together.

At a prior company, we had a fairly hopeless programmer. At one code review, we suggested that he not use a magic constant, but should rather make a #define and use that instead.

His code came back, and I kid you not at all, with this:

Code: [Select]

#define SEVENTEEN 17
and dutifully used SEVENTEEN in the subsequent comparisons. 

Ah...one of the gifted engineers that can write FORTRAN in any language.

[NorthGuy]

Ah...one of the gifted engineers that can write FORTRAN in any language.

Code: [Select]


#define NUMBER_OF_CHANNELS 5
#define CURRENT_ARRAY_SIZE 8
#define CURRENT_ARRAY_MASK (CURRENT_ARRAY_SIZE-1)

#define CURRENT_FOR_CHANNEL_0 0x400
#define CURRENT_FOR_CHANNEL_1 0x403
#define CURRENT_FOR_CHANNEL_2 0x408
#define CURRENT_FOR_CHANNEL_3 0x409
#define CURRENT_FOR_CHANNEL_4 0x40C
#define CURRENT_FOR_UNKNOWN_CHANNEL (CURRENT_FOR_CHANNEL_0)

uint16_t next_output_current[CURRENT_ARRAY_SIZE]= {
  CURRENT_FOR_CHANNEL_1,
  CURRENT_FOR_CHANNEL_2,
  CURRENT_FOR_CHANNEL_3,
  CURRENT_FOR_CHANNEL_4,
  CURRENT_FOR_CHANNEL_0,
  CURRENT_FOR_UNKNOWN_CHANNEL,
  CURRENT_FOR_UNKNOWN_CHANNEL,
  CURRENT_FOR_UNKNOWN_CHANNEL
};

ad7124_regs[AD7124_IOCon1].value=next_output_current[sample & CURRENT_ARRAY_MASK];

Better?

[John Coloccia]

Ah...one of the gifted engineers that can write FORTRAN in any language.

Code: [Select]


#define NUMBER_OF_CHANNELS 5
#define CURRENT_ARRAY_SIZE 8
#define CURRENT_ARRAY_MASK (CURRENT_ARRAY_SIZE-1)

#define CURRENT_FOR_CHANNEL_0 0x400
#define CURRENT_FOR_CHANNEL_1 0x403
#define CURRENT_FOR_CHANNEL_2 0x408
#define CURRENT_FOR_CHANNEL_3 0x409
#define CURRENT_FOR_CHANNEL_4 0x40C
#define CURRENT_FOR_UNKNOWN_CHANNEL (CURRENT_FOR_CHANNEL_0)

uint16_t next_output_current[CURRENT_ARRAY_SIZE]= {
  CURRENT_FOR_CHANNEL_1,
  CURRENT_FOR_CHANNEL_2,
  CURRENT_FOR_CHANNEL_3,
  CURRENT_FOR_CHANNEL_4,
  CURRENT_FOR_CHANNEL_0,
  CURRENT_FOR_UNKNOWN_CHANNEL,
  CURRENT_FOR_UNKNOWN_CHANNEL,
  CURRENT_FOR_UNKNOWN_CHANNEL
};

ad7124_regs[AD7124_IOCon1].value=next_output_current[sample & CURRENT_ARRAY_MASK];

Better?

Actually, if you do it like that you need to be very careful how you set your current array size or the mask will fail.  Honestly, I'd be happy with

Code: [Select]

uint16_t channel[] = { 0x400, 0x403, 0x408, 0x409, 0x40C };
#define NUM_CHANNELS (sizeof(channel)/sizeof(channel[0]))
...
chnum = (sample & 0xF) + 1;
chnum %= NUM_CHANNELS;


I'm really not big on #defining everything, and obfuscating the world. In fact, in our new embedded coding standards I've even eliminated typedefs nearly altogether, after seeing the mess that less than careful typedefs and inconsistent usage can do on a project we just inherited.  After thinking about it for a minute, it became clear that the easiest way to prevent us from ever doing the same thing is to just simply eliminate the damn things.

Code: [Select]

enum power_states curr_state;

will never make you wonder just what the heck curr_state actually is.

[NorthGuy]

Actually, if you do it like that you need to be very careful how you set your current array size or the mask will fail.  Honestly, I'd be happy with

Code: [Select]

uint16_t channel[] = { 0x400, 0x403, 0x408, 0x409, 0x40C };
#define NUM_CHANNELS (sizeof(channel)/sizeof(channel[0]))
...
chnum = (sample & 0xF) + 1;
chnum %= NUM_CHANNELS;



Very tidy.

A single extra division certainly won't hurt when you call a function which calculates CRC and communicates through SPI.

I wouldn't use the division myself, but I wouldn't have such wasteful functions neither.

[sokoloff]

Both operands of the division are known at compile time. Most compilers will optimize away the division and just place a constant. (Not in the define per-se, but in the usage of the define.)

Code: [Select]

#include <iostream>

using namespace std;

int array[45];
int a = 0;
#define a_l sizeof(array)/sizeof(array[0])

int main()
{
  cout << "a_l = " << a_l << endl;

  return a_l;
}


Code: [Select]

0000000000400880 <main>:
  400880: 55                    push   rbp
  400881: 48 89 e5              mov    rbp,rsp
  400884: 53                    push   rbx
  400885: 48 83 ec 08          sub    rsp,0x8
  400889: bb 2d 00 00 00        mov    ebx,0x2d
  40088e: be b0 09 40 00        mov    esi,0x4009b0
  400893: bf e0 0d 60 00        mov    edi,0x600de0
  400898: e8 b3 fe ff ff        call   400750 <std::basic_ostream<char, std::char_traits<char> >& std::operator<< <std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*)@plt>
  40089d: 48 89 de              mov    rsi,rbx
  4008a0: 48 89 c7              mov    rdi,rax
  4008a3: e8 b8 fe ff ff        call   400760 <std::ostream::operator<<(unsigned long)@plt>
  4008a8: be 80 07 40 00        mov    esi,0x400780
  4008ad: 48 89 c7              mov    rdi,rax
  4008b0: e8 bb fe ff ff        call   400770 <std::ostream::operator<<(std::ostream& (*)(std::ostream&))@plt>
  4008b5: b8 2d 00 00 00        mov    eax,0x2d
  4008ba: 48 83 c4 08          add    rsp,0x8
  4008be: 5b                    pop    rbx
  4008bf: 5d                    pop    rbp
  4008c0: c3                    ret   

45 is 0x2d. You'll see that is directly loaded into ebx prior to the call to cout the unsigned long and into eax prior to returning from main. There is no division happening at runtime.

[sokoloff]

That was with stock g++, no options passed to the compiler and then objdump to disassemble.

Code: [Select]

[ec2-user@]$ g++ --version
g++ (GCC) 4.8.3 20140911 (Red Hat 4.8.3-9)

[ec2-user@]$ objdump -drwC -Mintel  ./a.out

I'd wager most compilers will do constant folding like this.

[John Coloccia]

Yeah, it actually never even crossed my mind that the sizeof/sizeof might be implemented as a division. I just assumed it would become a constant. I guess some compiler might actually do a division, but I just assume that things like this become constants.

[NorthGuy]

Both operands of the division are known at compile time. Most compilers will optimize away the division and just place a constant. (Not in the define per-se, but in the usage of the define.)

The division happens at this line:

Code: [Select]

chnum %= NUM_CHANNELS;
<edit>To clarify: "chnum" is being divided by "NUM_CHANNELS"</edit>

Even though NUM_CHANNELS is known at compile time, I don't think the compiler will use this to eliminate the division.

[sokoloff]

Ah, your objection is to the modulus, not the sizeof/sizeof division. That's a fair point in a performance critical application.

[John Coloccia]

Ah, your objection is to the modulus, not the sizeof/sizeof division. That's a fair point in a performance critical application.

I suspect that implementing it as a division is generally not optimal and many compilers will implemented more cleverly depending on the specific platform.

[Mechatrommer]

Have a 'next' array with values of 1,2,3,4 and 0.
Update chnum  from that. (E.g chnum = next[chnum]; )

+1, if you really anal of not using if... but the drawback to this is its requires memory. and i bet fetching values from this memory (assign pointer into register and read memory from assigned register) will take more time, but the good thing is the code will run at uniform clock cycle at each chnum value. "if" statement if optimized correctly will take only 2-3 cycles to run, the shortest path you can get, but the drawback it will take more cycle when it reaches the boundary, hence not uniform execution resulting in jitter (depending on what you want), but since you are doing this in C, i dont see much point in uniform code execution...

[Nusa]

Ah, your objection is to the modulus, not the sizeof/sizeof division. That's a fair point in a performance critical application.

I suspect that implementing it as a division is generally not optimal and many compilers will implemented more cleverly depending on the specific platform.

I went and tried this code snippet on https://godbolt.org/, which is a fun little tool for cases like this:

int test(int num, int div) {
    num = num % div;
    num = 10 % div;
    num = num % 10;
    return num;
}

The results varied depending with compiler selection, but x86-64 gcc 7.1 used division for the first two cases, but switched to a customized implementation using multiply for the 3rd case when the divisor is a constant. I think I understand what it's doing, but it's more fun if you look at it yourself.

[sokoloff]

I went and tried this code snippet on https://godbolt.org/, which is a fun little tool for cases like this:

Thanks for this tool link! That would have saved me several hours over the last couple years...

[NorthGuy]

The results varied depending with compiler selection, but x86-64 gcc 7.1 used division for the first two cases, but switched to a customized implementation using multiply for the 3rd case when the divisor is a constant. I think I understand what it's doing, but it's more fun if you look at it yourself.

For "x%5" it's doing division through multiplication: x/5 = x*1717986919/0x200000000;

Division by 0x200000000 is easily implemented through shifts.

It's amazing that this still works faster on the CPU with hardware division. However, I think for the case where x is from 0 to 15, Intel's hardware division  with early termination could produce faster results than multiplication.

[orin]

The results varied depending with compiler selection, but x86-64 gcc 7.1 used division for the first two cases, but switched to a customized implementation using multiply for the 3rd case when the divisor is a constant. I think I understand what it's doing, but it's more fun if you look at it yourself.

For "x%5" it's doing division through multiplication: x/5 = x*1717986919/0x200000000;

Division by 0x200000000 is easily implemented through shifts.

It's amazing that this still works faster on the CPU with hardware division. However, I think for the case where x is from 0 to 15, Intel's hardware division  with early termination could produce faster results than multiplication.

After the division by multiplication, then what does it do?  (x - result * 5) I'd guess to get the remainder.  For this problem, I can't imagine that being faster than: if ( ++x == 5 ) x = 0;

If you are worried about jitter, then if ( ++x == 5 ) x = 0; else nop()*; where nop() is whatever forces your compiler to insert a no-operation opcode. *one or more depending on how long x = 0; takes.

Another point on using the % operator and speed.  On a highly pipelined processor, if the next instruction or so uses the result, it may stall the pipeline until the result is ready - negating the gains from pipelining and resulting in slower execution.

Did the OP even tell us what CPU this is running on?

FWIW, on a PIC, this sequence can be done in constant time using a test/skip instruction - something like (there are many variations):

Code: [Select]

    ; Bank switching code here if necessary
    INCF chnum, W
    MOVWF chnum
    XORLW 5              ; ++chnum == 5 ?  If so, the Z status bit will be set
    BTFSC STATUS,Z
    MOVWF chnum     ; only executes if the Z flag is set and conveniently, W is zero
                               ; if Z is clear, in effect, a NOP instruction is executed instead

If you want to make the test >= 5, then you'd use SUBLW* instead of XORLW and tear your hair out working out which status flag to test... but it would be the same basic instruction sequence.

* very basic PICs don't have this instruction, but that can be worked around.

[Kalvin]

Without if's or divs. Channels 5 - 7 are used for padding the unused entries. Note for the Arduino: The const tables are not in ROM address spscae:

Code: [Select]

#include <stdint.h>

typedef struct
{
    uint16_t data; // output data
    uint8_t  next; // next channel index
}
ChannelEntry_t;

const ChannelEntry_t channel[] = {
    {0x400, 1}, /* 0 */
    {0x403, 2}, /* 1 */
    {0x408, 3}, /* 2 */
    {0x409, 4}, /* 3 */
    {0x40C, 0}, /* 4 */
    {0x400, 0}, /* 5, unused */
    {0x400, 0}, /* 6, unused */
    {0x400, 0}  /* 7, unused */
};

extern void do_something(uint16_t dataval);

uint8_t chnum = 0;

int main ()
{
    while (1)
    {
        uint16_t dataval = channel[chnum & 0x07].data;
        chnum = channel[chnum & 0x07].next;

        do_something(dataval);
    }

    return 0;
}

Arduino AVR C++ compiler output disassembly:

Code: [Select]

Disassembly of section .text.startup.main:

00000000 <main>:
   0: 80 91 00 00 lds r24, 0x0000
   4: 87 70        andi r24, 0x07 ; 7
   6: 90 e0        ldi r25, 0x00 ; 0
   8: fc 01        movw r30, r24
   a: ee 0f        add r30, r30
   c: ff 1f        adc r31, r31
   e: e8 0f        add r30, r24
  10: f9 1f        adc r31, r25
  12: e0 50        subi r30, 0x00 ; 0
  14: f0 40        sbci r31, 0x00 ; 0
  16: 80 81        ld r24, Z
  18: 91 81        ldd r25, Z+1 ; 0x01
  1a: 22 81        ldd r18, Z+2 ; 0x02
  1c: 20 93 00 00 sts 0x0000, r18
  20: 0e 94 00 00 call 0 ; 0x0 <main>
  24: 00 c0        rjmp .+0      ; 0x26 <__zero_reg__+0x25>

Same thing using pointers:

Code: [Select]

#include <stdint.h>

struct ChannelEntry_t;

typedef struct ChannelEntry_t
{
    uint16_t data;                // output data
    const ChannelEntry_t * next;  // next channel entry
}
ChannelEntry_t;

const ChannelEntry_t channel[] = {
    {0x400, &channel[1]}, /* 0 */
    {0x403, &channel[2]}, /* 1 */
    {0x408, &channel[3]}, /* 2 */
    {0x409, &channel[4]}, /* 3 */
    {0x40C, &channel[0]}  /* 4 */
};

extern void do_something(uint16_t dataval);

const ChannelEntry_t * chdata = &channel[0];

int main ()
{
    while (1)
    {
        uint16_t dataval = chdata->data;
        chdata = chdata->next;

        do_something(dataval);
    }

    return 0;
}

and the disaasembly:

Code: [Select]

Disassembly of section .text.startup.main:

00000000 <main>:
   0: e0 91 00 00 lds r30, 0x0000
   4: f0 91 00 00 lds r31, 0x0000
   8: 80 81        ld r24, Z
   a: 91 81        ldd r25, Z+1 ; 0x01
   c: 22 81        ldd r18, Z+2 ; 0x02
   e: 33 81        ldd r19, Z+3 ; 0x03
  10: 30 93 00 00 sts 0x0000, r19
  14: 20 93 00 00 sts 0x0000, r18
  18: 0e 94 00 00 call 0 ; 0x0 <main>
  1c: 00 c0        rjmp .+0      ; 0x1e <__zero_reg__+0x1d>

The pointer implementation is pretty efficient and straight forward, and it doesn't require if's nor modulus.

[Kalvin]

Same thing using Ubuntu GCC-compiler with -O1 option:

Code: [Select]

main:
.LFB0:
.cfi_startproc
subq $8, %rsp
.cfi_def_cfa_offset 16
.L2:
movzbl chnum(%rip), %eax
andl $7, %eax
movzwl channel(,%rax,4), %edi
movzbl channel+2(,%rax,4), %eax
movb %al, chnum(%rip)
movzwl %di, %edi
call do_something
jmp .L2
.cfi_endproc

Code: [Select]

#include <stdint.h>

struct ChannelEntry_t;

struct ChannelEntry_t
{
    uint16_t data;                       // output data
    const struct ChannelEntry_t * next;  // next channel entry
};

const struct ChannelEntry_t channel[] = {
    {0x400, &channel[1]}, /* 0 */
    {0x403, &channel[2]}, /* 1 */
    {0x408, &channel[3]}, /* 2 */
    {0x409, &channel[4]}, /* 3 */
    {0x40C, &channel[0]}  /* 4 */
};

extern void do_something(uint16_t dataval);

const struct ChannelEntry_t const * chdata = &channel[0];

int main ()
{
    while (1)
    {
        uint16_t dataval = chdata->data;
        chdata = chdata->next;

        do_something(dataval);
    }

    return 0;
}

Code: [Select]

main:
.LFB0:
.cfi_startproc
subq $8, %rsp
.cfi_def_cfa_offset 16
.L2:
movq chdata(%rip), %rax
movzwl (%rax), %edi
movq 8(%rax), %rax
movq %rax, chdata(%rip)
movzwl %di, %edi
call do_something
jmp .L2
.cfi_endproc


[hamster_nz]

Unknown to me till jsut now, you use x64, and you have optimizations on, you do get jumpless for the "if ... then reset" coding:

Code: [Select]

  while(1) {
     a++;
     if(a > 4)
       a = 0;
     printf("%i\n",a);
  }

The loop becomes:

Code: [Select]

.L3:
        addl    $1, %ebx
        movl    $.LC0, %esi
        movl    $1, %edi
        cmpl    $5, %ebx
        cmovge  %ebp, %ebx
        xorl    %eax, %eax
        movl    %ebx, %edx
        call    __printf_chk
        jmp     .L3

cmovge is "conditional move if greater or equal", an x64 opcode.