| о ручной оптимизации замолвите слово |
[Oct. 9th, 2019|08:30 pm] |
как ни странно, но ручная микрооптимизация вида «заменяем деление сдвигом» всё ещё имеет смысл. да-да, у нас очень умные компиляторы, они умеют это делать сами. но только для беззнаковых целых. потому что деление отрицательного целого на два не то же самое, что арифметический сдвиг его вправо. потому что «-3/2 == -1», но «-3>>1 == -2». ой.
а теперь возьмём классический алгоритм двоичного поиска. если проигнорировать возможность переполнения (в большинстве случаев переполнение невозможно всё равно), то мы имеем операцию `m = (l+r)/2` для получения среднего элемента, и операцию `r = m-1` для одного из вариантов уменьшения диапазона. при `l: 0, r: 1` первое даёт нам `m: 0`, и тогда второе даст `r: -1`. поэтому мы не можем использовать беззнаковые целые. а раз `l` и `r` у нас знаковые, то и соптимизировать деление компилятор не сможет. скорее всего, для цпу что деление на два, что сдвиг в данном случае будут одинаково быстрые, но в принципе — это нигде не гарантируется. также деление потенциально может выкинуть исключение, а спекулятивный предсказатель может не знать, что на что мы делим в момент попытки предсказания, и пойти по самому пессимистичному пути.
в общем, поскольку мы хоть и используем целые со знаком, но точно знаем, что делить будем только положительные числа, то мы можем или сделать уродливое выражение `m = ((unsigned)l+(unsigned)r)/2u` (да, один каст и `u` не нужны, я знаю), или просто написать `m = (l+r)>>1`. лично мне нравится второй вариант, он красивей даже если поубирать из первого лишнее.
так что если вдруг увидите где-то в коде сдвиг вместо деления, не спешите кричать, что это бесполезное битоёбство, и компилятор сам всё порешает. возможно, автор как раз знал, что делает, и почему в этом случае компилятор порешать не имеет права. конечно, это всё ещё микрооптимизация, которая вряд ли будет иметь какое-то влияние на итоговый результат, но почему бы и да. и бесценный бонус: позлить хипсторов «устаревшим битоёбством», которое можно формально обосновать. |
|
|