Интересное исследование

← →
... (2013-12-23 11:29) [0]

http://codeforces.ru/blog/entry/10024

← →
icelex © (2013-12-23 12:35) [1]

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

← →
antonn © (2013-12-23 12:40) [2]

повод порадоваться за старичка D7? :)

← →
jack128_ (2013-12-23 13:27) [3]

Походу у дельфи большие проблемы с вещественными числами.
На массиве интов она всего процентов на 15% медленнее сишного варианта, а вот на массиве double"ов более чем в два раза.

← →
sniknik © (2013-12-23 13:33) [4]

> а вот на массиве double"ов более чем в два раза.
а сравнивать надо бы с Extended т.к. к double в дельфе делается преобразование. а в С возможно "найтивное" именно double.

хотя... все это чушь, сила в алгоритмах.

← →
jumping jack (2013-12-23 13:47) [5]

все давно перевели "плавучку" на SSE, а в дельфи - по старинке - FPU (x87)
хотя вроде в SSE нету extended - так его вообще мало кто поддерживает (у MS ни в C++, ни в .NET его нет)

← →
jack128_ (2013-12-23 14:52) [6]

> а сравнивать надо бы с Extended

Extended - еще тормознее

← →
DVM © (2013-12-23 14:53) [7]

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

Как можно сравнивать совершенно по разному написанный код? Например, Си шный вариант и дельфийский не одинаковы.

Все это ерунда, правильно сказали, сила в алгоритмах.

← →
DVM © (2013-12-23 14:54) [8]

> jack128_ (23.12.13 14:52) [6]

Почему он тормознее? И Double и Single к нему приводятся и потом усекаются обратно после выполнения действий. Должно быстрее быть чуть.

← →
Inovet © (2013-12-23 14:56) [9]

> [8] DVM © (23.12.13 14:54)
> Почему он тормознее?

10 байт неудобно читать.

← →
jack128_ (2013-12-23 14:56) [10]

> Почему он тормознее? И Double и Single к нему приводятся
> и потом усекаются обратно после выполнения действий. Должно
> быстрее быть чут

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

← →
Pavia © (2013-12-23 15:11) [11]

> Почему он тормознее? И Double и Single к нему приводятся
> и потом усекаются обратно после выполнения действий. Должно
> быстрее быть чуть.

Вот именно зачем лишнее действие по приведению? Тем более которое занимает несколько десяток тактов?
Поэтому Single быстрее.

← →
DVM © (2013-12-23 15:14) [12]

Если забыть про Double, а рассматривать вариант с Integer, то дельфийский вариант программы имеет больше операций индексации массива, чем вариант си, а каждая такая операция есть умножение. Пусть это и крохи, но при 10 млн повторений даст как раз разницу в эти 15 %

← →
Pavia © (2013-12-23 15:14) [13]

> 10 байт неудобно читать.

Дело не в удобности. А в точности. Чем точность ниже тем быстрее. Поэтому в скорости выигрывает Single Integer double Int64 Extended.

← →
jack128_ (2013-12-23 17:25) [14]

> а рассматривать вариант с Integer, то дельфийский вариант
> программы имеет больше операций индексации массива, чем
> вариант си, а каждая такая операция есть умножение. Пусть
> это и крохи, но при 10 млн повторений даст как раз разницу
> в эти 15 %

не-а. 15% не из-за этого. Более того, если кол-во индексаций в дельфи больше только из того, что автор дельфийского кода руками заинлайнил swap. Если же написать swap ручками и использовать его - то дельфийский результат еще больше ухудшится.

← →
DVM © (2013-12-23 17:54) [15]

> jack128_ (23.12.13 17:25) [14]

> Более того, если кол-во индексаций в дельфи больше только
> из того, что автор дельфийского кода руками заинлайнил swap.
>

Со swap меньше операций индексации. Туда (в swap) уже вычисленные два элемента массива по их индексам передаются по ссылкам и там обмениваются, плюс вся эта кухня в си наверняка заинлайнится (или это вообще макрос?), что внутри swap находится я не знаю, возможно там что типа ассемблерной команды XCHG (прошу прощения я асм не знаю).

В варианте с Делфи индекс вычисляется 4 раза на каждый такой обмен, а в сишном варианте 2 раза + 3 присваивания. И таких мест в коде 2 штуке.

Дело конечно не только в этом, там еще есть и другие отличия, но в целом в 15% все это складывается запросто.

