Temat: Tail call w C#, F#

Kiedyś w tym wątku wspomniałem, że zainteresuję się obsługą tail call i tym samym chciałem się podzielić moimi próbami.
Najpierw przykład w F# - rekurencyjne wyliczenie sumy wyrazów ciągu arytmetycznego 1, 2 ... aż do 1 miliona! Ten milion gwarantuje, że bez użycia tailcall będziemy mieli StackOverflowException. I tak F#:

let rec SumIt aList acc:int64 =

    match aList with

    | [] -> acc

    | head::rest -> SumIt rest (acc+head)



let sum = SumIt [1L..1000000L] 0L

printfn "Wynik: %d" sum

działa. Jak widać F# jako język funkcjonalny radzi sobie dobrze z rekurencją.
Oto mniej więcej odpowiednik w C# - różnice wynikają po prostu z różnych języków, ale koncepcyjnie algorytm ten sam: wywołaj rekurencyjnie sumę dla pozostałych elementów na liście:

static class Program {

	const int MAX_LENGTH = 1000000;

	static void Main(string[] args) {

		int[] _init = new int[MAX_LENGTH];

		for(int i=0; i<MAX_LENGTH; i++) _init[i] = i+1;

		Console.WriteLine(SumIt(_init, 0, 0L));

	}

	static Int64 SumIt(IList<int> aList, int pos, Int64 acc) {

		return (pos < MAX_LENGTH) ? SumIt(aList, pos+1, acc + aList[pos]) : acc;

	}

}

No i tutaj mamy StackOverflowException - kompilator C# nie generuje - przynajmniej mi się nie udało go do tego zmusić - wywołania tail call. Natomiast mógłby, o czym łatwo się można przekonać wprowadzając poprawkę na poziomie IL. Wpierw dekompilacja:
ildasm ConsoleApplication1.exe /out:test.il
potem w notatniku trzeba dodać prefix tail.:

    IL_0017:  add

    tail.	//o tutaj, mniej wiecej pod koniec

    IL_0018:  call       int64 ConsoleApplication1.Program::SumIt(class [mscorlib]System.Collections.... ciach

ponowna kompilacja:
ilasm test.il /out:test.exe
i nie ma już StackOverflowException.

Jak widać, gdyby kompilator C# chciał to mógłby... a sprawdzałem w .NET 3.5SP1, 4.0 i to samo. Coś mi mówi, że F# nieźle namiesza w głowach:)

Temat: Tail call w C#, F#

Jest więcej takich instrukcji które nie są wykorzystywane w C# a są np w C++ itp. Generalnie interesujące jest zrobienie narzędzia które w post kompilacji pozmienia instrukcje mało wydajne na bardziej wydajne, gdzieś na blogu mono pojawił się nawet taki pomysł.

Maciek btw co sądzisz o F#? Jakoś nigdy nie miałem czasu się nim zainteresować, ale sama idea języków funkcyjnych wydaje mi się ciekawa (bardzo lubię wyrażenia lambda :) )

Temat: Tail call w C#, F#

Bartosz Adamczewski:
Maciek btw co sądzisz o F#? Jakoś nigdy nie miałem czasu się nim zainteresować, ale sama idea języków funkcyjnych wydaje
mi się ciekawa (bardzo lubię wyrażenia lambda :) )

Ja nigdy w pełni nie wykorzystywałem obiektowości, więc siłą rzeczy pozostaje mi programowanie funkcjonalne. Ale nie tylko mi, każdy kto pisał coś w tSQL (bez cursorów) może śmiało powiedzieć, że programuje funkcjonalnie, operując na relacjach. Wyrażenia lambda to oczywiście jeden z produktów flagowych, więc reszta też Ci się spodoba:)

Wszystkim gorąco polecam książkę znanego Jona Skeeta Functional Programming in .NET - jest o tyle dobra, że zawiera więcej praktyki niż akademickich rozważań o wyższości OO Programming vs Functional Programming oraz ucząc F# opiera się na kodzie C# zatem można sobie łatwo przetłumaczyć o co chodzi.
Próbowałem kiedyś podejścia do F# przez inną książkę F# for Scientists ale poległem po pierwszym rozdziale, natomiast książka Jona po prostu uczy nie tyle samej składni F# ile pokazuje, jak myśleć funkcjonalnie.
Ja uważam, że to obowiązkowa lektura - niezależnie od tego, czy ktoś lubi FP czy nie, powinien poznać jego możliwości.

Temat: Tail call w C#, F#

maciek kański:
Jak widać, gdyby kompilator C# chciał to mógłby...

