Алгоритмы для жизни. Простые способы принимать верные решения - Том Гриффитс

В процессоры встроен кеш. В жесткие диски встроен кеш. Операционные системы используют кеш. Интернет-браузеры работают с помощью кеш-памяти. И даже серверы, которые «поставляют» контент в эти браузеры, тоже используют кеш, что позволяет нам в сотый раз моментально запускать видео, в котором кошка катается на роботе-пылесосе. Однако мы немного опережаем события.

История развития компьютерных технологий за последние пятьдесят с небольшим лет постоянно демонстрирует опережающий рост и отчасти позволяет нам сослаться на известное своей точностью предсказание, озвученное Гордоном Муром из корпорации Intel в 1975 году. Согласно этому предсказанию, количество транзисторов в компьютерном процессоре должно было удваиваться каждые два года. Тем не менее эффективность памяти при этом не прогрессировала, то есть затраты на доступ к памяти также многократно возрастали относительно времени обработки данных. Таким образом, чем быстрее вы пишете вашу дипломную работу, тем больше снижается продуктивность каждого похода в библиотеку. Аналогично эффективность завода, который удваивает скорость производства каждый год (но при этом получает все то же количество деталей из-за рубежа в прежнем неторопливом темпе), едва ли будет выше эффективности завода, работающего в два раза медленнее. Сначала казалось, что закон Мура не принес никакой пользы, кроме того что процессоры стали «простаивать» все больше и чаще. В 90-е годы эта проблема получила название «стена памяти».

Лучшим средством защиты компьютерной науки от удара об эту стену стало изобретение еще более сложной иерархии: кеш для кеша для кеша на всех уровнях памяти. Современные лэптопы, планшеты и смартфоны имеют шестиуровневую иерархию памяти, при этом экономное и разумное использование памяти еще никогда не было так важно для компьютерных технологий, как сейчас. Так давайте рассмотрим первый вопрос, который приходит на ум, когда речь заходит о кеш-памяти (или о шкафах, к примеру). Что же нам делать, когда все переполнено?

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

Как мы видим, роль IBM в части внедрения систем кеширования в 60-е годы была одной из основных. Неудивительно, что IBM стала первой проводить фундаментальные исследования алгоритмов кеширования. И, пожалуй, пальму первенства среди них нужно отдать алгоритму Ласло Белади. Белади родился в 1928 году в Венгрии, учился на инженера-механика, а во время Венгерской революции 1956 года бежал в Германию с одним рюкзаком, «в котором лежали только белье и диплом». Из Германии он переехал во Францию, затем в 1961 году эмигрировал в США вместе с женой, «маленьким сыном и тысячей долларов в кармане». Казалось, что он обладал отличным чувством меры и понимал, что нужно хранить, а с чем можно легко распрощаться, еще до начала своей работы над замещением кеша в IBM.

Работа Белади по алгоритмам кеширования, которую он написал в 1966 году, оставалась наиболее цитируемым исследованием в компьютерной науке в течение 15 лет. Согласно ей, цель использования кеша состоит в минимизации обращений к более медленной основной памяти в тех случаях, когда пользователь не может найти нужную информацию в кеше. Такие случаи называют «ошибка отсутствия страницы» или «число непопаданий в кеш». Оптимальная политика замещения кеша, как становится очевидно из определения, писал Белади, заключается в том, чтобы, когда кеш полностью заполнен, вытеснить любой его элемент, который максимально нескоро нам понадобится.

Разумеется, определить, когда нам понадобится та или иная информация, – задача трудновыполнимая.

Гипотетически всезнающий и предвидящий алгоритм, способный выбрать оптимальную политику, сегодня известен как алгоритм Белади. Это пример так называемого ясновидящего алгоритма, который использует информацию из будущего. На самом деле не все так безумно, как кажется, ведь существуют случаи, когда система может знать, чего ждать. Но в целом с ясновидением работать сложно, и специалисты по программному обеспечению часто шутят о «трудностях внедрения», которые возникают при попытках применить алгоритм Белади на практике. Таким образом, задача состоит в том, чтобы найти такой алгоритм, решение которого будет максимально дальновидным и точным в тех случаях, когда мы крепко завязли в настоящем и можем лишь гадать, что ждет нас впереди.

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

В рамках третьего подхода – вытеснения по давности использования – замещается тот фрагмент информации, к которому дольше всего не было обращений (вопрос Марты Стюарт «Когда в последний раз я это надевала или использовала?»).

Получается, что эти две мантры Марты Стюарт предлагают две разные стратегии. Более того, одна из них явно превосходит другую. Белади сравнил произвольное замещение, метод «первым вошел, первым вышел» и различные вариации вытеснения по давности использования на нескольких примерах и пришел к выводу, что метод вытеснения по давности использования неизменно показывал результаты, максимально близкие к ясновидению. Этот метод эффективен из-за так называемой временной локальности: если программа обращалась к некоему фрагменту информации единожды, то вполне вероятно, что это повторится в ближайшем будущем. Временная локальность отчасти обусловлена тем, как компьютер справляется с задачами (например, выполнением цикла быстрых операций, связанных со считыванием данных и их записью), но она также заметно проявляется и в том, как люди решают свои проблемы. Работая на компьютере, вы можете переключаться между электронной почтой, интернет-браузером и текстовым редактором. Тот факт, что вы недавно использовали одну из этих программ, указывает на то, что вы, вполне вероятно, откроете ее снова, и при прочих равных условиях программа, которой вы не пользовались дольше всего, с наибольшей вероятностью не будет открыта в ближайшее время.