[nem-pl] stos

[Marcin 'Qrczak' Kowalczyk]

W liście z pią, 20-02-2004, godz. 11:54, Lukasz Kaiser pisze:

> Hmm, mozesz mi powiedziec w jaki sposob ? Czy ty masz jakas super
> optymalizacje rekursji ogonowej czy po prostu sam implementujesz stos ?

Sam implementuję stos, co tak czy siak jest konieczne przy kompilacji
do C, jeśli się chce mieć dobrą rekurencję ogonową. Nie robię żadnych
akrobacji, żeby próbować zmienić asymptotyczne koszty tego przykładu,
w szczególności append używa tyle stosu ile myślisz.

Co do samej rekurencji ogonowej, opcjonalnie postprocesuję asemblerowy
wynik kompilatora C, żeby zamienić przenośne wołanie ogonowe przez
zwracanie wskaźnika na następną funkcję do driver loop na efektywne
wołanie ogonowe przez jmp.

Używam wirtualnych rejestrów w zmiennych globalnych, dzięki czemu
funkcje, które nie wołają nieogonowo żadnych innych funkcji, nie
potrzebują (prawie nigdy) ramki stosu, więc w szczególności nie muszą
sprawdzać przepełnienia stosu. Ramka stosu jest alokowana tak późno, jak
to możliwe, więc funkcja, która dla niektórych parametrów od razu wraca
albo skacze, a dla innych nie, też ma szansę nie użyć ramki stosu. Więc
sprawdzanie przepełnienia stosu nie jest dużym kosztem, a daje komfort
braku SIGSEGV-ów - zwłaszcza jeśli kiedyś zrobię wątki, którym inaczej
nie byłoby wiadomo, ile stosu dawać.

(SIGSEGV niestety jest jednak możliwy przy operacjach na bardzo dużych
liczbach, bo GMP domyślnie używa alloca() dla tymczasowych wartości, nie
sprawdzając przepełnienia.)

-- 
   __("<         Marcin Kowalczyk
   \__/       qrczak at knm.org.pl
    ^^     http://qrnik.knm.org.pl/~qrczak/