Fremtidige løfter

Sunday, August 8th, 2010
Skriv en kommentar

Nei, denne blogposten handler ikke om nyttårsforsetter, og heller ikke om politiske valgløfter. Den handler om to concurrency-relaterte features i Clojure som heter future og promise. Tilsvarende abstraksjoner har jeg ikke vært borti i andre språk, men til slutt i denne blogposten vil jeg implementere lignende funksjonalitet i C#.

Future er en liten makro som vil kjøre koden du gir den i en ny tråd. Resultatet av koden vil bli cachet, slik at man ikke behøver å re-kalkulere verdien hver gang man refererer den. Her er et lite eksempel:

(def radius 5.8)

(def x (future
(Thread/sleep 1000) ; simulerer at dette tar litt tid
(* 3.141592 radius radius)))

(time (println “Arealet er” @x))
(time (println “Arealet er” @x))

Output:

Arealet er 105.68315488
“Elapsed time: 1000.634298 msecs”
Arealet er 105.68315488
“Elapsed time: 1.096718 msecs”

Future er glimrende når man skal opprette en verdi som det tar litt tid å beregne, og man ikke nødvendigvis trenger verdien med en gang. Når man trenger verdien og den ikke er ferdig beregnet vil man måtte vente til den er ferdig. Men man kan også bruke future til samtidighet generelt, for å kjøre kode i en annen tråd, uten å bry seg om returverdien.

Promise er et løfte om at vi skal beregne en verdi på et eller annet tidspunkt. Her er et Hello World-eksempel som bruker både promise og future:

(comment “Promise that there at some point will be a
name to greet..”)
(def name-to-greet (promise))

(comment “At some point in the future, when there is
a name to greet, say hello”)
(future (println “Hello,” @name-to-greet))

(comment “Ask for the user’s name, and deliver on the
promise made earlier.”)
(print “What is your name? “) (flush)
(deliver name-to-greet (read-line))

(shutdown-agents) ; Just some thread cleanup

Future brukes til å opprette en tråd hvor man trenger verdien som er lovet. Den vil stå og vente på at verdien er tilgjengelig. Når vi leverer det vi har lovet kan futuren fullføres.

Eksempelkjøring:

What is your name? Billy Bob
Hello, Billy Bob

Advarsel: Promise er merket med “Alpha – subject to change” i API-dokumentasjonen. Bruk den derfor med varsomhet.

Som nevt i innledningen vil jeg nå vise én mulig C#-implementasjon av det jeg har vist. Det er godt mulig det finnes bedre måter, og at for eksempel Task Parallel Library i .NET 4.0 kan brukes på samme måte (har ikke lekt med det enda), men jeg synes følgende abstraksjoner ble ganske så fine. Først begynner vi med en C#-variant av den første Clojure-demoen:

static void Main(string[] args)

    const double radius = 5.8;

    var x = Future.Create(() =>

        Thread.Sleep(1000);

        return 3.141592 * radius * radius;

});

    Benchmark.Measure(() => Console.WriteLine(x.Value));

    Benchmark.Measure(() => Console.WriteLine(x.Value));

Her brukte jeg QuickBencher (et open source prosjekt jeg har liggende på CodePlex) til å måle forbrukt tid, og verifiserte samme oppførsel som Clojure-varianten.

Før jeg viser implementasjonen av Future-klassen tar vi også med en C#-variant av promise-eksempelet:

class Program

    static void Main(string[] args)

        var nameToGreet = new Promise<string>();

        Future.Create(() => Console.WriteLine("Hello {0}", nameToGreet.Value));

        Console.Write("What is your name? ");

        nameToGreet.Deliver(Console.ReadLine());

Ser ganske greit ut, ikke sant? Denne koden fungerer også som den skal. Her følger til slutt implementasjonen av Promise og Future. Legg merke til at Future egentlig er to ulike klasser, hvor den ene representerer en Future som har en returverdi. Create-metodene i den ikke-generiske klassen brukes til å opprette riktig type basert på lambda-argumentet.

public class Promise<T>

    private T _value;

    private bool _delivered;

    public T Value

get

            while (!_delivered) Thread.Sleep(10);

            return _value;

    public void Deliver(T value)

        _value = value;

        _delivered = true;

public class Future<T>

    private Thread _producerThread;

    private T _value;

    public T Value

get

            _producerThread.Join();

            return _value;

    public Future(Func<T> producer)

        _producerThread = new Thread(() => _value = producer());

        _producerThread.Start();

public class Future

    public static Future<T> Create<T>(Func<T> producer)

        return new Future<T>(producer);

    public static Future Create(Action action)

        return new Future(action);

    public Future(Action action)

        new Thread(() => action()).Start();

