Всего на сайте:
183 тыс. 477 статей

Главная | Информатика

Упражнение 7-6. Создайте набор тестов для оценки времени исполнения основных операц..  Просмотрен 195

 

Создайте набор тестов для оценки времени исполнения основных операций на используемых вами компьютерах и компиляторах. Изучите похожие и различающиеся аспекты производительности.

Упражнение 7-7

 

Создайте модель затрат для высокоуровневых операций в C++ — та­ких как создание, копирование и удаление объектов классов, вызовы функций-членов класса, виртуальных функций, встраиваемых (inline) функций, библиотеки lost ream, STL. Это упражнение не имеет фиксиро­ванного завершения, так что сосредоточьтесь на небольшом репрезента­тивном наборе операций.

Упражнение 7-8

 

Повторите предыдущее упражнение для Java.

Заключение

 

Если вы выбрали верный алгоритм, то, как правило, об оптимизации его производительности можно уже особо и не задумываться. Однако, если необходимость в ней все же возникла, основной цикл процесса дол­жен выглядеть так: выполните замеры; займитесь местами, изменения в которых дадут максимальный эффект; проверьте корректность измене­ний и выполните замеры снова. Останавливайтесь сразу же, как только достигнете приемлемых показателей; не забывайте сохранить первона­чальную версию как эталон для проверки новых версий на корректность и быстродействие.

Улучшая скорость программы и ее потребность в памяти, создайте для себя набор эталонных тестов, чтобы было проще оценить и впослед­ствии отслеживать быстродействие программы. При наличии стандартных тестов используйте и их тоже. Если программа получается достаточ­но изолированной, самодостаточной, то нередко создают набор "типич­ных" вариантов ввода — такой подход является основой тестов быстро­действия коммерческих и академических систем вроде компиляторов, вычислительных программ и т. п. Так, для Awk создан набор примерно-из 20 маленьких программ, которые в совокупности перекрывают боль­шую часть широко используемых конструкций языка. Эти программы применяются для того, чтобы удостовериться, что результаты работы верны и нет сбоев в производительности. Кроме того, у нас есть набор больших стандартных файлов ввода, которые мы также используем для тестирования времени исполнения программ. Полезно придать таким файлам какие-то легко проверяемые свойства, например размер их мо­жет быть степенью двух или десяти.

Замеры и шаблонные сравнения можно осуществлять с помощью ос­насток того же типа, что мы использовали в главе 6 для тестирования: замеры времени запускаются автоматически; в выводимых результатах достаточно информации для того, чтобы они были понятны и воспроиз­водимы; записи ведутся аккуратно, чтобы можно было отследить основ­ные тенденции и наиболее значительные изменения.

На самом деле создать хорошие тесты-замеры весьма непросто, и об этом прекрасно осведомлены компании, которые специально настраива­ют свои продукты так, чтобы те показывали как можно более высокие результаты именно на подобных тестах. Так что к их результатам надо относиться с известной долей скептицизма.

Дополнительная литература

 

Наше обсуждение спам-фильтра основывалось на работе Боба Флан-дрены (Bob Flandrena) и Кена Томпсона (Ken Thompson). Их фильтр включает в себя регулярные выражения для выполнения более осмыс­ленных проверок и автоматической классификации сообщений ("точно спам", "возможный спам", "не снам") в соответствии со строками, кото­рые были обнаружены.

Профилировочная статья Кнута "An Empirical Study of FORTRAN Programs" появилась в журнале Software — Practice and Experience (1, 2, p. 105-133, 1971). Ее основой стал статистический анализ ряда про­грамм, раскопанных в мусорных корзинах и общедоступных каталогах машин компьютерного центра.

Ион Бентли в своих книгах "Программирование на Pearls" и "Еще программирование на Pearls" (Jon Bentley. Programming Pearls. Addison-Wesley, 1986; Jon Bentley. More Programming Pearls. Addison-Wesley, 1988) приводит ряд хороших примеров улучшений программ, основанных на изменении алгоритма или настройке кода; очень неплохо описано созда­ние оснасток для улучшения производительности и использование про­филирования.

Книга Рика Буфа "Внутренние циклы" (Rick Booth. Inner Loops. Addison-Wesley, 1997) — хорошее руководство по настройке программ для PC. Правда, процессоры эволюционируют так быстро, что специфи­ческие детали стремительно устаревают.

Серия книг Джона Хеннеси и Дэвида Паттерсона по архитектуре ком­пьютеров (например: John Hennessy, David Patterson. Computer Organization and Design: The Hardware/Software Interface. Morgan Kaufmann, 1997) содер­жит вдумчивые рассуждения о вопросах производительности современных компьютеров.


