---

Ostehapsen wrote:

> Claus Rasmussen wrote:
>
>> Faktisk er reglen, at man bør afholde sig fra optimeringer på det niveau.
>
> Jeg er usikker på hvad du mener med "det niveau",

"Det niveau" består af alle de små smarte ting, du kan lave med pre/postfix
in/decrement, operator-and-assign (+=) og pointere.


> Hvis en ud af fem maskinkodeoperationer i en tæt løkke kan spares uden at
> rode med maskinkode, så er det vel værd at tage med?

Ja _hvis_ du sparer operationer, men det gør du bare /ikke/ ! Kompileren
er på de fleste områder meget snuere end dig - undtagen når du "optimerer"
din kode så meget, at den ikke længere kan rede trådene ud igen.

Jeg har vedhæftet to programmer. Det første er et C++ program, der har tre
varianter af den samme løkke:

Først den "rene" version:

for (long i = 0; i < SIZE; ++i) {
a[i] = a[i] * 2000;
a[i] = a[i] / 10000;
}

Så en version, hvor vi bruger pointere i stedet for index, og hvor vi bruger
operatorerne '*=' og '/=' :

int* p = a;
for (long i = 0; i < SIZE; ++i) {
*p *= 2000;
*p /= 10000;
++p;
}

Endelig en version, hvor vi også bruger pointere til at styre loopet:

int* end = a + SIZE;
for (int* p = a; p != end; ++p) {
*p *= 2000;
*p /= 10000;
}

Hvilken version er hurtigst ?


Jeg har også vedlagt et (linux) shell script, der måler tidsforbruget for
de tre versioner. Når man kører det, får man flg. resultat (i 1/100s):

Straight version : 335
Optimized version : 343
Extra optimized version: 341

Den "rene" version er hurtigst !!


Hvorfor ? Jo fordi du med disse "optimeringer" berøver kompileren den
information, den skal bruge for at gøre arbejdet bedre end du kan.

I den rene version af koden, ser kompileren straks, at "a[i]" refererer
den samme variabel overalt i det indre loop. Den behøves derfor ikke at
loade "a[i]" mere end een gang, og den behøver heller ikke at skrive
værdien af "a[i]" til lageret mere end een gang.

I de optimerede version af koden er kompileren ikke længere i stand til
at se at "*p" hele tiden peger på det samme element i array'et. Den
genererer derfor kode som om det første og det sidste "*p" refererede
forskellige variable.

Det kan du simpelthen ikke vide på forhånd (med mindre du selv har skrevet
kompileren) - derfor vil dine optimeringer i bedste fald ikke gøre nogen
forskel og i værste fald blot gøre dit program langsommere.

Du kan finde resultater for andre platforme her:

http://www.daimi.au.dk/~mis/dOvs/sli36.ps
http://www.daimi.au.dk/~mis/dOvs/sli36.pdf

Bladr ned til side 15-16 i .ps versionen.

-Claus

-c++ program---------------------------------------------------------------

#include <iostream>
#include <string>

// Size of array - choose a size that does not make your machine swap
#define SIZE 1000000

// Number of times to redo the test
#define REDO 100

int main(int argc, char** argv) {
int* a = new int[SIZE];

cout << "Initializing" << endl;
for (long i = 0; i < SIZE; ++i)
a[i] = i + 1;

if (argc == 2)
if (strcmp(argv[1], "straight") == 0) {
cout << "Iterating (straight)" << endl;

for (int j = 0; j < REDO; ++j)
for (long i = 0; i < SIZE; ++i) {
a[i] = a[i] * 2000;
a[i] = a[i] / 10000;
}

} else if (strcmp(argv[1], "optimized") == 0) {
cout << "Iterating (\"optimized\")" << endl;

for (int j = 0; j < REDO; ++j) {
int* p = a;

for (long i = 0; i < SIZE; ++i) {
*p *= 2000;
*p /= 10000;
++p;
}
}

} else if (strcmp(argv[1], "extra") == 0) {
cout << "Iterating (\"extra\")" << endl;

int* end = a + SIZE;

for (int j = 0; j < REDO; ++j)
for (int* p = a; p != end; ++p) {
*p *= 2000;
*p /= 10000;
}

} else {
cerr << argv[0] << ": Illegal argument: '" << argv[1] << "'"
<< endl
<< "Usage: " << argv[0] << " [straight|optimized|extra]"
<< endl;
return 1;
}
}

-shell script (finder den bedste tid af 100 kørsler)-----------------------

redo=100

