Производительность

Теперь можно сравнить несколько вариантов программы. Мы засекали время счета на библейской Книге Псалмов (версия перевода King James Bible), в которой содержится 42 685 слов (5238 уникальных слов, 22 482 префикса). В тексте довольно много повторяющихся фраз ("Blessed is the..."), так что есть списки суффиксов, имеющие более 400 элементов, и несколько сотен цепей с десятками суффиксов, и это хороший набор данных для теста.

Blessed is the man of the net. Turn thee unto me, and raise me up, that 
I may tell all my fears. They looked unto him, he heard. My praise shall 
 be blessed. Wealth and riches shall be saved. Thou hast dealt well with 
thy hid treasure: they are cast into a standing water, the flint into 
a standing water, and dry ground into watersprings.

Приведенная таблица показывает время в секундах, затрачиваемое на j генерацию 10 000 слов; тестирование проводилось на машине 250 MHz MIPS R10000 с операционной системой Irix 6.4 и на машине Pentium II 400 MHz со 128 мегабайтами памяти под Windows NT. Время выполнeния почти целиком определяется объемом вводимого текста; генерация происходит несравненно быстрее. В таблице приведен также примерный размер программы в строках исходного кода.

  250 MHz RlOOOO(c) 400 MHz Pentium II (c) Строки исходного кода
С 0.36 0.30 150
Java 4.9 9.2 105
C++/STL/deque 2.6 11.2 70
C++/STL/list 1.7 1.5 70
Awk 2.2 2.1 20
Perl 1.8 1.0 18

Версии С и C++ компилировались с включенной оптимизацией, а программы Java запускались с включенным JIT-компилятором (Just-In-Time, "своевременная" компиляция). Время, указанное для версий С и C++ под Irix, — лучшее врейя из трех возможных компиляторов; сходные результаты были получены и для машин Sun SPARC и DEC Alpha.

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

Что-то явно не так с версией STL/deque под Windows. Эксперименты показали, что дек, представляющий префиксы, поедает практически все время выполнения, хотя в нем никогда не содержится более двух элементов; казалось бы, большая часть времени должна уходить на основную структуру — отображение. Переход с дека на список (в STL это двухсвязный список) кардинальным образом улучшает время. Переход же с отображения (тар) на (нестандартный) контейнер hash под Irix не приносит никаких изменений (на машине с Windows у нас не было реализации hash). В пользу замечательного принципа проектирования библиотеки STL говорит тот факт, что для внесения этих изменений нам было достаточно заменить слово list на слово deque, а слово hash на слово тар в двух местах и скомпилировать программу заново. Мы пришли к выводу, что STL, которая является новым компонентом C++, все еще страдает некоторыми недоделками в реализации части своих элементов. Производительность при выборе различных версий STL или изменении используемых структур данных меняется непредсказуемым образом. То же самое можно отнести и к Java, где реализации также быстро меняются.

В тестировании программы, которая выдает в качестве результата что-то объемное, да к тому же выбранное случайным образом, есть доля творческого вызова. Как узнать, правильно ли программа работает? Всегд; ли она работает правильно? В главе 6, посвященной тестированию, м: дадим ряд советов на этот счет и расскажем, как мы тестировали наш; программу.