Скорость работы эквивалентного кода на Си и Паскаль

Интересные алгоритмы, олимпиадные задачи, эффектные и эффективные решения. freepascal, delphi, c, c++, c#, java, javascript, perl, ruby, python, php, bash, wsh и т.д. Компиляторы, интерпретаторы, линкеры, отладчики, системы контроля версий и многое другое.

Модератор: xdsl

Скорость работы эквивалентного кода на Си и Паскаль

Сообщение xdsl 18 дек 2008, 23:03

По мотивам поста https://shgpi.edu.ru/forum/viewtopic.php?p=36#p36 решил сравнить эффективность генерации машинного кода компиляторами gcc и freepascal. Ожидания оправдались с точностью до наоборот.
Итак, программа на Си test.c, реализующая тривиальный перебор:
Код: Выделить всё
#include <stdio.h>
int main ()
{
long int register i,k;
puts("Test begin");
for(i=0; i<=2000000000L; i++) for(k=0;k<=10;k++);
puts("Test end");
return 0;
}

Компилируем: gcc test.c -otest
Запускаем: time -f "%E" ./test
Получаем:
Код: Выделить всё
Test begin
Test end
0:52.90

Ну, думаю, аналог на паскале пропилит минуту и больше, ибо общеизвестная истина. Ага, щазз.
Аналогичная вышеприведенной программа на Паскале test.pp:
Код: Выделить всё
{$mode objfpc}
var i,k:longint;
begin
writeln('Test begin');
for i:=0 to 2000000000 do for k:=0 to 10 do;
writeln('Test end');
end.

Компилируем: fpc test.pp
Запускаем: time -f "%E" ./test
Получаем:
Код: Выделить всё
Test begin
Test end
0:15.90

Программа на паскале работает в 3 раза быстрее программы на Си!
Для чистоты эксперимента переписал код той и другой программы для приведения его к общему знаменателю:

На Си:
Код: Выделить всё
#include <stdio.h>
int main ()
{
long int register i,k;
puts("Test begin");
i=0;
while (i<=2000000000L) {
  i++;
  k=0; while (k<=10) k++;
}
puts("Test end");
return 0;
}

На Паскале:
Код: Выделить всё
{$mode objfpc}
var i,k:longint;
begin
writeln('Test begin');
i:=0;
while i<=2000000000 do begin
  inc(i);
  k:=0; while k<=10 do inc(k);
end;
writeln('Test end');
end.

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

P.S.
компилятор паскаля - fpc 2.2.2, оптимизация - использование регистровых переменных
компилятор си - gcc 4.1.1, оптимизация - использование регистровых переменных
xdsl
 
Сообщения: 1228
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Скорость работы эквивалентного кода на Си и Паскаль

Сообщение Vladislav_133 19 дек 2008, 20:03

Дм.Ан., вышли мне сегодня - завтра free-паскаль. Я посмотрю в чем разница между ним и скажем Visual C++. Мне приходилось писать по этому поводу. Так вот, VC++ побивает практически все сишные компиляторы, а о Дельфи и говорить не приходится. Это я все доказательно могу продемонстрировать. А вот free-паскаль я не исследовал, может там и есть какой-то мощный механизм оптимизации. Так что проверим.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1254
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Скорость работы эквивалентного кода на Си и Паскаль

Сообщение xdsl 19 дек 2008, 21:37

ftp://shgpi.edu.ru/ftp.vc.shgpi/langs/freepascal/2.2.2/
Для сети K+ shgpi.edu.ru заменяется на shgpi.shadrinsk.net
Фрипаскаль для виндовс там совместно с лазарусом в одном файле - ftp://shgpi.edu.ru/ftp.vc.shgpi/langs/f ... -win32.exe
На виндовс - не проверял, т.к. под рукой виндового сишного компилятора не имею.
xdsl
 
Сообщения: 1228
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Скорость работы эквивалентного кода на Си и Паскаль

Сообщение xdsl 19 дек 2008, 21:42

Да, еще момент: для генерации ASM-кода компилятором freepascal (чтобы было что с чем сравнивать) надо компилировать с опцией -al. Полученный файл с расширением .s содержит машинный код в текущей мнемонике (у меня по умолчанию установлена интелловская)
xdsl
 
