Categories
C

Optimalizace programu v C na příkladu vyhodnocení výrazu ve for cyklu

Na Facebook skupině Arduino a Raspberry poradna CZ & SK se objevil dotaz od pana Tesaře.

Protože mě zaujal, trochu se k němu rozepíši.

Na začátek je dobré si uvědomit, že kompilátory jsou dnes hodně chytré a když jim to nezakážeme, snaží se za nás udělat kód co nejoptimálnější.

Jsou různé techniky, jak kompilátor k optimalizaci může přistoupit. Nebudu je podrobně rozebírat (protože je sám stejně všechny neznám). Zkusíme se ale podívat, k čemu zřejmě došlo v tomto případě.

Zadání

Původní kód je napsaný pro Arduino a vypadá takto:

int a = Hod1;
int b = Hod2;
int c = Hod3;

unsigned long cas;
unsigned long cas1;
unsigned long cas2;

void setup() {
  Serial.begin(9600);
  cas1 = micros();

  for (int i = 0; i < 10000; i++)
    a = a + b + c;

  cas2 = micros();
  cas = cas2 - cas1;

  Serial.print("Čas operácií = ");
  Serial.print(cas);
  Serial.println(" µs");
  Serial.print("čas1 = ");
  Serial.println(cas1);
  Serial.print("čas2 = ");
  Serial.println(cas2);
}

void loop() {
}

Zjednodušení kódu

Arduino ekosystém při kompilaci obalí tento kód ještě dalšími příkazy (přidá implementaci funkce main, ve které volá funkce setup a loop atd.). Protože se ale v další části koukneme do assembleru, který kompilátor produkuje, zjednodušil jsem analyzovaný kód na nutné minimum (z mého pohledu). Místo Serial.println je použita funkce printf a místo micros je použita funkce time. K tomuto kroku jsem přistoupil, abych se zbavil nutnosti vkládat závislosti Arduino ekosystému.

#include <stdio.h>
#include <time.h>

time_t cas1;
time_t cas2;
int a = 1, b = 2, c = 3;

int main() {
  cas1 = time(NULL);

  for (int i = 0; i < 10000; i++) {
    a = a + b + c;
  }

  cas2 = time(NULL);

  printf("%d\n", a);
}

Tento program jsem uložil do souboru main.c.

Překlad kódu

Arduino projekty pro klasické desky založené na AVR procesorech (Uno, Mega, …) se kompilují pomocí avr-gcc (resp. avr-g++) kompilátoru.

Základní příkaz pro kompilaci souboru main.c je avr-gcc main.c. Kromě toho je ale možné funkci kompilátoru konfigurovat pomocí tzv. přepínačů.

Nás budou zajímat přepínače -Ox, který slouží k nastavení úrovně optimalizace a také přepínač -S, díky kterému bude kompilátor produkovat assembler. Ten budeme dále analyzovat.

Vypnutí optimalizací

Začneme tím, že se podíváme, jaký kód překladač produkuje při vypnuté optimalizaci. Assembler může vypadat děsivě, ale není potřeba rozumět všemu. Důležité části okomentuji.

Pro význam jednotlivých instrukcí je možné nahlédnout do dokumentace instrukčního setu AVR.

Takto vypadá Assembler při volání avr-gcc -mmcu=atmega328p -O0 -S main.c

Použitá ATMEGA328p je 8-bit mikrokontrolér, takže použité registry jsou 8bit. Když tedy chceme pracovat s 16bit hodnotou (int), musíme použít dva registry – viz např. řádky 66 a dále.

.file	"main.c"
__SP_H__ = 0x3e
__SP_L__ = 0x3d
__SREG__ = 0x3f
__tmp_reg__ = 0
__zero_reg__ = 1
	.text
	.comm	cas1,4,1
	.comm	cas2,4,1
.global	a						<-- od této části dále je vytvoření prostoru v paměti pro proměnné a, b, c
	.data
	.type	a, @object
	.size	a, 2
a:
	.word	1
.global	b
	.type	b, @object
	.size	b, 2
b:
	.word	2
.global	c
	.type	c, @object
	.size	c, 2
c:
	.word	3
	.section	.rodata
.LC0:
	.string	"%d %d %d\n"
	.text
.global	main
	.type	main, @function
main:							<-- zde začíná funkce main
	push r28
	push r29
	in r28,__SP_L__
	in r29,__SP_H__
	sbiw r28,10
	in __tmp_reg__,__SREG__
	cli
	out __SP_H__,r29
	out __SREG__,__tmp_reg__
	out __SP_L__,r28
