Свещеният сметач - списанието на глаголарите...
БРОЙ - 21 (март 2003)
Брой 21  Свещеният сметач
   
Анализ на почти празен цикъл

Емпирично-теоретичен, несериозен и неточен лъженаучен анализ на почти празен цикъл, извършен с четири сметача (Правец-8М, Правец-8Д, P54C-90, P55C-200) с различни програмни среди и операционни системи (6502, BASIC, Pascal, C, 286, 386; MS-DOS, MS-Windows). За разнообразие съдържа душеизлиятелни отклонения и лиготии на несериозния сметачолюбец, напраскал емпирично-теоретичния...

Миналото лято, 2002-ро, ми падна в ръчичките "изчерпателно четиво", което "българското програмистко общество очаква от години". Зачетох го с интерес и някъде в началото, най-интригуващата задача, която срещнах, беше за засичане на времето за изпълнение на вложени празни цикли. Винаги съм обичал времеизмерващите устройства, да натискам копчета на хронометри, тъй че "веднага се влюбих в заданието", добавих още една инструкция (любознателният читател би погледнал по-долу, за да разбере каква), за да има и нещо мое в него, и започнах да си играя.

Този "класически алгоритъм е един от първите, които начинаещият програмист научава"... И поради простотата си може много бързо и лесно да се пише на глаголица (сиреч Assembler), че и на вършачопис (машинен език).

Имах толкова голям мерак, че исках час по-скоро да почна и да свърша колкото мога по-бързо, а търсене, "мърсене" - много сложни ми се сториха, за скромните възможности на безличността ми. Зат'ва бързо приклещих почти празния цикъл и го оправих на няколко различни сметачета.

"Първият": Правец-8М, 6502/1.018 MHz

За любимия си Емчо съчиних следното стихче на вършачопис, което драгият MONITOR преведе на глаголица:

300: A9 00	LDA #$00, 2
302: 8D 00 50	STA $5000, 4
305: A2 00	LDX #00, 2
307: A0 00	LDY #00, 2
309: EE 00 50	INC $5000, 6
30C: 69 01	ADC 01, 2
30E: C9 10	CMP #$10, 2
310: F0 03	BEQ $0315, 2
312: 4C 09 03	JMP $309, 3
315: A9 00	LDA #00, 2
317: E8		INX, 2
318: E0 10	CPX #$10, 2
31A: F0 03	BEQ $031F, 2
31C: 4C 09 03	JPM $309, 3
31F: A2 00	LDX #00, 2
321: C8		INY, 2
322: C0 10	CPY #$10, 2
324: F0 03	BEQ $329, 2
326: 4C 09 03	JMP $309, 3
329: 20 DD FB	JSR $FBDD, 6 (ЗВЪНЧЕ)
32C: 60		RTS, 6
Както се вижда, в него освен празната въртележка, има и увеличаване с единица на клетка от паметта ($309: INC $5000), което е доста тежка казба за 6502 - цели 6 удара на сърцето... Сигурно също се вижда, че натрапващата се шестнайска ($10) е броят повторения и на трите вложени въртележки, следователно:

Общият брой цикления е N*N*N = N^3.

За лесно въвеждане на N бе написано кратко глаголище на личната ми програмистка "Основа" - BASIC.


10 N = 250 (N, M = N*N*N)
20 POKE 783, N
30 POKE 793, N
40 POKE 803, N
50 CALL 768
Като завъртях сметачето на въртележката (1.018 MHz), при N = 250 (M = 250^3 = 15.625E6), то се наигра за около 231.7 секунди, като постигна скорост от около 1018000/231.7 = 67436 врътки/сек. "Брей, не е малко" - си рекох и погледнах стихчето, за да преброя колко казби има във всяка врътка на най-вътрешната въртележка. Пет са, като ги гледам:

309: EE 00 50	INC $5000, 6
30C: 69 01	ADC 01, 2
30E: C9 10	CMP #$10, 2
310: F0 03	BEQ $0315, 2
312: 4C 09 03	JMP $309, 3
Тогава 67346*5 = 336730 казби/сек... Ех, да не беше това INC $xxxx, то изяжда 40% от цялото време (6/15). Все пак, и 67346/сек не са малко за сметачето...

Колко обаче са на BASIC?


5 N = 20
10 I = 0: J = 0; K = 0
20 C = 0
50 FOR I = 1 TO N
60 FOR J = 1 TO N
70 FOR K = 1 TO N
80 C = C + 1
90 NEXT: NEXT: NEXT
100 ?CHR$(7)	(ЗВЪН)
Пуснах глаголището при N = 20 и то изглаголи всичко за около 31.2 секунди, или 20*20*20 = 8000; 8000/31.2 = 256/сек. Брей, че бавно... Тогава махнах ред 80, да бъде само празна въртележка, и милото свърши само за 9.2 сек - около 870 врътки/сек.

256/сек, при около 250-350 хил. казби/сек (както установихме по-горе) означава, че мекицата на BASIC изпълнява поне около 1000 казби за всяка врътка...

Домашният ми любимец Домашко