Сообщения: 1228
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Скорость работы эквивалентного кода на Си и Паскаль

Сообщение Vladislav_133 21 дек 2008, 17:10

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

И так некоторые результаты моих исследований. Я буду пользоваться не промежуточным
ассемблерным кодом, а дизассемблером Ida Pro. В настоящее время это лучший дизассемблер.
Он работает со всеми основными исполняемыми и объектными форматами.
Так что мы легко , например, можем сравнить исполняемый код в Windows и в Linux.

И так, программа на языке pascal. Компилятор free-pascal.

Код: Выделить всё
program Project1;
{$mode objfpc}{$H+}
var
   i,s:integer;
begin
   s:=0;
   for i:=1 to 1024  do
   begin
      s:=s+i;
   end;
   writeln(s);
end.


Программа на C++. Компилятор Visual C++.

Код: Выделить всё
#include <stdio.h>
int i,s;
void main()
{
   s=0;
   for(i=1; i<=1024; i++)
   {
      s=s+i;
   }
   printf("%d\n",s);
}


Паскаль. Без оптимизации.

Код: Выделить всё
.text:0040137E                 mov     ds:dword_408004, 0
.text:00401388                 mov     ds:dword_408000, 1
.text:00401392                 dec     ds:dword_408000
.text:00401398
.text:00401398 loc_401398:                             
.text:00401398                 inc     ds:dword_408000
.text:0040139E                 mov     edx, ds:dword_408004
.text:004013A4                 mov     eax, ds:dword_408000
.text:004013A9                 add     edx, eax
.text:004013AB                 mov     ds:dword_408004, edx
.text:004013B1                 cmp     ds:dword_408000, 400h
.text:004013BB                 jl      short loc_401398


Паскаль (оптимизация o3)

Код: Выделить всё
.text:0040137F                 mov     ebx, 0
.text:00401384                 mov     edx, 1
.text:00401389                 dec     edx
.text:0040138A                 mov     esi, esi
.text:0040138C
.text:0040138C loc_40138C:                           
.text:0040138C                 inc     edx
.text:0040138D                 mov     eax, edx
.text:0040138F                 add     eax, ebx
.text:00401391                 mov     ebx, eax
.text:00401393                 cmp     edx, 400h
.text:00401399                 jl      short loc_40138C

Другие виды оптимизации не дают иных результатов. Слишком прост код.

C++. Без оптимизации.

Код: Выделить всё
.text:00401003                 mov     dword_40301C, 0
.text:0040100D                 mov     dword_403018, 1
.text:00401017                 jmp     short loc_401026
.text:00401019 loc_401019:                             
.text:00401019                 mov     eax, dword_403018
.text:0040101E                 add     eax, 1
.text:00401021                 mov     dword_403018, eax
.text:00401026 loc_401026:                             
.text:00401026                 cmp     dword_403018, 400h
.text:00401030                 jg      short loc_401046
.text:00401032                 mov     ecx, dword_40301C
.text:00401038                 add     ecx, dword_403018
.text:0040103E                 mov     dword_40301C, ecx
.text:00401044                 jmp     short loc_401019
.text:00401046 loc_401046:                             


С++. Оптимизация по объему кода.

Код: Выделить всё
.text:00401000                 xor     eax, eax
.text:00401002                 xor     ecx, ecx
.text:00401004                 inc     eax
.text:00401005
.text:00401005 loc_401005:                             
.text:00401005                 add     ecx, eax
.text:00401007                 inc     eax
.text:00401008                 cmp     eax, 400h
.text:0040100D                 jle     short loc_401005


С++. Оптимизация по объему кода (по сути тот же результат,
поскольку слишком простая программа).

Код: Выделить всё
.text:00401000                 xor     ecx, ecx
.text:00401002                 mov     eax, 1
.text:00401007
.text:00401007 loc_401007:                             
.text:00401007                 add     ecx, eax
.text:00401009                 inc     eax
.text:0040100A                 cmp     eax, 400h
.text:0040100F                 jle     short loc_401007