/* prologue: function */
/* frame size = 10 */
/* stack size = 12 */
.L__stack_usage = 12
	ldi r24,0
	ldi r25,0
	call time	<-- volání funkce pro zjištění aktuálního času
	std Y+3,r22
	std Y+4,r23
	std Y+5,r24
	std Y+6,r25
	ldd r24,Y+3
	ldd r25,Y+4
	ldd r26,Y+5
	ldd r27,Y+6
	sts cas1,r24
	sts cas1+1,r25
	sts cas1+2,r26
	sts cas1+3,r27
	std Y+2,__zero_reg__	<-- na adresách Y+2 a Y+1 je uložena hodnota čítače (proměnná i)
	std Y+1,__zero_reg__
	rjmp .L2	<-- skoč na návěstí L2
.L3:	<-- zde začíná tělo cyklu for
	lds r18,a	<-- načti nižší byte proměnné a do registru r18
	lds r19,a+1	<-- načti vyšší byte proměnné a do registru r19
	lds r24,b	<-- načti nižší byte proměnné b do registru r24
	lds r25,b+1	<-- načti vyšší byte proměnné b do registru r25
	add r18,r24	<-- sečti registry r18 a r24
	adc r19,r25	<-- sečti registry r19 a r25, přičti přenos z předchozího sčítání
	lds r24,c	<-- obdobná situace se opakuje pro proměnnou c
	lds r25,c+1
	add r24,r18
	adc r25,r19
	sts a+1,r25	<-- uložení vyššího byte součtu do proměnné a
	sts a,r24	<-- uložení nižšího byte součtu do proměnné a
	ldd r24,Y+1	<-- do registrů r24 a r25 je uložená hodnota čítače
	ldd r25,Y+2
	adiw r24,1	<-- k hodnotě čítače přičte 1
	std Y+2,r25	<-- uloží novou hodnotu čítače z registrů r24 a r25 na adresu Y+1 a Y+2
	std Y+1,r24
.L2:
	ldd r24,Y+1	<-- načtení dat pro vyhodnocení podmínky cyklu
	ldd r25,Y+2
	cpi r24,16	<-- vyhodnocení podmínky cyklu
	sbci r25,39
	brlt .L3	<-- pokud podmínka platí, skoč na L3, jinak pokračuj dále
	ldi r24,0
	ldi r25,0
	call time	<-- volání funkce pro zjištění aktuálního času
	std Y+7,r22
	std Y+8,r23
	std Y+9,r24
	std Y+10,r25
	ldd r24,Y+7
	ldd r25,Y+8
	ldd r26,Y+9
	ldd r27,Y+10
	sts cas2,r24
	sts cas2+1,r25
	sts cas2+2,r26
	sts cas2+3,r27
	lds r18,a
	lds r19,a+1
	lds r20,cas2
	lds r21,cas2+1
	lds r22,cas2+2
	lds r23,cas2+3
	lds r24,cas1
	lds r25,cas1+1
	lds r26,cas1+2
	lds r27,cas1+3
	mov r30,r19
	push r30
	push r18
	mov r18,r23
	push r18
	mov r18,r22
	push r18
	mov r18,r21
	push r18
	mov r18,r20
	push r18
	mov r18,r27
	push r18
	mov r18,r26
	push r18
	mov r18,r25
	push r18
	push r24
	ldi r24,lo8(.LC0)
	ldi r25,hi8(.LC0)
	mov r24,r25
	push r24
	ldi r24,lo8(.LC0)
	ldi r25,hi8(.LC0)
	push r24
	call printf
	in r26,__SP_L__
	in r27,__SP_H__
	adiw r26,12
	in __tmp_reg__,__SREG__
	cli
	out __SP_H__,r29
	out __SREG__,__tmp_reg__
	out __SP_L__,r28
	ldi r24,0
	ldi r25,0
/* epilogue start */
	adiw r28,10
	in __tmp_reg__,__SREG__
	cli
	out __SP_H__,r29
	out __SREG__,__tmp_reg__
	out __SP_L__,r28
	pop r29
	pop r28
	ret
	.size	main, .-main
	.ident	"GCC: (Homebrew AVR GCC 9.3.0_3) 9.3.0"
.global __do_copy_data
.global __do_clear_bss

Z Assembleru vidíme, že při vypnutých optimalizacích kompilátor “tupě” přeloží kód for cyklu z C do Assembleru.

Se zapnutými optimalizacemi

Jak už jsem psal dříve, kompilátoru je možné říci, jakým způsobem má optimalizovat. Přístupů je celá řada, například:

  • -O0 – bez optimalizací
  • -Os – optimalizace velikosti výsledného kódu
  • -O3 – optimalizace rychlosti

Nyní tedy zkusme kód zkompilovat s přepínačem -Os.

avr-gcc -mmcu=atmega328p -Os -S main.c

V následujícím kódu už není situace tak přehledná, takže část okomentuji v něm a část v odstavcích pod kódem.

.file	"main.c"
__SP_H__ = 0x3e
__SP_L__ = 0x3d
__SREG__ = 0x3f
__tmp_reg__ = 0
__zero_reg__ = 1
	.text
	.section	.rodata.str1.1,"aMS",@progbits,1
