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

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

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

С математическими функциями все обстоит еще интереснее. Как известно, существуют два основных подхода — вычисления на лету и предвычисленные таблицы (часто комбинируемые с различными алгоритмами интерполяции). Проблема в том, что мы наперед не знаем, какой из двух подходов окажется эффективнее. Вычисления требуют времени, предвычисленные таблицы — памяти, а обращение к памяти (особенно вытесненной на диск) — операция не из «дешевых». Однако кэширование вычислений позволяет решить эту проблему, автоматически адаптируясь под конкретную ситуацию и особенно хорошо себя проявляя в распределенных системах, где мы можем одновременно начать поиск с поиском уже вычисленного значения. А там уже кто кого опередит. Если ответ вернется раньше, чем вычисления будут закончены, прерываем их!

Даже на однопроцессорных машинах с поддержкой Hyper Threading уже наблюдается ощутимый прирост производительности! И чем больше процессоров, тем значительнее выигрыш. Единственное, о чем следует позаботиться, — чтобы 2 и более процессора не выполняли одни и те же вычисления одновременно. То есть, получив запрос на наличие уже вычисленных значений, функция не должна выполнять их сама, даже если они отсутствуют в ее кэше, поскольку их уже выполняет кто-то другой. Соответственно, если функция уже приступила к вычислениям, то одна должна вернуть сообщение: «Данных еще нет, но скоро будут», чтобы другая функция не начинала вычисления с нуля.