Bobrisuv blog

Zjednodušení DynamicMethod

bobris — Thu, 06 Oct 2011 21:35:35 GMT

Možná si ještě vzpomínáte jak jsem tu nedávno ukazoval zjednodušení pro generování IL kódu za běhu programu. No a když začnete generovat velké množství IL kódu, tak se asi chybám nevyhnete. Když generujete celou assembly, tak ji není problém uložit a podívat se na ní reflektorem(nebo ILSpy a spoustou jiných klonů), či zkontrolovat pomocí PEVerify. No jo ale co když používáte pouze DynamicMethod? Určitě se hodí tento Debugger Vizualizer. Ale problém se pěkně vyřeší až tímto obalem:

Nejdříve odkazy na zdroják:

https://github.com/Bobris/BTDB/blob/unstable/BTDB/IL/DynamicMethod.cs

Po staru bylo nutné napsat toto:

var method = new DynamicMethod("SampleCall", typeof(Nested), Type.EmptyTypes);
…
var action = (Func<Nested>)method.CreateDelegate(typeof(Func<Nested>));

Jak vidíte kód obsahuje velké množství duplicitní informace. Pomocí právě představené generické obálky už jen takto krátce:

var method = new DynamicMethod<Func<Nested>>("SampleCall");
…
var action = method.Create();

Ale hlavní výhoda je, že implementaci obálky můžeme na jednom místě změnit a tak místo generování pouze kódu v paměti, vytvořit i dll, kterou můžeme lehce zkontrolovat a tak rychleji odstranit chyby.

Na závěr malý hartusení(rant). Metro Win8 .Net aplikace zatím podporují právě pouze DynamicMethod (což byla novinka .Net 2.0), i Silverlight 4 podporuje podstatně rozsáhlejší DynamicAssembly, jak si MS vůbec může dovolit takovéto regrese ve funkcionalitě je pro mne záhadou. Bohužel při tolik opěvovaném jarním úklidu .Netu omylem rozbili i pár čínských váz. Portable Library project pak neobsahuje ani tuto DynamicMethod, ale oni šli ještě dál, protože tam nejsou ani Collections.Concurrent a ani Task<T>, takže to je snad vhodný jen na DTO objekty… Ale chápu, že vynoření z téhle bažiny nekompatibilit, kterou si ovšem naprosto zbytečně zavařili sami, něco dá a jsem rád, alespoň za tuto snahu.

Opravdu nema .Net budoucnost?

bobris — Wed, 28 Sep 2011 22:41:07 GMT

Nejdrive jsem to psal jako komentar k http://blog.vyvojar.cz/michalowo/archive/2011/09/27/vc-11-aneb-postupn-konec-netu.aspx, ale uz to bylo moc dlouhy tak to hodim do blogu, navic jsem stejne k tematu chtel neco napsat.

Myslim, ze to Michal nemyslel vazne, a chtel si jen zadiskutovat, ci zjistit pocity komunity k tematu, tak tedy do toho…

Nejdrive k “WinC++” se jiz vzilo oznaceni C++/CX. Pro ty co to jeste nevedi tak to je nastavba C++, syntaxi temer identicka k C++/CLI, ale s uplne jinym nativnim kod generatorem.

Souhlasim, ze WinRT je hodne o vyhre Windows divize(dale jen WinDiv) a mit neco rychle aby iPad nemel naskok 3 roky. Ale DevDiv pouzila trojskeho kone jmenem Async. Ano tim ze udelali vsechno async a C++ na rozdil od C#/VB pro to nema podporu, tak se v tom neda programovat nic slozitejsiho a uz vubec se to neda cist. Dodelat podporu pro Async do jazyka tak sloziteho jako je C++ a navic bez GC (jak vyresit closure?), je prakticky nemozny. Dnes je opravdu hodne modni mluvit o renezanci C++, ale v realu to neni zadna sranda, rychlosti kompilace a linkovani jsou stale k placi.

WinRT je stale "common runtime" (ve vyznamu ze musi byt pouzitelne z vice jazyku/platforem) a uz pomalu vyliza na svetlo jak pomaly to je (Jasne ze v dobe JS v mainstreamu uz na rychlost nikdo nehraje). Vetsina lidi totiz neumi Assembler (a priznam se ze ani me to netrklo i kdyz se mi to zdalo divny), tak si te lzi na Buildu jako ze v C++ to je jen prime volani metody nevsimla, detaily zde http://www.interact-sw.co.uk/iangblog/ (pokud to nechcete cist cely tak hledejte “That’s Not a Vtbl—THIS is a Vtbl”). Samozrejme ted uz se tahle lez vsude opakuje, dulezity je marketing, ne realita, a v “Hello world” aplikacich na tom fakt nezalezi, a jiny se na tablety delat nebudou.

V komentarich se strhla diskuze o GC k tomu muj pohled: GC je samozrejme vyrazne rychlejsi nez atomicky reference counting (I v MS to vedi minimalne 11 let viz http://blogs.msdn.com/b/brada/archive/2005/02/11/371015.aspx). Vyhoda C++ je v tom, ze kdyz si date hodne prace s optimalizacemi (manualnimi), tak se muzete vyhnout tomu reference countingu a tak byt vetsinou rychlejsi, stale ovsem zustava problem s fragmentaci pameti (V Metro aplikacich ume “vyreseno” nepodporou behu aplikaci na pozadi :-). Navic casto navrhovane rozdeleni aplikace na UI v C# (nedej boze v JS) a zbytek v C++, tak ma prave problem s navrhem rozhrani (ve smyslu interface) – jakekoliv volani na rozhrani (ve smyslu boundary :-) bude mit klasicky vykonostni propad jako v pripade PInvoke, takze to co mozna ziskate v C++ tak hned ztratite…

K MS, a jejich strategii. Tim ze i z MS zazniva odklon od .Netu, tak si predcasne podkopavaji WP7(.5). Protoze jestlize WP8 budou postavene nad WinRT, tak se budou muset vsechny aplikace napsat znovu, a tim vyvojare k WP7.5 neprilakaji.

Jinak asi dost hodne .Net vyvojaru v MS uteklo do Midori, i kdyz nevim jestli tam zustanou pred WinDiv v bezpeci.

Zpet k .Netu:

.Net a obecne managed prostredi maji vyhodu v JITu, Reflexi a GC. Umoznujici vytvaret skriptovatelne aplikace bez impaktu na rychlost. Znovu jako za starych casu vytvaret samomodifikujici se kod pro maximalni rychlost. A to vse +- nezavisle na platforme. .Net i JVM maji stale moznosti jak se vylepsovat, nativni kod se bude uz jen zpomalovat :-) a to vubec nemluvim o produktivite programatoru.

Dockame se renezance .Netu? Protoze pokud ne, tak nebudem psat v C++, ale v ObjectiveC… (A na to jsem asi fakt uz starej)

BDB vs BTDB

bobris — Mon, 13 Jun 2011 22:00:00 GMT

Můj projekt BTDB je již tak daleko, že snese i nějaký to rychlostní porovnání. Nejdříve porovnám nejnižší úroveň databáze klíč hodnota, klíče jsou setříděné a je tedy možné jimi iterovat.

