elizarov


Блог Романа Елизарова


Previous Entry Share Next Entry
Java vs C++ на целых числах
elizarov
Сравнение производительности разных языков программирования, технологий или библиотек это очень неблагодарное занятие. Все сравнения такого рода искусственные и часто страдают от того, что их авторы в разной степени владеют различными технологиями или потратили разное время для оптимизации кода под ту или иную технологию.

Однако, меня чаще всего интересует не столько крутизна той или иной технологии, сколько применимость различных технологий для решения различных реальных задач. На Java я обычно решаю бизнес задачи и написанный код в первую очередь должен быть простым и понятным, а уже во вторую очередь быстрым. Там же где нужна абсолютная скорость, приходится оптимизировать код, дизайн и архитектуру системы, и жертвовать многим, в том числе простотой и понятностью кода. И тогда возникает закономерный вопрос: а подходит ли Java для написания высокопроизводительных систем? Не надо ли все их писать на C или на C++? Может ли код на Java выжать максимум, или почти максимум, из имеющегося железа? Какую долю производительность приходится принести в жертву ради простоты и удобства Java?

Я не отвечу на все эти вопросы в этой записи, но поделюсь некоторым накопленным в этой области опытом. Для того, чтобы была пища для первоначального обсуждения, я переписал тест из предыдущей записи, который просто заполнял массив случайными 32-битными числами и замерял скорость их суммирования, на C++. Чтобы сохранить дух оригинального кода, я использовал не массив напрямую, а абстракцию динамически растущего массива целых чисел. К счастью, в C++ для этого не надо писать своего класса по аналогии с простеньким IntList.ViaJavaArray, который пришлось написать для теста на Java, а можно воспользоваться готовым vector<__int32> из STL. Я специально использую тип __int32, чтобы было проще потом проверить те же самые вычисления в другой архитектуре с другим размером int (для тех читателей, кто не часто общается с C/C++, напомню, что там размеры стандартных типов типа int и long не стандартизированы, а в общем случае зависят от архитектуры, компилятора и его настроек).

Основной цикл на C++ написан в том же самом духе, что и на Java, а весь код можно найти здесь. Я даже заполняю массив теми же самыми псевдо-случайными числами и убеждаюсь, что код на C++ выдает те же самые суммы, что и код на Java.

__int32 IntVectorIterationTiming::runIteration() {
	__int32 sum = 0;
	for (int i = 0, n = vec.size(); i < n; i++)
		sum += vec[i];
	return sum;
}

У меня на Windows машине для компиляции C++ кода есть Microsoft Visual C++ 2008 и gcc version 4.5.0 (GCC) для mingw32. Я потратил некоторое время экспериментируя с различными опциями оптимизации, пытаясь достичь максимальной скорости работы этого кода (минимального времени в расчете на одну итерацию) и добился наилучших результатов используя "g++ -O3 -funroll-loops". Напомню, что на Java я использовал "java -server" для запуска JVM. Вот что у меня получилось, в сравнении с аналогичным циклом итерации по массиву целых чисел на Java из предыдущей записи:

РазмерJavaC++
1 0000.370.38
10 0000.400.41
100 0000.440.42
1 000 0000.660.71
10 000 0000.750.73

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

Размерg++ -O3 -funroll-loopsg++ -O3
1 0000.380.75
10 0000.410.75
100 0000.420.75
1 000 0000.710.92
10 000 0000.730.92

Какие выводы можно отсюда сделать? Из одного сравнения нельзя делать далеко идущие выводы! Однако, занимаясь подобного рода сравнениями регулярно, можно заметить некоторые общие темы. При условии одинаковых структур данных и алгоритмов, работа с целыми числами оптимизируется HotSpot Server JVM на очень и очень достойном уровне и, в отличие от C++, не требует шаманства с настройками оптимизации компилятора, ибо HotSpot сам вычислит какие именно куски кода требуют компиляции, где нужно развернуть циклы, где применить агрессивный inlining, догадается где безопасно убрать проверки границ массивов, и т.д.

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

Ахиллесовой пятой HotSpot безусловно является работа с вещественными числами. В силу очень жестких ограничений спецификации Java на допустимые результаты вычислений в вещественной арифметике, многие оптимизации, которые могут выполнять компиляторы C++, на Java просто не возможны. Есть и другие тонкости и подводные камни, которые надо знать и которыми я планирую поделиться в своем журнале. Однако, есть и одно общее правило: если вам важна производительность, то измеряйте скорость работы кода для вашей задачи с выбранными вами технологиями, оптимизируйте, экспериментируйте.

UPDATE: Конечно, можно получить с помощью gcc и более быстрый код, если использовать "-msse2", но философские и практические аспекты этого (с результатами замеров) подождут отдельной темы про SIMD.

UPDATE2: Посмотреть ассемблерный код, который выдает Java для этого теста можно здесь.


  • 1
А покажи-ка ассемблер, который тебе гнусь сделала :)

А про ассемблер будет отдельный пост. Я покажу и гнусь ассемблер и HotSpot-овский. Как можно догадаться по результатам, они практически не отличаются в своей сути.

Давай. Заодно сделай тоже самое с вещественными числами. Интересно, что мешает джаве сделать тоже, что и си-компилеру.

C вещественными не хочу. Мешает Java Language Specification. Конкретно в п. 4.2.4. сказано "The Java programming language requires that floating-point arithmetic behave as if every floating-point operator rounded its floating-point result to the result precision."

