[nem-pl] rekursje ogonowe

[Michal Moskal]

Background:

W IL można napisać tail.call jakaś funkcja, co oznacza, że ramka stosu
aktualnej funkcji zostanie zastąpiona nową ramką.

Flaga kompilatora -general-tail-call-opt włącza emisję przedrostków
tail.  Niestety jest to trochę zepsute w mono, bug 53030 w mono bts.

Wcześniej mieliśmy bardziej ograniczoną formę eliminacji rekursji
ogonowej, która działała tylko jeśli funkcja f wywoływała samą siebie --
było to zamieniane na podstawienie pod argumenty i skok. Dodanie tej
optymalizacji jeszcze w czasach kompilatora z C# pośrodku poprawiło
wyniki na mono o około 20%.

Dodałem tę optymalizcję teraz. Żeby ją wyłączyć należy napisać
-no-self-tail-call-opt.

Mierzenie czasu:

W mono nie ma żadnej różnicy! Tzn. włączanie lub wyłącznie rekursji
ogonowej nic nie daje. Strasznie mnie to zdziwiło, ale to jeszcze nie
koniec.

W .NET włączenie self tail calls, bez general tail calls powoduje
przyrost prędkości o jakieś 3% (to może być błąd pomiaru). Natomiast
włączenie tylko general tail calls, bez self tail calls powoduje
*spadek* prędkości o 15%. To ostatnie jest naprawdę dziwne...

Chyba pójde już spać...

Tego użyłem do kompilacji poszczególnych wersji.

#!/bin/sh
 
s="extensions.n globalenv.n localvalue.n typingcontext.n macros.n macroregistry.n typattern.n tyexpr.n members.n tyinfo.n ../lib/aliases.n ../lib/core.n ../lib/option.n ../lib/list.n tree.n ../lib/hashtable.n ../lib/stack.n ../lib/queue.n ../lib/input.n ../lib/getopt.n ../lib/icollection.n ../lib/tree.n ast.n parsetree.n typedtree.n util.n passes.n scan_globals.n tyvars.n tyutil.n parser.n main.n flags.n lexer.n tycon.n cgtree.n cgexpr.n cgopt.n external.n xmldump.n cgil.n"
 
set -x
 
./ncc2.exe -no-tail-call-opt -self -texe -out ncc-no-tco.exe $s
./ncc2.exe -general-tail-call-opt -no-self-tail-call-opt -self -texe -out ncc-just-general.exe $s
./ncc2.exe -self -texe -out ncc-just-self.exe $s
./ncc2.exe -general-tail-call-opt -self -texe -out ncc-general-and-self.exe $s

Natomiast same exeki testowałem tak:

time ./ncc-just-general.exe -self -texe -out ncc-test-out.exe $s

-- 
: Michal Moskal :: http://www.kernel.pl/~malekith : GCS {C,UL}++++$ a? !tv
: When in doubt, use brute force. -- Ken Thompson : {E-,w}-- {b++,e}>+++ h