Optimalizační soutěž č.3

vložil Radek Červinka 24. února 2012 23:59

Pro zájemce třetí kolo soutěže. Úkolem je optimalizovat demo funkci, pravidla se od minule v podstatě nemění. Nejlepší (tj. nejrychlejší) vyhraje tričko s logem FireMonkey, flašku 4GB a případně 2x hrníček s logem Borland (viz minule, fakt se z něj dobře pije). Případně může být udělena i druhá cena (za nejzajímavější kód nebo nejrychlejší řešení bez ASM).

Uzávěrka je 21.3.2012 ve 20 hodin, ale řešení se může posílat průběžně (každý může poslat 3 řešení), ale nejdříve 1.3 - chtěl bych si zkusit ještě trošku poladit svoje řešení.

Pravidla

  • je možno použít libovolný kompilátor pascalu (Delphi 2 - Delphi XE2, FreePascal)
  • z povahy řešení není povoleno používat vlákna
  • testované budou výsledné Vámi přeložené aplikace, zdrojový kód je jen pro kontrolu vítězů
  • průběžně budou zveřejňovány přeložené aplikace, zaslané zdrojové kódy budou zveřejněny nakonec
  • výsledné pořadí bude určeno během na mém Core i3 @ 2.1G (Thinkpad T520i) na Windows 7 64bit
  • v případě stejných výsledků rozhoduje zajímavější řešení, rozhodne porota ve složení Já, Já a Já
  • můžu se tím pádem zúčastnit i já (bez nároku na výhru - doufám, že skončím aspoň v první polovině pole)
  • co se bude dít ve Vaší proceduře je jedno, jen se nesmí nijak cacheovat výsledky předchozích běhu, manipulovat s měřením atd.
  • Při každém vyvolání musí být výsledky vypočítány samostatně bez návaznosti na předchozí nebo následující výpočty. Výpočty z různých vyvolání nemohou běžet paralelně. Opakované vyvolání je jen pro zpřesnění měření a program se musí chovat stejně i při pouhém jednom opakovaní. Bere se minimum.
  • lze poslat max. 3 řešení
  • není povoleno manipulování s měřením času (jako přeprogramování časovače, patchnutí volání API funkce atd.)
  • program dávající špatné výsledky je vyřazen
  • na výhru není právní nárok :-)
  • je to pro zábavu, z principu je určitá tolerance měření

Doufám, že to bude zábava.

Zadání

Napište co nejrychlejší variantu

procedure IntToStrExFmt(i:Integer; var s:string);
var
  cr: Currency;
begin
  cr := i;
  FmtStr(s, '%.0n', [cr]);
end;

Funkce tedy vrací text, který obsahuje převedenou hodnotu čísla, ale bere v potaz oddělovač tisíců (+ znaménko). Program na konci provádí několik volání pro testovací výpis - výsledek se vypisuje včetně velikosti řetězce a musí se rovnat demo výstupu.

V programu upravte svoje jméno, případně podmíněnou kompilaci.

Ukázka výsledku:

-123 456 789
-2 147 483 647
2 147 483 647
123 456

Běh programu:

q:\soutez3>soutez.exe
ThousandSeparator:160
Autor: Radek Červinka,  kompilator:23,00
Last time = [18787]
Min time = [18787], Average time = [18818], Max time = [18845]
Kontrola:
-123 456 789, 12
-2 147 483 647, 14
2 147 483 647, 13
123 456, 7
-1, 2
0, 1

soutez3.zip - demo program.

Poznámky

Osobně jsem použil Delphi XE2, demo se provádí cca 19s. Vybral jsem záměrně takový příklad, který má velký potenciál pro optimalizaci a může si ho zkusit různě zkušený programátor. Délku provádění jsem odhadl podle mé soukromé verze soutěžního řešení s tím, že určitě nebudu nejrychlejší - tak ať je rezerva.

Pro antivirový test můžete použít virusscan.jotti.org.

V případě nejasností napište komentář.

A ještě jednou: je to pro zábavu.


Nabízíme Delphi školení na různá témata, primárně ve Vaší firmě.

Tagy:

soutez

Komentáře

27.2.2012 19:19:59 #

Zdeněk Vašků

Kam poslat kód?

Zdeněk Vašků

27.2.2012 21:10:16 #

Radekc

Po datu 1.3 na radekc@delphi.cz

Radekc

28.2.2012 14:33:58 #

Tom

Radku, nevím, jak se to projevuje v Tvém překladači, ale v testu je dosti značná chyba. RunTest, včetně volání IntToStrExFmt, v podstatě vůbec nic nedělá - jenom zaměstnává procesor, aniž by vyprodukoval něco,s čím by se dála pracovalo. Tj. pro překladač s dobrou meziprocedurální analýzou je to mrtvý kód, který se prostě vyhodí. Alespoň do nějaké míry. Ve výsledku pak takový benchmark není objektivní.

