Лабораторные работы №2 и №3
.pdfСанкт-Петербургский Государственный Электротехнический Университет
(ЛЭТИ)
кафедра МО ЭВМ
Отчет по лабораторной работе №2–3
Измерение характеристик динамической сложности программ
Выполнил студент группы 1382, ФКТИ |
Пухкал И. |
Санкт-Петербург 2006
2 Выполнение работы |
2 |
1.Постановка задачи
1.Ознакомиться с документацией на VTune и выполнить для программы prost0.c следующее задание:
•компиляция с использованием автономного отладчика;
•профилирование по времени;
•профилирование по частоте;
•профилирование по средним временам на 1 вызов;
•запись результатов профилирования в файл для печати.
2.Выполнить тестовые программ’s test_cyc.c, test_sub.c c анализом параметров повторения циклов и проверкой их влияния на точность и чувствительность профилирования.
3.Скомпилировать и выполнить программы на Паскале и С, разработанные в 1-ой лабораторной работе. Снять все виды профилей, выявить ¾узкие места¿, ввести в программы усовершенствования и получить новые профили. Если времена выполнения рассматриваемых при профилировании фрагментов программы малы для учета VTune, ввести вспомогательное зацикливание программы.
2.Выполнение работы
Прежде всего проведем первичную модификацию программного кода, приведенного в лабораторной работе №1. Очевидно, что любые операции ввода/вывода (в том числе и файловые) будут занимать несравнимо большее время, нежели операции, относящиеся непосредственно к вычислительному алгоритму программы. Поэтому эти участки кода будут заменены блоками автоматической генерации тестов и проверки верного выполнения алгоритма.
Листинг 1. ¾JUnit¿ (Pascal)
function verify(var x: TArray; dim: integer) : boolean; var i : integer ;
begin
i := 1;
5while (x[i] <= x[i+1]) and (i+1 <= dim) do begin i := i+1;
end;
if ( i = dim) then verify := true
10 else
verify := false ; end;
procedure init(var x: TArray; dim: integer); var 15 i : integer ;
begin
for i := 1 to dim do begin x[ i ] := random(100);
end;
20end;
begin randomize;
for t := 1 to 32000 do begin
2 |
Выполнение работы |
3 |
|
25 |
|
init (a, n); |
|
|
|
qsort(a, n); |
|
|
|
verify (a, n) |
|
end; end.
Листинг 2. ¾JUnit¿ (C)
bool verify (TArray &x, int dim) { int i = 0;
while ((x[ i] <= x[i+1]) && (i+1 <= dim)) { i++;
5}
if ( i == dim) { return true;
}
else {
10 return false ;
}
}
void init(TArray &x, int dim) {
15 for ( int i = 0; i <= dim; i++) { x[ i ] = random(100);
}
}
20
void main() { TArray a; int n = 100; randomize();
25 for ( int t = 0; t <= 31999; t++) { init (a, n);
qsort(a, n); verify (a, n);
}
30}
2.1. Условия выполнения
В качестве используемого профилировщика будет использован пакет Intel VTune Performance Analizer 5.0. Программы на Pascal откомпилированы под Borland Delphi 7, на C под Borland C++ Builder 6.
Программы выполнялись на компьютере следующих характеристик: P4 Prescott 2.8GHz/512Mb. Операционная система Microsoft Windows XP SP1. Запущено 52 процесса, средняя загрузка процессора 6 %.
2.2. Тестовая программа senna.cpp
Здесь и далее в круглых скобках указаны абсолютные значения (clockticks, samples count - total). Всюду интервал взятия образцов 1мкс. Размер буфера 65536 Кб.
Time-Sampling
7 #include "stdio.h";
9int primes[1000];
10 #define MAXPRIMES 1000
12main()
13{
14for (int t = 0; t <= 100; t++) {
16int j;
17int lastprime, curprime;
19 |
primes[0] = 2; |
|
|
2 Выполнение работы |
4 |
20primes[1] = 3;
21lastprime = 1;
22curprime = 3;
24printf("prime \%d = \%d\n", 0, primes[0]);
25printf("prime \%d = \%d\n", 1, primes[1]);
27while(curprime < MAXPRIMES)
28{
29for(j = 0; j <= lastprime; j++)
30 |
75.00\% |
if((curprime \% primes[j]) == 0) |
31 |
(27000) |
{ |
|
||
32 |
2.78\% |
curprime += 2; |
33 |
(1000) |
|
|
|
|
34 |
8.33\% |
break; |
35 |
(3000) |
} |
|
||
36 |
2.78\% |
if(j <= lastprime) |
37 |
(1000) |
continue; |
|
38lastprime++;
39printf("prime \%d = \%d\n", lastprime, curprime);
40 |
8.33\% |
primes[lastprime] = curprime; |
|
(3000) |
|
41 |
2.78\% |
curprime += 2; |
|
(2000) |
|
42}
43}
44}
Event-Based Sampling
7 #include "stdio.h";
9int primes[1000];
10 #define MAXPRIMES 1000
12main()
13{
140.01\% for (int t = 0; t <= 100; t++) { (8379)
15
16int j;
17int lastprime, curprime;
190.09\% primes[0] = 2; (106 134)
200.02\% primes[1] = 3; (27 930)
21lastprime = 1;
22curprime = 3;
24 |
0.00\% |
printf("prime \%d = \%d\n", 0, primes[0]); |
|
|
(2 793) |
|
|
25 |
0.03\% |
printf("prime \%d = \%d\n", 1, primes[1]); |
|
26 |
(36 |
309) |
|
|
|
|
|
27 |
0.67\% |
while(curprime < MAXPRIMES) |
|
|
(837 |
900) |
|
28 |
|
|
{ |
29 |
0.25\% |
for(j = 0; j <= lastprime; j++) |
|
|
(315 |
930) |
|
30 |
73.34\% |
if((curprime \% primes[j]) == 0) |
|
|
(91 |
543 |
368) |
31 |
|
|
{ |
32 |
0.11\% |
curprime += 2; |
|
33 |
(139 |
650) |
|
|
|
|
|
34 |
19.84\% |
break; |
|
|
(24 |
765 |
531) |
35 |
|
|
} |
36 |
1.16\% |
if(j <= lastprime) |
|
|
(1 443 981) |
||
37 |
0.01\% |
continue; |
|
38 |
(11 |
172) |
lastprime++; |
|
|
||
39 |
0.22\% |
printf("prime \%d = \%d\n", lastprime, curprime); |
|
|
|
|
|
2 |
Выполнение работы |
5 |
||
|
(279 |
300) |
|
|
40 |
4.10\% |
primes[lastprime] = curprime; |
|
|
|
(5 122 300) |
|
|
|
41 |
0.05\% |
curprime += 2; |
|
|
|
(58 |
653) |
|
|
42}
43}
44}
2.3. Тестовая программа test_cyc.c
Time-Sampling
6#define Size 1000000
7 int i, tmp, dim[Size];
9void main()
10{
11for(i=0;i<Size/10;i++){ tmp=dim[0]; dim[0]=dim[i]; dim[i]=tmp; };
12 |
3.70\% |
for(i=0;i<Size/5;i++){ tmp=dim[0]; dim[0]=dim[i]; dim[i]=tmp; }; |
|
(1000) |
|
13 |
3.70\% |
for(i=0;i<Size/2;i++){ tmp=dim[0]; dim[0]=dim[i]; dim[i]=tmp; }; |
|
(1000) |
|
14 |
18.52\% |
for(i=0;i<Size;i++) { tmp=dim[0]; dim[0]=dim[i]; dim[i]=tmp; }; |
15 |
(5000) |
for(i=0;i<Size/10;i++) |
|
||
16 |
3.70\% |
{ tmp=dim[0]; dim[0]=dim[i]; dim[i]=tmp; }; |
17 |
(1000) |
for(i=0;i<Size/5;i++) |
|
||
18 |
3.70\% |
{ tmp=dim[0]; dim[0]=dim[i]; dim[i]=tmp; }; |
19 |
(1000) |
for(i=0;i<Size/2;i++) |
|
||
20 |
7.41\% |
{ tmp=dim[0]; dim[0]=dim[i]; dim[i]=tmp; }; |
21 |
(2000) |
for(i=0;i<Size;i++) |
|
||
22 |
25.93\% |
{ tmp=dim[0]; dim[0]=dim[i]; dim[i]=tmp; }; |
|
(7000) |
|
23for(i=0;i<Size/10;i++)
24{ tmp=dim[0];
25dim[0]=dim[i];
26dim[i]=tmp;
27};
28for(i=0;i<Size/5;i++)
29{ tmp=dim[0];
30 3.70\% |
dim[0]=dim[i]; |
(1000) |
|
31dim[i]=tmp;
32};
33for(i=0;i<Size/2;i++)
34{ tmp=dim[0];
35dim[0]=dim[i];
36 11.11\% |
dim[i]=tmp; |
(3000) |
|
37};
38for(i=0;i<Size;i++)
39{ tmp=dim[0];
40 |
7.41\% |
dim[0]=dim[i]; |
|
(2000) |
|
41 |
11.11\% |
dim[i]=tmp; |
|
(3000) |
|
42};
43}
Event-Based Sampling
6#define Size 1000000
7 int i, tmp, dim[Size];
9void main()
10 |
{ |
|
11 |
1.91\% |
for(i=0;i<Size/10;i++){ tmp=dim[0]; dim[0]=dim[i]; dim[i]=tmp; }; |
|
(2 209 263) |
|
12 |
3.73\% |
for(i=0;i<Size/5;i++){ tmp=dim[0]; dim[0]=dim[i]; dim[i]=tmp; }; |
|
(4 320 771) |
|
|
|
|
2 |
Выполнение работы |
6 |
||
13 |
9.37\% |
for(i=0;i<Size/2;i++){ tmp=dim[0]; dim[0]=dim[i]; dim[i]=tmp; }; |
||
|
(10 |
859 |
184) |
|
14 |
18.76\% |
for(i=0;i<Size;i++) |
{ tmp=dim[0]; dim[0]=dim[i]; dim[i]=tmp; }; |
|
|
(21 |
735 |
126) |
|
15 |
|
|
for(i=0;i<Size/10;i++) |
|
16 |
1.84\% |
{ tmp=dim[0]; dim[0]=dim[i]; dim[i]=tmp; }; |
||
|
(2 123 852) |
|
||
17 |
|
|
for(i=0;i<Size/5;i++) |
|
18 |
3.69\% |
{ tmp=dim[0]; dim[0]=dim[i]; dim[i]=tmp; }; |
||
|
(4 270 497) |
|
||
19 |
|
|
for(i=0;i<Size/2;i++) |
|
20 |
9.19\% |
{ tmp=dim[0]; dim[0]=dim[i]; dim[i]=tmp; }; |
||
|
(10 |
649 |
857) |
|
21 |
|
|
for(i=0;i<Size;i++) |
|
22 |
18.34\% |
{ tmp=dim[0]; dim[0]=dim[i]; dim[i]=8) |
||
|
(21 |
251 |
937) |
|
23 |
|
|
for(i=0;i<Size/10;i++) |
|
24 |
0.43\% |
{ tmp=dim[0]; |
|
|
25 |
0.35\% |
dim[0]=dim[i]; |
|
|
26 |
1.06\% |
dim[i]=tmp; |
|
|
|
(=2 |
125 |
473) |
|
27};
28for(i=0;i<Size/5;i++)
29 |
0.66\% |
{ tmp=dim[0]; |
|
30 |
0.82\% |
dim[0]=dim[i]; |
|
31 |
2.18\% |
dim[i]=tmp; |
|
|
(=4 |
242 |
567) |
32};
33for(i=0;i<Size/2;i++)
34 |
1.70\% |
{ tmp=dim[0]; |
|
35 |
2.13\% |
dim[0]=dim[i]; |
|
36 |
5.35\% |
dim[i]=tmp; |
|
|
(=10 |
635 744) |
|
37};
38for(i=0;i<Size;i++)
39 |
2.50\% |
{ tmp=dim[0]; |
|
40 |
7.51\% |
dim[0]=dim[i]; |
|
41 |
8.49\% |
dim[i]=tmp; |
|
|
(=21 |
439 069) |
|
42};
43}
2.4. Тестовая программа test_sub.c
Time-Sampling
7 const unsigned Size = 1000;
10void TestLoop(int nTimes)
11{
12static int TestDim[Size];
13int tmp;
14int iLoop;
16while (nTimes > 0)
17{
18nTimes --;
19
20iLoop = Size;
2114.29\% while (iLoop > 0) (1000)
22{
23 |
28.57\% |
iLoop -- ; |
24 |
(2000) |
tmp = TestDim[0]; |
|
||
25 |
14.29\% |
TestDim[0] = TestDim[nTimes]; |
|
(1000) |
|
26 |
42.86\% |
TestDim[nTimes] = tmp; |
|
(2000) |
|
27}
28}
29} /* TestLoop */
32void main()
33{
34TestLoop(Size / 10); // 100 * 1000
2 Выполнение работы |
7 |
35TestLoop(Size / 5); // 200 * 1000
36TestLoop(Size / 2); // 500 * 1000
37TestLoop(Size / 1); // 1000* 1000
38}
Event-Based Sampling
7 const unsigned Size = 1000;
10void TestLoop(int nTimes)
11{
12static int TestDim[Size];
13int tmp;
14int iLoop;
16 80 997 while (nTimes > 0)
17{
18nTimes --;
20 |
22 344 |
iLoop = Size; |
|
|
21 |
4 |
128 054 |
while (iLoop |
> 0) |
22 |
|
|
{ |
|
23 |
2 |
206 470 |
iLoop -- ; |
|
24 |
9 |
437 547 |
tmp = TestDim[0]; |
|
25 |
5 |
711 685 |
TestDim[0] |
= TestDim[nTimes]; |
26 |
11 738 979 |
TestDim[nTimes] = tmp; |
27}
28}
29} /* TestLoop */
32void main()
33{
34TestLoop(Size / 10); // 100 * 1000
35TestLoop(Size / 5); // 200 * 1000
36TestLoop(Size / 2); // 500 * 1000
37TestLoop(Size / 1); // 1000* 1000
38}
2.5. Быстрая сортировка
2.5.1. Pascal
Time-Sampling
1program prog_pas;
5uses
6SysUtils;
8const
9N = 20;
11type
12TArray = array [1..N] of real;
14procedure swap(var p,q: real);
15 |
|
var hold |
: real; |
16 |
0.60\% |
begin |
|
17 |
1.05\% |
hold:=p; |
|
18 |
0.45\% |
p:=q; |
|
19 |
1.05\% |
q:=hold |
|
20 |
0.15\% |
end; |
{ swap } |
22 |
|
procedure qsort(var x: TArray; n: integer); |
27var left,right : array[1..20] of integer;
28i,j,sp,mid : integer;
29 |
pivot |
: real; |
31begin
32left[1]:=1;
33right[1]:=n;
34sp:=1;
35while sp>0 do
36begin
37 |
0.90\% |
if left[sp]>=right[sp] then begin |
38 |
1.20\% |
sp:=sp-1 |
39end
40else begin
41 |
|
i:=left[sp]; |
42 |
1.20\% |
j:=right[sp]; |
|
|
|
2 |
Выполнение работы |
8 |
||
43 |
0.30\% |
|
pivot:=x[j]; |
|
44 |
0.15\% |
|
mid:=(i+j)div 2; |
|
45 |
|
if (j-i)>5 then begin |
|
|
46 |
4.21\% |
|
if ((x[mid]<pivot)and(x[mid]>x[i])) or |
|
|
|
|
((x[mid]>pivot)and(x[mid]<x[i])) then begin |
|
47 |
0.15\% |
|
swap(x[mid],x[j]) |
|
48 |
|
end |
|
|
49 |
|
|
else begin |
|
50 |
0.90\% |
|
if((x[i]<x[mid])and(x[i]>pivot)) or |
|
|
|
|
((x[i]>x[mid])and(x[i]<pivot)) then begin |
|
51 |
0.15\% |
|
swap(x[i],x[j]); |
|
52 |
|
|
end; |
|
53 |
|
end; |
|
|
54 |
|
end; |
|
|
55 |
1.95\% |
|
pivot:=x[j]; |
|
56 |
1.50\% |
|
while i<j do begin |
|
57 |
38.35\% |
|
while x[i]<pivot do begin |
|
58 |
0.60\% |
|
i:=i+1; |
|
59 |
|
end; |
|
|
60 |
9.77\% |
|
j:=j-1; |
|
61 |
13.23\% |
|
while (i<j)and(pivot<x[j]) do begin |
|
62 |
0.75\% |
|
j:=j-1; |
|
63 |
|
end; |
|
|
64 |
10.98\% |
|
if i<j then swap(x[i],x[j]) |
|
65 |
|
end; |
{ while } |
|
66 |
|
j:=right[sp]; { pivot to i } |
|
|
67 |
1.65\% |
swap(x[i],x[j]); |
|
|
68 |
0.90\% |
if i-left[sp]>=right[sp]-i then begin |
{ put shorter part first } |
|
69 |
|
left[sp+1]:=left[sp]; |
|
|
70 |
0.90\% |
|
right[sp+1]:=i-1; |
|
71left[sp]:=i+1
72end
73else begin
74 |
0.60\% |
left[sp+1]:=i+1; |
75 |
0.30\% |
right[sp+1]:=right[sp]; |
76 |
0.15\% |
right[sp]:=i-1 |
77 |
end; |
|
|
78 |
sp:=sp+1 |
{ push stack } |
|
79 |
end; |
|
{ if } |
80 |
end |
{ while } |
|
81 |
end; |
{ QUICK SORT } |
83function verify(var x: TArray; dim: integer): boolean;
84var
85i: integer;
86begin
87i := 1;
881.05\% while (x[i] <= x[i+1]) and (i+1 <= dim) do begin
89i := i+1;
90end;
91if (i = dim) then
92verify := true
93else
94verify := false;
95end;
97procedure init(var x: TArray; dim: integer);
98var
99i: integer;
100begin
1010.15\% for i := 1 to dim do begin
1023.16\% x[i] := random(100);
103 |
0.15\% |
end; |
104 |
|
end; |
106var
107a: TArray;
108t: integer;
109begin
110randomize;
111for t := 1 to 32000 do begin
112init(a, n);
113qsort(a, n);
114verify(a, n)
115end;
116end.
2 Выполнение работы |
9 |
Event-Based Sampling
1program prog_pas;
5uses
6SysUtils;
8const
9N = 20;
11type
12TArray = array [1..N] of real;
14procedure swap(var p,q: real);
15 |
|
var hold |
: real; |
16 |
0.67\% |
begin |
|
17 |
0.87\% |
hold:=p; |
|
18 |
0.78\% |
p:=q; |
|
19 |
0.61\% |
q:=hold |
|
20 |
0.81\% |
end; |
{ swap } |
22 |
|
procedure qsort(var x: TArray; n: integer); |
27var left,right : array[1..20] of integer;
28i,j,sp,mid : integer;
29 |
|
pivot |
: real; |
31 |
0.01\% |
begin |
|
32 |
0.00\% |
left[1]:=1; |
33right[1]:=n;
34sp:=1;
35 |
0.19\% |
while sp>0 do |
36 |
|
begin |
37 |
0.52\% |
if left[sp]>=right[sp] then begin |
38 |
1.15\% |
sp:=sp-1 |
39end
40else begin
41 |
0.14\% |
|
i:=left[sp]; |
|
42 |
1.17\% |
|
j:=right[sp]; |
|
43 |
0.35\% |
|
pivot:=x[j]; |
|
44 |
0.19\% |
|
mid:=(i+j)div 2; |
|
45 |
0.21\% |
|
if (j-i)>5 then begin |
|
46 |
4.85\% |
|
if ((x[mid]<pivot)and(x[mid]>x[i])) or |
|
|
|
|
((x[mid]>pivot)and(x[mid]<x[i])) then begin |
|
47 |
0.44\% |
|
swap(x[mid],x[j]) |
|
48 |
|
end |
|
|
49 |
|
|
else begin |
|
50 |
1.80\% |
|
if((x[i]<x[mid])and(x[i]>pivot)) or |
|
|
|
|
((x[i]>x[mid])and(x[i]<pivot)) then begin |
|
51 |
0.38\% |
|
swap(x[i],x[j]); |
|
52 |
|
|
end; |
|
53 |
|
end; |
|
|
54 |
|
end; |
|
|
55 |
1.57\% |
|
pivot:=x[j]; |
|
56 |
2.54\% |
|
while i<j do begin |
|
57 |
34.66\% |
|
while x[i]<pivot do begin |
|
58 |
1.06\% |
|
i:=i+1; |
|
59 |
|
end; |
|
|
60 |
7.46\% |
|
j:=j-1; |
|
61 |
14.94\% |
|
while (i<j)and(pivot<x[j]) do begin |
|
62 |
0.63\% |
|
j:=j-1; |
|
63 |
|
end; |
|
|
64 |
11.00\% |
|
if i<j then swap(x[i],x[j]) |
|
65 |
|
end; |
{ while } |
|
66 |
0.18\% |
j:=right[sp]; { pivot to i } |
|
|
67 |
1.52\% |
swap(x[i],x[j]); |
|
|
68 |
0.61\% |
if i-left[sp]>=right[sp]-i then begin |
{ put shorter part first } |
|
69 |
0.07\% |
|
left[sp+1]:=left[sp]; |
|
70 |
0.90\% |
|
right[sp+1]:=i-1; |
|
71 |
0.09\% |
|
left[sp]:=i+1 |
|
72end
73else begin
74 |
0.90\% |
|
left[sp+1]:=i+1; |
|
75 |
0.08\% |
|
right[sp+1]:=right[sp]; |
|
76 |
0.12\% |
|
right[sp]:=i-1 |
|
77 |
|
end; |
|
|
78 |
0.09\% |
|
sp:=sp+1 |
{ push stack } |
79 |
|
end; |
{ if } |
|
80 |
|
end |
{ while } |
|
81 |
0.10\% |
end; |
{ QUICK SORT } |
|
83 |
|
function verify(var x: TArray; dim: integer): boolean; |
||
|
|
|
|
|
2 Выполнение работы |
10 |
84var
85i: integer;
86 |
0.01\% |
begin |
87 |
0.00\% |
i := 1; |
88 |
1.65\% |
while (x[i] <= x[i+1]) and (i+1 <= dim) do begin |
89 |
0.02\% |
i := i+1; |
90end;
910.08\% if (i = dim) then
92 0.00\% |
verify := true |
93else
94verify := false;
95end;
97procedure init(var x: TArray; dim: integer);
98var
99i: integer;
100 0.02\% begin
1010.24\% for i := 1 to dim do begin
1022.79\% x[i] := random(100);
103 |
0.14\% |
end; |
104 |
0.03\% |
end; |
106var
107a: TArray;
108t: integer;
109 0.00\% begin
110randomize;
1110.01\% for t := 1 to 32000 do begin
112 |
0.00\% |
init(a, n); |
113 |
0.01\% |
qsort(a, n); |
114 |
0.02\% |
verify(a, n) |
115end;
116end.
2.5.2. C
Time-Sampling
6#include <stdlib.h>
8typedef double TArray[20];
10 |
0.68\% |
void swap(double &p, double &q) { |
11 |
1.37\% |
double tmp = p; |
12 |
0.68\% |
p = q; |
13 |
1.37\% |
q = tmp; |
14 |
0.68\% |
} |
16void qsort(TArray &x, int n) {
17int left[21];
18int right[21];
19left[1] = 1;
20right[1] = n;
21int sp = 1;
22int i = 0;
23int j = 0;
24int mid = 0;
25double pivot;
26 |
0.68\% |
while (sp) { |
27 |
0.68\% |
if (left[sp] >= right[sp]) { |
28sp--;
29}
30else {
31 |
2.05\% |
i = left[sp]; |
32 |
|
j = right[sp]; |
33 |
1.37\% |
pivot = x[j]; |
34mid = ((i+j) / 2);
35if ((j - i) > 5) {
367.53\% if ( ((x[mid] < pivot) && (x[mid] > x[i])) ||
((x[mid] > pivot) && (x[mid] < x[i])) ) {
37swap(x[mid], x[j]);
38}
39else {
40 |
4.11\% |
if ( ((x[i] < x[mid]) && (x[i] > pivot)) || |
|
|
((x[i] > x[mid]) && (x[i] < pivot)) ) { |
41 |
0.68\% |
swap(x[i], x[j]); |
42 |
|
} |
43 |
|
} |
|
|
|