Asi nejznámější “konkurence” je Berkeley DB (BDB), aktuálně patřící Oraclu. Pro test jsem použil Berkeley DB 11g Release 2, library version 11.2.5.1.25: (January 28, 2011) tedy aktuální verzi v době psaní toho článku. Je pěkné, že má i .Net knihovnu, která je pouze zaobalením Céčkové implementace. Což znamená, že v případě povolení pouze bezpečného .Net kódu máte smůlu (třeba SL, WP7).

BDB má řekl bych až šíleně mnoho nastavení. Pokusil jsem se ji nastavit co nejblíže implementaci BTDB. ACID transakce se serializovatelnými transakcemi pomocí MVCC. Bohužel nejsem na BDB odborník, takže velmi rád přivítám radu jak ji nastavit lépe (se zachováním těchto vlastností). Především jsem nepřišel na to jak vypnout transakční log aby byla zachována durabilita (ale i v dokumentaci mají napsáno, že by to jít nemělo). Taky jsem zapnul kontrolu kontrolního součtu při čtení stránek z disku (BDB používá o něco méně kvalitní funkci než Flatcher32 použitá v BTDB, ale i tak to je velmi podobné). Vše jsem ověřoval v Profileru, kde nebyly vidět žádné zbytečné funkce.

Pro samotný test jsem zvolil 200 transakcí, kde každá vytvoří 200 párů 2 bytového klíče a různě dlouhých hodnot. Tato první část ukazuje rychlost vytvoření databáze pokud začneme z nuly.

Druhá část je i se čtením který přečte všechny klíče a hodnoty v každé transakci před commit a tím otestuje správnou implementaci serializace transakcí. V podstatě to je téměř hlavně na čtení zaměřený test. Pro čistý čas čtení lze jen odečíst čas prvního testu.

Třetí test je stejný jako první s rozdílem, že databázi nechám naplněnou z druhého testu. Tento test tedy testuje rychlost zapisování nových hodnot do existujících párů klíč hodnota.

Pro detaily se podívejte do implementací testu:

v BTDB: https://gist.github.com/1023790

v BDB: https://gist.github.com/1023779

Ve všech případech se pro kontrolu vypsal tento řádek:

Pure data length: 396130000

Naměřené výsledky podrobně:

Pouze vytvoření BTDB:

KeyValuePairCount:             40000
TransactionNumber:               201
WastedSize:                   773120
ReallyUsedSize:            411252224
DatabaseStreamSize:        412025344
Total Bytes Read:                  0
Total Bytes Written:       547714176
Time:        4170,065ms

Pouze vytvoření BDB:

Time: 58325ms
DB Size: 534675456
Log Size: 20971520

Vytvoření a čtení BTDB:

KeyValuePairCount:             40000
TransactionNumber:               201
WastedSize:                   773120
ReallyUsedSize:            411252224
DatabaseStreamSize:        412025344
Total Bytes Read:        26527795200
Total Bytes Written:       547714176
Time:     133180,8132ms

Vytvoření a čtení BDB:

Time: 212204ms
DB Size: 534675456
Log Size: 20971520

Třetí přepisovací část v BTDB:

KeyValuePairCount:             40000
TransactionNumber:               400
WastedSize:                  1477120
ReallyUsedSize:            411252224
DatabaseStreamSize:        412729344
Total Bytes Read:          407810048
Total Bytes Written:       541159552
Time:       5863,4538ms

Třetí přepisovací část v BDB:

Time: 64572ms
DB Size: 534675456
Log Size: 20971520

Takže si to sepíšeme do tabulky (stále jsem napřišel na to jak na tomhle blogu udělat v tabulce rámečky :-O):

	Fáze 1	Fáze 2-1	Fáze 3	DB Size/data
BTDB	4s	129s	6s	104%
BDB	58s	154s	65s	135%

No na čistě .Net implementaci to je hodně slušný. Z mého zaujatého pohledu vidím tyto výhody obou řešení:

BTDB

pouze Managed .Net

malá (150kb)

jednoduše použitelná díky málo funkcím a přirozenému .Net rozhraní

DB potřebuje jen o malo více diskové kapacity než samotná data

rychlá (hlavně v 64bit .Netu)

bez divných limitů (např. neomezená velikost transakce)

BDB

použitelná z více jazyků

mraky funkcí

ověřená časem

více paralelních zapisujících transakcí

dokáže běžet i v módech kdy více procesu sdílí stejnou databázi

Fluent Reflection.Emit

bobris — Wed, 25 May 2011 22:11:27 GMT

Dnes se dovíte jak udělat váš IL generující kód čitelnější a navíc přívětivý k refaktoringu.

Mějme tento jednoduchý test:

public class Nested
{
    public string PassedParam { get; private set; }

    public void Fun(string a)
    {
        PassedParam = a;
    }

    public void Fun(int noFun)
    {
        Assert.Fail();
    }
}

[Test]
public void NoILWay()
{
    var n = new Nested();
    n.Fun("Test");
    Assert.AreEqual("Test", n.PassedParam);
}

Zkusme ho tedy přepsat do DynamicMethod jen s tím co je .Net 4.0:

[Test]
public void ILOldWay()
{
    var method = new DynamicMethod("SampleCall", typeof(Nested), Type.EmptyTypes);
    var il = method.GetILGenerator();
    il.DeclareLocal(typeof(Nested));
    il.Emit(OpCodes.Newobj, typeof(Nested).GetConstructor(Type.EmptyTypes));
    il.Emit(OpCodes.Stloc_0);
    il.Emit(OpCodes.Ldloc_0);
    il.Emit(OpCodes.Ldstr, "Test");
    il.Emit(OpCodes.Call, typeof(Nested).GetMethod("Fun", new[] { typeof(string) }));
    il.Emit(OpCodes.Ldloc_0);
    il.Emit(OpCodes.Ret);
    var action = (Func<Nested>)method.CreateDelegate(typeof(Func<Nested>));
    var n = action();
    Assert.AreEqual("Test", n.PassedParam);
}

Především si všimněte řádků s Newobj a Call instrukcemi. Co by se totiž stalo kdyby jsme třeba zrušili konstruktor s nula parametry, nebo přejmenovali funkci Fun, problém bychom nalezli až za běhu. Takže co využít Expression a extension metody. Fluent interface FTW.

public static ILGenerator Newobj(this ILGenerator il, Expression<Action> expression)
{
    var constructorInfo = (expression.Body as NewExpression).Constructor;
    return Newobj(il, constructorInfo);
}

public static ILGenerator Newobj(this ILGenerator il, ConstructorInfo constructorInfo)
{
    il.Emit(OpCodes.Newobj, constructorInfo);
    return il;
}

Protože C# nemá možnost přímo zakódovat token k metodě, přesto tato funkce je použitá pro vytvoření Expression. Pak už si ho ve funkci zjistíme a zbytek Expression zahodíme protože nás nezajímá. Samotný ILGenerator jen vrátíme pro umožnění velmi kompaktního zápisu.

Takže po o něco víc podobných metodách lze stejný kód zapsat takto:

[Test]
public void ILNewWay()
{
    var method = new DynamicMethod("SampleCall", typeof(Nested), Type.EmptyTypes);
    var il = method.GetILGenerator();
    il.DeclareLocal(typeof(Nested));
    il
        .Newobj(() => new Nested())
        .Stloc(0)
        .Ldloc(0)
        .Ldstr("Test")
        .Call(() => ((Nested)null).Fun(""))
        .Ldloc(0)
        .Ret();
    var action = method.CreateDelegate<Func<Nested>>();
    var n = action();
    Assert.AreEqual("Test", n.PassedParam);
}