.LC0:
	.string	"%d %d %d\n"
	.section	.text.startup,"ax",@progbits
.global	main
	.type	main, @function
main:
/* prologue: function */
/* frame size = 0 */
/* stack size = 0 */
.L__stack_usage = 0
	ldi r25,0
	ldi r24,0
	call time	<-- volání funkce pro zjištění aktuálního času
	sts cas1,r22
	sts cas1+1,r23
	sts cas1+2,r24
	sts cas1+3,r25
	lds r18,b	<-- načtení hodnot z proměnných do registrů
	lds r19,b+1
	lds r20,c
	lds r21,c+1
	lds r24,a
	lds r25,a+1
	add r24,r18	<-- posčítá a+b+c do registrů r24 a r25
	adc r25,r19
	add r24,r20
	adc r25,r21
	add r18,r20
	adc r19,r21
	ldi r22,lo8(15)	<-- do r22 ulož hodnotu 15
	ldi r23,lo8(39)	<-- do r23 ulož hodnotu 39
	mul r18,r22	<-- r1,r0 = r18 * r22 (součin dvou 8bit hodnot je až 16bit hodnota, výsledek je uložen do registrů R1 a R0)
	movw r20,r0	<-- r20 = r0, r21 = r1
	mul r18,r23
	add r21,r0
	mul r19,r22
	add r21,r0
	clr r1
	add r24,r20
	adc r25,r21
	sts a+1,r25
	sts a,r24
	ldi r25,0
	ldi r24,0
	call time	<-- volání funkce pro zjištění aktuálního času
	sts cas2,r22
	sts cas2+1,r23
	sts cas2+2,r24
	sts cas2+3,r25
	lds r18,a+1
	push r18
	lds r18,a
	push r18
	push r25
	push r24
	push r23
	push r22
	lds r24,cas1+3
	push r24
	lds r24,cas1+2
	push r24
	lds r24,cas1+1
	push r24
	lds r24,cas1
	push r24
	ldi r24,lo8(.LC0)
	ldi r25,hi8(.LC0)
	push r25
	push r24
	call printf
	in r24,__SP_L__
	in r25,__SP_H__
	adiw r24,12
	in __tmp_reg__,__SREG__
	cli
	out __SP_H__,r25
	out __SREG__,__tmp_reg__
	out __SP_L__,r24
	ldi r25,0
	ldi r24,0
/* epilogue start */
	ret
	.size	main, .-main
.global	c
	.data
	.type	c, @object
	.size	c, 2
c:
	.word	3
.global	b
	.type	b, @object
	.size	b, 2
b:
	.word	2
.global	a
	.type	a, @object
	.size	a, 2
a:
	.word	1
	.comm	cas2,4,1
	.comm	cas1,4,1
	.ident	"GCC: (Homebrew AVR GCC 9.3.0_3) 9.3.0"
.global __do_copy_data
.global __do_clear_bss

Na řádcích 26 až 31 dojde k načtení hodnot v proměnných a, b, c, do registrů.

Na řádcích 32 až 37 se hodnoty v registrech posčítají a uloží do registru, kde je právě uchována hodnota a.

Tím jsme vlastně dokončili první průchod cyklem.

Na řádcích 38 a 39 se uloží hodnoty 15 a 39 do registrů r22 a r23. K čemu to je? Když na nižší byte 16 bit hodnoty dáme hodnotu 15 (= 00001111 binárně) a na vyšší byte dáme hodnotu 39 (= 00100111 binárně), získáme 0010011100001111, což je dekadických 9999. Už tušíte, kam vítr vane? Na řádcích 32 až 37 jsme odbyli první průchod cyklem a zbývá nám ještě 9999. Reálně ale cyklem nemusíme procházet! Součet b + c je v našem případě neměnný. Stačí ho 9999 přičíst k hodnotě v registru s hodnotou proměnné a.

Cyklus kompilátor tedy zoptimalizoval do podoby a = a + b + c + 9999 * (b + c)

a=1, b=2, c=3
a = 1 + 2 + 3 + 9999*(2+3)
a = 50001

K čemu tedy došlo v případě kódu od pana Tesaře?

P. Tesař zmiňuje, že čas je stejný, bez ohledu na to, jestli je cyklus v kódu přítomen, nebo ne. Podle mě totiž dochází ještě k jedné optimalizaci v dalších fázích přípravy strojového kódu.

Můžete si všimnout, že hodnoty všech proměnných jsou známé již v době kompilace (viz předchozí rovnice). Po odstranění cyklu tak kompilátor mohl přistoupit rovnou k tomu, že výpočet v cyklu vyřešil v době kompilace!

Doufám, že vám článek trochu nastínil, co se při kompilaci může dít. (Ne)souhlasíte? Dejte vědět v komentářích 🙂

Leave a Reply

Your email address will not be published. Required fields are marked *