Hacker News Reader

Hacker News

Comment by dusted | Hacker News Reader

Full thread

dusted

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";

View on HN

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 < total_countries ? countries[cc] : "UNKNOWN";

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.

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 :)

This jives with the overall point of the article of keep it simple and readable. The semi fancy indexing caused 2 errors and the upside is negligible after the compiler gets done with it.

I think that's the best solution (the only potential optimization I can think of would be to add a padding byte after every country to force 32bit alignment which would make the offset computation faster on some architectures, although probably not on x86).

Stylistically-wise I think the best solution would be to write the array like:

    const char countries[][3] = {
        [0] = "A1",
        [1] = "A0",
    };

This way the codes are explicit when you read the code and it makes editing the array a little easier. Unfortunately gcc only warns if you set the same index twice with -Wextra, it remains silent with -Wall.

> This way the codes are explicit when you read the code

Good call. It might have caught the off-by-one mistake I made (the codes start from 1 and not 0 in the blog post). Maybe even switch to using an enum as our index instead of an int.

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.

Anyone know what the purpose of the mov edi, edi instruction there is?

Edited to add: I understand that it's a NOP, but why would the compiler emit one here?

It does nothing, so its a noop of sorts. I wonder if its a branch-delay tactic of some kind? Surely the algorithm is unchanged if it were removed.

It’s just a two byte NOP. IIRC, it’s Intel’s recommended form for one of that length. Windows uses it for hot patching,[0], but I can’t imagine that’s the reason here.

[0]: https://devblogs.microsoft.com/oldnewthing/20110921-00/?p=95...

That instruction clears upper 4 bytes of the rdi register. Note the next instruction uses rdi in the address.

edi register is the lower 4 bytes of rdi. Instructions which write these smaller pieces zero out the unused higher bytes of the destination registers. This helps with performance because eliminates data dependencies on the old values in these higher bytes.

This is not a NOP; it explicitly clears the upper 32 bits of EDI since the compiler does not know that they are zero in this situation. If you change cc from an int to size_t (long on x86-64) the compiler will generate:

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

Note that in some cases the compiler can do this automatically via lifetime analysis but not in this freestanding example.

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.

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

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.

Wow I had no idea you could use it on the LHS. TIL.

A TIL of my own: it seems not to be allowed in C.

It works if you take the address of the b and c and then dereference. I assume this works without those in C++ because of references.

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.

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.

As pointed out above, gcc ≥11 optimises it to a switch / lookup table (https://godbolt.org/z/PxvGKqGrd).

oh wow. this is really nice. was expecting some sort if gcc documentation or a blog post. got the real deal. thanks for the link

> I'm wondering how you guys would optimize that code ?

Run it on infinite multiverse, construct a mechanism to destroy the Universe every time branch predictor did not predict every single conditional correctly.

won't we need quantum computing for that first?

You don't need that.

The branch predictor can select a random branch, so it doesn't even need to actually predict anything. It should use quantum noise so that it has chance of selecting different branches in different copies of the universe. There is noting to compute, quantum or otherwise.

The bomb to destroy the universe will take care of all universes where it made wrong predictions, so that is where we should concentrate our development resources.

It has more utility than just branch prediction. Imagine the bomb going off automatically whenever there starts a war.

Any copy of the universe that starts a war is automatically eliminated and this guarantees that you, as an observer, will never observe any wars.

It reaches out it reaches out it reaches out it reaches out— One hundred and thirteen times a second.

I immediately wanted to rewrite it as an array, yep, since the countries are already indexed.

And to minimize the risk of errors such as the "Anguila" error above.

Reply on news.ycombinator.com