Kompletní kód aktuálně najdete (vše v MIT Licenci):

https://github.com/Bobris/BTDB/tree/unstable/BTDB/IL

https://github.com/Bobris/BTDB/blob/unstable/BTDBTest/ILExtensionsTest.cs

Záludnost v ILGenerator.Emit

bobris — Fri, 20 May 2011 21:50:00 GMT

Pokud chcete napsat něco netriviálního s použitím dynamicky generovaného kódu v .Netu, tak si začnete vytvářet různé pomocné funkce.

Jako například funkci na načtení int konstanty na zásobník (zkráceno):

OpCode op = value >= -128 && value <= 127 ? OpCodes.Ldc_I4_S : OpCodes.Ldc_I4;

il.Emit(op, value);

Říkáte si jak ste dobrý, když stejný kód napíšou i takové špičky jako Marc Gravell. No ale je to blbě.

A nejlepší na tom je, že to i často funguje, takže chybu ani jen tak nezjistíte.

Pokud totiž použijete Ldc_I4_S instrukci (a mnoho dalších končících _S) tak druhý parametr Emit metody musí byt v tomto případě typu sbyte a ne int! Naštěstí .Net primárně vznikl na Little endian platformě, takže třeba číslo 42 bude zakódováno jako sekvence bytů 42, 0, 0, 0. Další ?prozřetelnost? je v tom, že 0 znamená Nop instrukci. Takže ve výsledku jsme nic neušetřili v délce kódu a místo jedné instrukce načtení malé konstanty necháme kompilovat ještě 3 Nopy navíc, ale kód alespoň funguje. V záporných hodnotách to je ovšem horší 255 je prefixref a její použití podle MSDN dokumentace by mělo vyvolat chybu (neověřoval jsem).

Takže správně má být:

if (value >= -128 && value <= 127)

    il.Emit(OpCodes.Ldc_I4_S, (sbyte)value);

else

    il.Emit(OpCodes.Ldc_I4, value);

Pro kompletní funkci se koukněte sem: https://github.com/Bobris/BTDB/blob/unstable/BTDB/IL/ILGeneratorExtensions.cs

Jsou tam i další perly, ale o nich zas někdy příště.

BTW Stejný problém je řešen, ale chybně, zde: http://stackoverflow.com/questions/1498162/c-ilgenerator-nop

Reference counted string v C++

bobris — Tue, 22 Sep 2009 20:39:00 GMT

Chtěl bych se s Vámi podělit o jednom velmi reálném měření z jedné “nejmenované” komerční aplikace. Je napsaná jak už asi tušíte v C++ hodně přes 2 miliony řádků. Pro práci se stringy tato aplikace používá vlastní implementaci na základě počítání počtu ukazatelů. Samotný string je tedy velký pouze jeden pointer. Pokud je ukazatel jen jeden, tak se chová na způsob .Netího StringBuilderu, jinak jako .Net string. Prázdný string má pak v sobě NULL. Aplikace to je více vláknová, proto musí být přičítání a odečítání počtu ukazatelů atomické. No ale taky lze tato aplikace pustit tak, že má potřebuje pouze jedno vlákno. Proto není od věci zkusit co by provedlo nahrazení atomických operací obyčejnými.

Testy proběhly na 64bit Vistách, kompilátor je MSVC 2005, procesor pak přetaktované obstarožní Core2Duo E6400. InterlockedIncrement i InterlockedDecrement jsou intrinsic (tzn. že je nativně kompilátor zná a přímo vkládá jejich kód místo volání API funkce). Samotný test je o tom načíst nějaká data a vytvořit z nich PDF (dost času se stráví kompresí, která žádné inkriminované operace neobsahuje). Vše je ve vyrovnávací paměti měřím až druhé spuštění, takže diskové operace by měly být zanedbatelné.

Takže k výsledkům:

	Velikost Exe	Čas
32bit Atomic	25205 kB	17.7
32bit Plain	25295 kB	16.6
64bit Atomic	39696 kB	14.6
64bit Plain	39557 kB	13.1

Rozdíl velikosti exe souborů je rozhodně zajímavý 32bit aplikace se “zjednodušením” zvětšila a naopak 64bit se zmenšila. 64bit aplikace se pak zrychlila o víc než 32bit verze, těžko říct proč, samotný čítač je v obou verzích 32bitový. Velký rozdíl velikosti a i zrychlení 64bit verze oproti 32bit, pak připisuji především používání C++ vyjímek, v 32bit Windows totiž try catch není zadarmo.

Pokud byste uvažovali o stejné aplikaci v .Netu, tak by to bylo rychlejší v tom, že by tam dokonce nebyl vůbec žádný čítač, pomalejší o konverze mezi stringem a StringBuilderem. Obecně se mi zdá, že pro více vláknové aplikace, výhoda GC oproti malloc/free, začíná být zajímavá.

Běž a uklízej

bobris — Sat, 15 Aug 2009 19:45:00 GMT

Chtěl bych vám představit jednu z nejlepších novinek .Netu 4.0 a zajímavé je, že v seznamu What's New in the .NET Framework 4 ji ani nenajdete.

Nejdříve ale zase ukázkový kód, spustitelný v .Net 3.5:

        static void Main(string[] args)
        {
            for (int i = 0; i < 100000; i++)
            {
                if (i % 1000 == 0) Console.WriteLine(i);
                AssemblyBuilder ab = AppDomain.CurrentDomain.DefineDynamicAssembly(
                    new AssemblyName("DynAsm"+i.ToString()), AssemblyBuilderAccess.Run);
                ModuleBuilder mb = ab.DefineDynamicModule("DynMod"+i.ToString());
                TypeBuilder tb = mb.DefineType("DynType" + i.ToString(), TypeAttributes.Public);
                tb.DefineField("F1", typeof(string), FieldAttributes.Public);
                tb.DefineField("F2", typeof(int), FieldAttributes.Public);
                MethodBuilder metb = tb.DefineMethod("create",
                    MethodAttributes.Public | MethodAttributes.Static, tb, System.Type.EmptyTypes);
                var ilg = metb.GetILGenerator();
                ilg.Emit(OpCodes.Newobj, tb.DefineDefaultConstructor(MethodAttributes.Public));
                ilg.Emit(OpCodes.Ret);
                Type t = tb.CreateType();
                var del = (Func<object>)Delegate.CreateDelegate(typeof(Func<object>), t.GetMethod("create"));
                object d = del();
            }
        }

Tento prográmek vytváří nové typy, nakonec pak i vytváří jejich instance. Pokud to spustím v .Netu 3.5 tak před 7000 iterací dojde paměť. To samé v .Netu 4.0 beta 1 skončí až před 21000 iterací, takže třikrát méně paměťově náročnější.

No a konečně se dostáváme k té novince nahraďme AssemblyBuilderAccess.Run za AssemblyBuilderAccess.RunAndCollect a paměť nedojde nikdy. Osciluje kolem 7,5 MB. Nový mód RunAndCollect má pár omezení, ale nic s čím by se nedalo žít. Hlavně to nenechte běžet dlouho v debuggeru, protože to pak dojde pamět jemu kvůli symbolům z nových assembly.

DynamicMethod v .Net 2.0 byl začátek, ale tohle konečně umožňuje vytvářet dynamicky optimalizovatelné programy bez zpomalení komunikací mezi AppDomainy. SkyNet se blíží …