Закономерно и милият Домашко бе впрегнат да тегли въртележките. Неговото вършаче е същото - 6502, но то работи не на 1.018 MHz, а (поне доколкото знам), само на 1.000 MHz. "Базикът" му е "MICROSOFT EXTENDED", простира се на 16 КБ, за разлика от 12 КБ-овия на Ябълчицата; може да чертае окръжности, да използва помощното звуково вършаче, за да свири и пее... Страшна работа!
Да, страшна, обаче в сметките, Домашкото ("Орикчото") изостава доста от Ябълката.
Същата горна мекичка, при N = 20, мъничето Домашко изтегли за около 42.5 сек, около 188 врътки/сек, или |188 - 256| = 68/256 = 26.6% по-бавно от Ябълката, при разлика в работните честоти - около 1.8%.

Натъжих се тогаз за Бил Гейтс и си помислих: "Ех, мили MICRO-computer SOFT, мили Били, или ако искаш Уили, още Ябълката ви е била, мили Били, и то с 20%, майки мили...". Но скоро последва мисълта - "Голяма работа" - след като "второто Аз" откри, че първото си мисли тъпотии.

Мацета?!... Обичам мацета!...

Сметачетата Емчо и Домашко минаха през изпитанието и дойде реда на Мацето.
Тъй като мацетата заемат голямо място в сметачолюбското ми сърчице, широко колкото обема на паметта на машината на Тюринг, ще си позволя отклонение от "научно-изследователския" поток на мислите.

Обичам всякакви мацета - мяукащи и мъркащи, със светещи очи, умилкващи се, рижави, ангорски, късокосмести и дългокосмести, русокоси, кестеняви, чернокоси, "с две хубави очи и с душата на дете", дребни и високи, със светли или тъмни очи, с напращяли 20-килограмови мигачи или с нежни плоски показвачи, с бързи или бавни вършачи - какво пък, все са си сметачи...

През живота си съм се влюбвал и в трите вида мацета. Прекрасните стада от представители на мъркащия вид в Пловдив, ми изпълват душицата. Само да видя уличници и да им хвърля няколко предизвикателни погледа, те също да ме погледнат, и омърлушеното ми личице, закрито с черни затъмнители, в миг се осветлява... Тъй става и като виждам някои определени мацета "с две хубави очи", но да си призная, докато очичките ми лесно привличат погледите на мяукащите котки, на говорещите - не... Но не унивам съвсем, щото очичките ми са много привлекателни за мацетатата с напращяли светещи мигачи и (по името на вида си) осем-шестицови вършачи... Това е "истинска любов"...

Бях станал много напорист и реших да събудя страстите не само на 6502, с добре тренирано сърце на бегач на дълги разстояния, туптящо спокойно и уверено около 61 милиона пъти в секунда, но и на нетърпеливо и буйно осем-шестаче, чийто пулс достига милиарди удара в минута.

По онуй време, 'га слънцето напичаше кат' в пустата Са'ара, мацката ми беше малко старичка, "спробвана", но, най-малкото, беше много опитна. В на-пра(сяшалите)щялите й гърди туптеше горд P54C-90, смятащ (180 милиона пъти в секунда) свръхработната памет от второ равнище за излишна. Тогаз написай следното велико съчинение на "Це", с букваче "main()" на "Це++".


	short int i,j,k,n,c;

int main()
{
 int i,p,q,t,
 printf("N = ?");
 scanf("%d", &n);
  for (i=0; i < n; i++)
   for (j=0; j < n; j++)
    for (k=0; k < n; k++)
     c++;
}
Използвай GNU DEV C++ 4 - 'убаво съставителче. Пуснай го ази, съчиненийцето, и ето к'во излязи:

n = 500, n*n*n = 125E6 - 16.7 секунди
125E6/16.7 = 7.485030E6 врътки/сек
Тук анализът обаче излиза по-сложен, щото Петакът много "върти и сучи" изпълнението на казбите и колко минават през вършача във всеки момент, не мога да кажа ей така, но горе-долу по десетина-двайсет казби на въртележка има. По-зле е от 5-те на вършачопис за 6502, но е много по-добре от 1000-та на мигновения преводач от BASIC...

Напраскай го и на PrASCAL!

Добрият стар французин Паскал Седми, син на Борланд, също се включи в играта.


var i,j,k,n,c: word;

begin
 writeln('N = ?');
 readln(N);
  for i := 1 to n do
   for j := 1 to n do
    for k := 1 to n do
     inc(c);
    writeln(chr(7));
end;
Не си спомням под чист "MICRO-computer SOFT DOS" ли го пусках, или под прозоречен DOS (тогавашното Маце нещо се поскапа (благодарение на мен) и запалва, но отхвърля като чужди тела всички клавиатури, които му присаждам).
 N = 500, N^3 = 125E6, 11.5 сек -> 10.87Е6 врътки/сек.