Да из-за чего понятно,

← →
Rouse_ © (2013-12-23 18:16) [16]

> Дело конечно не только в этом, там еще есть и другие отличия,
> но в целом в 15% все это складывается запросто.

Я ж вроде сказал, что в дельфе свап только увеличивает время работы. УВЕЛИЧИВАЕТ. В асм код не смотрел, но скорее всего это потому что дельфя нормально инлайнить не умеет.

← →
Rouse_ © (2013-12-23 18:20) [17]

> Rouse_ ©

Это jack128_

← →
DVM © (2013-12-23 18:22) [18]

Странно, у меня Swap32_1 работает быстрее Swap32 раз в 5. Даже без инлайна. Или я где то ошибся?

procedure Swap32(var A, B: LongWord); asm MOV ECX,[EAX] XCHG ECX,[EDX] MOV [EAX],ECX end; procedure Swap32_1(var A, B: LongWord); var X: LongWord; begin X := A; A := B; B := X; end;

← →
Rouse_ © (2013-12-23 18:36) [19]

чесно говоря хз.
Завтра выложу свой код.

← →
Sapersky (2013-12-23 19:09) [20]

По плавающей точке, точность расчётов для Double/Single можно принудительно снизить через FPU control word. В сети есть документ Coding for speed in Delphi, там всё расписано. Но в целом да, x86 компилятор плохо оптимизирует операции с FPU.
В x64 компиляторе используется SSE (без векторизации), стало лучше, но не принципиально. У меня рекурсивный гауссовский фильтр ускорился на 20-25%.

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

mov eax, [esi+edx*4] вроде бы не умножение? Просто режим адресации такой.
И откуда 15%? Одинаково же (С++ => 630, Delphi 7 => 630).

← →
Anatoly Podgoretsky © (2013-12-23 20:15) [21]

> сила в алгоритмах.

Сила в Ньютонах

← →
DVM © (2013-12-23 23:00) [22]

> Sapersky (23.12.13 19:09) [20]

> mov eax, [esi+edx*4] вроде бы не умножение? Просто режим
> адресации такой.

Обращение к n-ому элементу массива, если n неизвестно на этапе компиляции в любом случае потребует дополнительных инструкций для вычисления смещения от начала. Это будет либо умножение n на размер элемента массива или замена умножения на другие эквивалентные операции, но индексация бесплатной не будет все равно.

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

← →
Rouse_ © (2013-12-23 23:02) [23]

> Rouse_ © (23.12.13 18:36) [19]
> чесно говоря хз.
> Завтра выложу свой код.

С моим логином был Jack128 и похоже я его завтра грохну, раз он не научился перелогиниваться :)

← →
DVM © (2013-12-23 23:18) [24]

> Rouse_ © (23.12.13 23:02) [23]

> и похоже я его завтра грохну

логин или джека?

← →
Sapersky (2013-12-24 01:45) [26]

> Обращение к n-ому элементу массива, если n неизвестно на
> этапе компиляции в любом случае потребует дополнительных
> инструкций для вычисления смещения от начала. Это будет
> либо умножение n на размер элемента массива или замена умножения
> на другие эквивалентные операции, но индексация бесплатной
> не будет все равно.

У mov, если судить по таблицам Агнера Фога, сложная индексация бесплатная (указаны одинаковые такты для "all adressing modes"), при этом можно делать умножение на 2,4,8 и т.д. и два сложения. Если размер элемента "некруглый", без умножения не обойтись, но компилятор проявляет завидную изворотливость, пытаясь заменить его на lea или сдвиги-сложения-вычитания. И по крайней мере в моём примере компилятор сообразил сделать это псевдоумножение один раз на итерацию, так что оно совершенно не чувствуется.