for opt in straight optimized extra
do for (( i = 0; $i < $redo; i = $i + 1 ))
do echo -ne "$opt: $(( $i + 1 ))\r" >&2
/usr/bin/time -f "%U" a.out $opt 2>&1 >/dev/null
done \
| sort \
| sed -n -e 's/\.//' -e 's/^00*//' -e 1p
echo >&2
done \
| {
read straight
read optimized
read extra

echo "Straight version : $straight"
echo "Optimized version : $optimized"
echo "Extra optimized version: $extra"
}

---

"Claus Rasmussen" <clr@cc-consult.dk> wrote

> Jeg har også vedlagt et (linux) shell script, der måler tidsforbruget for
> de tre versioner. Når man kører det, får man flg. resultat (i 1/100s):
>
> Straight version : 335
> Optimized version : 343
> Extra optimized version: 341
>
> Den "rene" version er hurtigst !!
>

Et praktisk taget tilsvarende program under MS-Windows 2000 oversat med
Intel C++ V5.01 med release optimering slået til, giver:
Straight: 81155099
Optimized: 81534725
Extra: 81083551

Et praktisk taget tilsvarende program under MS-Windows 2000 oversat med
Microsoft Visual C++ V6.0 med release optimering slået til, giver:
Straight: 90097032
Optimized: 87239090
Extra: 85964825

Enheden er clock-ticks.
Begge compilere anses normalt for at generere god kode.

Den ekstra optimerede version er den hurtigste med begge compilere. Ikke
meget, men dog hurtigst.

Min konklussion er at man ved ikke hvilken funktion der er hurtigst uden at
have målt det, på den relevante compiler og platform.
Jeg er naturligvis enig i at man skal først og fremmest skrive koden
tydeligt.
Jeg mener naturligvis også, at hvis man performance optimerer skal man måle
før man starter og når man er færdig, for at være sikker på at man faktisk
har lavet en optimering.

Desuden syntes jeg at "extra" udgaven er lige så klart skrevet som
"straight" udgaven.



>
> Det kan du simpelthen ikke vide på forhånd (med mindre du selv har skrevet
> kompileren) - derfor vil dine optimeringer i bedste fald ikke gøre nogen
> forskel og i værste fald blot gøre dit program langsommere.
>

I bedste fald bliver programmet hurtigere.
I værste fald bliver programmet langsommere.


Venlig hilsen

Mogens Hansen

PS.
Det test program som jeg anvendte er

#include <iostream>
#include <cstddef>
#include <vector>
#include <windows.h>

using namespace std;

// ARRAY_SIZE of array - choose a ARRAY_SIZE that does not make your machine
swap
const size_t ARRAY_SIZE = 1000000;

// Number of times to redo the test
const unsigned REDO = 4;

void init(int* a)
{
for (long i = 0; ARRAY_SIZE != i ; ++i)
a[i] = i + 1;
}

void straigth(int* a)
{
for (int j = 0; REDO != j ; ++j)
for (long i = 0; ARRAY_SIZE != i; ++i) {
a[i] = a[i] * 2000;
a[i] = a[i] / 10000;
}
}

void optimized(int* a)
{
for (int j = 0; REDO != j ; ++j) {
int* p = a;
for (long i = 0; ARRAY_SIZE != i; ++i) {
*p *= 2000;
*p /= 10000;
++p;
}
}
}

void extra(int* a)
{
const int* end = a + ARRAY_SIZE;
for (int j = 0; REDO != j ; ++j) {
for (int* p = a; p != end; ++p) {
*p *= 2000;
*p /= 10000;
}
}
}

int main(void)
{
::SetProcessAffinityMask(::GetCurrentProcess(), 0x01);
vector<int> array(ARRAY_SIZE);
int* a = &*array.begin();
LARGE_INTEGER start;
LARGE_INTEGER straigth_end, opt_end, extra_end;
int straigth_dur, opt_dur, extra_dur;


do {
init(a);
QueryPerformanceCounter(&start);
straigth(a);
QueryPerformanceCounter(&straigth_end);
} while (start.HighPart != straigth_end.HighPart);
straigth_dur = straigth_end.LowPart - start.LowPart;

do {
init(a);
QueryPerformanceCounter(&start);
optimized(a);
QueryPerformanceCounter(&opt_end);
} while (start.HighPart != opt_end.HighPart);
opt_dur = opt_end.LowPart - start.LowPart;


do {
init(a);
QueryPerformanceCounter(&start);
extra(a);
QueryPerformanceCounter(&extra_end);
} while (start.HighPart != extra_end.HighPart);
extra_dur = extra_end.LowPart - start.LowPart;

cout << "Straight: " << straigth_dur << "\n"
"Optimized: " << opt_dur << "\n"
"Extra: " << extra_dur << endl;

return 0;
}

---

Mogens Hansen wrote:

[saks udemærket eksempel på Windows]