Результат мне кажется весьма интересен. Я бы сказал счет один-один
и сейчас объясню. Не оптимизированные варианты. Паскалевский код короче.
Но есть два момента. Здесь требуется проверка, но я пока говорю по памяти.
Дело в том, что если a - адрес ячейки,
Код: Выделить всё
inc a
, выполняется медленнее,
чем
Код: Выделить всё
mov eax,a/add eax,1/mov a,eax
. Есть и еще один нюансик, но здесь
я помню не точно и это следует проверить. А именно, условный переход
выполняется медленнее, чем условный переход без перехода+безусловный
переход. Таким образом изначально компилятор free-pascal ориентирован
на объем, а Visual C++ на скорость.

В случае же использования оптимизированного
кода Visual C++ несколько лучше оптимизирует, чем free-pascal (см. листинги).

Это мой первый выпуск. Далее я продолжу свои исследования.

P.S.
Да, и сранение по скорости также будет, но позднее, просто и другие дела есть.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1254
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Скорость работы эквивалентного кода на Си и Паскаль

Сообщение xdsl 21 дек 2008, 20:49

Решил воспользоваться GCC для сравнения его оптимизации с оптимизацией на Visual C++. На мой взгляд, GCC бьет Visual C++ по всем статьям:
Ваш код в файле 1.c:
Код: Выделить всё
#include <stdio.h>
int i,s;
void main()
{
   s=0;
   for(i=1; i<=1024; i++)
   {
      s=s+i;
   }
   printf("%d\n",s);
}
Компилируем с простейшей оптимизацией: gcc -O1 -S 1.c
Получаем ASM-код в файле 1.s:
Код: Выделить всё
       .file   "1.c"
        .section        .rodata.str1.1,"aMS",@progbits,1
.LC0:
        .string "%d\n"
        .text
.globl main
        .type   main, @function
main:
        leal    4(%esp), %ecx
        andl    $-16, %esp
        pushl   -4(%ecx)
        pushl   %ebp
        movl    %esp, %ebp
        pushl   %ecx
        subl    $8, %esp
        movl    $1025, i
        movl    $524800, s
        pushl   $524800
        pushl   $.LC0
        pushl   $1
        call    __printf_chk
        movl    -4(%ebp), %ecx
        addl    $16, %esp
        leave
        leal    -4(%ecx), %esp
        ret
        .size   main, .-main
        .comm   i,4,4
        .comm   s,4,4
        .ident  "GCC: (GNU) 4.1.1 20070105 (ALT Linux, build 4.1.1-alt11)"
        .section        .note.GNU-stack,"",@progbits
Обращаю Ваше внимание на результаты оптимизации - цикл был полностью исключен из кода, а вместо него - рассчитанные самим компилятором значения:
Код: Выделить всё
        ...
        movl    $1025, i
        movl    $524800, s
        ...

На Паскале такого результата добиться не мог, это признаю. Но судя по Вашему примеру, Visual C++ тоже отдыхает ;)
xdsl
 
Сообщения: 1228
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Скорость работы эквивалентного кода на Си и Паскаль

Сообщение xdsl 21 дек 2008, 23:51

Дабы избежать шибко умной оптимизации компилятора GCC и сравнить скорость работы переборных программ на си и паскале, скомпилировал с оптимизацией и без нее следующий код:
Паскаль:
Код: Выделить всё
{$mode objfpc}
var i,k,m:longint;
    r:double;
begin
writeln('Test begin');
r:=0;
for i:=0 to 1000 do
  for k:=0 to 1000 do
   for m:=0 to 1000 do
     r:=r+i+k+m;
writeln('Test end', r);
end.

Си:
Код: Выделить всё
#include <stdio.h>
double r; long int i,k,m;
int main ()
{
puts("Test begin");
r=0.0;
for(i=0; i<=1000; i++)
  for(k=0; k<=1000; k++)
   for(m=0; m<=1000; m++)
     r=r+i+k+m;
printf("Test end: %f",r);
return 0;
}

