Лет 7 назад я придумал как можно проверять значение int за O(1). Тогда я подумал что можно просто разделить программу на одинаковые по размеру блоки и прыгнуть на соответствующий. Мне не было известно об устройстве switch, да и ассемблер я не знал.

Уже спустя пару лет я понял, что современный switch как раз этим и занимается, но только вчера я проверил, что теория сошлась с практикой.

Виной всему послужил доклад с cppcon:

Посмотрев на switch со слайдов, я вспомнил про свою старую идею и полез на godbolt проверять.

https://godbolt.org/z/uMkkfV

Собственно, все достаточно оптимально выглядит на ассемблере. Странно только, что clang вставил команду xor rax, 128. Из-за этого ему также пришлось перелопатить таблицу значений. gcc этим заниматься не стал, а сгенерировал как раз максимально ожидаемый код.

Потом я, правда, вернулся к докладу, который оказался просто божественным. В магию goto я не поверил, но оно работает в современном gcc даже при std=c++98:

int main() {
    void* exitAddress = &&L1;
    goto* exitAddress;
    
    return 1;
L1:
    return 0;
}

Кто это придумал, и значем это нужно, по-прежнему остается загадкой.