Diskuze: C++ Hodnoty proměnných při rekuzivním volání funkce
V předchozím kvízu, Online test znalostí C++, jsme si ověřili nabyté zkušenosti z kurzu.
Zobrazeno 4 zpráv z 4.
V předchozím kvízu, Online test znalostí C++, jsme si ověřili nabyté zkušenosti z kurzu.
Nevím přesně, jak je to s předáváním parametrů při rekurzivním volání.
Záleží, jaký způsob předávání volaná funkce podporuje. Například konvence stdcall říká
U fastcall (obvyklá pro 64bitový kód, alespoň na Windows) se zase první čtyři parametry předávají v registrech (RCX, RDX, R8, R9), zbytek na zásobníku. Ale i pro ty první čtyři parametry se tam vyhrazuje místo.
Konvence cdecl se opět trochu liší, dokonce má svoji variantu pro Windows (Microsoft) a ostatní systémy.
Pro volání funkce slouží instrukce CALL, pro návrat z ní RET.
Co se týče hodnot proměnných, lokální proměnné má každá instance volání své vlastní. Jejich změna se neprojeví v nadřazených funkcích. Lokální proměnné se alokují na zásobníku, často nějak takto:
SUB (R)SP, PocetBajtuKtereZabirajiLokalniPromenne
Teoreticky ale ne všechny proměnné je nutné ukládat na zásobník, některé mohou žít (a je to ideální stav) jen v registrech.
Jinak řečeno, procesoru nemusíš nějak speciálně říkat, že voláš nějakou funkci rekurzivně. VOláš ji prostě jako jakoukokli jinou (jistě, pro procesor je rekurzivní volání asi fajn, neb daný kód bude mít určitě v L1 cache, ale to je pro tento příspěvek vedlejší).
Co se týče samotného psaní funkcev Assembleru, pokud se s tím moc nechces "mazat", nech za tebe práci vykonat překladač a jeho výsledek si uprav dle svého (tzn. nech si od něj vygenerovat ASM listing té funkce, nebo si ji vytáhni disassemblerem z přeložené binárky). Já vím, je to ošklivý podvod, ale můžeš se tím vyhnout nepříjemným chybám, které se těžko hledají.
Mimochodem, proč ses rozhodl použít mergesort? Jelikož jej potřebuješ napsat v Assembleru, asi ti jde o výkon. Nebylo by pak lepší zkusit použít třeba quicksort, který je v průměrném případě (nej)rychlejší? Případně pokud máš těch čísel k třídění opravdu hodně, nebo toho třídění děláš hodně, trošku tu práci paralelizovat a zaměstnat celý procesor, ne jen jedno jádro?
Díky za info. Nejde mi o assembler, ten znám celkem perfektně, včetně předávání funkcí. Jde mi o tu funkci v C++, která funguje. Při ladění programu jsou před jejím voláním hodnoty "l" a "r":
0 0 0 0 1 2 3 3 3 4 5
5 2 1 0 1 2 5 4 3 4 5
Pokud přesně nevím, jak u této funkce funguje předávání hodnot při rekuzivním volání, těžko to mohu naprogramovat v asm.
Program chci použít na setřídění pole dat (__int32) o velikosti 50 mil. řádků (data v 7GB RAM). Nyní mi vyhledání hodnoty v nesetříděném poli trvá v assembleru cca 2 sekundy. Chci to zkusit urychlit na pár ms, v poli hledám pro jednu úlohu asi 1 000 za sebou. Merge sort by pro to měl být ideální.
Ukázka funkce v asm (pro pole o 6ti číslech, oproti C++ v kódu zatím nemám funkci merge):
...
mov r8, 0 ; "l"
mov r9, 5 ; "r"
call MS
xor rax, rax ; Vrátíme 0
pop rdi
pop rsi
pop rbx
ret
MS:
cmp r8, r9
jge MS_end ; "l" >= "r" tak konec
mov rax, r9
sub rax, r8 ; "r" - "l"
shr rax, 1 ; /2
add rax, r8 ; +"l"
mov [rsi+96], rax ; "l" a "m" = l + (r - l) / 2 (dočasné ulož. "m" v rámci
mov r9, rax ; jednoho volání funkce, rsi bych měl asi incrementovat
call MS ; /decrementovat podle instance rekurz. volání funkce)
mov rax, [rsi+96]
inc rax
mov r8, rax ; "m"+1 a "r"
call MS
MS_end:
ret
Funkce_Sort ENDP
END
Pokud přesně nevím, jak u této funkce funguje předávání hodnot při rekuzivním volání, těžko to mohu naprogramovat v asm.
Ta funkce setřídí pole mezi indexy l a r (včetně krajních mezí). Toto o ní potřebuješ vědět, i když ji programuješ v jakémkoliv jazyce. Assembler tady nic nepřidává.
Merge sort by pro to měl být ideální.
Tam může být problém v tom, že jej voláš i třeba na setřídění dvojic čísel (nebo krátkých úseků), kde je režie samotných volání vyšší než vlastní třídění.
50 mil. řádků (data v 7GB RAM)
Hm, to bych se asi spíš zamyslel nad vícevláknovým provedením toho třídění, tím by se teoreticky mohlo dát ušetřit víc. Zrovna mergesort celkem paralelizovat jde, alespoň první kroky.
Zobrazeno 4 zpráv z 4.