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

11–20 of 109 posts

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

#11

Post by qayxc »

majke wrote: post #8
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

clang does the same - I tested it back to clang 7.0.

So clang did this for a long time it seems.

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

#12

Post by PixelOfDeath »

throwaway744678 wrote: post #6
fallingknife wrote: post #5

Earlier quoted context omitted.

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.

Until after C++11, ternary was the only way to use "if then" in constexpr functions. So it has slightly more use from a C++ point of view.

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

#13

Post by TonyTrapp »

throwaway744678 wrote: post #6
fallingknife wrote: post #5

Earlier quoted context omitted.

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.

And to make it more complicated, both "regular" ifs and ternaries may not generate a branch at all, e.g. by using the CMOV (conditional move) instruction on x86. This avoids a branch but can obviously not eliminate the data dependency between the condition and a later consumer of the result.

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

#14

Post by gpderetta »

PixelOfDeath wrote: post #12
throwaway744678 wrote: post #6

Earlier quoted context omitted.

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

Until after C++11, ternary was the only way to use "if then" in constexpr functions. So it has slightly more use from a C++ point of view.

In a funny turn of events, in C++17 there is no ?: shorthand for 'constexpr if' .

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

#15

Post by MaxBarraclough »

PixelOfDeath wrote: post #12
throwaway744678 wrote: post #6

Earlier quoted context omitted.

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

Until after C++11, ternary was the only way to use "if then" in constexpr functions. So it has slightly more use from a C++ point of view.

Following that line, it's never exactly been syntactic sugar. When initializing a const local, you can use the ternary operator on the right hand side of the assignment, but you can't get the same effect using if (short of writing a new function). Similarly, C++ lets you use the ternary operator for the left hand side of an assignment, (a ? b : c) = 42; although you could use an if for this pretty easily.

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

#16

Post by dusted »

messe wrote: post #7
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 o…

Well caught! I have two off by one errors :D seems they start from 1 instead of 0, and I didn't account for the null byte :D your solution is nicer and easier to read :)

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

#17

Post by tuesdayrain »

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…

If that was javascript you could make it return "AI" with the right `valueOf` call - https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...

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

#18

Post by crazypython »

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…

Wouldn't the compiler optimize this to an array lookup?

    static const char* countries[257];
Or even:

    static const char countrycodes[514];
    return countrycodes[i * 2];

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

#19

Post by dahfizz »

crazypython wrote: post #18
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…

Wouldn't the compiler optimize this to an array lookup? static const char* countries[257]; Or even: static const char countrycodes[514]; return countrycodes[i * 2];

Doesn't look like it. Each case is a compare and jump:

https://godbolt.org/z/KWYEW3d9s

Post reply on HN