Лабораторные работы № 2 и 3

Санкт-Петербургский Государственный Электротехнический Университет

(ЛЭТИ)

кафедра МО ЭВМ

Отчет по лабораторной работе №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		}