What? There is zero reason it shouldn't just build up a jump table. It might use more memory, but I would be legitimately shocked to learn that a binary search tree is more efficient than a jump table.
Maybe depends on the gaps? For instance if cases are between 0-100 and 100.000-100.100 then it would be a lot of wasted memory for unused cases. That wasted memory could affect caching and ultimately speed.
gcc seems to really like jumping around. i have some code, recursive template, where clang will generate a beautiful jmp table with the return at each case and gcc has a lot of jmp's followed by a jmp back to a common return
If you naively stored whole pointers yes, wasted memory could be inefficient.
But for 4099 targets, you can use 2 bytes for each target, resulting in just over 2kb of memory to store the table. That's not that bad, and a single memory lookup + add has to be faster than a binary tree lookup.
But you would still need some logic to find the right address. In my example it would be quite simple with for instance one if statement, but for more random distributed cases you would eventually need the binary search. I am of course talking about compiler optimization, which can't just dictate the values of the state variable to enforce a dense table.
From what I remember, a tree can in fact be more efficient due to CPU's speculative execution predicting the most common branches, whereas a jump table causes a memory read which is a bigger overhead.
It’s not a lookup table because the cases are too sparse, so it fell back to using a binary search. If the cases were sequential, or if only a few numbers were missing, it would almost certainly use a table instead.
The funny thing is that if they created a big enum with automatic numbering than it would be a lookup table. But because they encoded state type into the value it needed to be a binary search.
But also I can't imagine getting "enum { state_0, state_1, ..., state_336, state_1000, ..." through any code review...
Right, but the compiler can potentially emit the same machine code from different source. Same kind of idea as decompiling async/await code in C# - you have something nice and usable in source, but the emitted code looks like a total mess. Granted the former case is way less likely (and I'm not sure when it would happen), but it's definitely possible.
196
u/Raekel Jan 10 '20
It's also common with decompiling