Ještě upozornění, pokud na konec cyklu dopíšete:

                dynamic dd = d;
                dd.F1 = "Hello";

Tak to sice funguje, ale zabrání to úklidu, takže paměť dojde před 7000 iterací. Pravděpodobně implementace dynamic si drží vygenerované metody navždy. Možná to ještě opraví, ale ono stejně kombinovat DynamicAssembly s dynamic nedává smysl. Když už jste na úrovni, že dokážete používat DynamicAssembly, tak si můžete naprogramovat vlastní dynamic.

První dojmy z VS2010 Beta 1

bobris — Tue, 19 May 2009 21:41:43 GMT

1.2 GB iso image… 3 vynucené restarty … a jde se na věc …

Nejdříve jsem si musel promnout oči, protože jsem si myslel, že vidím nějak rozostřeně. Ano bylo to mé první setkání s WPF v “seriózní” aplikaci. A bude to chtít hódně zvykání na text o kvalitě analogového signálu v nenativním rozlišení LCDčka :-). Ale zato na první pohled poznáte co je WPF a co je “staré”. Customizace toolbaru je bohužel v Betě vypnutá. Povšimněte si pak selekce s gradientovou výplní, no jo když ono je to tak jednoduchý to ve WPF udělat, tak proč to tím “nevylepšit”. Takhle z aplikací alespoň už nejde poznat jestli máte vadný podsvícení nebo to je umělecký záměr.

Po prvním restartu během instalace již je nainstalovaný .Net 4.0. Takže jsem vyzkoušel Reflektor. Částečně jede, sem tam hází výjimky, takže jsem zvědav jak se Red Gate pochlapí, Lutz by v tuhle dobu již měl dávno plně funkční verzi venku …

No ještě jeden screenshot s C++0x auto. Bohužel kvůli muzeálním platformám je tohle jen malé uslintnutí nad něčím co jen tak nebudeme v robotě používat … (Font editoru jsem zvětšil z 10pt na 11pt, aby se na to dalo koukat)

Intelisence v takhle krátkým zdrojáku jede dobře, ale to šla i v VS2008. Nově pak i v reálném čase podtrhává chyby. Na větší projekty se zatím nedostalo času …

Ukazatel na funkci 5

bobris — Wed, 15 Apr 2009 21:07:00 GMT

Po Googlovaní toho tailcallu, jsem našel jen pár dalších stěžovatelů si na jejich rychlost. Potenciálně tuším co by mohl dělat “foobar” – profiler hook, i když profiler sem připojený neměl, možná to je kvůli tomu ze CLR (ani 4.0) nepodporuje “rejit”, takže ten hook tam musí být již od začátku. No a taky jsem se dočetl, že by 64bit tailcall měl být rychlejší než 32bit. ~~No takže to je přesně obráceně a to tak, že asi o 500%, takže 64bit tailcall je ještě 6 krát pomalejší než 32bitový na tom příkladu z minula, to už mě hlava nebere…~~ Tak to byla moje chyba, je to opravdu tak, ze 64bit je rychlejší než 32bit tailcall a to více než 20 krát v našem příkladu, což vypadá již dost optimalně.

Pár linků …

Podobně podrobné vysvětlení: http://barrkel.blogspot.com/2006/05/clr-tailcall-optimization-or-lack.html

Bug na connectu od Nemerle lidí: http://connect.microsoft.com/VisualStudio/feedback/ViewFeedback.aspx?FeedbackID=98236

Vysvětlení problému a vysvětlení, že jeho řesení musí počkat za .Net 2.0 http://blogs.msdn.com/shrib/archive/2005/01/25/360370.aspx

Ukazatel na funkci 4

bobris — Tue, 14 Apr 2009 23:16:24 GMT

Jak tedy může být implementovaný tailcall. Zjištění nebude jednoduché, kompilátor F# je dobře připraven to neukázat jen tak zadarmo. Když totiž začneme s jednoduchou zkouškou:

    1 #light

    2 open System

    4 let rec fn1 i max=

    5     if i<max then

    6         fn2 (i+1) max

    7     else

    8         max

    9 and fn2 i max=

   10     if i<max then

   11         fn1 (i+1) max

   12     else

   13         max

   15 fn1 0 10000000 |> ignore

Tak ta se funkce fn2 přeloží jako while cyklus s rozvinutou fn1 a jediný tailcall je ve fn1 při volání fn2, ale ten si nezměříme, když je jen jeden. Mimochodem kdy myslíte že se dočkáme kompilátoru, který to zoptimalizuje na: let fn1 x y=y (já jsem pesimista s odhadem od 10 do 15 let :-))

Tak to trochu zjednodušíme a zároveň pro F# zesložitíme:

    1 #light

    2 open System

    4 type Recursive(max) =

    5     abstract run: int -> int

    6     default this.run(i)=

    7         if i<max then

    8             this.run(i+1)

    9         else

   10             i

   12 let sw = new Diagnostics.Stopwatch()

   13 let r=new Recursive(10000000)

   14 System.GC.Collect(); System.GC.WaitForPendingFinalizers()

   15 sw.Start()

   16 r.run 0 |>ignore

   17 sw.Stop()

   18 printf "%d" sw.ElapsedMilliseconds