Результаты - близки к ожидаемым. Скомпилировав программы без оптимизации (кроме регистровой), получил время выполнения ~14 секунд, причём программа на паскале стабильно быстрее сишной примерно на 0.2-0.3 секунды. Дальнейшая паскалевская оптимизация не дала практически ничего. Зато сишная привела к крайне резкому ускорению работы. Компиляция с опцией -O3 уменьшила время выполнения почти до 6 секунд. Сравнение ассемблерного кода с оптимизацией (gcc -O3 -S test.c) и без (gcc -S test.c и fpc -al test.pp) показал, что: 1. при оптимизации временный результат последовательных операций сложения r+i+k+m хранится в одном из регистров FPU, а без оптимизации - во временной области памяти. 2. в сишной программе при оптимизации значения всех переменных хранятся в регистрах, в том числе - и вещественной r (в одном из регистров FPU), а в паскалевской - значения только двух переменных (k и m). 3. много всего по мелочи (напр. вместо загрузки нулевой переменной в регистр процессора выполняется xor над регистром, и т.п.)

Вцелом делаю вывод, что компилятор GCC оптимизирует код много лучше компилятора fpc. В тоже время в отсутствие оптимизации паскалевский код часто более эффективен, чем сишный.
xdsl
 
Сообщения: 1228
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Скорость работы эквивалентного кода на Си и Паскаль

Сообщение Vladislav_133 22 дек 2008, 10:13

Да, я думаю, что надо сравнивать именно vc и gcc. Ну что же, проверим.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1254
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Скорость работы эквивалентного кода на Си и Паскаль

Сообщение Vladislav_133 23 дек 2008, 17:09

Дискуссия чрезвычайно интересна. Я чувствую, что закончится она защитой докторских диссертаций дискутирующими.

В начале о VC++. В нем существует оптимизация циклов. В данном случае оптимизация, подобная указанной Дм.Ан. происходит в случае использования локальных переменных. Т.е. если мы имеем программу

Код: Выделить всё
#include <stdio.h>
int main()
{
   int i,s;
   s=0;
   for(i=1; i<=1024; i++)
   {
      s=s+i;
   }
   printf("%d\n",s);
   return 0;
}

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

Да, и должно быть понятно, почему, например, если i - глобальная переменна, то нельзя заменять результат выполнения цикла константой. Дело в том, что все переменные, определенные вне функции считаются глобальными и внешними. Другими словами модификатор extern не используется. Таким образом предполагается, что объетный модуль и переменную i могут использовать из других модулей.

Далее. Я не поленился просидел часа три в Linux. Но к сожалению результата, который представил Дм.Ан. я не получил. А результаты вот какие (для gcc, нотация Intel благодаря дизассемблеру Ida Pro):

(для -O0)

Код: Выделить всё
.text:0804835C main            proc near               ; DATA XREF: _start+17o
.text:0804835C
.text:0804835C var_8           = dword ptr -8
.text:0804835C var_4           = dword ptr -4
.text:0804835C
.text:0804835C                 push    ebp
.text:0804835D                 mov     ebp, esp
.text:0804835F                 sub     esp, 8
.text:08048362                 and     esp, 0FFFFFFF0h
.text:08048365                 mov     eax, 0
.text:0804836A                 sub     esp, eax
.text:0804836C                 mov     [ebp+var_8], 0
.text:08048373                 mov     [ebp+var_4], 1
.text:0804837A
.text:0804837A loc_804837A:                            ; CODE XREF: main+36j
.text:0804837A                 cmp     [ebp+var_4], 400h
.text:08048381                 jle     short loc_8048385
.text:08048383                 jmp     short loc_8048394
.text:08048385 ; ---------------------------------------------------------------------------
.text:08048385
.text:08048385 loc_8048385:                            ; CODE XREF: main+25j
.text:08048385                 mov     eax, [ebp+var_4]
.text:08048388                 lea     edx, [ebp+var_8]
.text:0804838B                 add     [edx], eax
.text:0804838D                 lea     eax, [ebp+var_4]
.text:08048390                 inc     dword ptr [eax]
.text:08048392                 jmp     short loc_804837A
.text:08048394 ; ---------------------------------------------------------------------------
.text:08048394
.text:08048394 loc_8048394:                            ; CODE XREF: main+27j
.text:08048394                 sub     esp, 8
.text:08048397                 push    [ebp+var_8]
.text:0804839A                 push    offset aD       ; "%d\n"
.text:0804839F                 call    _printf
.text:080483A4                 add     esp, 10h
.text:080483A7                 mov     eax, 0
.text:080483AC                 leave
.text:080483AD                 retn
.text:080483AD main            endp

