pipeline stall optimize :: no branch programing

Question

I'm studied about pipeline stall on branch predict miss so I make some codes of mine avoid stalling and be faster. But I can't know if this optimization really matters or makes things worse. I don't know muschabout asm, or cpus.

I add some disassembly codes of mine. So guys, am I optimizing the program correctly? Is it faster than before? Can you tell me If I optimize codes like this, what should be a problem?

// before
switch (i - '0')
{
    case 0: a.f1(); break;
    case 1: a.f2(); break;
    case 2: a.f3(); break;
    case 3: a.f4(); break;
}

///asm with 12 cases
switch (i - '0')
00007FF620461434  movsx       ecx,byte ptr [rax]  
00007FF620461437  add         ecx,0FFFFFFD0h            
00007FF62046143A  cmp         ecx,0Bh                   
00007FF62046143D  ja          main+185h (07FF6204614D5h)    
00007FF620461443  movsxd      rcx,ecx                   
00007FF620461446  mov         edx,dword ptr [r11+rcx*4+1614h]       
00007FF62046144E  add         rdx,r11                   
00007FF620461451  jmp         rdx                   


// asm with 4 cases
    64:             switch (i - '0')
00007FF6927413A5  movsx       eax,byte ptr [rdx]  
00007FF6927413A8  sub         eax,30h  
00007FF6927413AB  je          main+110h (07FF6927413E0h)  
00007FF6927413AD  sub         eax,1  
00007FF6927413B0  je          main+104h (07FF6927413D4h)  
00007FF6927413B2  sub         eax,1  
00007FF6927413B5  je          main+0F8h (07FF6927413C8h)  
00007FF6927413B7  cmp         eax,1  
00007FF6927413BA  jne         main+11Ah (07FF6927413EAh)  
    69:             case 3: a.f4(); break;
00007FF6927413BC  lea         rcx,[a]  
00007FF6927413C1  call        OBJ::f4 (07FF6927412C0h)  
00007FF6927413C6  jmp         main+11Ah (07FF6927413EAh)  
    68:             case 2: a.f3(); break;
00007FF6927413C8  lea         rcx,[a]  
00007FF6927413CD  call        OBJ::f3 (07FF6927412B0h)  
00007FF6927413D2  jmp         main+11Ah (07FF6927413EAh)  
    67:             case 1: a.f2(); break;