To už si netroufne zoptimalizovat (ani se nedivím) a trvá to 221ms (poměrně přesně (609ms (F#)-184ms(C#)) /2 (byli tam 2 tailcall na iteraci) = 212ms) . V C# a ani v Monu tohle nezkoušejte pokud nechcete vidět toto:

Unhandled Exception: System.StackOverflowException: The requested operation caused a stack overflow.

at Program+Recursive.run (Int32 i) [0x00000] (tento řádek se tisickrát opakuje :-)

Jak tedy vypadá metoda run v assembleru:

03520160 55              push    ebp // klasický vstup funkce
03520161 8bec            mov     ebp,esp
03520163 57              push    edi // zazálohujeme si edi, esi, ebx – konvence .Netu
03520164 56              push    esi
03520165 53              push    ebx
03520166 8bc2            mov     eax,edx // edx je první parametr = i
03520168 3b4104          cmp     eax,dword ptr [ecx+4] // ecx je this a první member je na pozici 4, pozice 0 je vyhrazena virtuální tabulce metod
0352016b 7d26            jge     03520193 // skoč když i>=max
0352016d 40              inc     eax // +1
0352016e 8bd0            mov     edx,eax // nové i = i+1, ecx zůstává zachováno
03520170 8b01            mov     eax,dword ptr [ecx] // ukazatel na tabulku virtualních metod
03520172 8b4038          mov     eax,dword ptr [eax+38h] // asi něco jako id definice metody run
03520175 6a00            push    0 // asi něco jako rozdíl počtu parametrů aktuální funkce a té tailcall volané
03520177 6a00            push    0 // tak podobně
03520179 6a01            push    1
0352017b 50              push    eax
0352017c 833d9c333b7a00 cmp     dword ptr [mscorwks!GetHistoryFileDirectory+0xf0998 (7a3b339c)],0 // tenhle test mě fakt nenapadá na co by mohl být
03520183 7409            je      0352018e // tady to vždy skočí
03520185 51              push    ecx // uložit nové this a parametry
03520186 52              push    edx
03520187 e847c8ba76      call    mscorwks!CorLaunchApplication+0x111bd (7a0cc9d3) // foobar :)
0352018c 5a              pop     edx // obnovit this a parametry
0352018d 59              pop     ecx
0352018e e8fd269576      call    mscorwks+0x2890 (79e72890) // a tohle je ta obecná relativně pomalá funkce co provede tailcall případně JITuje pokud je potřeba
03520193 5b              pop     ebx // klasický výstup z funkce
03520194 5e              pop     esi
03520195 5f              pop     edi
03520196 5d              pop     ebp
03520197 c3              ret

Ta “pomalá” funkce na tailcall je pak asi dalších 20 instrukcí co se provádí v našem případě. Asi to “musí” být takto složité, ono správně vyřešit asynchronní výjimky nebude žádná sranda. Ale jak již jsem řekl F# to moc nepomáhá.

Ukazatel na funkci 3

bobris — Mon, 13 Apr 2009 22:37:45 GMT

Další pokračování s dalšími objevy. Chtěl jsem ještě zjistit jako to je s tím přetypováním z prvního dílu. Aby se mi to lépe v Assembleru ladilo, tak jsem přepsal tento F# v C#:

    1 #light

    2 open System

    4 let inline add x y = x + y

    5 let inline sub x y = x - y

    6 type test() =

    7     let mutable op = add

    8     let addop = add

    9     let subop = sub

   11     member private this.testiter (i:int) =

   12         op i i

   13         op <- subop

   14         op i i

   15         op <- addop

   17     member public this.test max =

   18         for ii in 0..max-1 do this.testiter ii

   20 let sw = new Diagnostics.Stopwatch()

   21 let t=new test()

   22 t.test 10

   23 System.GC.Collect(); System.GC.WaitForPendingFinalizers()

   24 sw.Start()

   25 t.test 10000000

   26 sw.Stop()

   27 printf "%d" sw.ElapsedMilliseconds

“stejná věc” v C# (tak jak ji zkompiluje F#):

    1 using System;

    3 namespace Test

4 {

    5     class Program

    6     {

    7         abstract class FastFunc<T,U>

    8         {

    9             public abstract U Invoke(T t);

   10             public static V InvokeFast2<V>(FastFunc<T, FastFunc<U, V>> f, T t, U u)

   11             {

   12                 var func = f as FastFunc2<T, U, V>;

   13                 if (func != null)

   14                 {

   15                     return func.Invoke(t, u);

   16                 }

   17                 return f.Invoke(t).Invoke(u);

   18             }

   19         }

   21         abstract class FastFunc2<T,U,V>:FastFunc<T, FastFunc<U, V>>

   22         {

   23             class Closure : FastFunc<U, V>

   24             {

   25                 internal Closure(FastFunc2<T, U, V> f, T t)

   26                 {

   27                     _t = t;

   28                     _f = f;

   29                 }

   30                 public override V Invoke(U u)

   31                 {

   32                     return _f.Invoke(_t, u);

   33                 }

   34                 private readonly T _t;

   35                 private readonly FastFunc2<T, U, V> _f;

   36             }

   37             public override FastFunc<U, V> Invoke(T t)

   38             {

   39                 return new Closure(this,t);

   40             }

   41             public abstract V Invoke(T t, U u);

   42         }

   44         class AddBinOp: FastFunc2<int,int,int>

   45         {

   46             public override int Invoke(int x, int y)

   47             {

   48                 return x + y;

   49             }

   50         }

   51         class SubBinOp : FastFunc2<int, int, int>

   52         {

   53             public override int Invoke(int x, int y)

   54             {

   55                 return x - y;

   56             }

   57         }

   58         class Test

   59         {

   60             FastFunc2<int, int, int> op = new AddBinOp();

   61             readonly FastFunc2<int, int, int> opadd = new AddBinOp();

   62             readonly FastFunc2<int, int, int> opsub = new SubBinOp();

   64             void testiter(int i)

   65             {

   66                 FastFunc<int, int>.InvokeFast2(op, i, i);

   67                 op = opsub;

   68                 FastFunc<int, int>.InvokeFast2(op, i, i);

   69                 op = opadd;

   70             }

   72             public void dotest(int max)

   73             {

   74                 for(int i=0;i<max;i++) testiter(i);

   75             }

   76         }

   78         static void Main(string[] args)

   79         {

   80             var sw = new System.Diagnostics.Stopwatch();

   81             var t=new Test();

   82             t.dotest(10);

   83             GC.Collect(); GC.WaitForPendingFinalizers();

   84             sw.Start();

   85             t.dotest(10000000);

   86             sw.Stop();

   87             Console.Write(sw.ElapsedMilliseconds);

   88         }

   89     }

   90 }

Řádky 23 až 36 jsou tam jen pro úplnost, nikdy se v tomto testu nespustí.

No jo, ale v F# to trvá 609ms a v C# jen 184ms. Takže je jasné, že přetypováním (jak jsem si myslel v prvním díle) to není. Po prohlídnutí ILka, jsem zase uviděl tailcall (v C# zobrazení v Reflektoru totiž normální call od tailcallu nepoznáte). Ale k otestování samotné “—optimize notailcalls” nepomůže, protože FastFunc2 je implementovaná v FSharp.Core, takže ještě přidáme již zmíněný “—standalone” a výsledek je 189ms, rozdíl od C# se mi v assembleru už hledat nechce, ILko vypadá v podstatě shodně. Mimochodem to “—standalone” tam opravdu napere celou FSharp.Core i to co se nepoužívá (kompilace najednou trvá již znatelných 5s).

Pokud tedy v .Net 4.0 nebude tailcall optimalizovaný tak jak má, tak to funkcionální jazyky jako F# dost penalizuje a tak ztrácí mé cenné body :-).

Ještě taková perlička na závěr. Mono je známé tím, že tailcall zatím ignoruje. Tím ovšem je pro funkcionální jazyky, stejně jako Java, téměř nepoužitelné. Po přeměření v Monu 2.4 to co trvalo na .Netu (F#) 609ms trvá “jen” 361ms. To co v .Netu (C#) trvalo 184ms, tak v Monu 387ms.

Ukazatel na funkci 2

bobris — Fri, 10 Apr 2009 22:26:05 GMT

Pokračování z minula … (pokud jste ještě nečetli první část, tak tohle ani nemá moc cenu číst)

Takže delegát volání vypadá takto:

originál v C#: op(i,i); op je delegát

0000002c push        esi // v esi je naše “i” druhý parametr se již nevejde do registrů proto jde na zásobník
0000002d mov         ecx,dword ptr ds:[022F1EE8h] // nahraje ze static proměnné (globální, proto na ds (datovém) segmentu) ukazatel na delegáta
00000033 mov         edx,esi // máme první parametr nastavíme taky na “i”
00000035 mov         eax,dword ptr [ecx+0Ch] // načteme ukazatel na kód samotné funkce
00000038 mov         ecx,dword ptr [ecx+4] // načteme “this” volaného objektu (my ho nepotřebujeme ale to volání degáta neví)
0000003b call        eax // a samotné volání

Takhle velmi podobně vypadá volaní virtuální funkce v C++ v případě jednoduché dědičnosti.

V případě volání virtuální funkce na interface v .Netu to vypadá takto (v C# op.DoIt(i,i);): op je interface

00000006 push        esi // stejně jako u delegáta
00000007 mov         ecx,dword ptr ds:[022F84B8h] // naše this
0000000d mov         edx,esi // první parametr jako u delegáta
0000000f call        dword ptr ds:[00990210h] // magické volání které se snaží být rychlé

V samotném VS pokud dáte StepInto tak jste rovnou v naší funkci. Bohužel to nemůže být pravda, to by ani obecně nefungovalo a bylo by to výrazně rychlejší než případ s delegátem. Takže pustíme WinDbg a zjistíme, že to skáče na takovýto kód (tento kód se tam objeví až po pár iteracích):

00997012 cmp     dword ptr [ecx],983D48h // test na typ objektu
00997018 jne     0099a011 // tohle nikdy neskočí protože v tom konkrétním řádku vždy voláme stejnou virtuální metodu
0099701e jmp     00cd01e8 // přímo skok na implementaci naší sčítací nebo odčítací funkce

V tomto případě máme tedy .Netnetem dynamicky generovaný “optimalizovaný” kód. Což mě přivedlo na myšlenku jak to ještě zrychlit:

    4 [<AbstractClass>]

    5 type BinOp() =

    6     abstract member run : int * int -> int

    7 type AddBinOp() =

    8     inherit BinOp()

    9     override this.run(x,y) = x+y

   10 type SubBinOp() =

   11     inherit BinOp()

   12     override this.run(x,y) = x-y

   14 type test() =

   15     static let mutable op = new AddBinOp() :> BinOp

   16     static let opadd = new AddBinOp() :> BinOp

   17     static let opsub = new SubBinOp() :> BinOp

   19     static let testiter i=

   20         op.run(i,i)

   21         op <- opsub

   22         op.run(i,i)

   23         op <- opadd

Výsledek 124ms. Takže je to přece jen rychlejší než delegáti (130ms). To samé v C# je 110ms. No a ještě z assembleru je vidět, že to přiřazení “op <- opadd” není jen obyčejná kopie ukazatele. To je kvůli garbage collectoru, musí se nějak dozvědět o všech změnách globálních proměnných typu ukazatel. Takže když ještě smažeme static:

    1 #light

    2 open System

    4 [<AbstractClass>]

    5 type BinOp() =

    6     abstract member run : int * int -> int

    7 type AddBinOp() =

    8     inherit BinOp()

    9     override this.run(x,y) = x+y

   10 type SubBinOp() =

   11     inherit BinOp()

   12     override this.run(x,y) = x-y

   14 type test() =

   15     let mutable op = new AddBinOp() :> BinOp

   16     let opadd = new AddBinOp() :> BinOp

   17     let opsub = new SubBinOp() :> BinOp

   19     let testiter i=

   20         op.run(i,i)

   21         op <- opsub

   22         op.run(i,i)

   23         op <- opadd

   25     member public this.test max =

   26         for i in 0..max-1 do testiter i

   28 let sw = new Diagnostics.Stopwatch()

   29 let t=new test()

   30 t.test 10

   31 System.GC.Collect(); System.GC.WaitForPendingFinalizers()

   32 sw.Start()

   33 t.test 10000000

   34 sw.Stop()

   35 printf "%d" sw.ElapsedMilliseconds

Dostáváme se na 104ms (v C# to již je stejně rychlé). To je více než desetkrát rychlejší než první test. A to je myslím už nejlepší čas jakého jde dosáhnout při zachování myšlenky testu.

Když bych to shrnul:

1) Rychlosti volání metod od nejrychlejšího jsou: nevirtuální metoda; virtuální metoda objektu; delegát na členskou metodu; delegát na statickou metodu; virtuální metoda interfacu. Pořadí posledních dvou možností závisí ještě na počtu a typu parametrů.

2) Předpočítejte co se dá (i když to vypadá nevinně)

3) Časté ukládání do statických/globálních ukazatelů je pomalé – raději se tomu vyhnout

PS: Pokud bylo něco nesrozumitelného nebo máte nějaký požadavek jít někde ještě více do hloubky tak se neostýchejte a napište mi to do komentářů.

Ukazatel na funkci

bobris — Wed, 08 Apr 2009 22:50:42 GMT

No nejdříve jsem si myslel, že budu psát rant na způsob jak jsou delegáti pomalejší oproti F# FastFunc, vždyť to má přece v názvu že má být rychlá, tak proč by to nemělo vyjít :-). Bohužel jsem nějak začal s následujícím mikrobenchmarkem:

    1 #light

    2 open System

    4 type test() =

    5     static let add x y = x+y

    6     static let sub x y = x-y

    7     static let mutable op = add

    9     static let testiter i=

   10         op i i |> ignore

   11         op <- sub

   12         op i i |> ignore

   13         op <- add

   15     static member public test max =

   16         for i in 0..max-1 do testiter i

   18 let sw = new Diagnostics.Stopwatch()

   19 test.test 10

   20 System.GC.Collect(); System.GC.WaitForPendingFinalizers()

   21 sw.Start()

   22 test.test 10000000

   23 sw.Stop()

   24 printf "%d" sw.ElapsedMilliseconds

Řádky 15 a dál již nebudu opakovat, budou státe ty stejné a nezajímavé. Když se podíváte na vygenerovaný kód Reflektorem, určitě budete chvíli koukat kolikrát se tam ta operace (+) objeví, ač řádky 7 a 13 přiřazují to samé tak jsou pro to vytvořeny 2 naprosto stejné objekty, toto se ale doufám určitě v dalších verzích kompilátoru vylepší. Ale proč to vlastně nejsou delegáti .Netí ukazatel na funkci, proč to jsou nějaké objekty. To si nejdříve uděláme vysvětlující odbočku z funkcionálních jazyků.

V F# kód “let add x y = x+y” definuje funkci add s tímto typem “int –> int –> int”, již z tohoto je jasné, že není všechno tak jak jsme zvyklí. Je to funkce s jedním int parametrem, která vrací funkci o jednom parametru a návratové hodnotě typu int. Takže je to taková funkce generující funkci. V .Netu pak to je typ: FastFunc<int, FastFunc<int, int>>. FastFunc je typ nadefinovaný v F# runtime knihovně FSharp.Core.dll (pokud chcete jen jedno exe můžete použít parameter –standalone u kompilátoru). FastFunc má pak abstraktní funkci U Invoke<T,U>(T a). Takže volání “op i i” by znamenalo vytvoření dočasného přičítače i a na ten teprve zavolat Invoke(i). Autoři F# to tedy vyřešili typem FastFunc2<int,int,int> funkci s dvěma parametry. Ta má již V Invoke(T,U) a taky genericky implementovanou FastFunc<U,V> Invoke(T). Samotné volání “op i i” pak je přeloženo jako volání statické funkce která nejdříve otestuje jestli to není FastFunc2 a rovnou jí zavolá, bez vytváření dočasného objektu. Tato optimalizace ovšem nejde pomocí delegátů implementovat delegát nemůže mít zároveň 2 typy Func<int,Func<int,int>> a Func<int,int,int> a to ho prvního se “funkcionalisté” vzdát nemohou.

Výsledný čas na mém počítači je pak 1200ms.

Můžeme to, ale zkusit F# ulehčit takto:

    4 type test() =

    5     static let add (x,y) = x+y

    6     static let sub (x,y) = x-y

    7     static let mutable op = add

    9     static let testiter i=

   10         op (i,i) |> ignore

   11         op <- sub

   12         op (i,i) |> ignore

   13         op <- add

Dokonce to vypadá i podobněji jako C# :-). No jo jenže jen vypadá. Zápis “(x,y)” je definice “tuple”, takže nově má add tuto definici (int * int) –> int. Je to již funkce o jednom! parametru. Nejdřive jsem se podíval na výsledek do Reflektoru mráz mě polil je to “class Tuple<A, B>” ano class, takže při každém volání se alokuje (int num = op@7.Invoke(new Tuple<int, int>(i, i));). To jsem si tedy moc nepomohl jsem si říkal, jak může být alokace rychlejší než podmínka na typ a přetypování. Výsledek překvapil: 880 ms

Ovšem i řádek 11 a 13 jsou alokace, taky je zkusíme eliminovat:

    4 type test() =

    5     static let add (x,y) = x+y

    6     static let sub (x,y) = x-y

    7     static let mutable op = add

    8     static let opadd = add

    9     static let opsub = sub

   11     static let testiter i=

   12         op (i,i) |> ignore

   13         op <- opsub

   14         op (i,i) |> ignore

   15         op <- opadd

Výsledek 710ms - lepší. Pokud se stejně předalokuje původní kód tak to dělá 1100ms.

Zkusíme tedy pomoci F# znovu, použijeme delegáty:

    4 type IntBinaryOp = delegate of int * int -> int

    6 type test() =

    7     static let add x y = x+y

    8     static let sub x y = x-y

    9     static let mutable op = new IntBinaryOp(add)

   11     static let testiter i=

   12         op.Invoke(i,i) |> ignore

   13         op <- new IntBinaryOp(sub)

   14         op.Invoke(i,i) |> ignore

   15         op <- new IntBinaryOp(add)

Ze začatku výsledek 1080ms nevypadá vůbec nadějně. Do té doby než zjistíme, že řádek 13 má v F# v sobě zbytečně 2 alokace:

op@9 = new Program.IntBinaryOp(new Program.testiter@13@15().Invoke);

První je delegát, jasně to tam být musí, ale to druhé je object bez memberů který jen volá statickou metodu sub, naprostá zbytečnost. Trošku jako by delegáti byli “2nd class” obyvatelé v F# a není jim věnováno tolik pozornosti kolik by si možná zasloužili, ale je jasný, že to není problém vylepšit v C# to samé je ok. Ok provedeme předalokování:

    4 type IntBinaryOp = delegate of int * int -> int

    6 type test() =

    7     static let add x y = x+y

    8     static let sub x y = x-y

    9     static let mutable op = new IntBinaryOp(add)

   10     static let opadd = new IntBinaryOp(add)

   11     static let opsub = new IntBinaryOp(sub)

   13     static let testiter i=

   14         op.Invoke(i,i) |> ignore

   15         op <- opsub

   16         op.Invoke(i,i) |> ignore

   17         op <- opadd

   19     static member public test max =

   20         for i in 0..max-1 do testiter i

Výsledek mě nepotěšil 570ms. Proč nepotěšil, vždyť je to nejlepší výsledek, jenže já už znal výsledek C# ze stejného kódu:

    1 using System;

    3 namespace Test

4 {

    5     class Program

    6     {

    7         class Test

    8         {

    9             static int add(int x, int y)

   10             {

   11                 return x + y;

   12             }

   13             static int sub(int x, int y)

   14             {

   15                 return x + y;

   16             }

   18             static Func<int, int, int> op = add;

   19             static Func<int, int, int> opadd = add;

   20             static Func<int, int, int> opsub = sub;

   22             static void testiter(int i)

   23             {

   24                 op(i, i);

   25                 op = opsub;

   26                 op(i, i);

   27                 op = opadd;

   28             }

   30             public static void dotest(int max)

   31             {

   32                 for(int i=0;i<max;i++) testiter(i);

   33             }

   34         }

   36         static void Main(string[] aArgs)

   37         {

   38             var sw = new System.Diagnostics.Stopwatch();

   39             Test.dotest(10);

   40             GC.Collect(); GC.WaitForPendingFinalizers();

   41             sw.Start();

   42             Test.dotest(10000000);

   43             sw.Stop();

   44             Console.Write(sw.ElapsedMilliseconds);

   45         }

   46     }

   47 }

155 ms! Výsledný kód je až na to jedno volání v F# navíc stejný, navíc u takhle krátkých metod by mohl .Net bez problémů inlinovat. Dobře né úplně bez problémů jak si ukážeme v zápětí, ta funkce totiž vypadá v ILku takto:

.method assembly instance int32 Invoke(int32, int32) cil managed
{
    .maxstack 6
    L_0000: ldarg.1
    L_0001: ldarg.2
    L_0002: tail
    L_0004: call int32 Program/test::add@7(int32, int32)
    L_0009: ret
}

Už tušíte je tam tall call a ne obyčejný call. Dobře ověříme si to pomocí parametru --optimize- notailcalls je vypneme výsledek je tento:

.method assembly instance int32 Invoke(int32, int32) cil managed
{
    .maxstack 6
    .locals init (
        [0] int32 num,
        [1] int32 num2)
    L_0000: ldarg.1
    L_0001: stloc.0
    L_0002: ldarg.2
    L_0003: stloc.1
    L_0004: ldloc.0
    L_0005: ldloc.1
    L_0006: call int32 Program/test::add@7(int32, int32)
    L_000b: ret
}

A čas 140 ms! ano zdá se, že .Net tailcall neinlinuje, ale navíc s tím musí mít ještě nějaký problém rozdíl je příliš velký. No ale proč je to tedy, ale teď rychlejší než C#. Ano to je již známý problém volání static funkce pomocí delegáta a nutnosti posunout parametry v registrech kvůli neexistujícímu this ve statické metodě. Opravíme tedy náš C# kód takto:

    9             int add(int x, int y)

   10             {

   11                 return x + y;

   12             }

   13             int sub(int x, int y)

   14             {

   15                 return x + y;

   16             }

   18             static Func<int, int, int> op = new Test().add;

   19             static Func<int, int, int> opadd = new Test().add;

   20             static Func<int, int, int> opsub = new Test().sub;

A výsledek je 126ms. Podobného výsledku dosáhneme v F# pokud napíšeme třeba takto (již je to ale trochu jiný benchmark opustili sme statické metody a dokonce i členské a navíc odstraníme i “|> ignore”, které to taky trochu né úplně logicky zpomaluje:

    6 let add x y = x+y

    7 let sub x y = x-y

    8 type test() =

    9     static let mutable op = new IntBinaryOp(add)

   10     static let opadd = new IntBinaryOp(add)

   11     static let opsub = new IntBinaryOp(sub)

   13     static let testiter i=

   14         op.Invoke(i,i)

   15         op <- opsub

   16         op.Invoke(i,i)

   17         op <- opadd

Výsledek je 130ms. Nevím proč je to o 4ms pomalejší, žádný rozumný důvod pro rozdíl již v Reflektoru nevidím.

Ještě si ukážeme “objektové” řešení v F#:

    4 type IBinOp =

    5     abstract member run : int * int -> int

    6 type AddBinOp() =

    7     interface IBinOp with

    8         member this.run(x,y) = x+y

    9 type SubBinOp() =

   10     interface IBinOp with

   11         member this.run(x,y) = x-y

   13 type test() =

   14     static let mutable op = new AddBinOp() :> IBinOp

   15     static let opadd = new AddBinOp() :> IBinOp

   16     static let opsub = new SubBinOp() :> IBinOp

   18     static let testiter i=

   19         op.run(i,i)

   20         op <- opsub

   21         op.run(i,i)

   22         op <- opadd

Zajímavé je že běží 146ms. Takže z toho vyplívá, že rychlost volání delegáta je rychlejší než volání virtuální metody a to už je co říct …

V závěru co z toho plyne: měřit, reflektorovat a znovu měřit a znovu reflektorovat a znát co váš kompilátor a platforma umí dobře a to preferovat. Na příště mi zbývá zjistit jak se liší virtualní metoda od delegáta v assembleru a jestě se podívám na to pomalé přetypovaní na FastFunc2 (být pomalejší než alokace to už chce hodně kumštu). Taky jsem zvědav na .Net 4.0, tam už mohli F#isti zatlačit, aby třeba tailcall byl lépe optimalizován, takže s .Net 4.0 se může vše změnit, nějaká beta běžící mimo virtualizaci by se hodila :).

Iterátory C# vs F#

bobris — Wed, 11 Mar 2009 23:30:00 GMT

Již jsem tu na blogu trochu kritizoval F# za nedostatečně optimální kód. Ted bych rád byl více konkrétní. Na pomoc jsem zavolal CLRProfiler. Napsal jsem dva “identické” programy. Nejdříve F# verzi:

    1 #light
    2 open System
    3 open System.IO
    4 
    5 let mutable fileCount = 0
    6 let mutable dirCount = 0
    7 
    8 let rec allFiles dir = 
    9     seq {
   10         for file in Directory.GetFiles dir do
   11             fileCount <- fileCount + 1
   12             yield file
   13         for subdir in Directory.GetDirectories dir do
   14             dirCount <- dirCount + 1
   15             yield! (allFiles subdir) 
   16         }
   17 
   18 for i in allFiles @"C:\Windows\System32\" do Console.WriteLine i
   19 printf "Files: %d Dirs: %d" fileCount dirCount

Krátké, výstižné, nedebugovatelné (ale to počítám, že snad s dalšími verzemi F# vyřeší) …

A pokračuje C# verze:

    1 using System;
    2 using System.IO;
    3 using System.Collections.Generic;
    4 
    5 namespace Test
    6 {
    7     class Program
    8     {
    9         static int fileCount = 0;
   10         static int dirCount = 0;
   11 
   12         static IEnumerable<string> allFiles(string aDir)
   13         {
   14             foreach (var file in Directory.GetFiles(aDir))
   15             {
   16                 fileCount++;
   17                 yield return file;
   18             }
   19             foreach (var subdir in Directory.GetDirectories(aDir))
   20             {
   21                 dirCount++;
   22                 foreach (var file in allFiles(subdir))
   23                 {
   24                     yield return file;
   25                 }
   26             }
   27         }
   28 
   29         static void Main(string[] aArgs)
   30         {
   31             foreach (var i in allFiles(@"C:\Windows\System32\")) Console.WriteLine(i);
   32             Console.WriteLine("Files: {0} Dirs: {1}", fileCount, dirCount);
   33         }
   34     }
   35 }

Delší (hlavně o závorky a chybějící “yield foreach”), ale taky myslím výstižné, bez problému debugovatelné.

Na mém počítači vypíše poslední WriteLine toto: (samozřejmě obě verze mají naprosto stejný výstup)

Files: 4924 Dirs: 243

No a teď výsledky z CLRProfileru: (zakroužkoval jsem objekty co jsou “navíc”, povšimněte si taky velikosti scrollbaru)

Takže už víte co jsem myslel tím větším tlakem na GC. V tomto konkrétním případě s relativně dlouhými řetězci, to dělá o 30% hůře pro F# (112% v počtu instancí!).

PS: Vývojáři F#, ale mají u mne jedno malé plus za to, že #light režim bude výchozí nastavení. Začínám vidět výhody velmi kontroverzního Python like scope==indent :-) (Především vynucená disciplína alespoň nějakého vzhledu zdrojáků)

Maestro a Monitor

bobris — Sun, 01 Mar 2009 23:13:00 GMT

Maestro jazyk se nám začíná rozjíždět. Již má vlastní blog: http://blogs.msdn.com/maestroteam

Co se ale na blogu nepřímo (je to až v komentářích) dočtete je, že je to postavené nad “forknutým” a lehce modifikovaným CCR.

Jinak doporučuji zhlédnout http://channel9.msdn.com/shows/Going+Deep/Expert-to-Expert-Meijer-and-Chrysanthakopoulos-Concurrency-Coordination-and-the-CCR/ – George je hodně zanícený o CCR (řecká povaha se nezapře)

No a další video je pak http://channel9.msdn.com/shows/Going+Deep/Joe-Duffy-Perspectives-on-Concurrent-Programming-and-Parallelism/ – Joe Duffy je skinhead paralelismu :-), už se těším na jeho bichli Concurrent Programming on Windows, příjde na řadu hned jak dočtu Expert F# :-). Je tam rychle načrtnuto hodně různých věcí na kterých pracují, dokonce možnost forkovat BCL na paralelní (ve smyslu vývoje) anotovanou popisem vedlejších efektů knihovnu například používající “nové” delegáty deklarující, že jsou bez vedlejších efektů a tak …

Druhá část ublognutí bude o komentáři od “pazu” cituji:

Osobně si myslím, že pokud se v kódu objevují ManualResetEvent a jiné "zamykací" mechanismy, nemá smysl věc komplikovat a stačí použít tradiční přístup - místo hypotetického superframeworku na vysoké abstraktní úrovni radši problém vyřešit na mirkoúrovni Monitor&spol pro můj jeden konkrétní případ.

Zrovna ManualResetEvent byl použit v komentovaném článku v tomto “vzoru”:

    1 var ev = new System.Threading.ManualResetEvent(false);
    2 System.Threading.ThreadPool.QueueUserWorkItem((o) =>
    3     {
    4         // Do something long
    5         ev.Set();
    6     });
    7 // Do something different
    8 ev.WaitOne();

Pokud bych toto chtěl napsat pomocí Monitoru, tak mě nic jiného než toto nenapadá:

    1 var monitor = new Object();
    2 var done = false;
    3 System.Threading.ThreadPool.QueueUserWorkItem((o) =>
    4     {
    5         // Do something long
    6         System.Threading.Monitor.Enter(o);
    7         done = true;
    8         System.Threading.Monitor.Pulse(o);
    9         System.Threading.Monitor.Exit(o);
   10     }, monitor);
   11 // Do something different
   12 System.Threading.Monitor.Enter(monitor);
   13 if (!done) System.Threading.Monitor.Wait(monitor);
   14 System.Threading.Monitor.Exit(monitor);

Proměnná “done” tam musí být, aby bylo ošetřeno pokud by “something different” trvalo déle než “something long” Navíc Monitor stejně musí opravdový Win32 Event vytvořit pokud čekání ve Waitu trvá déle jinak nelze udělat dlouhodobé čekání ve Windows, aby to bralo minimálně zdrojů.

Takže i když pravděpodobně to bylo myšleno trochu jinak, rozhodně se není potřeba ManualResetEventu bát :-). Na druhou stranu je to ale debata bez budoucnosti, protože v .Net 4.0 PFX pak tento vzor vyřeší ještě optimálněji a kratčeji ještě než pomocí ManualResetEventu (v podstatě řádky 1 a 5 nebudou potřeba).