8.

Переносимость

 

Наконец, стандартизация, так же как и соглашения, может служить еще одной

демонстрацией строгого порядка. Но, в отличие от соглаше­ний, она принимается в

современной архитектуре как продукт, хоть и украшающий нашу технологию, но опасный

из-за ее потенциального доминирования и грубости.

 

Роберт Вентури. Сложности и противоречия в архитектуре

 

 

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

Этот идеал называется переносимостью (portability). На практике термин "переносимость" нередко относят к более слабому свойству: про­грамму проще видоизменить при переносе в другую среду исполнения, чем написать заново. Чем меньше изменений надо внести, тем выше пе­реносимость программы.

Вы можете спросить, почему вообще зашел разговор о переносимости: если программа будет исполняться в какой-то конкретной среде, зачем тратить время на то, чтобы обеспечивать ей более широкую область при­менения? Ну, во-первых, каждая хорошая программа почти по опреде­лению начинает с какого-то момента применяться в непредсказуемых местах. Создание продукта с функциональностью более общей, чем из­начальная спецификация, приведет к тому, что меньше сил придется тратить на поддержку продукта на протяжении его жизненного цикла. Во-вторых, среда исполнения меняется. При замене компилятора, опе­рационной системы, железа меняются многие параметры окружения программы. Чем меньше программа зависит от специальных возможно­стей, тем меньше вероятность возникновения сбоев при изменении ус­ловий и тем проще программа адаптируется к этим условиям. И нако­нец, последнее и самое важное обстоятельство: переносимая программа всегда лучше написана. Усилия, затраченные на обеспечение переносимос­ти программы, сказываются на всех ее аспектах; она оказывается лучше спроектированной, аккуратнее написанной и тщательнее протестирован­ной. Технологии программирования переносимых программ непосред­ственно привязаны к технологиям хорошего программирования вообще.

Естественно, степень переносимости должна определяться исходя из реальных условий. Нет такой вещи, как абсолютно переносимая про­грамма, — разве только программа, опробованная не во всех средах. Од­нако мы можем сделать переносимость одной из своих главных целей, стараясь создать программу, которая бы выполнялась без изменений практически везде. Даже если эта цель не будет достигнута в полном объеме, время, потраченное на ее достижение, с лихвой окупится, если программу придется переделывать под другие условия.

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

Язык

Придерживайтесь стандарта.Первое, что необходимо для создания пе­реносимого кода, — это, конечно, использование языка высокого уровня, причем его стандарта, если таковой определен. Двоичные коды перено­сятся плохо, исходный код — несколько лучше. Однако и для него труд­но, даже для стандартных языков, описать точно, каким именно образом компилятор преобразует его в машинные инструкции. Очень немногие из распространенных языков представлены единственной реализацией: обычно имеется множество производителей различных версий для раз­личных операционных систем, которые к тому же со временем изменя­ются. Каждая версия будет обрабатывать ваш код по-своему.

Почему стандарт не является строгим описанием? Иногда стандарт неполон и не описывает отдельных специфических случаев. Иногда он намеренно неконкретен: например, тип char в С и C++ может иметь знак, а может и не иметь; он даже не обязательно должен быть 8-битовым.

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

Иногда же языки вообще не стандартизованы. Официальный стандарт ANSI/ISO С был принят в 1988 году, а стандарт ISO C++ ратифицирован только в 1998-м. На момент написания этой книги не все из распростра­ненных компиляторов поддерживают это официальное описание. Язык Java сравнительно молод, и его стандарт можно ждать только через не­сколько лет. Вообще стандарт языка разрабатывается только после того, как создаются несколько конфликтующих версий, которые надо унифици­ровать, а сам язык получает достаточно широкое распространение, оправ­дывающее затраты на стандартизацию. А между тем по-прежнему надо пи­сать программы и поддерживать в этих программах различные среды исполнения.

Итак, несмотря на то что при знакомстве со справочными руководства­ми и стандартами складывается впечатление жесткой спецификации язы­ка, они никогда не описывают язык полностью, и различные версии ком­пиляторов могут создавать работоспособные, но несовместимые друг с другом реализации. Иногда возникают даже ошибки. Вот довольно ха­рактерный пример: подобные внешние описания недопустимы в С и C++

 

? *х[] = {"abc"};

 

Проверив с десяток компиляторов, мы выяснили, что лишь несколько из них корректно определяют пропущенный определитель типа — слово char для х. Значительная часть выдает предупреждение о несовмести­мости типов (очевидно, те, что используют старое описание языка: они неверно полагают х массивом указателей на int), а еще пара компилиро­вала этот недопустимый код, не сделав ни вздоха.