00007FF6927413D4  lea         rcx,[a]  
00007FF6927413D9  call        OBJ::f2 (07FF6927412A0h)  
00007FF6927413DE  jmp         main+11Ah (07FF6927413EAh)  
    65:             {
    66:             case 0: a.f1(); break;
00007FF6927413E0  lea         rcx,[a]  
00007FF6927413E5  call        OBJ::f1 (07FF692741290h)

//after
static decltype(&OBJ::f1) func[4] = { &OBJ::f1, &OBJ::f2, &OBJ::f3, &OBJ::f4 };
(a.*func[i - '0'])();


// asm
    61:             static decltype(&OBJ::f1) func[4] = { &OBJ::f1, &OBJ::f2, &OBJ::f3, &OBJ::f4 };
    62:             (a.*func[i - '0'])();
00007FF71D7213B9  movsx       rax,byte ptr [rbx]  
00007FF71D7213BD  lea         rcx,[a]  
00007FF71D7213C2  call        qword ptr [r13+rax*8-180h]

I'm using MSVC. this code is in main-loop. below is my test code, input is

12031023012031020310230120301203012031020310231023012030123012030120301230203323030200201023022210100123002010100120310230120310203102301203012030120310203102310230120301230120301203012302033230302002010230222101001230020101001203102301203102031023012030120301203102031023102301203012301203012030123020332303020020102302221010012300201010012031023012031020310230120301203012031020310231023012030123012030120301230203323030200201023022210100123002010100120310230120310203102301203012030120310203102310230120301230120301203012302033230302002010230222101001230020101001203102301203102031023012030120301203102031023102301203012301203012030123020332303020020102302221010012300201010012031023012031020310230120301203012031020310231023012030123012030120301230203323030200201023022210100123002010100120310230120310203102301203012030120310203102310230120301230120301203012302033230302002010230222101001230020101001203102301203102031023012030120301203102031023102301203012301203012030123020332303020020102302221010012300201010012031023012031020310230120301203012031020310231023012030123012030120301230203323030200201023022210100123002010100120310230120310203102301203012030120310203102310230120301230120301203012302033230302002010230222101001230020101001203102301203102031023012030120301203102031023102301203012301203012030123020332303020020102302221010012300201010012031023012031020310230120301203012031020310231023012030123012030120301230203323030200201023022210100123002010100120310230120310203102301203012030120310203102310230120301230120301203012302033230302002010230222101001230020101001203102301203102031023012030120301203102031023102301203012301203012030123020332303020020102302221010012300201010012031023012031020310230120301203012031020310231023012030123012030120301230203323030200201023022210100123002010100120310230120310203102301203012030120310203102310230120301230120301203012302033230302002010230222101001230020101001203102301203102031023012030120301203102031023102301203012301203012030123020332303020020102302221010012300201010012031023012031020310230120301203012031020310231023012030123012030120301230203323030200201023022210100123002010100120310230120310203102301203012030120310203102310230120301230120301203012302033230302002010230222101001230020101001203102301203102031023012030120301203102031023102301203012301203012030123020332303020020102302221010012300201010012031023012031020310230120301203012031020310231023012030123012030120301230203323030200201023022210100123002010100120310230120310203102301203012030120310203102310230120301230120301203012302033230302002010230222101001230020101001203102301203102031023012030120301203102031023102301203012301203012030123020332303020020102302221010012300201010012031023012031020310230120301203012031020310231023012030123012030120301230203323030200201023022210100123002010100120310230120310203102301203012030120310203102310230120301230120301203012302033230302002010230222101001230020101001203102301203102031023012030120301203102031023102301203012301203012030123020332303020020102302221010012300201010012031023012031020310230120301203012031020310231023012030123012030120301230203323030200201023022210100123002010100120310230120310203102301203012030120310203102310230120301230120301203012302033230302002010230222101001230020101001203102301203102031023012030120301203102031023102301203012301203012030123020332303020020102302221010012300201010012031023012031020310230120301203012031020310231023012030123012030120301230203323030200201023022210100123002010100120310230120310203102301203012030120310203102310230120301230120301203012302033230302002010230222101001230020101001203102301203102031023012030120301203102031023102301203012301203012030123020332303020020102302221010012300201010012031023012031020310230120301203012031020310231023012030123012030120301230203323030200201023022210100123002010100120310230120310203102301203012030120310203102310230120301230120301203012302033230302002010230222101001230020101001203102301203102031023012030120301203102031023102301203012301203012030123020332303020020102302221010012300201010012031023012031020310230120301203012031020310231023012030123012030120301230203323030200201023022210100123002010100120310230120310203102301203012030120310203102310230120301230120301203012302033230302002010230222101001230020101001203102301203102031023012030120301203102031023102301203012301203012030123020332303020020102302221010012300201010012031023012031020310230120301203012031020310231023012030123012030120301230203323030200201023022210100123002010100120310230120310203102301203012030120310203102310230120301230120301203012302033230302002010230222101001230020101001203102301203102031023012030120301203102031023102301203012301203012030123020332303020020102302221010012300201010012031023012031020310230120301203012031020310231023012030123012030120301230203323030200201023022210100123002010100120310230120310203102301203012030120310203102310230120301230120301203012302033230302002010230222101001230020101001203102301203102031023012030120301203102031023102301203012301203012030123020332303020020102302221010012300201010012031023012031020310230120301203012031020310231023012030123012030120301230203323030200201023022210100123002010100120310230120310203102301203012030120310203102310230120301230120301203012302033230302002010230222101001230020101001203102301203102031023012030120301203102031023102301203012301203012030123020332303020020102302221010012300201010012031023012031020310230120301203012031020310231023012030123012030120301230203323030200201023022210100123002010100120310230120310203102301203012030120310203102310230120301230120301203012302033230302002010230222101001230020101001203102301203102031023012030120301203102031023102301203012301203012030123020332303020020102302221010012300201010012031023012031020310230120301203012031020310231023012030123012030120301230203323030200201023022210100123002010100120310230120310203102301203012030120310203102310230120301230120301203012302033230302002010230222101001230020101001203102301203102031023012030120301203102031023102301203012301203012030123020332303020020102302221010012300201010012031023012031020310230120301203012031020310231023012030123012030120301230203323030200201023022210100123002010100120310230120310203102301203012030120310203102310230120301230120301203012302033230302002010230222101001230020101001203102301203102031023012030120301203102031023102301203012301203012030123020332303020020102302221010012300201010012031023012031020310230120301203012031020310231023012030123012030120301230203323030200201023022210100123002010100120310230120310203102301203012030120310203102310230120301230120301203012302033230302002010230222101001230020101001203102301203102031023012030120301203102031023102301203012301203012030123020332303020020102302221010012300201010012031023012031020310230120301203012031020310231023012030123012030120301230203323030200201023022210100123002010100120310230120310203102301203012030120310203102310230120301230120301203012302033230302002010230222101001230020101001203102301203102031023012030120301203102031023102301203012301203012030123020332303020020102302221010012300201010012031023012031020310230120301203012031020310231023012030123012030120301230203323030200201023022210100123002010100120310230120310203102301203012030120310203102310230120301230120301203012302033230302002010230222101001230020101001203102301203102031023012030120301203102031023102301203012301203012030123020332303020020102302221010012300201010012031023012031020310230120301203012031020310231023012030123012030120301230203323030200201023022210100123002010100120310230120310203102301203012030120310203102310230120301230120301203012302033230302002010230222101001230020101001203102301203102031023012030120301203102031023102301203012301203012030123020332303020020102302221010012300201010012031023012031020310230120301203012031020310231023012030123012030120301230203323030200201023022210100123002010100120310230120310203102301203012030120310203102310230120301230120301203012302033230302002010230222101001230020101001203102301203102031023012030120301203102031023102301203012301203012030123020332303020020102302221010012300201010012031023012031020310230120301203012031020310231023012030123012030120301230203323030200201023022210100123002010100120310230120310203102301203012030120310203102310230120301230120301203012302033230302002010230222101001230020101001203102301203102031023012030120301203102031023102301203012301203012030123020332303020020102302221010012300201010012031023012031020310230120301203012031020310231023012030123012030120301230203323030200201023022210100123002010100120310230120310203102301203012030120310203102310230120301230120301203012302033230302002010230222101001230020101001203102301203102031023012030120301203102031023102301203012301203012030123020332303020020102302221010012300201010012031023012031020310230120301203012031020310231023012030123012030120301230203323030200201023022210100123002010100120310230120310203102301203012030120310203102310230120301230120301203012302033230302002010230222101001230020101001203102301203102031023012030120301203102031023102301203012301203012030123020332303020020102302221010012300201010012031023012031020310230120301203012031020310231023012030123012030120301230203323030200201023022210100123002010100120310230120310203102301203012030120310203102310230120301230120301203012302033230302002010230222101001230020101001203102301203102031023012030120301203102031023102301203012301203012030123020332303020020102302221010012300201010012031023012031020310230120301203012031020310231023012030123012030120301230203323030200201023022210100123002010100

#include <iostream>
#include <chrono>

using clk = std::chrono::high_resolution_clock;
using namespace std::chrono;
using namespace std::literals::string_view_literals;

namespace timer {
    static clk::time_point StopWatch;

    inline void start() {
        StopWatch = clk::now();
    }

    inline void end(const std::string_view mess = ""sv)
    {
        auto t = clk::now();
        std::cout << mess << " : " << duration_cast<milliseconds>(t - StopWatch) << '\n';
    }
}

// controll //
#define noBranch
#define noInline
// controll //


#ifdef noInline
#define INLINE __declspec(noinline)
#else 
#define INLINE 
#endif

class OBJ {
public:
    size_t x = 0;
    INLINE void f1() {
        x += 13;
    }
    INLINE void f2() {
        x += 23;
    }
    INLINE void f3() {
        x += 18;
    }
    INLINE void f4() {
        x += 15;
    }
};

int main()
{
    size_t sum = 0;
    std::string in;
    std::cin >> in;
    timer::start();
    for (size_t q = 0; q < 1'000'000; q++) {
        for (const auto i : in) {
            OBJ a;
#ifdef noBranch
            static decltype(&OBJ::f1) func[4] = { &OBJ::f1, &OBJ::f2, &OBJ::f3, &OBJ::f4 };
            (a.*func[i - '0'])();
#else
            switch (i - '0')
            {
            case 0: a.f1(); break;
            case 1: a.f2(); break;
            case 2: a.f3(); break;
            case 3: a.f4(); break;
            }
#endif
            sum += a.x;
        }
    }
    std::cout << "sum" << sum << std::endl;
    timer::end();
}

You partially answered your own question. The applied optimization is not always better regarding the use-case. The point is we do not have enough information to really help you: the context is missing. What is `obj`? Is this code in a loop? Is the execution predictable? How big are the functions? Please provide a [MRE](https://stackoverflow.com/help/minimal-reproducible-example). — Jérôme Richard, Sep 26 '21 at 13:00
@JérômeRichard thank you for advice, In this moment, What I wanna know is the side effects of this branchless optimizations. and better way to make branchless code than my way. I tested how big func size and how much complex, so I have no more question about it. — sunkue, Sep 26 '21 at 13:36
*Branching is mandatory here* as long as the functions cannot be merged together somehow but it is hard to tell without the code of the functions. Note however that not all kind of branching are equivalent. A short jump to a predictable address next to the current address is very cheap while a long jump on an unpredictable address not yet in the cache is very expensive. — Jérôme Richard, Sep 26 '21 at 13:46
@JérômeRichard oh, that should be a reason of why this code faster than switch thanks. — sunkue, Sep 26 '21 at 13:47
@JérômeRichard I editted new asm of test code, and now I can see why this code is faster . what I did is not a branchless code, but less-branch optimized. — sunkue, Sep 26 '21 at 14:39
A chain of `sub eax,1` / `je` looks pretty silly vs. `cmp eax, 2`/`je` / `cmp eax,3`/`je` etc. Perhaps MSVC used to optimize for code-size with `dec eax`/`je`, but then some tuning option changed to `sub` (because of P4 partial-flag stuff, or Silvermont-family?) defeating that purpose? Now it's just worse for no benefit, not macro-fusing on AMD and introducing a dependency chain where there didn't need to be one. But that's just the compiler did for your original switch. A better compiler (like gcc or clang) should do better. Try it on https://godbolt.org/ compiler explorer. — Peter Cordes, Sep 26 '21 at 15:05
@PeterCordes Yeah, MSVC make switch to if-else in small case, With 12 case, asm is change, I editted it. — sunkue, Sep 26 '21 at 15:14
I think the best solution for this specific code it to unroll the loop (eg. 4 times), use 4 different accumulators (`sum`), and use a lookup table to find the increment from the `i` value. However, I guess this is just a toy program. Still, note that a very good optimizing compiler should be able to do that with the switch-based implementation. This is a good advantage for the switch-based implementation. Since the input is not fully random, another optimization could be to use jumps in each case to help the prediction unit to learn time-dependent patterns (based on the previous jumps). — Jérôme Richard, Sep 26 '21 at 20:32

score 2 · Accepted Answer · answered Sep 26 '21 at 13:23

2

Call by a pointer is also a branch, so branch mis-prediction apply here as well.

C++ pointer-to-member-function is a complex construct that is hard for the compiler to optimize.

Making truly branchless code using a lookup table would have worked, if you look up data, not code, and make no branches based on that data.

answered Sep 26 '21 at 13:23

Alex Guteniev

12,039
2
34
79

ok, call by a pointer is also branch. then this code is not a optimizing pipline stall, I have to check why my code optimized, thank you. – sunkue Sep 26 '21 at 13:40
3

@sunkue: predicting patterns in one indirect branch is a somewhat different problem from predicting a chain of 4 branches, as far as what will actually happen in the hardware. See [Branch Prediction and the Performance of Interpreters - Don’t Trust Folklore](https://hal.inria.fr/hal-01100647/document) re: modern CPUs (Intel since Haswell) with TAGE predictors that do well if there's any pattern. Also, a chain of 4 conditional branches makes the worst case 3 mispredicts before you get to the always-taken 4th (you don't have any digits > 3 for the case to fall through), vs. 1 miss for indirect – Peter Cordes Sep 26 '21 at 15:10
@PeterCordes thank your help and link. this is big fun subject to learn ! – sunkue Sep 26 '21 at 15:20
2

@sunkue: See also [Modern Microprocessors A 90-Minute Guide!](http://www.lighterra.com/papers/modernmicroprocessors/) for an excellent intro. Also links in https://stackoverflow.com/tags/x86/info for more x86 performance details, especially https://www.agner.org/optimize/ – Peter Cordes Sep 26 '21 at 15:40
@PeterCordes these sites seems golden, also you too, golden bro. thank u. – sunkue Sep 26 '21 at 16:09

pipeline stall optimize :: no branch programing

1 Answers1

Linked