Výsledky 2. soutěže

vložil Radek Červinka 28. února 2011 21:29

Tak jo, zde jsou výsledky. Když jsem tuto optimalizační soutěž navrhoval, tipoval jsem limit tak kolem 100ms. Navrhoval jsem úlohu, která je dostatečně rychlá na základní naprogramování, má potenciál na optimalizaci a která by se dala celkem jednoduše paralelně zpracovávat. Výsledek mne opravdu překvapil.

Výsledky

Pro informaci: měření jsou na mém Core2Duo T8100 @ 2.10GHz.

Program očekává v adresáři patřičné vstupní data - viz generator.zip.

1. Radomír Sova - čas 21ms (Delphi 2007) (virusscan) - ASM, multithread - zdrojové kódy

2. Jan Král (2. pokus) (čas 24ms) - (Delphi 7) (virusscan) - ASM, multithread - zdrojové kódy

3. Neuromancer - čas 26ms (Delphi 7) (virusscan) - ASM, multithread - zdrojové kódy

4. Pepák (čas 30ms) (3. pokus) - (Delphi 5) (virusscan) - ASM, multithread - zdrojové kódy

5 - 6. Jiří Jelínek (čas 34ms) (3. pokus) - (Delphi 7) (virusscan) - PUREPASCAL, multithread - zdrojové kódy

5 - 6. Roman Kubín (čas 34ms) - (Delphi 5) (virusscan) - PUREPASCAL, multithread - zdrojové kódy

7. Dalibor Bradáč (čas 52ms) - (Delphi 2009) (virusscan) - PUREPASCAL, multithread - zdrojové kódy

8. Petr Barták (čas 117ms) - (nejlepší čas byl kompilován Delphi XE) (virusscan) - PUREPASCAL, single thread - zdrojové kódy

9. Radek Červinka (2. pokus) (čas 219ms) - (Delphi 2007) (virusscan) - PUREPASCAL, single thread - zdrojové kódy

10. Tomáš Kořínek (čas 224ms) - (Delphi 2009) (virusscan) - PUREPASCAL, single thread - zdrojové kódy

Mimo soutěž

Jan Král (4. pokus, navíc po časovém limitu - 17ms) - moc škoda! To snad ani není možné.

Takže vítězem je Radomír Sova s opravdu zajímavým řešením (škoda bez komentářů, přesto první cena). Osobně se mi moc líbí řešení Jana Krále, které ač je v ASM je velmi pěkně a čistě napsané, komentované a proto získává cenu poroty. A mimořádnou druhou cenu poroty získává moc pěkné řešení Jiřího Jelínka za PURE pascal, pěkný a rychlý kód (který se mi líbil o kapánek více než kód Romana Kubína) - dlouho jsem se nemohl rozhodnout koho z těchto tří odměnit. Výherce budu kontaktovat mailem.

Jinak pokud můžu doporučit tak se koukněte na zdrojáky i ostatních, a speciálně Pepáka, který tam má celkem dost textů proč a jak. Vůbec mi nevadilo (naopak myslím, že to ocení všichni), kdyby z toho vznikl i menší článeček s nějakými špeky a to platí i jako nabídka pro ostatní (něco co Vás překvapilo, zkušenosti atd.).

Doufám, že se Vám to líbilo a děkuji všem za jejich řešení a někdy zase …

Určitě to není naposledy (ale pár měsíců bude pauza). Mimochodem: momentální pravidla se mi celkem líbí, takže určitě bude ASM povolen (pokud to bude o optimalizacích). A samozřejmě můžete své pocity ventilovat dole v komentářích - v původním článku jsou komentáře hodně výživné :-)


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

Tagy:

Optimalizace

Komentáře

1.3.2011 0:22:35 #

HonzaK

Dekuji Radkovi za zajimavou soutez. Zaroven blahopreji vitezi. Fakt je, ze kdybych dal na kolegu driv, ktery si myslel, ze i na procesoru kde jdou spustit jen dve vlakna zaroven, jde zaridit rozdeleni ulohy nejen na 2 casti, ale na 4 (coz v podstate vystihl i p. Sova jeho resenim), tak jsem mohl byt jeste i o kousek lepsi. Muj posledni kod (poslany jen na overeni rychlosti uz davno mimo limit a po terminu :-) ) dava na Radkove PC vysledek jeste o malinko lepsi.

HonzaK

1.3.2011 0:28:48 #

radekc

Honzo, Vaše řešení mimo soutěž je uvedeno hned za tabulkou.

radekc

1.3.2011 14:31:38 #

NkD