Следуйте основному руслу.Неспособность некоторых компиляторов вы­явить ошибку в приведенном примере весьма прискорбна, но зато мы теперь сможем осветить важный аспект переносимости. У каждого языка есть свои непроработанные моменты, точки зрения на которые разнятся (например, битовые поля в С и C++), и благоразумие подсказывает избегать их исполь­зования. Стоит использовать только те возможности, описание которых не­двусмысленно и хорошо понятно. Очевидно, что именно такие возможнос­ти, скорее всего, будут широко доступны и реализованы везде одинаковым образом. Мы называем их основным руслом (mainstream) языка.

Трудно однозначно определить, какие именно конструкции входят в это основное русло, но зато те, что в него не входят, определить просто. Совершенно новые возможности, такие как complex или комментарии // в С, или возможности, специфичные для конкретной архитектуры, вро­де ключевых слов near и far, обязательно создадут вам проблемы. Если что-то в языке настолько необычно или непонятно, что для того, чтобы разобраться, вам приходится консультироваться с "языковым правове­дом" — экспертом по чтению его описаний, не используйте такую воз­можность вовсе.

В своем обсуждении мы сконцентрируем основное внимание на С и C++, широко распространенных и универсальных языках. Стандарт С существует уже более десятка лет, и язык очень стабилен, правда, разра­батывается новый стандарт, так что впереди очередные подвижки. А вот стандарт C++ появился совсем недавно, и потому еще не все реализации этого языка приведены с ним в соответствие.

Что можно считать основным руслом в С? Этот термин обычно отно­сят к установившемуся стилю использования языка, но иногда лучше принимать во внимание грядущие изменения. Например, первоначаль­ная версия С не требовала создания прототипов функций. Описание функции sq rt выглядело при этом так:

 

? double sqrt();

 

что определяло тип возвращаемого значения, но не параметров. В ANSI С были добавлены прототипы функций, в которых определялось уже все:

 

double sqrt(double);

 

Компиляторы ANSI С должны воспринимать и прежний синтаксис, но мы настоятельно рекомендуем вам забыть об этом и всегда писать про­тотипы для всех функций. Это сделает код более безопасным, вызовы функций будут полностью проверены на совместимость типов, и при изменении интерфейса компилятор это отловит. Если в коде употребля­ется вызов

 

func(7, PI);

 

a func не имеет прототипа, компилятор не сможет проверить коррект­ность такого вызова. Если библиотека впоследствии изменится так, что у f unc станет три аргумента, компилятор не сможет предупредить о не­обходимости внесения изменений в программу, потому что старый синтаксис не предусматривает проверки типов аргументов функций.

C++ — более мощный и обширный язык, и стандарт его появился лишь недавно, поэтому говорить об основном русле применительно к нему несколько сложнее.

Например, нам представляется очевидным, что STL войдет в это основное русло, что происходит, однако, не мгновенно, и по­этому некоторые существующие реализации языка поддерживают STL не в полной мере.

Избегайте неоднозначных конструкций языка.Как мы уже говорили, не­которые вещи в стандартах умышленно оставлены неопределенными для того, чтобы предоставить создателям компиляторов большую свободу для маневра. Список таких неопределенностей обескураживающе велик.

Размеры типов данных.Размеры основных типов данных в С и C++ не определены. Не существует никаких гарантированных свойств, кроме общих правил, гласящих, что

 

sizeof(char) <= sizeof(short) <= sizeof(int) <= sizeof(long)

sizeof(float) <= sizeof(double)

 

а также что char должен иметь как минимум 8 битов, short и int — как минимум 16, a long — по крайней мере 32. Не требуется даже, чтобы зна­чение указателя умещалось Bint.

Проверить, какие значения использует конкретный компилятор, до­статочно просто:

 

/* sizeof: выводит размеры базовых типов */

int main(void)

{

printf("char %d, short %d, int %d, long %d,",

sizeof(char), sizeof(short),

sizeof(int), sizeof(long));

printf(" float %d, double %d, void* %d\n",

sizeof(float), sizeof(double), sizeof(void *));

return 0;

}

 

Результат будет одинаковым для большинства распространенных машин:

 

char 1, short 2, int 4, long 4, float 4, double 8, void* 4

 

однако возможны и другие значения. Некоторые 64-битовые машины покажут такие значения:

 

char 1, short 2, int 4, long 8, float 4, double 8, void* 8

 

а ранние компиляторы под PC показали бы такое:

 