Jeg lurer lidt på den måde, du måler performance. Clock tics - omfatter
det clock tics forbrugt af operativsystemet, når programmet laver
systemkald ?

Hvis ja, så afhænger dit resultat af, hvordan Windows håndterer allokering
af dynamisk memory. På linux sker der nemlig det, at allokeringen faktisk
først sker, når du bruger lageret. Så kommer der en page fault ogoperativ-
systemet giver sig til at knalde en masse cykler af på at allokere lageret.
I dit eksempel ville det være det derfor være straight versionen, der tog
hugget.

Den tid, jeg målte på linux, var kun den tid, som programmet selv brugte.

Prøv forresten som et ekstra tjek at køre programmet flere gange, og se
om du får det samme antal cykler.

[...]

> Et praktisk taget tilsvarende program under MS-Windows 2000 oversat med
> Intel C++ V5.01 med release optimering slået til, giver:
> Straight: 81155099
> Optimized: 81534725
> Extra: 81083551
>
> Et praktisk taget tilsvarende program under MS-Windows 2000 oversat med
> Microsoft Visual C++ V6.0 med release optimering slået til, giver:
> Straight: 90097032
> Optimized: 87239090
> Extra: 85964825

Rimeligt sej, den der Intel kompiler

-Claus

---

"Claus Rasmussen" <clr@cc-consult.dk> skrev i en meddelelse
news:a0mpjm$esb$1@sunsite.dk...
> Mogens Hansen wrote:
>
[klip]
> Hvis ja, så afhænger dit resultat af, hvordan Windows håndterer allokering
> af dynamisk memory. På linux sker der nemlig det, at allokeringen faktisk
> først sker, når du bruger lageret. Så kommer der en page fault ogoperativ-
> systemet giver sig til at knalde en masse cykler af på at allokere
lageret.
> I dit eksempel ville det være det derfor være straight versionen, der tog
> hugget.

Burde det ikke være kaldet til init() som forårsagede denne page-fault?

> Den tid, jeg målte på linux, var kun den tid, som programmet selv brugte.

[klip]
> > Et praktisk taget tilsvarende program under MS-Windows 2000 oversat med
> > Intel C++ V5.01 med release optimering slået til, giver:
> > Straight: 81155099
> > Optimized: 81534725
> > Extra: 81083551
[klip]
> Rimeligt sej, den der Intel kompiler

Har Intel-oversætteren noget der tilsvarer -S i gcc og /FA i Visual C++, så
der spyttes assembler ud? Det kunne være interessant at sammenligne de indre
løkker som VC++ og IC++ genererer dem, når der er så ganske markant forskel
i køretiden.

Hilsen Anders

---

Anders Borum wrote:

>> I dit eksempel ville det være det derfor være straight versionen, der tog
>> hugget.
>
> Burde det ikke være kaldet til init() som forårsagede denne page-fault?

Jeg har åbenbart haft en mindre hjerneblødning, da jeg skrev det. Jo,
naturligvis: Init-loopet accesser jo netop alle dele af det allokerede
lager

[...]

> Har Intel-oversætteren noget der tilsvarer -S i gcc og /FA i Visual C++,
> så der spyttes assembler ud? Det kunne være interessant at sammenligne de
> indre løkker som VC++ og IC++ genererer dem, når der er så ganske markant
> forskel i køretiden.

Det har den sikkert, men jeg har kun hørt om den. Jeg synes også, at der
er voldsom stor forskel: 10% for et så lille program !

-Claus

---

"Anders Borum" <aborum@hotmail.com> wrote
>
> Har Intel-oversætteren noget der tilsvarer -S i gcc og /FA i Visual C++,
så
> der spyttes assembler ud? Det kunne være interessant at sammenligne de
indre
> løkker som VC++ og IC++ genererer dem, når der er så ganske markant
forskel
> i køretiden.

Ja.
Men jeg syntes det er extremt svært at forudsige performance, selv med et
værktøj som Intel VTune der kan lave en statisk analyse i forhold til
forskellige Intel CPUer.
Moderne CPUer er ekstremt komplicerede med flere pipe-lines, cache etc.

Intel C++ V5.01:

; COMDAT ?straigth@@YAXPAH@Z
; -- Begin ?straigth@@YAXPAH@Z
; mark_begin;
ALIGN 4
; parameter 1(a): 8 + esp
PUBLIC ?straigth@@YAXPAH@Z
?straigth@@YAXPAH@Z PROC NEAR
$B2$1: ; Preds $B2$0
$LN10:

;;; {

push edi ;21.1
push esi ;21.1
push ebp ;21.1
push ebx ;21.1
push esi ;21.1
$LN11:
mov eax, DWORD PTR [esp+24] ;20.6
$LN12:

;;; for (int j = 0; REDO != j ; ++j)

xor ecx, ecx ;22.11
mov ebp, eax ;22.11
; LOE ecx ebp
$B2$2: ; Preds $B2$1 $B2$4
$LN13:

;;; for (long i = 0; ARRAY_SIZE != i; ++i) {

mov esi, ebp ;23.13
lea edi, DWORD PTR [ebp+4000000] ;23.13

; LOE ecx ebp esi edi
$B2$3: ; Preds $B2$2 $B2$3
$LN14:

;;; a[i] = a[i] * 2000;

mov edx, DWORD PTR [esi] ;24.11
imul ebx, edx, 2000 ;24.11
$LN15:

;;; a[i] = a[i] / 10000;

mov eax, 1759218605 ;25.11
imul ebx ;25.11
sar edx, 12 ;25.11
sar ebx, 31 ;25.11
sub edx, ebx ;25.11
$LN16:
mov DWORD PTR [esi], edx ;25.4
$LN17:
add esi, 4 ;23.39
$LN18:
cmp edi, esi ;23.3
jne $B2$3 ; Prob 90% ;23.3
; LOE ecx ebp esi edi
$B2$4: ; Preds $B2$3
$LN19:
inc ecx ;22.32
$LN20:
cmp ecx, 50 ;22.2
jne $B2$2 ; Prob 90% ;22.2
; LOE ecx ebp
$B2$5: ; Preds $B2$4
$LN21:

;;; }
;;; }

add esp, 4 ;27.1
pop ebx ;27.1
pop ebp ;27.1
pop esi ;27.1
pop edi ;27.1
ret ;27.1
ALIGN 4
; LOE
; mark_end;
?straigth@@YAXPAH@Z ENDP
;?straigth@@YAXPAH@Z ENDS
_TEXT ENDS
_DATA SEGMENT PARA PUBLIC USE32 'DATA'
_DATA ENDS
; -- End ?straigth@@YAXPAH@Z
_TEXT SEGMENT PARA PUBLIC USE32 'CODE'
; COMDAT ?optimized@@YAXPAH@Z
; -- Begin ?optimized@@YAXPAH@Z
; mark_begin;
ALIGN 4
; parameter 1(a): 8 + esp
PUBLIC ?optimized@@YAXPAH@Z
?optimized@@YAXPAH@Z PROC NEAR
$B3$1: ; Preds $B3$0
$LN22:

;;; {

push edi ;30.1
push esi ;30.1
push ebp ;30.1
push ebx ;30.1
push esi ;30.1
$LN23:
mov eax, DWORD PTR [esp+24] ;29.6
$LN24:

;;; for (int j = 0; REDO != j ; ++j) {

xor ecx, ecx ;31.11
mov ebp, eax ;31.11
; LOE ecx ebp
$B3$2: ; Preds $B3$1 $B3$4
$LN25:
mov esi, ebp ;30.1
$LN26:

;;; int* p = a;
;;; for (long i = 0; ARRAY_SIZE != i; ++i) {

xor edi, edi ;33.13

; LOE ecx ebp esi edi
$B3$3: ; Preds $B3$2 $B3$3
$LN27:

;;; *p *= 2000;

mov edx, DWORD PTR [esi] ;34.4
imul ebx, edx, 2000 ;34.4
$LN28:

;;; *p /= 10000;

mov eax, 1759218605 ;35.4
$LN29:
inc edi ;33.39
$LN30:
imul ebx ;35.4
sar edx, 12 ;35.4
sar ebx, 31 ;35.4
sub edx, ebx ;35.4
mov DWORD PTR [esi], edx ;35.4
$LN31:

;;; ++p;

add esi, 4 ;36.6
$LN32:
cmp edi, 1000000 ;33.3
jne $B3$3 ; Prob 90% ;33.3
; LOE ecx ebp esi edi
$B3$4: ; Preds $B3$3
$LN33:
inc ecx ;31.32
$LN34:
cmp ecx, 50 ;31.2
jne $B3$2 ; Prob 90% ;31.2
; LOE ecx ebp
$B3$5: ; Preds $B3$4
$LN35:

;;; }
;;; }
;;; }

add esp, 4 ;39.1
pop ebx ;39.1
pop ebp ;39.1
pop esi ;39.1
pop edi ;39.1
ret ;39.1
ALIGN 4
; LOE
; mark_end;
?optimized@@YAXPAH@Z ENDP
;?optimized@@YAXPAH@Z ENDS
_TEXT ENDS
_DATA SEGMENT PARA PUBLIC USE32 'DATA'
_DATA ENDS
; -- End ?optimized@@YAXPAH@Z
_TEXT SEGMENT PARA PUBLIC USE32 'CODE'
; COMDAT ?extra@@YAXPAH@Z
; -- Begin ?extra@@YAXPAH@Z
; mark_begin;
ALIGN 4
; parameter 1(a): 8 + esp
PUBLIC ?extra@@YAXPAH@Z
?extra@@YAXPAH@Z PROC NEAR
$B4$1: ; Preds $B4$0
$LN36:

;;; {

push edi ;42.1
push esi ;42.1
push ebp ;42.1
push ebx ;42.1
push esi ;42.1
$LN37:
mov edx, DWORD PTR [esp+24] ;41.6
$LN38:

;;; const int* end = a + ARRAY_SIZE;

lea eax, DWORD PTR [edx+4000000] ;43.19
$LN39:

;;; for (int j = 0; REDO != j ; ++j) {

xor ecx, ecx ;44.11
mov ebx, eax ;44.11
mov ebp, edx ;44.11
; LOE ecx ebx ebp
$B4$2: ; Preds $B4$1 $B4$6
$LN40:
mov esi, ebp ;42.1
$LN41:

;;; for (int* p = a; p != end; ++p) {

inc ecx ;45.3

; LOE ecx ebx ebp esi
$B4$4: ; Preds $B4$2 $B4$4
$LN42:

;;; *p *= 2000;

mov edi, DWORD PTR [esi] ;46.4
imul edi, edi, 2000 ;46.4
$LN43:

;;; *p /= 10000;

mov eax, 1759218605 ;47.4
imul edi ;47.4
sar edx, 12 ;47.4
sar edi, 31 ;47.4
sub edx, edi ;47.4
mov DWORD PTR [esi], edx ;47.4
$LN44:
add esi, 4 ;45.32
$LN45:
cmp esi, ebx ;45.3
jne $B4$4 ; Prob 98% ;45.3
; LOE ecx ebx ebp esi
$B4$6: ; Preds $B4$4
$LN46:
cmp ecx, 50 ;44.2
jne $B4$2 ; Prob 90% ;44.2
; LOE ecx ebx ebp
$B4$7: ; Preds $B4$6
$LN47:

;;; }
;;; }
;;; }

add esp, 4 ;50.1
pop ebx ;50.1
pop ebp ;50.1
pop esi ;50.1
pop edi ;50.1
ret ;50.1
ALIGN 4
; LOE
; mark_end;
?extra@@YAXPAH@Z ENDP
;?extra@@YAXPAH@Z ENDS



Microsoft Visual C++:
?straigth@@YAXPAH@Z PROC NEAR ; straigth, COMDAT

; 21 : {

push ebx

; 22 : for (int j = 0; REDO != j ; ++j)

mov ebx, DWORD PTR _a$[esp]
push ebp
push esi
push edi
mov ebp, 50 ; 00000032H
$L49783:

; 23 : for (long i = 0; ARRAY_SIZE != i; ++i) {

mov esi, ebx
mov edi, 1000000 ; 000f4240H
$L49787:

; 24 : a[i] = a[i] * 2000;

mov eax, DWORD PTR [esi]
add esi, 4
lea eax, DWORD PTR [eax+eax*4]
lea eax, DWORD PTR [eax+eax*4]
lea ecx, DWORD PTR [eax+eax*4]

; 25 : a[i] = a[i] / 10000;

mov eax, 1759218605 ; 68db8badH
shl ecx, 4
imul ecx
sar edx, 12 ; 0000000cH
mov eax, edx
shr eax, 31 ; 0000001fH
add edx, eax
dec edi
mov DWORD PTR [esi-4], edx
jne SHORT $L49787

; 22 : for (int j = 0; REDO != j ; ++j)

dec ebp
jne SHORT $L49783
pop edi
pop esi
pop ebp
pop ebx

; 26 : }
; 27 : }

ret 0
?straigth@@YAXPAH@Z ENDP ; straigth
_TEXT ENDS
PUBLIC ?optimized@@YAXPAH@Z ; optimized
; COMDAT ?optimized@@YAXPAH@Z
_TEXT SEGMENT
_a$ = 8
?optimized@@YAXPAH@Z PROC NEAR ; optimized, COMDAT