Chtělo by to udělat tak, aby se výsledek funkce IntToStrExFmt nějak dál zpracoval. Buď se poslal na stdout, což ale udělá nedeterministické zpoždění a zase ovlivní výsledek měření, anebo aby RunTest nasčítávala délky řetězců a výsledek pak vrátila, aby se mohl vytisknout na stdout.

AFAIK starší Delphi takový mrtvý kód neodhalí, ale nevím, jak jsou na tom novější. Jako jiný příklad stejného problému, viz dead-code elimination tady: https://www.ibm.com/developerworks/library/j-jtp12214/

Tom

28.2.2012 14:43:35 #

Radekc

No ale IntToStrExFmt není v principu mrtvý kód. Není v mezích kompilátoru vyhodit funkci která se volá a navíc volá další interní funkce.

Jinak linker Delphi vyhazuje funkce, které nejsou nikde používány.
Ale to snad nic nemění na tom příkladu. Nechtěl jsem zanášet další zpoždění nějakým sčítáním nebo tak.

Radekc

28.2.2012 18:22:59 #

Tom

IntToStrExFmt jako takový ne, třeba už proto, že jeho výstup používá Check. Ale v RunTest se jeho výsledek jenom přiřadí do proměnné, o kterou už nikdo nestojí. Takže tenhle úsek v RunTest je kód, který nemá vliv na výstup programu (kromě rychlosti vykonávání). Obecně, pro překladač je to pak mrtvý kód, který eliminuje. Ale jestli to pozná překladač Delphi, a kolik toho případně vyhodí, to už je pochopitelně jiná otázka.

Myšlenka je taková, že kdo napíše rutinu v ASM, potenciálně může být pomalejší, než Pascalovský kód. A to proto, že z ASM překladač nic nevyhodí. A co by vyhodil z Pascalovského kódu, to je otázka i toho, nakolik a jak agresivně bude inlinovat. Nevím, jak se v tomhle chovají poslední Delphi.

Na vysvětlenou, osobně jsem totiž zvyklý na GCC a MSVC, které jsou sofistikovanější. A ohledně sčítání, AFAIK add trvá na superskalárním x86-64 jeden cyklus. Tím se to nezpodí:)

Tom

28.2.2012 21:09:21 #

Radekc

No nechápu o co ti jde. RunTest se bude překládat stejně stále (ať už pro ASM nebo Pascal verzi). A to jak to přeloží Delphi se klidně můžeš podívat (a taky se většina lidí dívá - jinak by nemohla optimalizovat).

Opakuji, že Delphi umí vyhodit mrtvý kód, ale tohle není ten případ - kompilátor nemůže určit (nebo spíše těžce), zda volaná procedura kromě vracení řetězce nedělá nic jiného co by se jejím vynecháním porušilo (tzv. sideefect).  Pokud by bylo jasné, že některá část se nebude provádět tak se vyhodí (např. podmínka bude vždy false). Seznam optimalizací co umí Delphi je zde někde na webu (pro Delphi tak kolem 2005).

Já bych zase GCC a MSVC nepřeceňoval. Aspoň výsledky benchmarků ukazují, že v některých případech je Delphi rychlejší. Ale záleží na úloze. Ale vůbec bych to sem netahal.

Radekc

Komentování ukončeno

Naše nabídka

Partial English version.

MVP
Ing. Radek Červinka - Embarcadero MVP
profil na linkedin, Twitter:@delphicz

Nabízím placené poradenství a konzultace v oblasti programování a vývoje SW.
Dále nabízíme i vývoj speciálního software na zakázku.

Neváhejte nás kontaktovat (i ohledně reklamy nebo burzy práce).

Pokud chcete podpořit tento server libovolnou částkou, můžete použít PayPal. Moc děkuji.

Delphi Certified Developer

O Delphi.cz

Delphi je jediný moderní RAD nástroj podporující tvorbu nativních aplikací pro platformu Win32, Win64 , Mac OSX a na iPhone a Android (s výhledem na další platformy díky FireMonkey) na současném trhu (včetně Windows 8.1).

V současnosti je světová komunita přes dva miliónů vývojářů.

Delphi.cz je nezávislý portál pro uživatele Delphi. Portál není koncipován pro úplné začátečníky, i když i ti se zde nebudou nudit, ale spíše na programátory, kteří již něco znají a chtějí své znalosti dále rozvíjet a sledovat novinky.

Anketa

Poslední komentáře

Comment RSS