char 1, short 2, int 2, long 4, float 4, double 8, void* 2

 

Во времена появления PC аппаратура поддерживала несколько видов указателей. Для того чтобы справиться с такой неразберихой, были при­думаны модификаторы указателей far и near, ни один из которых не входит в стандарт, но до сих пор эти ключевые слова-призраки появля­ются во многих компиляторах. Если ваш компилятор может менять раз­меры базовых типов или если вы имеете доступ к машинам, поддержива­ющим другие размеры, постарайтесь скомпилировать и оттестировать вашу программу при таких новых для нее условиях.

Стандартный заголовочный файл stddef. h определяет ряд типов, ко­торые могут помочь с переносимостью. Наиболее часто используемый из них — size_t, который представляет собой тип беззнакового целого, возвращаемого оператором sizeof. Значения этого типа возвращаются функциями типа strlen и во многих функциях, включая malloc, исполь­зуются в качестве аргументов.

Наученная чужим горьким опытом, Java четко определяет размеры всех своих базовых типов: byte — 8 битов, char и short 16, int 32 и long — 64 бита.

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

Порядоквычислений. В С и C++ порядок вычислений операндов выра­жений, побочных эффектов и аргументов функций не определен. На­пример, в присваивании

 

? n = (getchar() << 8) | getchar();

 

второй getcha r может быть вызван первым: порядок, в котором выраже­ние записано, не обязательно соответствует порядку, в котором оно ис­полняется. В выражении

 

? ptr[count] = name[++count];

 

значение count может быть увеличено как до, так и после использования его в качестве индекса ptr, а в выражении

? printf("%c %c\n", getchar(). getcharO);

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

 

? printf("%f %s\n", log(-1.23), strerror(errno));

 

значение errno может оказаться вычисленным до вызова log.

Для некоторых выражений существуют четкие правила вычисления. По определению все побочные эффекты и вызовы функций должны быть завершены до ближайшей точки с запятой или при вызове функ­ции. Операторы && и | | выполняются слева направо и только до тех пор, пока это требуется для определения их значения (включая побоч­ные эффекты). В операторе ?: сначала вычисляется условие, включая возможные побочные эффекты, и только после этого вычисляется одно из двух завершающих оператор выражений.

В Java порядок вычислений описан более жестко. В нем предусмотре­но, что выражения, включая побочные выражения, вычисляются слева направо; правда, в одном авторитетном руководстве дан совет не писать кода, который бы "критично" зависел от этого порядка. Прислушаться к этому совету просто необходимо при создании программ, у которых есть хотя бы призрачный шанс конвертироваться в С или C++: как мы уже сказали, там нет никаких гарантий соблюдения такого же порядка. Конвертирование из одного языка в другой — экстремальный, но иногда весьма полезный тест на переносимость программы.

 

Наличие знака у char. В С и C++ не определено, является ли char знако­вым или беззнаковым типом данных. Это может привести к проблемам при использовании комбинаций char и int, как, например, в приводимом коде, где вызывается функция getchar(), возвращающая значение типа int. Если вы напишете

 

? char с; /* должно было быть int */

? с = getchar();

 

то значение с будет в диапазоне от 0 до 255, если char — беззнаковый тип, и в диапазоне от -128 до 127, если char — знаковый тип; речь идет о практически стандартной конфигурации с 8-битовыми символами на машинах с дополнительным до двух кодом. Это имеет особый смысл, если символ должен использоваться как индекс массива или для провер­ки на EOF, который в stdio обычно представляется значением -1.

Напри­мер, представим, что мы разработали этот код из параграфа 6.1 после ис­правления некоторых граничных условий в начальной версии. Сравнение s[i] == EOF никогда не будет истиной, если char — беззнаковый тип:

 

? int i;

? char s[MAX];

?

? for (i = 0; i < MAX-1; i++)