Promise fungerer rett og slett slik at om man forsøker å aksessere verdien før den er satt så vil den vente til den har en verdi å levere (med en optimistisk og kanskje litt naiv loop). Future fungerer ved at den eksekverer jobben den har fått i en ny tråd. Versjonen som har en returverdi er nokså lik Promise; om man forsøker å aksessere verdien sørger jeg for at tråden er ferdig med det den skal gjøre (altså produsere verdien) før jeg returnerer ved å kalle Join() på tråden.

I eksempelet hvor jeg kombinerte Promise og Future vil altså futuren stå og vente på at løftet leveres. Og løftet står og venter på at jeg taster inn navnet mitt, som jeg gjør i hovedtråden.

Spørsmål?

Kategorier: LISP/Clojure, OO-design/clean code, Polyglot.
RSS feed for kommentarene. Tilbaketråkk.

4 kommentarer til “Fremtidige løfter”

Vidar Says:
August 9th, 2010 at 8:28 am
Tør eg foreslå å bruke http://msdn.microsoft.com/en-us/library/system.threading.autoresetevent.aspx istedet for while(..) sleep(). ;) Etter å ha oppdaga den prøver eg sjøl i mest mulig grad å bruke den istedet når eg lager parallell kode.

Når det gjelder Future så vil Async-cache gi deg noge av den samme funksjonaliteten, dog ikkje heilt samme, men eg anbefaler deg å ta ein kikk:
http://blogs.msdn.com/b/pfxteam/archive/2010/04/23/10001621.aspx

Og TPL + extensions extras e virkelig kult! ;)
Anders Norås Says:
August 9th, 2010 at 8:56 am
Fin fin post Torbjørn.

Jeg tror den mest kjente implementasjonen av future-patternet på .NET-plattformen må være NHibernate.Futures, men også LINQs defered execution er en variant av dett. I en ORM er det massevis av sense i å benytte slike patterns, slik at rammeverket selv kan optimere spørring mm.

Jeg likte særlig godt at du benyttet delegates fremfor å gå den “magiske” AOP-veien med implementasjonen din. Ved å bruke delegates eksplisitt blir det lettere å lese koden og man vet at man ikke har noen garanti for at en delegate eksekveres umiddelbart dersom man har noen år med C# i ryggen.

Selvom Clojure-eksemplet, og mange andre eksempler man ser, fokuserer på multi-threading, har egentlig dette patternet lite å gjøre med multi-threading. Ta NH-eksemplet jeg refererte til. NH bruker futures for å “lære” mer om hva brukeren faktisk har til hensikt å gjøre slik at databasespørringene blir mer effektive. (Se linken over for kodeeksempeler).
Tenk også en eller annen form for aggregeringskode:

IProducer p = new Producer();
IFuture c = p.Count();
IFuture maxl = p.Max(x => x.Length);
p.Produce(strings);
Console.WriteLine(“Actual count: ” + c.Value);
Console.WriteLine(“Actual max length: ” + maxl.Value);

Her brukes futures for deklare antall og makslengde-aggregatorer før man jobber med data. Selve aggregeringen gjøres først når man leser av verdien. Dette er tilsavarende hvordan deferred execution i LINQ fungerer. Der kan man deklarere en spørring, men denne utføres ikke før man prøver å lese resultatet.
Torbjørn Says:
August 9th, 2010 at 10:18 am
Takk, Vidar. Her er Promise implementert med AutoResetEvent. Den fungerer nå litt anderledes, og kan gjenbrukes. Den forventer nå et kall til Deliver for hver gang man aksesserer Value. Vil du ha en versjon som “leveres” én gang men kan aksesseres mange ganger kan du kombinere implementasjonen av min orginale Promise med denne. Kommer an på hvordan man forventer at den skal fungere..
```
    public class Promise
    {
        private T _value;
        private AutoResetEvent _delivered = new AutoResetEvent(false);
        public T Value
        {
            get
            {
                _delivered.WaitOne();
                return _value;
            }
        }
        public void Deliver(T value)
        {
            _value = value;
            _delivered.Set();
        }
    }
```
Vidar Says:
August 9th, 2010 at 10:37 am
:) Glimdrende, den implementasjonen vil nok vere ein god del meir cpu-effektiv, siden tråden nå ikkje “våkner” opp kvart 10ms for å sjekke om den har fått noge data.
Men både med denne implementasjonen og den originale så må ein være bevisst at ein kan havne i ein deadlock-situasjon, der kode som venter på Promise blir ståande og vente i all evighet. Enten fordi ein har “glemt” å faktisk gi data til Promise, eller fordi ein av trådane har kasta ein exception før den fekk gitt ein verdi. Eg har hatt eit par sånne bugs og det som skjer er at hovedtråden bare står og spinner mens den venter på at alle trådane skal bli ferdig. Eg jobber med ein ganske massiv parallell kodebase nå, og har hatt eit par tilsvarende Heisenbugs. Heisenbugs fordi det er ikkje alltid trådane som skal sende ut verdi går i Exception. ;)