и

(для -O1,-O2,-O3)
Код: Выделить всё
.text:08048360 main            proc near               ; DATA XREF: _start+17o
.text:08048360                 push    ebp
.text:08048361                 mov     ebp, esp
.text:08048363                 mov     eax, 1
.text:08048368                 push    edx
.text:08048369                 push    edx
.text:0804836A                 and     esp, 0FFFFFFF0h
.text:0804836D                 xor     edx, edx
.text:0804836F                 nop
.text:08048370
.text:08048370 loc_8048370:                            ; CODE XREF: main+18j
.text:08048370                 add     edx, eax
.text:08048372                 inc     eax
.text:08048373                 cmp     eax, 400h
.text:08048378                 jle     short loc_8048370
.text:0804837A                 push    eax
.text:0804837B                 push    eax
.text:0804837C                 push    edx
.text:0804837D                 push    offset aD       ; "%d\n"
.text:08048382                 call    _printf
.text:08048387                 leave
.text:08048388                 xor     eax, eax
.text:0804838A                 retn
.text:0804838A main            endp

Они практически полностью совпадают с ранее представленными результатами для VC++ но с глобальными переменными. А здесь переменные были локальны, но нужного результата я не получил. Проверил я и с глобальными переменными также. Кроме этого проверил компилятор c++ - результат тот же. Скорее всего у меня старая версия компилятора. Так что жду новых версий.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1254
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Скорость работы эквивалентного кода на Си и Паскаль

Сообщение xdsl 23 дек 2008, 22:49

Хотелось-бы увидеть результат вывода gcc -v
Дело в том, что оптимизация зависит от версии компилятора. У меня в репозитарии их два - 3.4 и 4.1. Пользуюсь, естественно, последним.
Еще хотелось-бы знать, где именно проверяете линуксовый вариант. Если на Вашем личном виртуальном сервере в институте, то могу подсказать, что и как установить.

Проверил все еще раз. С помощью objdump -d дизассемблировал полученный исполняемый файл и получил те-же самые результаты - цикл преобразуется в два присвоения.
xdsl
 
Сообщения: 1228
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Скорость работы эквивалентного кода на Си и Паскаль

Сообщение xdsl 23 дек 2008, 23:01

И еще момент, связанный с глобальными переменными. На мой взгляд, цикл должен преобразовываться в два присвоения вне зависимости от использования глобальных или локальных переменных, т.к. результат вычисления никоим образом не зависит от области видимости переменной. Обеим переменным присваиваются первоначальные значения до начала цикла. По окончании цикла - в обеих переменных конкретные значения, на которые не могут повлиять никакие внешние модули, пока поток выполнения - единственный.
xdsl
 
Сообщения: 1228
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Скорость работы эквивалентного кода на Си и Паскаль

Сообщение xdsl 23 дек 2008, 23:20

С углублением в тему уже захотелось проверить оптимизацию, которую обеспечивает VC++. У майкрософт есть бесплатный вариант их компилятора? Если есть - где скачать?
xdsl
 
Сообщения: 1228
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Скорость работы эквивалентного кода на Си и Паскаль

Сообщение alekam 24 мар 2009, 00:15

У MS бесплатные версии девелоперских продуктов называются Express Edition. Скачать можно отсюда http://www.microsoft.com/express/download/
.. ну или взять на кафедре ПСТ.
alekam
 
Сообщения: 46
Зарегистрирован: 23 дек 2008, 14:36
Полное имя: A.K.

Re: Скорость работы эквивалентного кода на Си и Паскаль

Сообщение xdsl 24 мар 2009, 08:23

alekam писал(а):.. ну или взять на кафедре ПСТ.
Уел ;)
xdsl
 
Сообщения: 1228
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.


Вернуться в Алгоритмизация и программирование

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1

cron