? if ((s[i] = getchar()) == ‘\n' | | s[i] == EOF)

? break;

? s[i] = ‘\0';

 

Когда getchar возвратит EOF, в s[i] будет сохранено значение 255 (OxFF, результат преобразования -1 в unsigned char). Если s[i] беззнаковое, то при сравнении с EOF его значение останется 255, и, следовательно, про­верка не пройдет.

Однако, даже если char является знаковым типом, код все равно не­корректен. В этом случае сравнение с EOF будет проходить нормально, но при вводе вполне допустимого значения OxFF оно будет воспринято как EOF и цикл будет прерван. Так что вне зависимости от того, знаковый или беззнаковый у вас char, хранить значение, возвращаемое getchar, вы долж­ны в int, и тогда проверка на конец файла будет осуществляться нор­мально. Вот как должен выглядеть наш цикл в переносимом виде:

 

int с, i;

char s[MAX];

 

for (i = 0; i < MAX-1; i++) {

if ((c = getchar()) == '\n’ | с == EOF)

break;

s[i] = c;

}

s[i] = ‘\0';

 

В языке Java вообще нет спецификатора unsigned; порядковые типы данных являются знаковыми, а тип char (16-битовый) — беззнаковым.

Арифметический или логический сдвиг.Сдвиг вправо знаковых величин с помощью

оператора >> может быть арифметическим (при сдвиге распро­страняется копия знакового бита) или логическим (при сдвиге освободившиеся биты заполняются нулями). И здесь Java, наученная горьким опы­том С и C++, резервирует >> для арифметического сдвига вправо и предо­ставляет отдельный оператор >>> для логического сдвига вправо.

Порядок байтов.Порядок байтов внутри short, int и long не определен: байт с младшим адресом может быть как наиболее значимым, так и наи­менее значимым. Этот вопрос зависит от аппаратуры, и мы подробно обсудим его несколько ниже в этой главе.

Выравнивание членов структуры или класса.Расположение элементов внутри структур, классов и объединений (union) не определено, утверж­дается лишь, что члены располагаются в порядке объявления. Напри­мер, в структуре

 

struct X {

char c;

int i;

};

 

адрес i может находиться на расстоянии 2, 4 или 8 байтов от начала структуры. Некоторые (немногие) машины позволяют целым хранить­ся на нечетных границах, но большинство требует, чтобы n-байтовые элементарные типы данных хранились на n-байтовых границах, чтобы, например, double, которые имеют, как правило, длину в 8 байтов, храни­лись по адресам, кратным 8. В дополнение к этому создатели компиля­торов могут вносить и свои ограничения — такие как принудительное выравнивание для повышения производительности.

Никогда не рассчитывайте на то, что элементы структуры занимают смежные области памяти. Ограничения на выравнивание вызывают появление "дыр" в структурах — так, st ruct X всегда будет содержать по крайней мере один байт неиспользуемого пространства. Из-за этих дыр размер структуры может быть больше, чем сумма размеров ее членов, причем этот размер может быть разным на разных машинах. Если вы хотите зарезервировать память под структуру, всегда запрашивайте sizeof(struct X) байтов, но не sizeof(char) + sizeof(int).

Битовые поля.Битовые поля настолько зависят от конкретных машин, что никому не следует их использовать.

 

Все перечисленные опасные места можно миновать, следуя несколь­ким правилам. Не используйте побочные эффекты нигде, кроме как в идиоматических конструкциях типа

 

a[i++] = 0;

с = *p++;

*s++ = *t++:

He сравнивайте char с EOF. Всегда используйте sizeof для вычисления размера типов и объектов. Никогда не сдвигайте вправо знаковые значе­ния. Убедитесь, что тип данных достаточно велик для диапазона значе­ний, которые вы собираетесь в нем хранить.

Попробуйте несколько компиляторов. Иногда вам может показаться, что вы решили все проблемы с переносимостью, однако компиляторы в состоянии увидеть проблемы, которые не вы заметили, и вообще, раз­ные компиляторы воспринимают вашу программу по-разному, и этим можно воспользоваться. Включите все предупреждения компилятора. Попробуйте использовать разные компиляторы на одной машине и на разных машинах. Попытайтесь компилировать вашу С-программу на компиляторе C++.

Поскольку язык, воспринимаемый различными компиляторами, мо-. жет несколько отличаться от стандарта, тот факт, что ваша программа компилируется одним компилятором, не дает гарантии даже того, что она корректна синтаксически. А вот если несколько компиляторов при­нимают ваш код, значит, все не так плохо. Мы компилировали каждую программу, приведенную в книге, на трех компиляторах С для трех раз­личных операционных систем (Unix, Plan 9, Windows) и на паре компи­ляторов C++. При таком подходе были найдены десятки ошибок пере­носимости — никакое самое пристальное изучение программ человеком не смогло бы найти их все. Исправлялись же все ошибки тривиально.

Естественно, сами компиляторы тоже вызывают проблемы с перено­симостью из-за разного толкования не описанных в стандарте случаев. Однако наш подход — писать программы, избегая применения деталей, которые могут варьироваться, позволяет надеяться на создание про­грамм, работающих вне зависимости от внешних условий.

Предыдущая статья:Математические функции Следующая статья:Заголовочные файлы и библиотеки
page speed (0.0127 sec, direct)