; 30 : {

push ebx

; 31 : for (int j = 0; REDO != j ; ++j) {

mov ebx, DWORD PTR _a$[esp]
push ebp
push esi
push edi
mov ebp, 50 ; 00000032H
$L49794:

; 32 : int* p = a;

mov esi, ebx
mov edi, 1000000 ; 000f4240H
$L49799:

; 33 : for (long i = 0; ARRAY_SIZE != i; ++i) {
; 34 : *p *= 2000;

mov eax, DWORD PTR [esi]

; 35 : *p /= 10000;
; 36 : ++p;

add esi, 4
lea eax, DWORD PTR [eax+eax*4]
lea eax, DWORD PTR [eax+eax*4]
lea ecx, DWORD PTR [eax+eax*4]
mov eax, 1759218605 ; 68db8badH
shl ecx, 4
imul ecx
sar edx, 12 ; 0000000cH
mov eax, edx
shr eax, 31 ; 0000001fH
add edx, eax
dec edi
mov DWORD PTR [esi-4], edx
jne SHORT $L49799

; 31 : for (int j = 0; REDO != j ; ++j) {

dec ebp
jne SHORT $L49794
pop edi
pop esi
pop ebp
pop ebx

; 37 : }
; 38 : }
; 39 : }

ret 0
?optimized@@YAXPAH@Z ENDP ; optimized
_TEXT ENDS
PUBLIC ?extra@@YAXPAH@Z ; extra
; COMDAT ?extra@@YAXPAH@Z
_TEXT SEGMENT
_a$ = 8
?extra@@YAXPAH@Z PROC NEAR ; extra, COMDAT

; 42 : {

push ebx
push esi
push edi

; 43 : const int* end = a + ARRAY_SIZE;

mov edi, DWORD PTR _a$[esp+8]
mov ebx, 50 ; 00000032H
lea esi, DWORD PTR [edi+4000000]
$L49807:

; 45 : for (int* p = a; p != end; ++p) {

cmp edi, esi
mov ecx, edi
je SHORT $L49808
$L49811:

; 46 : *p *= 2000;

mov eax, DWORD PTR [ecx]
add ecx, 4
lea eax, DWORD PTR [eax+eax*4]
lea eax, DWORD PTR [eax+eax*4]
lea edx, DWORD PTR [eax+eax*4]

; 47 : *p /= 10000;

mov eax, 1759218605 ; 68db8badH
shl edx, 4
imul edx
sar edx, 12 ; 0000000cH
mov eax, edx
shr eax, 31 ; 0000001fH
add edx, eax
cmp ecx, esi
mov DWORD PTR [ecx-4], edx
jne SHORT $L49811
$L49808:

; 44 : for (int j = 0; REDO != j ; ++j) {

dec ebx
jne SHORT $L49807
pop edi
pop esi
pop ebx

; 48 : }
; 49 : }
; 50 : }

ret 0
?extra@@YAXPAH@Z ENDP ; extra
_TEXT ENDS


Venlig hilsen

Mogens Hansen

---

Goddag Mogens og Claus.

Jeg har koncentreret mig om straight-løkken da denne udviser den største
forskel i køretid.
Sammenligner man linie for linie bliver divisionen udført næsten ens idét
a[i] = a[i] / 2000
udregnes ved at gange a[i] med en stor konstant og rotere resultatet til
venstre.
Altså noget i stil med:
a[i] = (a[i] * 1759218605) >> 12
hvorefter der korrigeres for afrundingsfejl.

Multiplikationen er der derimod uenighed om. Intel ganger rent faktisk bare
med 2000 mens Visual forsøger at addere og shifte sig til resultatet, som
bliver lidt i stil med:
int t = (a[i] * 16);
t = t + t * 4;
t = t + t * 4;
t = t + t * 4;
a[i] = t;
hvor multiplikationer med 2'er-potenser jo selvfølgelig kan udregnes
hurtigt. Enten ved at rotere eller ved at bruge lea-instruktionen som det
gøres i vores tilfælde.

Teknikken er nærmere beskrevet på følgende side:
http://www.azillionmonkeys.com/qed/amult.html

Men det virker som om det nok er hurtigere bare at bruge
multiplikations-instruktionen istedet for at bruge shift & add til at
foretage operationen; tror jeg.

Hilsen Anders

---

"Claus Rasmussen" <clr@cc-consult.dk> wrote

> Mogens Hansen wrote:
>
> [saks udemærket eksempel på Windows]
>
> Jeg lurer lidt på den måde, du måler performance. Clock tics - omfatter
> det clock tics forbrugt af operativsystemet, når programmet laver
> systemkald ?
>

Hvilke systemkald ?
Der er ingen, inden for det interval som der måles med Win32 API funktionen
"QueryPerformanceCounter"..

> I dit eksempel ville det være det derfor være straight versionen, der tog
> hugget.
>

Nej, det er i givet fald init der betaler.
Men det ved du allerede.

> Den tid, jeg målte på linux, var kun den tid, som programmet selv brugte.
>
> Prøv forresten som et ekstra tjek at køre programmet flere gange, og se
> om du får det samme antal cykler.
>

Det har jeg gjort. Det varierer naturligvis lidt.
Man kan gøre det lidt mere konstant ved at øge processens prioritet.
Det skal også lige siges at det kører på en dual-processor maskine - derfor
er det vigtigt at man sikrer at programmet ikke flytter fra den ene til den
anden CPU (med Win32 API funktionen SetProcessAffinityMask).
Jeg har øget REDO til 50

Intel C++ V5.01:

Straight: 1080618668
Optimized: 1086206714
Extra: 1080069591

Straight: 1083993504
Optimized: 1089160920
Extra: 1084017798

Straight: 1081150349
Optimized: 1085990587
Extra: 1080941575



Microsoft Visual C++ V6.0:

Straight: 1102665168
Optimized: 1102417903
Extra: 1104523930

Straight: 1101603024
Optimized: 1101042398
Extra: 1104625364

Straight: 1098198132
Optimized: 1097774468
Extra: 1102396848

>
> Rimeligt sej, den der Intel kompiler
>

Den har en rigtig god C++ frontend - den bedste jeg kender (EDG). Det er
vigtigst for mig.
Samtidig generer den anstændig kode. Det er ikke altid at den er bedre end
Microsoft Visual C++ - men den er også svært at slå.
Jeg har tilmed et eksempel hvor Borland C++Builder generer bedre kode - men
det er ekstremt (og Microsoft compileren havde givet op i forhold til den
C++ kode).
Intel compileren kan downloades til fri ikke kommerciel brug til Linux.
Jeg oplever den som en uproblematisk erstatning for Microsoft compileren
inde fra Visual C++ IDE'et.
Men det er naturligvis en minoritets compiler på MS-Window platformen.

Venlig hilsen

Mogens Hansen

---

"Mogens Hansen" <mogens_h@dk-online.dk> wrote in message
news:a0mvng$17rb$2@news.cybercity.dk...

> Hvilke systemkald ?
> Der er ingen, inden for det interval som der måles med Win32 API
funktionen
> "QueryPerformanceCounter"..
>

Hmm..
Jeg tror at han mener at hukomelsen måske er 'Commited' men ikke sat op i
paging tabelerne, dvs. at første gennemløb laver page faults, som tager
extra tid at håndtere.


Ved at bruge QueryPerformanceCounter før og efter en algoritme får man vel
et udtryk for hvorlang tid der er gået fra algoritmen startede til den
sluttede. Hvad er det egentlig en for en timer der bruges til dette i Intel
arkitekturen?, er det noget der er bagudkompetibelt med den gamle I8259A ? I
min maskine returnere QueryPerformanceFrequency 3579545 Hz, hvilket er ikke
går op i 4.77Mhz ?

Hvad nu hvis systemet har kørt nogle tråde med høj prioitet, eller ligefrem
måtte behandle nogle interrupts (timer, Mus, HD, netkort etc.) bliver det så
ikke timet med ?
Det samt hvilke data der ligger i diverse cache, TLB etc. kan vel forklare
at afviklingen varierer i tid fra forsøg til forsøg.?
Især hvis afviklingen af en enkelt test tager kort tid, har få gennenløb.
Findes der ikke en funktion i Win32 API'et til at time den tid en tråd har
brugt ?

med venlig hilsen
Niels Erik Danielsen

---

"Niels Erik Danielsen" <ned@post6.tele.dk> wrote
>
> "Mogens Hansen" <mogens_h@dk-online.dk> wrote in message
> news:a0mvng$17rb$2@news.cybercity.dk...
>
> > Hvilke systemkald ?
> > Der er ingen, inden for det interval som der måles med Win32 API
> funktionen
> > "QueryPerformanceCounter"..
> >
>
> Hmm..
> Jeg tror at han mener at hukomelsen måske er 'Commited' men ikke sat op i
> paging tabelerne, dvs. at første gennemløb laver page faults, som tager
> extra tid at håndtere.
>

Som det er nævnt et par gange i denne tråd, vil funktionen "init" betale
denne pris, hvis den skal betales.
"init" initialiserer hele bufferen.
Maskinen har iøvrigt hukommelse nok til at der ikke er nogen grund til at
bufferen skulle blive paged ud og ind under måligen.

>
> Ved at bruge QueryPerformanceCounter før og efter en algoritme får man vel
> et udtryk for hvorlang tid der er gået fra algoritmen startede til den
> sluttede.

Ja.

> Hvad er det egentlig en for en timer der bruges til dette i Intel
> arkitekturen?, er det noget der er bagudkompetibelt med den gamle I8259A ?

Så vidt jeg ved er det en tæller der ligger i CPUen på "nyere" Intel (og
formodentligt også AMD).
Pentium II og senere har dem så vidt jeg ved. Jeg ved ikke på stående fod
hvornår de bliv tilføjet, eller hvad assembler instruktionen til at læse dem
med hedder.

> I
> min maskine returnere QueryPerformanceFrequency 3579545 Hz, hvilket er
ikke
> går op i 4.77Mhz ?
>

På den maskine jeg målte det på giver QueryPerformanceFrequency direkte
clock-frekvensen.

> Hvad nu hvis systemet har kørt nogle tråde med høj prioitet, eller
ligefrem
> måtte behandle nogle interrupts (timer, Mus, HD, netkort etc.) bliver det
så
> ikke timet med ?

Jo - men...
* Jeg havde ikke sat computeren til at lave andet imens.
* Processen blev udført som REALTIME_PRIORITY_CLASS - hvilket selvfølgelig
ikke udelukker _alt_ andet
* Det er en dual-processor maskine, så jeg vil forvente at andre
små-opgaver vil blive udført på den ledige processor
* Hvis kørslen tager lidt tid, vil jeg forvente at alle 3 algoritmer
belastes ligemeget (eller i det mindste tilfældigt) af hvad der ellers
foregår på maskinen

> Det samt hvilke data der ligger i diverse cache, TLB etc. kan vel forklare
> at afviklingen varierer i tid fra forsøg til forsøg.?

Nej, det tror jeg ikke.
Det skulle i givet fald betyde, at hvis de 3 algoritmer kører i modsat
rækkefølge, så får man et andet resultat og det kan jeg ikke se at man gør.

> Især hvis afviklingen af en enkelt test tager kort tid, har få gennenløb.

Afviklingen af een test tager 7-8 sekunder.

Performance måling er svær, og netop derfor vedlagde jeg den kode jeg havde
målt med, så andre kan efterprøve det og kommentere på målemetoden.

Venlig hilsen

Mogens Hansen

---

Goddag Klaus.

Jeg tror sådan set dine betragtninger om moderne oversætteres evne til at
optimere er korrekte, men din tidsmåling og dermed bevisførelse er jeg ikke
helt vild med.
Så vidt jeg kan se måler du også tidsforbruget af logikken der styrer
hvilken af de tre løkker som bliver afviklet og den uoptimerede løkke bliver
kørt efter færrest strengsammenligninger og vinder altså på denne
usikkerhed.
Denne tid er måske forsvindende lille eller kan ihvertfald blive det ved at
skrue på REDO konstanten. Men hvorfor ikke bruge clock-funktionen fra
<time.h>. Denne funktion måler også kun hvor meget tid som den faktiske
process har haft til rådighed og man kan så kalde clock() _lige_ før og
efter løkken og måle forskellen.

Mit bud på en håndoptimeret c++-udgave ville foriøvrigt være følgende:

const int* end = a + SIZE;
for (int* p = a; p != end; ++p) {
register int t = *p;
t *= 2000;
t /= 10000;
*p = t;
}

Hilsen Anders

[alt er klippet - læs hele det gamle indlæg, evt. hele den gamle tråd]

---

Anders Borum wrote:

> Så vidt jeg kan se måler du også tidsforbruget af logikken der styrer
> hvilken af de tre løkker som bliver afviklet og den uoptimerede løkke
> bliver kørt efter færrest strengsammenligninger og vinder altså på denne
> usikkerhed.
> Denne tid er måske forsvindende lille eller kan ihvertfald blive det ved
> at skrue på REDO konstanten. ...........................................

Den tid /er/ forsvindende lille. Min første udgave timede faktisk også
initialiserings-loopet, så jeg kunne se procentforskellen mellem de
forskellige varianter. Initialiseringsloopet tog så lidt tid, at jeg
droppede det igen


> ............................ Men hvorfor ikke bruge clock-funktionen fra
> <time.h>. Denne funktion måler også kun hvor meget tid som den faktiske
> process har haft til rådighed og man kan så kalde clock() _lige_ før og
> efter løkken og måle forskellen.

Som jeg skriver i mit svar til Mogens, forsøger jeg at undgå at få den
tid, som bruges til at allokere det dynamiske array med i mine tal. Jeg
bruger derfor user-time fra time kommandoen. System-time er faktisk noget
nær halvdelen af kørselstiden og den varierer voldsomt fra kørsel til
kørsel.

-Claus

---

On Sun, 30 Dec 2001 06:27:39 +0100,
Claus Rasmussen <clr@cc-consult.dk> wrote:

> Først den "rene" version:
>
> for (long i = 0; i < SIZE; ++i) {
> a[i] = a[i] * 2000;

Jeg vil mene at a[i] *= 2000; er lettere at læse, da man så ikke skal
tænke over om der nu står det samme på begge sider af lighedstegnet.

--
Like a rat in a maze Anders Bo Rasmussen mailto:fuzz01@spamfilter.dk
The path before me lies Frimestervej 42 1.tv http://www.fuzz.dk
And the pattern never alters 2400 Kbh. NV
Until the rat dies.