Diskuze: C++ Hodnoty proměnných při rekuzivním volání funkce

Caster

Člen

Caster:25.5.2018 20:38

Potřeboval bych napsat následující funkci v assembleru, ale není mi jasné, jak rekurzivní volání funguje.

/* l is for left index and r is right index of the
sub-array of arr to be sorted */
void mergeSort(int arr[], int l, int r)
{
        if (l < r)
        {
                // Same as (l+r)/2, but avoids overflow for
                // large l and h
                int m = l + (r - l) / 2;

                // Sort first and second halves
                mergeSort(arr, l, m);
                mergeSort(arr, m + 1, r);

                merge(arr, l, m, r);
        }
}

Jde o část programu, který setřídí pole dat. Hlavní část programu je:

int main()
{
        int arr[] = { 12, 11, 13, 5, 6, 7 };
        int arr_size = sizeof(arr) / sizeof(arr[0]);

        printf("Given array is \n");
        printArray(arr, arr_size);

        mergeSort(arr, 0, arr_size - 1);

        printf("\nSorted array is \n");
        printArray(arr, arr_size);
        return 0;
}

Nevím přesně, jak je to s předáváním parametrů při rekurzivním volání. Předpokládám, že proměnné funkce mergeSort int l, int r zůstavají během opakovaného volání stále stejné, t.j. mají stále stejné hodnoty, pokud je program nezmění.

Proměnná int m = l + (r - l) / 2; která je definována uvnitř funkce asi při opakovaném volání funkce nabývá různých hodnot.

Odpovědět

25.5.2018 20:38

Martin Dráb

Tvůrce

Martin Dráb:25.5.2018 20:57

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á

parametry zprava doleva hodit na zásobník (PUSH ...)
návratová hodnota se předává v registru (E)AX,
zásobník spotřebovaný na parametry uklízí volaná funkce (RET n*4).

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?

Nahoru Odpovědět

25.5.2018 20:57

2 + 2 = 5 for extremely large values of 2

Caster

Člen

Caster:25.5.2018 21:30

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

Nahoru Odpovědět

25.5.2018 21:30

Martin Dráb

Tvůrce

Martin Dráb:25.5.2018 21:46

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.

Nahoru Odpovědět

25.5.2018 21:46

2 + 2 = 5 for extremely large values of 2