Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Branch predictor: How many “if”s are too many?

blog.cloudflare.com

Post reply on HN
Print view View original

1–10 of 109 posts

Re: Branch predictor: How many “if”s are too many?

#4

Post by rantwasp »

dusted wrote: post #2

I'm wondering how you guys would optimize that code ? My naive approach would be something like this: const int numCountryIndicies = however many there are..; const char* countries = "A1\0A2\0..."; return (cc < numCountryIndicies)?countries[cc*2]:"UNKNOWN";

it’s probably a switch on the index (or in this case you could actually have an array and use the index).

I don’t know my compilers that well but if I had to guess I would say there is a good chance this will be optimized away by the compiler.

Re: Branch predictor: How many “if”s are too many?

#5

Post by fallingknife »

dusted wrote: post #2

I'm wondering how you guys would optimize that code ? My naive approach would be something like this: const int numCountryIndicies = however many there are..; const char* countries = "A1\0A2\0..."; return (cc < numCountryIndicies)?countries[cc*2]:"UNKNOWN";

Does a ternary actually eliminate a logic branch? I always assumed it was just high level shorthand, and would be the same in assembly as writing out the if block.

Re: Branch predictor: How many “if”s are too many?

#6

Post by throwaway744678 »

fallingknife wrote: post #5
dusted wrote: post #2

I'm wondering how you guys would optimize that code ? My naive approach would be something like this: const int numCountryIndicies = however many there are..; const char* countries = "A1\0A2\0..."; return (cc < numCountryIndicies)?countries[cc*2]:"UNKNOWN";

Does a ternary actually eliminate a logic branch? I always assumed it was just high level shorthand, and would be the same in assembly as writing out the if block.

It does not eliminate the conditional jump, it's just synctatic sugar.

Re: Branch predictor: How many “if”s are too many?

#7

Post by messe »

dusted wrote: post #2

I'm wondering how you guys would optimize that code ? My naive approach would be something like this: const int numCountryIndicies = however many there are..; const char* countries = "A1\0A2\0..."; return (cc < numCountryIndicies)?countries[cc*2]:"UNKNOWN";

You have an off-by-one error. The strings are 3 bytes long.

I'd write something similar, more or less; Probably the following, not for optimization, but more as a matter of style:

    const char countries[][3] = {
        "A1",
        "A0",
       // [...]
    };

    // [...]

    int total_countries = (int) (sizeof(countries) / sizeof(countries[0]));
    return cc
No need to hard code the length, and the cast is guaranteed to be within the bounds of an int on all platforms as long as you don't go over 2^16-1 countries.

Re: Branch predictor: How many “if”s are too many?

#8

Post by majke »

dusted wrote: post #2

I'm wondering how you guys would optimize that code ? My naive approach would be something like this: const int numCountryIndicies = however many there are..; const char* countries = "A1\0A2\0..."; return (cc < numCountryIndicies)?countries[cc*2]:"UNKNOWN";

Modern freshest gcc 11 can optimize the if's nicely https://godbolt.org/z/771foExcG

  getCountry:
        mov     eax, OFFSET FLAT:.LC0
        cmp     edi, 258
        ja      .L1
        mov     edi, edi
        mov     rax, QWORD PTR CSWTCH.1[0+rdi*8]
  .L1:
        ret

Re: Branch predictor: How many “if”s are too many?

#9

Post by throwaway744678 »

Unrelated to the actual topic, but I believe there is a copy-paste bug in the first sample:

    const char *getCountry(int cc) {
        if(cc == 1) return "A1";
        if(cc == 2) return "A2";
        if(cc == 3) return "O1";
        if(cc == 4) return "AD";
        if(cc == 5) return "AE";
        if(cc == 6) return "AF";
        if(cc == 7) return "AG";
        if(cc == 1) return "AI";
        ...
        if(cc == 252) return "YT";
        if(cc == 253) return "ZA";
        if(cc == 254) return "ZM";
        if(cc == 255) return "ZW";
        if(cc == 256) return "XK";
        if(cc == 257) return "T1";
        return "UNKNOWN";
   }
This will never return "AI" (Anguila, as it seems!)

Re: Branch predictor: How many “if”s are too many?

#10

Post by klohto »

throwaway744678 wrote: post #9

Unrelated to the actual topic, but I believe there is a copy-paste bug in the first sample: const char *getCountry(int cc) { if(cc == 1) return "A1"; if(cc == 2) return "A2"; if(cc == 3) return "O1"; if(cc == 4) return "AD"; if(cc == 5) return "AE"; if(cc == 6) return "AF"; if(cc == 7) return "AG"; if(cc == 1) return "AI"; ... if(cc == 252) return "YT"; if(cc == 253) return "ZA"; if(cc == 254) return "ZM"; if(cc == 2…

Full example doesn't have this mistake, so I would assume it's not in production :) https://godbolt.org/z/KWYEW3d9s
Post reply on HN