Trochu jsem pomahal s algoritmem Jirky Jelinka, to jen aby se vedelo kam patrim a trosku mi prijde nefer, ze lze pouzit ASM. Trosku proto, ze sam ho neumim a taky proto, ze tak nejak citim, ze by to melo byt o Delphi/Pascalu a algoritmizaci jako takove. Ten ASM do toho zanasi uplne jinej rozmer. V podstate se cela soutez degraduje na ASM, protoze v pascalu jsou proste limity, ktere ho oproti ASM znevyhodnuji. Mam radost, ze Jirka obsadil delene "prvni" misto v PUREPASCAL a taky zes rozhodnul o cene "poroty". Ale stejne me malicko ty assembleristi stvou ;-)

NkD

1.3.2011 16:30:40 #

Dalibor Toman

to NkD: priste se nekdo ozve, ze je nefer, ze se pouziva rucne psany kod. Mel by se zakazat a pouzivat jen to, co se namysuje tahanim komponent :-)

Assembler je jen dalsi programovaci jazyk a na rozdil od high level jazyku je IMHO velmi jednoduchy. Zakladnich instrukci je jen par. Staci se naucit nekolik jmen instrukci a zpusob zapisu operaci s pameti. Jen zpusob premysleni a pristup k programovani je treba dost zmenit. Pokud se prestanes ASM bat, muzes ho vyuzit i jinde (jednocipy apod). Pravda, dnes pouziti ASM ve vetsine pripadu neni nutne (ci je i nezadouci - prenositelnost kodu). Vykon PC je vetsinou dostatecny.

Ber to taky tak, ze v ASM mas mnohem vetsi prostor k tomu, jak problem naprogramovat (ukazalo se, ze pro dnesni CPU to plati obzvlast), takze, ti kdo programovali v ASM, do toho pravdepodobne investovali vetsi mnozstvi casu, aby nasli tu optimalni variantu, cili si to umisteni v soutezi zaslouzi.

PS: IMHO reseni Jirky Jelinka ma jeste prostor ke zrychlovani i v cistem Pascalu

Dalibor Toman

1.3.2011 16:35:28 #

radomirs

NkD: taky mne stvou lidi co jsou chytrejsi nez ja ;-) a protoze jsem uz vyrostl ze skolky (kde to slo resit nakladackou) beru to aspon jako impulz k dalsimu studiu :-) Pocit kdyz se pak "dilo" podari stoji za to.
... i kdyz ted naposled mi vydrzel asi 4s nez sem zjistil ze je i rychlejsi reseni (byt publikovane po uzaverce).
Takze abych si cenu aspon trosku zaslouzil (a aby z toho neco meli i assemblerem nedotceni) slibuji ze svuj kod radne okomentuji a vysvetlim ;-)

radomirs

1.3.2011 20:13:10 #

Radim

Blahozelam vsetkym zucastnenym.
Pekne, pekne.

Radim

1.3.2011 20:30:20 #

pepak

Vypíchnul bych dva momenty, které mě ve vítězných řešeních opravdu zaujaly:

1) Struktura tabulky délek a počtů - mít to jako jednu tabulku s recordem a ne dvě samostatné. Tím se vysvětluje, proč jsem musel pracně rozlišovat mezi koncovým a normálním tagem - při dvou samostatných tabulkách dostává těžce na frak cachování a tříbajtový "hash" je neskutečně pomalejší proti dvoubajtovému.

2) Geniální myšlenka rozdělit každý thread na dvě samostatné části a tím kapitalizovat na tom, jak funguje pipeline v procesorech. Ono je to svázané s tím prvním bodem (při dvou samostatných tabulkách se začne nedostávat registrů), ale proč nepřiznat, že mě to vůbec nenapadlo.

Na druhou stranu vůbec nechápu, jak to, že je to vítězné pascalské řešení tak rychlé. Fakt to tam nevidím. Podle mých pokusů bych pro tohle řešení čekal čas někde u 50-60 milisekund, rozhodně ne těsně nad 30.

pepak

1.3.2011 20:40:18 #

radekc

Přikláním se k ostatním. ASM je jen další prostředek, navíc zde se dá krásně něčemu přiučit. A myslím, že právě soutěžní kód Honzy Krále je pěkná demonstrace, kdy většina programu je v Delphi a jen pár klíčových instrukcí je v ASM.

radekc

2.3.2011 20:57:07 #

HonzaK

Pepo, on nakonec sel rozdelit kazdy thread do 3 casti, na mem PC to udelalo zmenu z 18ms na 15ms. U Radka a i na jinem me dostupnem PC to uz bylo bez rozdilu proti rozdeleni jen do dvou casti.

HonzaK

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