Трюки от Крыса

Крис Касперски

Хакер, номер #095, стр. 095-136-2

xxx.ou=ROL(xxx.ou,8);

}

Откомпилировав программу и запустив ее на выполнение, мы получим следующий результат, для экономии бумаги записанный в одну строку:

* -> ** -> ** -> * -> * -> ** -> ** -> *

** * * ** ** * * **

Как видно, «бумеранг» исправно вращается против часовой стрелки (или по часовой стрелке, если используется функция ROR), но стоит нам выбрать другую схему отображения, как вместо вращения мы получим зеркальное отображение. Для этого в нашей программе достаточно изменить всего одну строку:

printf("%c%c\n%c%c\n\n",xxx.uo[0], xxx.uo[1], xxx.uo[2], xxx.uo[3]);

* -> * -> ** -> ** -> * -> * -> ** -> **

** ** * * ** ** * *

Теперь каждая последующая трансформация «бумеранга» представляет собой зеркальное отображение предыдущей!

Слегка усовершенствовав функцию циклического разворота, мы сможем трансформировать не только массивы 2x2, но и гораздо большие фигуры.

Вещественная арифметика в целых числах

Прошло то время, когда математический сопроцессор считался предметом гордости его владельца. Теперь это неотъемлемая часть процессора, однако скорость сложения/вычитания вещественных чисел заметно отстает от целых, и потому в приложениях, критичных к производительности, использование целочисленных переменных является более предпочтительным. А как быть, если нам нужна дробная часть? Очень просто. Умножаем целое число на 10*N (где N – количество знаков после запятой) и дальше работаем с ним как обычно, а на финальном этапе вычислений делим результат на 10*N.

Однако, используя этот прием, следует помнить о том, что операции умножения/деления на 10 нельзя реализовать через битовые сдвиги, а операция целочисленного деления на x86 выполняется крайней медленно и неэффективно. Намного менее эффективно, чем операция вещественного деления! Поэтому преобразование типов съедает львиную долю выигрыша от производительности и оправдывает себя лишь в случае действительно громоздких вычислений, когда временем, потраченным на преобразование, можно пренебречь. Но и в этом случае в целочисленных вычислениях не должно присутствовать инструкций деления, иначе лучше все-таки использовать вещественную арифметику и не выпендриваться.

Разумеется, под «делением» (равно как и взятием остатка) имеется в виду «деление на число, не являющееся степенью двойки». Кстати говоря, существуют формулы быстрого деления/взятия остатка на любую константу, и некоторые компиляторы (в том числе и Microsoft Visual C++) используют их, придавая производительности неожиданное подкрепление. Так что вопрос о том, какую арифметику лучше всего использовать, — остается открытым. Это зависит и от типа процессора, и от интеллектуальности компилятора, и от многих других вещей, поэтому, прежде чем приступать к оптимизации, следует внимательно изучить конкретную оперативную обстановку.

Кэширование вычислений

Если «тяжеловесная» функция многократно вызывается с одними и теми же аргументами, лучшим способом оптимизации будет запоминание однажды вычисленного результата и возвращение его в готовом виде в случае совпадения аргументов. В особенности это касается операций поиска в файле/базе данных. Идентичные запросы здесь — обычное дело, и базы данных давно научились кэшировать их. Так почему бы не применить этот подход и к поиску в файле?