Jakby chciał i jakby mógł być niekompatybilny wstecz. Na zmianę logiki budowania stackframe'u raczej się MS nie zgodzi. W C# z założenia masz widzieć wszystkie ramki, więc tailcall odpada. Zresztą jak chcesz tailcall, to możesz go symulować trampoliną tam gdzie potrzeba ;)

Temat: Tail call w C#, F#

Stanisław Pitucha:
i jakby mógł być niekompatybilny wstecz. Na zmianę logiki budowania stackframe'u raczej się MS nie zgodzi.

No ale można by dodać jakiś atrybut np:

[UseTailCall(true)]

static Int64 SumIt(IList<int> aList, int pos, Int64 acc) {

    (...)

}

i domyślnie zachować kompatybilność wstecz.

Temat: Tail call w C#, F#

Hmm... można by się pokusić o automatyzację tego przez Cecil :) W sumie to nie problem znaleźć exit-block'i kończące się call'em...

Temat: Tail call w C#, F#

Spokojnie da radę też PostSharpem taki atrybucik wdorożyć - swego czasu zrobiłem coś takiego do wymuszania atrubytu BeforeFieldInitAttribute (co można uznać za zabawę i trening) oraz exportowania metod kodu zarządzanego tak, aby można go było wywoływać z niezarządzanego C++ (odpowiednik .NETowego DllImportAttribute; trzeba było zmienić tylko corflags, zrobić vtfixup a potem w oznaczonych metodach dodać vtentry i export). To akurat było mi potrzebne w pracy.

Ale wracając do tematu ja się pytam - po co taki atrubyt UseTailCallAttribute, skoro mamy F#? :-) W moim przypadku (nazwijmy to DllExport) w 2.0 po prostu nie miałem innego rozwiązania (poza manulną edycją ILa, co siłą rzeczy było bez sensu). Skoro i F# i C# to ta sama platforma, w C# robimy sobie wszystkie data entities, w F# wydajne algorytmy (jeżeli ich potrzebujemy oczywiście) i gotowe.

KIS :-)

Temat: Tail call w C#, F#

Krzysztof Mierzejewski:
Ale wracając do tematu ja się pytam - po co taki atrubyt UseTailCallAttribute, skoro mamy F#? :-)
Skoro i F# i C# to ta sama platforma, w C# robimy sobie wszystkie data entities, w F# wydajne algorytmy (jeżeli ich potrzebujemy oczywiście) i gotowe.

Ja się zgadzam z Tobą w 100%, że tak właśnie soft się będzie pisało.
A sam atrybut to odpowiedź na pytanie Stanisława odnośnie kompatybilności wstecz.

Temat: Tail call w C#, F#

Co do samej rekurencji to:
Zrobiłem małe zestawienie wydajności dla funkcji fib dla C# jak i F#.

Być może nie jest to najlepszy przykład ale jako że dopiero uczę się F# (właściwie to mój pierwszy program), więc nie należy tego traktować jako pełne testy wydajnościowe rekurencji o obu językach.

C#:



        public long Fib(int n)

        {

            if (n == 1)

                return 1;

            else if (n == 2)

                return 2;

            else

                return Fib(n - 1) + Fib(n - 2);

        }



        public long FibA(int n)

        {

            return Fibx(n, 0, 1);

        }



        private long Fibx(int n, int a, int b)

        {

            if (n == 0) return a;

            else return Fibx(n - 1, a + b, a);

        }



F#:



let rec fib(n) =

    if n = 1 then 1

    elif n = 2 then 2

    else

    fib(n - 1) + fib(n - 2)



let rec fibm(n) =

    match n with

    | 1 -> 1

    | 2 -> 2

    | n -> fib(n - 1) + fib(n - 2)

        

let fibA(n) =

    let rec fibx (n, a, b) =

        match (n, a, b) with

          | (0, a, b) -> a

          | _ -> fibx (n - 1, a + b, a)

    fibx (n, 0I, 1I)

Zrobiłem małe zestawienie wydajności.

w przypadku funkcji fib dla n = 42

C# : 9 sek
F# : 6 sek fibm jest ok 200 ms wolniejsze.

w przypadku funkcji fibA dla n = 42
C# : 5 ms
F# : 350 ms

w obu przypadkach kompilator nie pokusił się o tail call.

Temat: Tail call w C#, F#

Być może nie jest to najlepszy przykład ale jako że dopiero uczę się F#

ja też się uczę i dość szybko doszedłem do prostszego zapisu mojej funkcji:

[1L..1000000L] |> List.fold (fun acc element -> acc+element) 0L

używam interactive console w VS. Teraz to jest zapis Funkcjonalny:)

w przypadku funkcji fibA dla n = 42
C# : 5 ms
F# : 350 ms

w obu przypadkach kompilator nie pokusił się o tail call.

w fsc.exe jest przełącznik --tailcalls plus odpowiedni ptaszek w ustawieniach projektu w VS, może on coś daje

Temat: Tail call w C#, F#

Jeszcze taka mała ciekawostka: [...] the C# compiler does not do tail call optimization. Instead, all managed languages have a second opportunity to optimize through either NGEN or the JIT compiler. As it turns out, the x64 version of the JIT will optimize the tail call right now, whereas the 32 bit compiler will not..

Temat: Tail call w C#, F#

Bartosz Adamczewski:

C#:

        public long Fib(int n)

                return Fib(n - 1) + Fib(n - 2);



        public long FibA(int n)

            return Fibx(n, 0, 1);



        private long Fibx(int n, int a, int b)

            else return Fibx(n - 1, a + b, a);



F#:

let rec fib(n) =

    fib(n - 1) + fib(n - 2)



let rec fibm(n) =

    | n -> fib(n - 1) + fib(n - 2)

        

let fibA(n) =

    let rec fibx (n, a, b) =

          | _ -> fibx (n - 1, a + b, a)

    fibx (n, 0I, 1I)

Zrobiłem małe zestawienie wydajności.

w przypadku funkcji fib dla n = 42

C# : 9 sek
F# : 6 sek fibm jest ok 200 ms wolniejsze.

w przypadku funkcji fibA dla n = 42
C# : 5 ms
F# : 350 ms

w obu przypadkach kompilator nie pokusił się o tail call.

Nie mógł w przypadku fib(). Wywołanie fib nie jest ostatnią instrukcją funkcji (jest jeszcze "+"). A fibA() - wychodzi na to, że to match jest dosyć wolny (i fibm i fibA jest wolniejsze)... - może spróbujesz bez niego?Stanisław Pitucha edytował(a) ten post dnia 11.02.10 o godzinie 13:04

Temat: Tail call w C#, F#

Stanisław Pitucha:
Nie mógł w przypadku fib(). Wywołanie fib nie jest ostatnią instrukcją funkcji (jest jeszcze "+"). A fibA() - wychodzi na to, że to match jest dosyć wolny (i fibm i fibA jest wolniejsze)... - może spróbujesz bez niego?

Wczoraj jeszcze porobiłem kilka testów i wymusiłem na nim tail w opcjach projektu ale za wiele to nie dało, natomiast ponowny call tej samej metody dał już z 80 ms w przypadku fibA. Ale co nie zmienia faktu ze i tak myślałem że prędkość będzie zawrotna a tu pff :)

fib jest trochę złym przykładem. Może napisze jakieś sortowanie kolekcji.

maciek kański:
ja też się uczę i dość szybko doszedłem do prostszego zapisu
mojej funkcji:

[1L..1000000L] |> List.fold (fun acc element -> acc+element) 0L 

używam interactive console w VS. Teraz to jest zapis Funkcjonalny:)

 let fibs = Seq.unfold (fun (a, b) -> Some(a, (b, a + b) )) (1,1)

let x = Seq.toList (Seq.take 42 fibs);

Maciek czy teraz juz jestem Funkcyjny ? ;-)

apropo to rozwiązanie tez daje ok 300 msBartosz Adamczewski edytował(a) ten post dnia 11.02.10 o godzinie 15:06

Temat: Tail call w C#, F#

Wywołanie fib nie jest ostatnią instrukcją funkcji

No właśnie tak z ciekawości: czy ktoś potrafi zapisać funkcjonalnie (nie imperatywnie) tego Fibonnaciego aby się nadawał
do taila? Bo chyba funkcjonalności kodu nie połączymy tutaj z jego wydajnością.

Znane z SQLa problemy: nie wystarczy napisać co chcemy, musimy się zastanawiać nad tym jak to osiągnąć:)

Dodano:

Maciek czy teraz juz jestem Funkcyjny ? ;-)

niestety nie:) Funkcjonalnie to zgodnie z definicją, tj: fib(n - 1) + fib(n - 2)
Uczciwie się przyznam, że zrozumienie zasady działania twojej funkcji zajęło mi trochę czasu, w przeciwieństwie do zrozumienia samej definicji, która jest oczywista.maciek kański edytował(a) ten post dnia 11.02.10 o godzinie 15:19