Там есть поблажки в п. 4.2.3 " In addition, an implementation of the Java programming language may support either or both of two extended-exponent floating-point value sets, called the float-extended-exponent value set and the double-extended-exponent value set. These extended-exponent value sets may, under certain circumstances, be used instead of the standard value sets to represent the values of expressions of type float or double (§5.1.13, §15.4)." Но они дают мало свободы. Реально любое присваивание во временную переменную означает обязательное приведение к double/float, а значить невозможность простого хранения числа в extended формате в регистре x86 архитектуры.


Эээ... Рома, я может быть заблуждаюсь, но вроде бы совсем таки нет... Ты в каком веке живешь? Extended формат - это разве не x87? В х86 уже давно в хмм регистрах лежат либо даблы, либо флоаты :)

В xmm ты прав -- double & float. Но какой код компилирует JVM для вещественной арифметики и чем он отличается от кода C++ компиляторов? Это тема для отдельного исследования.

Кстати, посмотрел, что у меня гнусь нагенерила - отстой :( Микровекторизацию они так и не справились сделать.

А кто её умеет делать? Будет интересно обсудить это в отдельной теме, особенно если ты сможешь поделиться компилятором, который умудриться этот код автовекторизовать.



Ну, вот что я получил от нашего компилятора (оставил только сам цикл, остальное нюансы):

{                   8  } .CG5.26:

/ BLOCK: 10, pred: 21 48, succ: 21, count: 32.0000

{                      }        prefetcht0      256(%rdi)

/    8                !         sum += vec[i];

{  fp[ 2]           8  }        paddd   (%rdi),%xmm0
{  fp[ 2]           8  }        paddd   16(%rdi),%xmm0
{  fp[ 2]           8  }        paddd   32(%rdi),%xmm0
{  fp[ 2]           8  }        paddd   48(%rdi),%xmm0
{ int[ 1]           8  }        addq    $64,%rdi
{ int[ 1]           8  }        addl    $16,%esi
{                   8  } .LU3.135:

/ BLOCK: 21, pred: 10, succ: 26 10(backward), count: 32.0000
                                                                        
{ int[ 1]           8  }        cmpl    %ecx,%esi                       
{                   8  }        jle     .CG5.26 


Я уверен, что любой приличный компилер должен делать не хуже. Интел точно справится. Pathscale и PGI - тоже.

Какой версии? Какие опции? Где взять можно? /хочу померить скорость работы результирующего кода на своей машине -- опубликую результаты/

Версию я тупо взял последний билд от разработчиков, т.к. мне он ближе, но и последний релиз это все делал (я от нашего компилятора добился векторизации простейших циклов уже много лет назад, сейчас бьемся над хитровые сложными).
Опции - "-fast -m64". Сейчас точно не скажу, возможно для последнего релиза (он уже старый, скоро новый будет) требуется еще "-xvector=simd".
Интелу хватит "-fast", Pathscale - "-Ofast", PGI - не помню их аналог.
Но у тебя будет маленькая проблема: Интел есть под Винду, нас и PGI точно нет, Pathscale вроде был.

А, где взять. Мы есть тут: http://www.oracle.com/technetwork/server-storage/solarisstudio/downloads/index.html?ssSourceSiteId=ocomen
Интел тут: http://software.intel.com/en-us/articles/intel-compilers/
Pathscale и PGI можешь сам поискать, но можешь и не заморачиваться. На данный момент они ни нам, ни Интелу не конкуренты.

А хотя не надо. Умеет всё gcc делать, если -msse2 сказать. Но это я отложу до отдельной темы про SIMD.

Да? Мне не помогло.

$ g++ -S tmp.cpp -O3 -msse2

.L3:
        addl    (%rcx,%rdx), %eax
        addq    $4, %rdx
        cmpq    %rsi, %rdx
        jne     .L3

-funroll-loops забыл! Он по-умолчанию не включен (типа из-за того что сильно раздувает код, наверное)

Та же фигня, только анролл появился.

gcc version 4.6.1 (Ubuntu/Linaro 4.6.1-9ubuntu3)

А не включен он у них, потому что не умеют правильно анролл делать. Мы долго тюнили, как оно правильнее :)

Ну не судьба значит тебе. gcc он такой gcc.

Это да. Существуют компиляторы, а существуют gcc и msvc ;)

Парадокс-то в том, что только они у меня на машине и есть. И этот тот base-line которым воспользуется среднестатистический программист сравнивая производительность C/C++ с чем-нибудь еще.

Да я знаю :) Только среднестатистический программист еще и джаву без "-server" запустит ;)

И с опциями оптимизации C/C++ компилятора тоже особенно играться не будет, что несколько уравнивает шансы ;)

Это точно. Хорошо, если -О скажет :)

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

Попробую. Спасибо.

P.S. Скопилировано на Барселоне (amd k10h) с оптимизациями под нее же. Но результат не изменится и на других современных процессорах.

Ассемблер можно увидеть
здесь.

Показательно было бы еще на C++ просуммировать через accumulate, раз уж все равно STL используется.

Это скучно, ибо результат будет на 100% такой же как если воспользоваться циклом с STL итератором, что, в свою очередь, лишь немного медленней через через индекс, как в моем примере кода. Я же хотел показать сравнение максимально похожих подходов: цикл с индексом и там и там. С итератором и там и там получилось бы более запутанно, учитывая что итераторы в Java и в С++ концептуально очень по-разному устроены. И вообще, про шаблон итератора и аспекты его производительности как-нибудь расскажу отдельно.

  • 1
?

Log in

No account? Create an account