Изводът, до който стигнах след дълги размишления, бе че Паскалчо, дето се мъчи с 286, е по-добър в "почти празните" връткания, отколкото 32-битовия mingw32 (Да бе, не моиш сравнява текстова операционна система с Г-УЙ-ова, пък и к'ви сметки праи таз' програма, та да използва нещо 32-битово?)

Глаголица за х86

Къде се е чуло и видяло стихоплетец да не посвети някое стихотворение на своето Маце? И аз се чудех, колко ли въртележки "за единица време" ще мога да ударя със стихоплетка?... Първо си помогнах с Паскалчо.


var n;
...
nx := 1000;
...

procedure broi16;assembler;
     asm
     mov dx,0  {знам, че добрият}
     mov ax,0  {стихоплетец пише}
     mov bx,0  {xor reg, reg    }
     mov cx,0  {но аз нямам претенции  ;-}
@1:  inc dx
     inc ax
     cmp ax,nx
     je  @2
     jmp @1
@2:  mov ax,0
     inc bx
     cmp bx,nx
     je  @3
     jmp @1
@3:  mov bx,0
     inc cx
     cmp cx,nx
     je  @4
     jmp @1
@4:
     end;
Това нещо, при N (nx) = 1000 (N^3 = 1E9), под Windows 95B се изпълни за около 47 сек, или 21.276Е6 врътки/сек. Под чист DOS: около 45 сек, или 22.222E6 врътки сек. Вътрешната въртележка използва най-малко 5 казби, затова достигнатата скорост на вършачето е поне около 111 милиона целочислени казби в секунда (МЦКС), или средно 1.23 за всяко туптене на сърцето.

Широко скроената глаголица NetWide Assembler

Следващият ученик за изпитване беше "NetWide Assembler". Същото стихче на глаголица се извъртя по-бързо на него, отколкото в Паскалчо.


%include "exebin.mac"
EXE_begin
EXE_stack 128
section .text
                  
mov dx,zdr
mov ah,9
int 0x21
mov ah,8  ;прочита клавиш, без да го показва
int 21h
mov dx,starta
mov ah,9 
int 21h

mov ebx,0
mov ecx,0

cikyl:
     mov dx,0   ;broi
     mov ax,0
     mov bx,0
     mov cx,0
@1:  inc dx
     inc ax
     cmp ax,1000
     je  @2
     jmp @1
@2:  mov ax,0
     inc bx
     cmp bx,1000
     je  @3
     jmp @1
@3:  mov bx,0
     inc cx
     cmp cx,1000
     je  @4
     jmp @1

@4:  mov dx,krais	;"Заключителни думи"
     mov ah,9
     int 0x21

krai: mov ax,0x4c00
	int 0x21
 
	section .data

nx:	 dw 10
zdr:	  db ' HATUCHU BYTOH 3A CTAPT... ', 13, 10, '$'
krais    db ' Bpoq4 3a npa3Ha bpyTka', 13, 10, '$'
starta:   db ' CMETKU...',13,10, '$'

	  EXE_end
Под "Windows":
35.5 сек - около 28.17Е6 врътки/с или близо 141 МЦКС (1.57 казби/удар). Под чист DOS скоростта се вдигна още: 33.8 сек и около 29.59Е6 врътки/с, което прави около 148 МЦКС или 1.64 казби/удар!...
Двете поточки на Петака толкова добре са сработени от изключително сложното стихотворение, че премахването на реда, правещ от празния цикъл "почти празен" (inc dx), не променяше времето за изпълнение...

И новото Маце иска да ми ги мери

Последната ми любов, с по-младо сърце и душа, по случай тази статийка стана предмет на бурните ми страсти. Мацето ми има P55C-200 и е по-скромно от старото ми гадже - използва и услугите на свръхработна памет от 2-ро равнище.

1E9 въртележки:

- Глаголица, вмъкната в Паскал, DOS под Windows-98SE: 20.8 сек, ~ 48.08Е6 врътки/с, поне 240 МЦКС, 1.2 казби/удар
- Глаголица, NetWide Assembler, DOS под Windows-98SE: ~ 15.9 сек, 62.89Е6/с, 314 МЦКС, 1.57 казби/удар
- Глаголица, NetWide Assembler, MS-DOS: ~ 15.2 сек, ~ 65.8Е6 врътки/с, 329 МЦКС, 1.65 казби/удар
- Глаголи, Dev C++ 4, Windows-98SE: 216E6 (N=600), ~ 13.4 сек, ~ 16.12E6 врътки/с

Очевидното заключение, до което достигаме, наблюдавайки резултатите от изпълнението на стихчетата на глаголица е, че относителната скорост: казби/удар (другояче казано: "инструкции за такт") при изпълнение на "почти празен цикъл", е еднаква за P54C-90 с 16 КБ L1-cache и без L2-cache, и P55C-200 с 32 КБ L1-cache и 2097152 бита (май само толкова) L2-cache. Т.е. при изпълнение на прости алгоритми, като почти празния цикъл, по-големият обем свръхработна памет не носи изгода...


© Тодор Илиев Арнаудов (Тош), февруари 2003
Лична страница на Тош
Прочети още статии от Тош и други автори и от тук: http://bgit.net