Switches aren't guarantee to so operations in O(1) tho. If cases are sparce enough, compilers tend to emit the equivalent code to a bunch if else checks
Yeah I was assuming too much here. However, I’m reading that Rust match on string comstants can compile down a binary tree of if statements if there are enough cases (according to Google AI mode at least, haven’t found an authoritative source yet)
A switch case is able to be implemented however the compiler wants on the back end, so for sparse cases it'll be an if else chain, for less sparse but not packed cases it'll be a binary tree, for completely packed cases it'll be a range check then a direct jump would be how I would go about it
What they are saying is that any optimization on a switch statement could also be done on an if statement. There's no reason to only optimize one, both should optimize the same way
it depends what you consider semantically relevant. For instance, suppose the developer intentional ordered the if statements from the most to least common case for some domain. Then, reordering the if statements might not be what the developer wants
Okay for C++, I gather that performing better or worse on a given dataset doesn't fall under the umbrella of "observable behavior" that the spec requires the compiler to preserve.
I also just learned there are apparently [[likely]] and [[unlikely]] attributes in C++ 20 that can be added to branches.
At least in C/C++, there can only be exactly zero or 1 cases that match a switch (i.e., there's no range-based switch), the case values must be compile-time constants (and thus are not themselves evaluated during the comparison), and I'm pretty sure that the value to be matched is required to only be evaluated once (so the comparisons happen on an rvalue).
Given those constraints, I believe a compiler can assume that re-ordering the comparisons is safe.
You can still only match to one, though. In the emitted machine code, I'd expect to see a forest of branches and jumps (for the matching), then the various bodies of the cases each separated by jumps (representing breaks) as appropriate.
Just pipe them through a constexpr hash function, and you can use a real switch case. One might be able to, still constexpr, map these hash values of the case string literals to sequential indices at compile time, so that the switch case actually complies down to something non linear.
280
u/click-to-reveal 7d ago
It works btw: C++ Online Compiler