Ответ Е: в некоторое другое время

Вспомним, что в ответе г) мы рассматривали встраивание в процессе инсталляции в некоторой среде времени выполнения, такой как JVM или .NET CLR. Конечно, проницательные читатели уже заметили, что ранее я упоминал только трансляцию из байт-кода в машинные команды в процессе инсталляции приложения, но есть и другое более распространенное время такой трансляции, а именно - JIT, где аббревиатура JIT означает компиляцию just-in-time , т.е. при необходимости.

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

> Рекомендация

Встраивание может быть выполнено в любой момент времени.

Резюме

Подобно всем оптимизациям, встраивание зачастую более эффективно, если оно выполняется инструментарием, который осведомлен о генерируемом коде и/или среде выполнения, а не программистом. Чем позже выполняется встраивание, тем более точным и соответствующим целевой среде работы программы оно оказывается.

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

Встраивание - эго нечто гораздо большее, чем одно ключевое слово inline.

Задача 26. Форматы данных

и эффективность. Часть 1: игры в сжатие. Сложность: 4

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

До п о л н итсл ьн ыс требования: предполагается, что вы знакомы с азами шахмат. Вопрос для новичка

1. Какой из перечисленных стандартных контейнеров использует меньше памяти для хранения одного и того же количества объектов одинакового типа т: deque, list, set или vector? Поясните свой ответ.

Вопрос для профессионала

2. Вы создаете всемирный шахматный сервер, который хранит все когда-либо сыгранные на нем партии. Поскольку база данных может оказаться очень большой, вы хотите представить каждую партию с минимально возможными затратами памяти. Здесь мы рассматриваем только ходы игры, игнорируя всю остальную информацию, например, имена игроков и комментарии.

Для каждого из приведенных далее размеров данных приведите формат представления партии, требуюший указанное количество памяти для представления полухода (под пол уходом мы подразумеваем ход одного игрока). Считается, что в одном байте - 8 битов.

а) 128 байтов на полуход

б) 32 байта на полуход

в) от 4 до 8 байтов на полуход

г) от 2 до 4 байтов на полуход

д) 12 битов на полуход

Решение

1. Какой из перечисленных стандартных контейнеров использует меньше памяти для хранения одного и того же количества объектов одинакового типа т: deque, list, set или vector? Поясните свой ответ.

Вспомним задачи 20 и 21, в которых говорилось об использовании памяти и структурах стандартных контейнеров. Каждый тип контейнера представляет собой тот или иной компромисс между используемой памятью и производительностью.

vector<T> хранит данные в виде непрерывного массива объектов т и, таким образом, не имеет никаких дополнительных расходов на хранение одного элемента.

deque<T> может рассматриваться как vector<T>, внутреннее представление которого разбито на отдельные блоки. deque<T> хранит блоки, или страницы объектов. Для этого требуется по одному дополнительному указателю на с границу, что обычно приводит к дополнительным расходам памяти, составляющим доли бита на один элемент. Других дополнительных затрат памяти нет, по

скольку у deque<T> нет никаких дополнительных указателей или другой информации для отдельных объектов т.

list<T> представляет собой двухсвязный список узлов, которые хранят элементы т. Это означает, что для каждого элемента т в list<T> хранятся также два указателя, которые указывают на предыдущий и последующий узлы списка. При вставке нового элемента в список мы создаем два дополнительных указателя, так что дополнительные затраты контейнера list<T> составляют два указателя на один хранимый элемент.

И наконец, set<T> (и аналогичные в данном отношении multiset<T>, тар<кеу,т> и multimap<Key,т>) также гранят объекты т (или pair<const кеу,т>) в узлах. Обычная реализация set<T> включает три дополнительные указателя на каждый узел. Зачастую, услышав об этом, многие спрашивают: Откуда три указателя? Разве недостаточно двух -- на левый и правый дочерние узлы? Дело в том, что требуется еще один указатель на родительский узел, иначе задача определения следующего узла по отношению к некоторому произвольно взятому не может быть решена достаточно эффективно. (Возможны и другие способы реализации этих контейнеров; например, можно воспользоваться структурой списков с чередующимися пропусками (alternating skip list) - но и в этом случае требуется как минимум три указателя на каждый элемент (см. [МагпеОО]).)

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

Различные способы представления данных

Цель второго вопроса задачи - п р о де м о н стри ро вать, что может быть множество способов представления одной и той же информации.

2. Вы создаете всемирный шахматный сервер, который хранит все когда-либо сыгранные на нем партии. Поскольку база данных может оказаться очень большой, вы хотите представить каждую партию с минимально возможными затратами памяти. Здесь мы рассматриваем только ходы игры, игнорируя всю остальную информацию, например, имена игроков и комментарии.

В оставшейся части задачи мы используем следующие стандартные термины и аббревиатуры: К King (Король) Q Queen (Ферзь) R Rook (Ладья) В Bishop (Слон) N Knight (Конь) Р Pawn (Пешка)

Поля на шахматной доске определяются горизонталью и вертикалью, к которым они относятся. Вертикали обозначаются слева направо (с точки зрения игрока белыми фигурами) буквами от я до Л, а горизонтали - цифрами от 1 (горизонталь, ближайшая к игроку белыми фигурами) до 8.

Для каждого из приведенных далее размеров данных приведите формат представления партии, требующий указанное количество памяти ддя представления полухода (под полуходом мы подразумеваем ход одного игрока). Считается, что в одном байте - 8 битов.

а) 128 байтов на полуход