procedure xQuickSoft24(Bmp:TFastDIB); { var a,b,c: PFColor; x,y: Integer; begin a:=Pointer(Bmp.Bits); b := a; Inc(b); c := b; Inc(c); for y:=0 to Bmp.AbsHeight-1 do begin a.b:=(a.b+b.b)shr 1; a.g:=(a.g+b.g)shr 1; a.r:=(a.r+b.r)shr 1; for x:=0 to Bmp.Width-3 do begin b.b:=(a.b+c.b)shr 1; b.g:=(a.g+c.g)shr 1; b.r:=(a.r+c.r)shr 1; Inc(a); Inc(b); Inc(c); end; b.b:=(b.b+a.b)shr 1; b.g:=(b.g+a.g)shr 1; b.r:=(b.r+a.r)shr 1; a:=PFColor(NativeInt(a)+Bmp.Gap+6); b:=PFColor(NativeInt(b)+Bmp.Gap+6); c:=PFColor(NativeInt(c)+Bmp.Gap+6); end; } var // same speed, but more understandable ln : PLine24; x,y: Integer; begin for y:=0 to Bmp.AbsHeight-1 do begin ln := Bmp.Scanlines[y]; ln[0].b := (ln[0].b + ln[1].b) shr 1; ln[0].g := (ln[0].g + ln[1].g) shr 1; ln[0].r := (ln[0].r + ln[1].r) shr 1; for x:=1 to Bmp.Width-2 do begin ln[x].b := (ln[x-1].b + ln[x+1].b) shr 1; ln[x].g := (ln[x-1].g + ln[x+1].g) shr 1; ln[x].r := (ln[x-1].r + ln[x+1].r) shr 1; end; x := Bmp.Width-1; ln[x].b := (ln[x-1].b + ln[x].b) shr 1; ln[x].g := (ln[x-1].g + ln[x].g) shr 1; ln[x].r := (ln[x-1].r + ln[x].r) shr 1; end; end;

Иногда выгоднее смешанный метод:
ln[1].b := (ln[0].b + ln[2].b) shr 1;
Inc(PFColor(ln));

← →
jumping jack (2013-12-24 03:04) [27]

DVM> Странно, у меня Swap32_1 работает быстрее Swap32 раз в 5. Даже без инлайна. Или я где то ошибся?

а в окно ЦПУ заглянуть - что тебе компилятор накомпилировал?
push ebx mov ecx, [eax] mov ebx, [edx] mov [eax], ebx mov [edx], ecx pop ebxкак ни странно, это действительно в 5 раз быстрее
вот и верь после этого в ассемблерную оптимизацию :)

← →
Sapersky (2013-12-24 03:19) [28]

"The XCHG register,[memory] instruction is dangerous. This instruction always has an implicit LOCK prefix which forces synchronization with other processors or cores. This instruction is therefore very time consuming, and should always be avoided unless the lock is intended."
http://www.agner.org/optimize/optimizing_assembly.pdf

Сила в правде!

> jumping jack (24.12.13 03:04) [27]

> а в окно ЦПУ заглянуть - что тебе компилятор накомпилировал?

Конечно заглянул, потому и удивило - инструкций больше в два раза, а работает быстрее в 5 раз. Мне раньше казалось, что XCHG быстрее должна быть, но ссылка Sapersky (24.12.13 03:19) [28] все проясняет.

> вот и верь после этого в ассемблерную оптимизацию :)

я в нее никогда особо и не верил, по крайней мере в свою :)

> Sapersky (24.12.13 01:45) [26]

> У mov, если судить по таблицам Агнера Фога, сложная индексация
> бесплатная (указаны одинаковые такты для "all adressing
> modes"), при этом можно делать умножение на 2,4,8 и т.д.
> и два сложения.

Понятно, спасибо.

← →
jack128_ (2013-12-24 10:42) [33]

> И откуда 15%? Одинаково же (С++ => 630, Delphi 7 => 630).

из моего личного теста. В статье для измерения времени в плюсовом варианте используется сишная функция clock(), но она начинает измерение со старта программы, соответсвенно какое то время уходит на инициализацию рантайма. В дельфийском варианте измеряется только время непосредственно работы алгоритма.
Вот мой вариант сишного кода http://pastebin.com/R9CqJx58
а вот дельфйского http://pastebin.com/VbW9cEyb
Страждущие могут поиграть дефайнами чтоб увидеть, как меняется скорость в зависимости от типов данных и использования swap"а

> Inovet © (24.12.13 10:41) [32]
> > [31] DVM © (24.12.13 10:25)
> > при этом можно делать умножение на 2,4,8 и т.д.
>
> На 10 нельзя.

Это наверное не мне, а Sapersky. А по теме, да, только 2,4,8.

> [34] DVM © (24.12.13 10:49)

Ну так это к вопросу об массиве extended. А так-то да, это умножение делается аппаратно, скорее всего простым переключением разрядов одновременно с остальным вычислением адреса. Т.е. дополнительного времени оно не должно занимать.

Интересное исследование Найти похожие ветки