Продолжается подписка на наши издания! Вы не забыли подписаться?

Кто сегодня самый шустрый-2?

Владислав Чистяков

Исходный код тестов.

Предыдущая серия: Первая серия
Следующая серия: Третья серия.

Замечания по Delphi

После опубликования предыдущей серии тестов мы получили ряд откликов от читателей. В тесте Delphi нам справедливо указали на допущенную ошибку. Это вылилось в достаточно пространное обсуждение (желающие могут найти его на сайте Королевство Delphi, http://www.delphikingdom.com/cgi-bin/talk.cgi?ID=195). Ошибка заключалась в том, что при переводе кода С-подобных языков на Delphi (а изначально тесты писались именно на С++) код, конкатенирующий конец строки:

ss += '\n';

был необдуманно переведен в:

ss := ss + '\n';

То есть, строка, состоящая из одного спецсимвола конца строки с ASCII-кодом 0x10 (в шестнадцатеричной форме) превратилась в строку, состоящую из двух символов "\" и "n" в Object Pascal. Нам резонно заметили, что лишний символ может сказаться на скорости выполнения теста. И хотя там же прозвучало резонное замечание, что основные задержки производительности в Delphi связаны с динамическим перераспределением памяти, отводимой под строки, и один лишний символ не слишком скажется на результате, мы провели тесты для Delphi повторно, чтобы узнать, насколько мы обидели Delphi.

Мы заменили приведенный выше код на

ss := ss + #10;

то есть привели его в соответствие остальным тестам. Каково же было наше удивление, когда измененный код не ускорился, а замедлился, проиграв "неправильной" версии около 1 секунды – что составляет около 10%! Мы несколько раз повторили тест в обоих вариантах, с неизменным результатом. Здесь мы не будем вдаваться в подробности причин такого замедления. Все желающие могут прогнать тест под отладчиком в ассемблерном режиме (предварительно включив создание отладочной информации в опциях проекта), взяв обновленные исходные тексты с нашего сайта.

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

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

function StrFastCopy( s1 : PChar; const s : string ) :PChar;
var
   len : Integer;
begin
  len := Length(s);
  StrMove(S1, PChar(s), len);
  Result := s1 + len;
end;
procedure TForm1.pbStringTest2Click(Sender: TObject);
var
    s0, s1 : PChar;
    //ss : string;
    i : Integer;
begin
    Utility1.TimerStart();
    GetMem(s0, 1000 );
    for i := 0 To 10000000 - 1 do
    begin
        s1 := StrFastCopy(s0, '>>>>>...>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>');
        s1 := StrFastCopy(s1, 'Мама ');
        s1 := StrFastCopy(s1, 'мыла ');
        s1 := StrFastCopy(s1, 'раму');
        StrFastCopy(s1, #10);
        s1 := s0;
        //ss := s0;
    end;
    Utility1.TimerEnd();
    //ShowMessage(ss);
    ShowMessage(s1);
    FreeMem(s0);
end;

Этот тест показал лучший результат (3.28 секунды), но принять его в зачет мы все-таки не можем. Дело в том, что работать со строками на Паскале в таком стиле – это (как бы помягче сказать) извращение. Да и микс из паскалевских и С-строк строк не всегда может пройти. Если же учесть еще, что большинство популярных функций в Паскале принимают именно паскалевскую строку (совершая, если нужно, неявные преобразования), а имеющиеся функции работы со строками в формате PChar ориентированы на подсчет длины строки на основании завершающего нулевого символа, то добиться серьезного увеличения производительности вряд ли удастся. Вы, наверное, заметили выделенные жирным строки в приведенном выше коде. Если закомментировать незакомментированные и наоборот, раскомментировать закомментированные строки, и провести тест в таком варианте, то результат будет 7.47 секунды. Это хотя и не самый худший, но близкий к нему результат, а ведь единственное, что изменилось – в конце копирования массив символов был преобразован в строку Паскаля.

Какие же выводы можно сделать? Во-первых, не стоит так уж серьезно относиться к результатам этого теста и бежать переписывать весь свой код на PChar-ы. Не так уж много критичного ко времени исполнения кода имеется в среднестатистической программе. Если уж и оптимизировать, то сначала нужно проверить, какие куски кода действительно критичны, и переписывать только их. Во-вторых, Паскаль разрабатывался с целью повысить качество программирования, и введение строк в состав язык имело целью именно увеличение читаемости текста и уменьшение количества ошибок, связанных с ручной работой с памятью и массивами. Так что код с PChar может серьезно ухудшить ваш проект, и выигрыш в скорости может оказаться несущественным по сравнению с ухудшением качества всего проекта.

Object Pascal – это компонентно-ориентированный язык. И было бы совершенно логично создать компонент – StringBuilder (или просто класс-хелпер, имя вообще не критично), который инкапсулировал бы в себе работу со строкой переменного размера. Такой класс должен иметь как свойство (значение которого хранится в скрытой переменной), отражающее текущую длину строки, так и свойство Capacity, отражающее размер выделенного буфера. При этом буфер должен расширятся скачкообразно (лучше всего путем умножения прошлого значения на два), что должно резко сократить количество перезаемов памяти. В нашем примере было бы 2-3 перезаема на весь тест! Да и то, если Capacity не было бы задано предварительно в достаточно большое значение (как это делалось в других языках). Причем для такого класса нужно предусмотреть методы которые выполняют основные (часто используемые) операции над строками. Вот результаты такого теста можно было бы считать законными. Хотя, видимо, еще лучшим решением было бы оптимизировать работу со строками, встроенными в язык, настолько, чтобы о дополнительных средствах даже не приходилось задумываться. Но этого пока не сделал никто.

Новые участники

Мы протестировали еще три компилятора, а именно: GNU C++ 2.95.3-7 (вернее его порт на Windows - mingw), Borland C++ 5.5 и VC.Net (v 7.0) beta 2.

Компилятор GNU C++ (далее gcc) тестировался нами и в других версиях (меньших чем 2.95.3-7). Причем он каждый раз показывал несколько различающиеся результаты, но так как серьезное отличие оказалось в и без того спорном тесте «Float-Тест» (подробнее см. в комментарии к этому тесту), я не буду здесь заострять внимание на этой особенности. Gcc на сегодня имеется и версии 3.х, но она не была доступна на платформе Windows на время проведения испытаний. И, так как 2.95.3-7 – это практически бета-версия для 3.х, можно закрыть на это глаза. В будущем мы проверим эти тесты на 3.x и, в случае существенной разницы, опубликуем результаты с нашими комментариями.

Borland C++ 5.5 (далее bcc) – это последняя версия компилятора C++ от фирмы Borland. Это добротный компилятор, довольно точно соответствующий стандарту. Интерес к нему подогревается еще и тем, что Borland C++ 5.5 стал свободно распространяемым.

VC.Net (v 7.0) beta 2 (далее VC7) – это еще бета версия, но его результаты уже позволяют говорить о том, что алгоритмы оптимизации в новой версии заметно улучшились. Не все тесты стали выполняться быстрее, но некоторые (подсчет p , и строковый тест) – несомненно.

Тесты

Итак перейдем к самим тестам.

Вызов метода объекта (Method call)

Компилятор Опции Время (с)
GNU C++ 2.95.3-7 (mingw) Без разворота циклов 1.44
с разворотом циклов 0.37
с "полным" разворотом циклов 0.36
Borland C++ 5.5   9.39
VC.Net (v 7.0) beta 2 С inline-подстановкой 0.00
Без inline-подстановки 0.00

Единственный, кто не стал утруждать себя «излишней» оптимизацией – bcc. Но его результат оказался одним из худших уступив последнее место только явному «лидеру» VB.

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

Gcc прекрасно справился с этим тестом, хотя ни в одном из вариантов не смог полностью соптимизировать весь цикл. По уму, для зачета нужно брать результат, полученный без опций компилятора, заставляющих его раскручивать циклы. Это связано с тем, что цикл в нашем случае – это не зло, а способ заставить компилятор выполнять код достаточное количество раз, чтобы занимаемое процессом время можно было измерить. Учитывая, что компилятор все равно не смог полностью соптимизировать цикл, результаты тестов с раскруткой циклов становятся бесполезными. Однако мы решили оставить его, хотя бы ради справедливости. Так что вы можете сами принять для себя решение, как оценивать gcc.

Еще раз напомним, что не стоит обращать особого внимания на синтетические тесты, ибо выигрыш в данном тесте зачастую достигается не оптимальностью вызова метода, а другими оптимизациями (раскрутка цикла, inline-подстановки...), и тем, что время, затрачиваемое на вызов, относительно невелико. Удивительно то, что это время оказалось на треть больше, чем у Delphi, также продукта этой фирмы. Видимо недаром бытует мнение, что Borland невзлюбил C++.

Вызов виртуального метода объекта (virtual method call)

Компилятор Опции Время (с)
GNU C++ 2.95.3-7 (mingw) Без разворота циклов 18.78
с разворотом циклов 18.67
с "полным" разворотом циклов 18.66
Borland C++ 5.5   8.90
VC.Net (v 7.0) beta 2 С inline-подстановкой 5.77
Без inline-подстановки 5.77

VC7 стал победителем этого теста в общем зачете, улучшив время, показанное своим предшественником на 2 сотых секунды :). Такую победу можно было бы и не считать победой, если бы VC7 не показал того же времени в режиме без автоматической inline-подстановки (в этом режиме VC6 показал заметно худший результат, 6.49 секунды, хотя стал в прошлый раз лидером).

Bcc в очередной раз показал время, хотя и немногим, но худшее, чем Delphi. Что же, это некритичное отставание, как это было в случае с VB6, но все равно обидно.

Для gcc этот тест был, пожалуй, наиболее неудачным. Gcc умудрился отстать даже от Java. Причем не помог ему даже вариант компиляции с полной раскруткой циклов – разница в скорости была незначительной (18.78 секунд в обычном режиме и 18.66 в режиме с полной раскруткой циклов). Назвать эту разницу серьезной (особенно на фоне столь серьезного отставания) нельзя. Видимо, повсеместное использование COM, как известно, основанного на виртуальных вызовах, заставило разработчиков традиционных для Windows компиляторов с большим усердием заниматься оптимизацией вызовов виртуальных методов.

Доступ к члену класса

Компилятор Опции Время (с)
GNU C++ 2.95.3-7 (mingw) Без разворота циклов 4.01
с разворотом циклов 0.40
с "полным" разворотом циклов 0.40
Borland C++ 5.5   6.79
VC.Net (v 7.0) beta 2 С inline-подстановкой 1.44
Без inline-подстановки 4.33

Результаты данного теста похожи на предыдущий, с той лишь разницей, что VC7 не смог полностью оптимизировать тест в режиме с автоматической inline-подстановкой. Это странно, так как мы видели, что VC7 не задумываясь выбрасывает лишние вызовы и применяет оптимизацию к результатам подстановки. В конце концов, если обращение к члену класса заменить на обращение к глобальной переменной, то VC7 спокойно выбросит цикл, заменив его константным вычислением и подставив его результат в переменную. Короче говоря, Microsoft еще есть над чем работать в следующей версии своего компилятора C++, если таковой планируется.

Gcc продемонстрировал относительно неплохой результат, но все таки отстал от лидера (C#). Как и в прошлый раз, результаты с разворотом цикла приводятся исключительно в целях справедливости и не должны рассматриваться в качестве оцениваемых.

Quick Sort (быстрая сортировка)

Компилятор Опции Время (с)
GNU C++ 2.95.3-7 (mingw) Без разворота циклов 9.36
с разворотом циклов 9.95
с "полным" разворотом циклов 9.97
Borland C++ 5.5   10.71
VC.Net (v 7.0) beta 2 С inline-подстановкой 8.08
Без inline-подстановки 8.10

Первый не синтетический тест. Что же он показал? Собственно, показал примерно те же зависимости, которые мы наблюдали в предыдущих тестах. Всс отстал и занял место между Delphi и Java. Gсс был более удачлив, но раскрутка циклов на реальных задачах не дала прироста производительности. Напротив, тест без разворота циклов занял наименьшее время, 9.36, с разворотом циклов – среднее, 9.95, с "полным" разворотом циклов – 9.97, а если включить сразу оба варианта разворотов циклов, то время выполнения теста и вовсе выходит за 10 секунд. Так что данная оптимизация на хороших алгоритмах может дать скорее замедление (хотя и незначительное), чем прирост производительности.

Порадовал только один VC7, который снова смог поднять планку, в этот раз уже на ощутимые полсекунды. Снова повторился прирост не только в режиме с автоматической inline-подстановкой, но и в обычном.

Пузырьковая сортировка

Компилятор Опции Время (с)
GNU C++ 2.95.3-7 (mingw) Без разворота циклов 5.36
с разворотом циклов 4.81
с "полным" разворотом циклов 4.81
Borland C++ 5.5   5.05
VC.Net (v 7.0) beta 2 С inline-подстановкой 5.00
Без inline-подстановки 5.00

Это первый тест, в котором опция раскрутки циклов в gcc дала прирост производительности, тем самым позволив gcc занять верхнюю ступень пьедестала почета. Кривизна алгоритма как бы частично компенсировалась разворотом цикла. Однако вариант с "полным" разворотом циклов ничем не отличался от более простого аналога. Время gcc, показанное без оптимизаций раскрутки циклов, оказалось хуже, чем у большинства участников, но тоже очень достойным, подтвердив, что gcc является качественным продуктом. Для сравнения, конечно же, нужно брать результат с раскруткой цикла.

Порадовал в этот раз и bcc. Его результат был хотя и не лучшим, но настолько мало отставал от лидера, что bcc можно поздравить с неплохим результатом.

Подсчет p (целочисленные вычисления)

Компилятор Опции Время (с)
GNU C++ 2.95.3-7 (mingw) Без разворота циклов 4.10
с разворотом циклов 3.80
с "полным" разворотом циклов 3.80
Borland C++ 5.5   6.84
VC.Net (v 7.0) beta 2 С inline-подстановкой 3.77
Без inline-подстановки 3.77

В этом тесте VC7 и gcc показали примерно одинаковый результат, практически вдвое лучший, чем у всех конкурентов. Это уже действительно достижение, так как данный тест является совершенно реальным целочисленным расчетом с не очень оптимальным алгоритмом, но все же намного более оправданным, чем (воистину бредовый) алгоритм пузырьковой сортировки.

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

Borland показал достойный результат, но, как всегда, чуть хуже чем у Delphi.

Tree sort

Компилятор Опции Время (с)
GNU C++ 2.95.3-7 (mingw) Без разворота циклов 12.63
с разворотом циклов 12.56
с "полным" разворотом циклов 12.71
Borland C++ 5.5   11.54
VC.Net (v 7.0) beta 2 С inline-подстановкой 11.34
Без inline-подстановки 11.37

Удивительно, но трех сотых секунды было достаточно, чтобы пальма первенства ушла из рук Delphi в руки VC7. Не думаю, что поклонники Delphi от этого сильно расстроятся, ведь результат Delphi поистине замечателен, но факт есть факт.

Однако сейчас хочется поговорить немного о другом. Как уже говорилось, в прошлой серии скорость выполнения этого теста в большей степени зависит не от качества компилятора, а от качества реализации хипа. По умолчанию Delphi использует однопоточный режим работы с хипом, и некоторые читатели (с одновременно знакомым и загадочным именем Anonym) усомнились в том, что реализация хипа в Delphi лучше, чем стандартная реализация в W2k. Обосновывалось это тем, что мы не провели тестов в многопоточном режиме. мы решил исправить данное упущение.

Для того, чтобы включить многопоточный режим, мы добавили в обработчик события FormCreate переключение свойства IsMultiThread:

procedure TForm1.FormCreate(Sender: TObject);
begin
    IsMultiThread := True;
end;

Это действительно привело к снижению скорости выполнения теста до 11.51 секунды, но повторное выполнение не привело к какому бы то ни было увеличению времени. А если учесть, что результаты VC6 и Intel C++ были приведены тоже для однопоточного режима, и то, что даже в этом случае Delphi осталась лидером (среди тех участников), то можно сказать, что слова о качестве реализации хипа в Delphi совершенно справедливы. Однако мы не делали тестов на конкурентный доступ к хипу из нескольких потоков, и не можем сказать, как поведут себя конкретные реализации в этом случае. Возможно, в будущем мы проведем такой тест.

Пока можно сказать, что первенство VC7 несколько омрачается тем, что в многопоточном режиме время повторного выполнения этого теста значительно увеличивается. Но, как уже говорилось, это проблема не VC7 как такового, а W2k.

String-тест

Компилятор Опции Время (с)
GNU C++ 2.95.3-7 (mingw) Без разворота циклов 5.12
с разворотом циклов 5.39
с "полным" разворотом циклов 5.13
Borland C++ 5.5   15.80
VC.Net (v 7.0) beta 2 С inline-подстановкой 4.11
Без inline-подстановки 4.10

Кое что о этом тесте мы уже сказали. Так что Delphi мы больше трогать не будем. Поговорим лучше об остальных участниках. К сожалению, результаты этого теста нельзя назвать удовлетворительными, так как мы не смогли обеспечить одинаковые условия сравнения даже для C++-компиляторов. Дело в том, что подключение MFC к не Microsoft-овским компиляторам – это непростая задача, на которую попросту не было времени. Особенно это было сложно с gcc. Поэтому мы приняли решение воспользоваться более переносимой реализацией из STL – std::string. Но и тут не все так просто. Существует множество реализаций STL, и наши подопытные (а именно bcc и gcc) использовали разные версии. Причем у bcc оказался самый древний и медленный вариант от HP. Однако результаты теста имеют право на жизнь, так как скорее всего пользоваться программист будет тем, что имеется под рукой.

VC7, как и в других тестах, несколько улучшил свой результат, но до лидеров не достал.

Bcc показал совсем плохой результат, но как уже говорилось, возможно это в большей степени зависит не от качества оптимизации, а от качества реализации STL.

Float-Тест

Компилятор Опции Время (с)
GNU C++ 2.95.3-7 (mingw) Без разворота циклов 14.46
с разворотом циклов 3.34
с "полным" разворотом циклов 3.36
Borland C++ 5.5   15.12
VC.Net (v 7.0) beta 2 С inline-подстановкой 12.26
Без inline-подстановки 12.26

Еще одним тестом, в котором выигрывает не сильнейший, а хитрейший, стал «Float-Тест». Так, gcc в обычном режиме показал совершенно посредственный результат, заняв место между Java и VB6. Однако с включенной опцией раскручивания циклов он вдруг сразу переместился на вторую позицию (первым, напомню, был Intel C++). Причем я смог добиться только результата 3.34 секунды, а Юнусов Булат (автор одного из вариантов теста для gcc) добился ~1.5 секунд. Такой результат весьма хорошо выглядит, но совершенно непригоден для сравнения, так как он достигается не за счет увеличения качества оптимизации вычислений с плавающей точкой, а за счет банальной борьбы с циклом. Осознание этого еще больше наталкивает на мысль, что для получения реалистичных результатов нужен осмысленный алгоритм. Причем к этому алгоритму предъявляются довольно строгие требования: он должен в основном состоять из вычислений над переменными типа double, он не должен содержать значительных обращений к массивам (иначе языки, производящие контроль доступа к массивам, будут в заведомо плохих условиях, да и большая часть теста будет мерить скорость доступа к шине памяти).

Если у кого-нибудь на примете есть алгоритм, удовлетворяющий условиям, перечисленным выше, большая просьба связаться с нами по e-mail (tcs@k-press.ru), и передать этот алгоритм.

Благодарности

Хочется поблагодарить Александра Корсукова, Булата Юнусова и Игоря Ткачева, помогавших (своим личным трудом и советами) в переносе кода под gcc и bcc.


Copyright © 1994-2016 ООО "К-Пресс"