Optimalizační soutěž č.2

vložil Radek Červinka 7. února 2011 22:15

Aktualizace:

  • update: výsledky
  • update6: Tomáš Kořínek
  • update5: J. Jelínek a jeho třetí pokus.
  • update4: aktualizace pořadí, změna na možnost 3 řešení, průběžné výsledky jsou zpět
  • update3: podle návrhu udělím i cenu za nejoriginálnější řešení - i když nebude nejrychlejší - něco jako minule cena poroty. Jako podporu pro zasílání i krapet pomalejších řešení.
  • update2: další soutěžící
  • update: vylepšené měření, můj druhý pokus, dva další soutěžící

Od minulé soutěže mi už otrnulo a jelikož převážná většina lidí v anketě nebyla proti dalšímu kolu soutěže a do jara ještě chvilku máme čas, je zde další úkol.

Proti minulému kolu jsem změnil několik pravidel:

  • je možno použít libovolný kompilátor pascalu (Delphi 2 - Delphi XE, FreePascal, ohledně C++Builderu zatím nevím zda by byl zájem)
  • testované budou výsledné Vámi přeložené aplikace (minule jen jedna obsahující všechny řešení), 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 2 jádrovém Core 2 Duo (Thinkpad R400) na XP SP3
  • 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 mezi označenými místy kódu je úplně na Vás - dostanete vstupní data a na výstupu musí být naplněno pole počtů. Můžete použít i vlákna nebo si předat vhodně data. Žádná pravidla. Jen musí být data vypočítána programem (výsledný běh bude nad kapánek jinými daty)
  • Pro určení pořadí bude rozhodující minimální čas ze 40 vyvolání soutěžní části programu. 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í.
  • lze poslat max. 3 řešení (změna: dříve bylo 2 ř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
  • konec 28.2.2011 ve 22:00 (tj. tři týdny)
  • na výhru není právní nárok :-)

Doufám, že se pobavíte stejně jako já.

Zadání

Níže uvedený program vygeneruje testovací data (nejsou to ale data, která budou použita pro výsledný test) - jejich velikost zhruba odpovídá, formát bude přesně stejný. Jedná se o textový neunicode soubor, obsahující na každém řádku (konec řádku je CRLF) jeden z 20 tagů, případně jeho ukončovací variantu. Ukončovací varianta, tj. </xxxxxxx se bude ignorovat a nezapočítává se do výsledku.

generator.zip - program pro vygenerovaní vstupních dat - generování trvá několik sekund :-D

Ukázka výsledného souboru:

</body>
</strong>
<li>
</ul>
<div>
<head>
<head>
</head>
<td>
</em>
</html>
</tr>

Cílem je do připraveného pole spočítat jednotlivé výskyty.

  • Ukončovací varianta, tj. </xxxxxxx se bude ignorovat a nezapočítává se do výsledku.
  • Je garantováno, že nejsou jiné než povolené řetězce, tj. obsahem vstupního souboru je jen povolená množina tagů. (viz. řádky 15 - 18), můžete na to spoléhat (viz generátor).
  • Základní kostra pro pascal je součástí zadání (sorry pro uživatele C++Builderu, ale pokud se chcete zúčastnit, můžete mi poslat kostru pro C++Builder)

Např. v uvedeném příkladu se bude jako první počítat <li>.

kostra.zip - základní program, zajistí načtení dat z data.bin (získáno generátorem nebo ručně), výpočet času a výpis výsledků. Mezi řádky 34 a 38 je Vaše hrací pole. Výsledek bude v aiCount, nulování není kostrou zaručeno. asData je množina povolených tagů, jejich pořadí a texty se nesmí a nebudou měnit, tj. můžete na to spoléhat.

Na návrh diskutujících (Pepák a anonym) byla upravena kostra - používá se nyní QueryPerformanceCounter a minimum ze 40 běhů.

program Soutez;
{$APPTYPE CONSOLE}
{$RTTI EXPLICIT METHODS([]) PROPERTIES([]) FIELDS([])}
{$STRINGCHECKS OFF}
{$INLINE ON}
{$O+}
{$R-}
uses
  Sysutils,
  windows,
  classes;

const
  ciCount = 20;
  asData : array [1..ciCount] of string =
  ('<body>', '<head>', '<html>', '<p>', '<table>', '<li>', '<ul>', '<div>', '<img>',   //9
   '<td>','<tr>', '<h1>', '<h2>', '<h3>', '<h4>', '<a>', '<em>', '<strong>',
   '<code>', '<pre>');    //20
var
  aiCount: array [1..ciCount] of integer;


const
  LOOP_COUNT = 40;
var
  pData: PByteArray;
  f: TFileStream;
  tick, tickend, frequency: Int64;

  sOut:string;
  x: Integer;
  Loops: integer;
  CurTime, TotalTime, MaxTime, MinTime: DWORD;
begin
  f:= TFileStream.Create('data.bin', fmOpenRead );
  try
    GetMem(pData, f.Size);
    f.Read(pData^, f.Size);
    TotalTime := 0;
    MaxTime := 0;
    MinTime := $ffffffff;
    for Loops := 1 to LOOP_COUNT do
    begin
      QueryPerformanceFrequency(frequency);

      QueryPerformanceCounter(tick);
// zacatek souteze, predavani je zalezitosti programatora
   // v pData jsou data
   // zde si muzete hrat

      QueryPerformanceCounter(tickend);
// konec souteze
      CurTime := Round(1000*(tickend - tick)/frequency);
      Inc(TotalTime, CurTime);
      if CurTime < MinTime then
        MinTime := CurTime;
      if CurTime > MaxTime then
        MaxTime := CurTime;
    end;
    writeln(format('Autor: Radek Červinka,  kompilator:%f', [CompilerVersion]));

    writeln(Format('Last time = [%d]', [CurTime]));
    writeln(Format('Min time = [%d], Average time = [%d], Max time = [%d]',
      [MinTime, TotalTime div LOOP_COUNT, MaxTime]));
    for x := 1 to 20 do
      Writeln(Format('%s = %d', [asData[x], aiCount[x]]));

    FreeMem(pData);
  finally
    FreeAndNil(f);
  end;
end.

Ceny

Hraje se na první místo dle času výpočtu. Pokud by se náhodou nedejbože stalo, že bych byl první (čemu ale opravdu nevěřím), cenu dle svého výběru získává druhý v pořadí.

Výběr je následující (jedna z variant + PDF verzi delphi.cz):

  • 3x hrneček s logem Borland (archeologické kousky - ale je opravdu kvalitní a má tu správnou velikost na kafe - ideální do výbavy pro manželství)
  • nebo vázanou knihu Delphi v kostce (1-5) (úplně nová)
  • nebo epesní šiltovka s logem Embarcadero a uvedený hrneček

Delphi v kostce

Hrneček Borland

Poznámky

Osobně jsem použil Delphi 2007, v této úloze generuje zhruba stejně rychlý kód jako Delphi XE, jen je výsledné exe kratší.

Výsledné exe + zdrojové kódy mi zašlete a já Vám potvrdím přijetí. Pro antivirový test můžete použít virusscan.jotti.org.

Pořadí

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.

Výsledky jsou v samostatném článku.

Tagy:

soutez

Komentáře

8.2.2011 1:19:18 #

pingback

Pingback from topsy.com

Twitter Trackbacks for
        
        Delphi.cz | OptimalizaÄŤnĂ­ soutěž ÄŤ.2
        [delphi.cz]
        on Topsy.com

topsy.com

8.2.2011 8:38:08 #

pepak

Upřesňující dotazy od šťoury:

1) Tak, jak je kostra napsaná, nepůjde program pod spoustou verzí Delphi přeložit (např. Delphi 5 vyhazují na neznámých direktivách kompilátoru chybu). Je možné kostru v tomto smyslu upravit? Z logiky věci vyplývá, že ano, ze zadání vyplývá, že ne.

2) Obecně - jak moc je kostra závazná? Mohu si do ní například doplnit svoje funkce? Pokud je moje herní pole jen mezi řádky 34 a 38 kostry, tak ne, protože tam nelze proceduru/funkci vložit.

3) Skutečně "žádná pravidla"? Napadá mě řešení, které vyhovuje všem podmínkám soutěže a zcela jistě by ji podle stanovených kriterií vyhrálo, ale rozhodně nesplňuje jejího ducha...

pepak

8.2.2011 9:41:14 #

radekc

ad 1) Kostru je mozno samozřejmě upravit tak aby sla přeložit

ad 2) lze doplnit svoje funkce, lze doplnit ruzne statické tabulky, deklarace typů, globalni promenne atd,  jen volani (te hlavni funkce pro vypocet) musi byt mezi temi radky - tj. mezi merenim casu

Nesmí být jen natvrdo napsané výsledky - program to musi SPOCITAT, vysledná testovaci data - vstupni soubor bude jiný (velikost cca stejná, pořadí a výskyt slov jiné)

ad 3) No nepadá mne nic, zkus mi napsat, ale primárně si myslím, že opravdu nebudou žádná pravidla - tj. pokud ten program nějakým způsobem dokáže spočítat to co má spočítat tak je to OK.

radekc

8.2.2011 16:37:53 #

Dalibor Toman

BTW: je to chyba kompilatoru nebo ne?
Porovnani znaku ve stringu pretypovane na DWORD to prelozilo do ASM takto:

Soutez.dpr.88: if DWORD(asData[J][K*4+1]) <> DWORD(pData^[I+K*4]) then
0043943A 8BDA             mov ebx,edx
0043943C 03DB             add ebx,ebx
0043943E 03DB             add ebx,ebx
00439440 8B30             mov esi,[eax]
00439442 0FB71C5E         movzx ebx,[esi+ebx*2]
00439446 8BF2             mov esi,edx
00439448 03F6             add esi,esi
0043944A 03F6             add esi,esi
0043944C 0335C80F4400     add esi,[$00440fc8]
00439452 8B3DB80F4400     mov edi,[$00440fb8]
00439458 0FB63437         movzx esi,[edi+esi]
0043945C 3BDE             cmp ebx,esi

Jen pro info: pouzite movzx nahraje z pameti jen dolnich 8 bitu vyssi nastavi na 0 (cili jako by tam to pretypovani na  DWORD nebylo). Moc uz v Delphi neprogramuju ale na takovehle zachazeni nejsem zvykly :-). Delphi 2010

Dalibor Toman

8.2.2011 19:59:39 #

pepak

Nevím, jestli bude stačit pustit to na těch 10 milionů stringů. Teď to tak trochu zkouším a je tam pořád dost velký rozptyl podle toho, co se zrovna v systému děje nebo neděje.

Jinak pro zajímavost, druhá testovací verze je skoro dvakrát rychlejší než tvoje, Radku :-) (První byla taky, ale to jsem jen zkoušel algoritmus bez threadů.) Poslal bych to, ale když můžu poslat jen dvě...

pepak

9.2.2011 1:55:55 #

Jan Javůrek

Ahoj, hodte sem casove vysledky s pripadnou HW konfiguraci, na ktere toho bylo dosazeno.

At vsichni maji duvod porad vylepsovat svuj kod :)

PS. Svuj cas poslu az zbastlim prvni verzi :)

Jan Javůrek

9.2.2011 7:27:55 #

pepak

S časovými výsledky je problém, že neskutečně lítají všemi směry. Můj aktuální kód se pohybuje mezi 250 a 450 milisekundami, podle toho, co se zrovna v počítači děje. Radkův kód se na stejné konfiguraci jeví podstatně stabilnější, cca 620-650 ms.

pepak

9.2.2011 8:33:50 #

pepak

Pro zajímavost, doplnil jsem si do kostry průběh X smyčkami s měřením průměrného, nejlepšího a nejhoršího času:

<pre>
{$IFDEF AVERAGE}
const
  LOOP_COUNT = 100;
{$ENDIF}
var
  pData: PByteArray;
  f: TFileStream;
  tick, tickend: Cardinal;
  x: Integer;
  {$IFDEF AVERAGE}
  Loops: integer;
  CurTime, TotalTime, MaxTime, MinTime: DWORD;
  {$ENDIF}
begin
  f:= TFileStream.Create('data.bin', fmOpenRead );
  try
    GetMem(pData, f.Size);
    f.Read(pData^, f.Size);
    {$IFDEF AVERAGE}
    TotalTime := 0;
    MaxTime := 0;
    MinTime := $ffffffff;
    for Loops := 1 to LOOP_COUNT do
      begin
    {$ENDIF}
    tick:= GetTickCount;
// zacatek souteze, predavani je zalezitosti programatora
   // v pData jsou data
   // zde si muzete hrat
// konec souteze

    tickend := GetTickCount;
    {$IFDEF AVERAGE}
      CurTime := tickend - tick;
      Inc(TotalTime, CurTime);
      if CurTime < MinTime then
        MinTime := CurTime;
      if CurTime > MaxTime then
        MaxTime := CurTime;
      end;
    {$ENDIF}
    // zmenit jmeno
    writeln(format('Autor: Pepak,  kompilator: %s', [ {$IFDEF VER130} 'Delphi 5' {$ELSE} {$IFDEF VER200} 'Delphi 2009' {$ELSE} 'Delphi 2007' {$ENDIF} {$ENDIF} ]));

    writeln(Format('Time = [%d]', [tickend - tick]));
    {$IFDEF AVERAGE}
    writeln(Format('Average time = [%d], Min time = [%d], Max time = [%d]', [TotalTime div LOOP_COUNT, MinTime, MaxTime]));
    {$ENDIF}
    for x := 1 to 20 do
      Writeln(Format('%s = %d', [asData[x], aiCount[x]]));

    FreeMem(pData);
  finally
    FreeAndNil(f);
  end;
end.
</pre>

Průměr 255 milisekund, minimum 250 milisekund, maximum 438 milisekund. Maximum lítá všude možně, minimum a průměr je konzistentní. Možná by nebylo od věci v tomto smyslu upravit i oficiální kostru - na dobu testu to nemá až takový vliv, ale odfiltruje to to, že Windows zrovna provádějí nějakou práci a blokují aplikaci...

pepak

9.2.2011 8:58:21 #

pepak

Ano, je to normální. Ty totiž na DWORD přetypováváš znak (Char - 1 nebo 2 bajty, podle verze Delphi) asData[j][k*4+1]. Abys dosáhl toho, o co ti zřejmě jde, musel bys použít něco jako PDWORD(@asData[j][k*4+1])^

pepak

9.2.2011 9:43:30 #

radekc

Právě proto jsem tam vrazil svoje řešení - ať je nějaká motivace a ať si to každý může zkusit u sebe. Postupně tam budu řešení přidávat - jak budou chodit.

BTW: Myslel jsem si, že jsem vymyslel celkem cool algoritmus, ale pepák mi už naznačil i že bez vláken je rychlejší.

radekc

9.2.2011 16:04:20 #

radomir

Prvni nastrel (zbabele v asembleru / single thread): 156 vs 421 [radekc]

BTW: GetTickCount ma docela velkou granularitu - 15ms na mem PC. Je duvod nepouzit QueryPerformanceCounter ?

radomir

9.2.2011 23:11:29 #

radekc

Dal jsem tam svůj druhý pokus - docela zásadně jsem optimalizoval svůj původní algoritmus na cca 1/2. Zároveň změna kostry na přesnější měření.

radekc

10.2.2011 13:57:37 #

PetrB

Ahoj,
tak také přispěji se svojí troškou do urychlovače ;-).
V současné době mám třetí verzi řešení. První byla rychlá metoda co do vymýšlení a ta mi trvala cca 50x více než Radkovi, ale za to byla hotová za pár minut.
Druhá už byla sofistikovanější, její laděním jsem prožil asi 3 hodiny a rychlost cca 115% Radka. (Furt hodně).
A teď mám 3., kterou jsem ladil trochu déle, cca 5 hodin (hlavně jsem honil duchy protože jsem špatně rozluštil své zápisky grrr) a zde jsou její výsledky. Pro zajímavost to uvádím i pro jednotlivé verze Delphi, které mám teď instalované:

Verze      velikost   rychlost min   rychlost průměr  rychlost max
Radekc2   84 480       204                   204                  206
D3            53 760      124                    123                  125         Drobná změna hl. smyčky, jiné typy
D6          131 072      123                    123                  125
D2010     302 592      117                    119                  122
DXE        315 904      110                    112                  117  

Kromě Radka je to všechno stejný algoritmus bez vláken a ASM, čistě Delphi.

PetrB

11.2.2011 12:05:17 #

PetrB

Ahoj,
měl bych ještě malou připomínku k pravidlům. Neměla by se změnit pod vlivem toho, že se čas počítá průměrem z více průchodů? Hlavně část věty "nebo si vhodně předat data" si říká o hezký výklad ve smyslu "Spočítám to prvním průchodem a pak si jenom vhodně předám výsledky....". To by pak byly časy hóóódně zajímavé. Dal bych tam něco jako "Pro určení pořadí bude rozhodující průměrný čas ze 40 vyvolání soutěžní části programu. 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ě."

PetrB

12.2.2011 1:54:16 #

Jan Javůrek

Kurna tomu rikam definice :)

Jan Javůrek

13.2.2011 19:45:57 #

HonzaK

V jednovlaknovem provedeni mam vysledek 80 proti 332 vzoroveho prikladu. Myslim, ze rychleji uz to nedonutim. Jeste bych se zeptal kolik ma ten zkusebni pocitac RAMky. Je zajimave, ze rychlost ruznych algoritmu zavisi dost i od volne pameti. Tak at je prehled a vime na co to optimalizovat.

HonzaK

13.2.2011 19:50:23 #

radekc

Celkem 2G / cca 1G volné, XP SP 3, tj. dejme tomu, že s 512M se dá počítat - ale to mi přijde celkem jako extrém

radekc

14.2.2011 17:58:23 #

radomir

vzorovy priklad = Radek Červinka (druhý pokus)  {radekc2.zip} ??

radomir

18.2.2011 17:01:43 #

pepak

Uz aby byl konec. Moc me zajima momentalne vedouci reseni, trikrat rychlejsi nez moje, protoze me uz nenapada, kde usetrit - ted jsem svoje puvodni reseni prepsal na uplne jiny pristup, ktery je pri pouziti Pascalu stejne rychly jako puvodni v assembleru, prepsanim by se jeste dalo neco usetrit, ale kde srazit cele dve tretiny, to uz fakt nevidim. Je evidentni, ze to je nejaka zasadni algoritmicka zmena, ale nenapada me jaka - byl bych rekl, ze na tom, co jsem si napsal ted pred chvili, uz se nic zlepsit neda.

pepak

18.2.2011 18:40:27 #

Dalibor Toman

princip je velmi jednoduchy, ale za implementaci je pomerne dost hodin premysleni a doladovani. Dokonvertovali jsme s kolegou v praci k prakticky identickemu reseni, kazdy trosku jinudy. Cele je to postavene na jedine myslence - absolutni minimalizace poctu cyklu CPU potrebnych na zpracovani dat a vyuziti vseho, co zadani ulohy povolilo.

Protoze, jsem doposud na modernich CPU nebyl nucen nic takhle brutalne optimalizovat, docela jsem se diky tomu naucil/poucil. Treba to, ze zlikvidovani 30% instrukci v cyklu nemusi vest ke zrychleni ale naopak. Nebo, ze nektere typy instrukci je mozne temer vzdy beztrestne pridavat. Nektere krasne vypadajici rozepsat na dve tri osklivejsi instrukce a zrychlit tim vyrazne zpracovani. Zatracenej pipelining :-)
Zatim nevim jaky kod poslat do souteze. Ten nejrychlejsi je implementace stejne myslenky jako poslal HonzaK a asi nema smysl ho posilat. Mozna poslu jednu 'slepou ulicku' - dokud jsem ji neimplementoval byl jsem presvedceny, ze nic rychlejsiho neni. Pipelining mel jiny nazor. Jedna se o kod, ktery dnesni bezni higlevel koderi asi nejsou schopni napsat. Cili by to mohlo byt poucne (i kdyz v pascalu neimplementovatelne (resp slo by to ale nebylo by to ono a bylo by to pomale)).

Dalibor Toman

18.2.2011 21:37:54 #

radekc

Nenapovídat prosím :-)

radekc

18.2.2011 23:47:48 #

HonzaK

No 3x se musi brat s rezervou bo to bezi v nekolika vlaknech najednou. Z rozdilu casu proti jednovlaknu je videt ze zrejme jen ve dvou. Vic Radkuv PC zrejme neumi. Takze ten rozdil neni az takovy. Dalsi vec je, ze Delphi je dost ukecane co se tyka vysledneho kodu, takze tim padem i malo optimalni co se tyka rychlosti.

HonzaK

19.2.2011 18:49:43 #

pepak

Mě to samozřejmě také běží ve vláknech, v tom by problém být neměl (leda že by Radkův stroj potají zvládal víc než dvě vlákna...). Teď jsem to přepisem na úplně jiný algoritmus zrychlil, ale že by mě to zrovna uspokojovalo, to ne (ještě bych to zvládl sesekat o nějakých 10%, ale zdá se mi to příliš pracné a nepřehledné, než aby to stálo za to). Hlavně mě děsí, že i když je stávající zpracování rychlejší než všichni kromě tebe, tak je bonus trochu malý na to, že jedu multithreadově v ASM a konkurenční práce jsou v single threadu v Pascalu...

Ještě pořád mám jeden nápad, co zkusit. Ale netroufnu si ani odhadnout, jestli to může být rychlejší než moje momentální řešení. Mohlo by, nemuselo - tak podrobně optimalizace na moderních PC* neznám, abych to dokázal říct. Původně jsem si myslel, že stávající řešení, kde mám pro každý řádek ve vstupním souboru pouhé tři podmíněné skoky (včetně testu, jestli už jsem zpracoval celý soubor!), musí být pro pipelining nejlepší, ale z výsledků je zřejmé, že není. Každopádně se moc těším na odhalení výsledků, fakt jsem na ta řešení zvědavý (ale neprozrazovat, třeba na to ještě přijdu).

* Vlastně nikde. Kdykoliv jsem optimalizoval, tak spíš na velikost než na rychlost.

pepak

20.2.2011 8:24:13 #

pepak

Tak nic. Napsal jsem ten včerejší nápad včetně vylepšení, která mě napadla ve spánku, ale je to o třetinu horší než můj předchozí pokus. V podstatě jsem to očekával, na druhou stranu to byl poslední způsob, který mě napadal, který by teoreticky mohl být rychlejší než moje druhá verze.

pepak

20.2.2011 16:58:47 #

PetrB

Taky jsem svůj algoritmus přepsal na více vláken. Z času min. 90 jsem se na svém pc dostal na min. 50 (Honza K. má u mě ve vláknech 28) a je už jedno, jestli to spustím ve 2 nebo 8 vláknech.
Zkoušel jsem vymyslet ještě něco jiného, rychlejšího, ale jaksi mi to už nejde. ;-) A když jsem naposledy dělal asm, tak byla 80386 na 40Mhz posledním výkřikem techniky, takže tudy taky moje cesta nevede.

PetrB

20.2.2011 22:08:01 #

HonzaK

Pro vsechny (vcetne Petra a Pepy): to, ze nekomu funguje jeho program na jeho PC pomaleji, nez jiz zaslane, jeste nutne nemusi znamenat, ze budou mit stejny pomer na Radkove PC. Mam overene, ze na mem PC jsou ruzne algoritmy docela dost od sebe vzdalene, co se tyka casu kazdeho jednoho a na Radkove PC jsou skoro stejne. Podobnou zkusenost na jinem stroji, na kterem byly programy zkousene jsme dostali vysledky i s opacnym poradim, nez na tom ,kde se to ladilo. Takze doporuceni zni: nezoufejte a posilejte, protoze nemuzete mit jistotu, ze to jinde nepobezi trochu jinak, treba pro vas vyhodneji

HonzaK

20.2.2011 22:52:37 #

radekc

Nečekal jsem, že půjdeme až na takovou úroveň. Myslel jsem, že bude stačit říct, že se jedná o Core 2 Duo.

Chápal bych rozdíl mezi dejme tomu AMD a Intel, ale v rámci platformy?  Pro úplnost, jedná se o tento procesor:

http://www.cpu-world.com/CPUs/Core_2/Intel-Core 2 Duo Mobile T8100 FF80576GG0453M.html

radekc

20.2.2011 23:25:50 #

PetrB

Já nezoufám nad rychlostí,  ale nad tím že už ze mne jiný algoritmus neleze. Dostal jsem se na svoje optimalizační maximum.  Jako vrchol těch snah považuji zakomponování do vláken a tím končím. Pokud si porovnávám rychlosti na mém PC s Radkovým "referenčním", tak jsem asi 1,3x rychlejší nebo tak nějak, takže se dokážu orientovat ve svém skutečném pořadí. Ještě nechám vlákna trochu uzrát a pak je pošlu, abych měl vyčerpány dva pokusy.
A to jestli jsem nejrychlejší nebo ne neřeším (optimalizace na rychlost nebyla nikdy moje silná stránka). Spíš mne zajímají jednotlivé algoritmy, takže jsem zvědavý na příští pondělí.

PetrB

21.2.2011 11:08:47 #

pepak

No nic, když vybyde čas, zkusím ještě jeden poslední pokus, ve kterém zkombinuji poznatky ze všech tří stávajících verzí, co to udělá. Když ne, tak holt pošlu svoji druhou verzi, ta funguje celkem slušně.

pepak

21.2.2011 20:23:52 #

pepak

Konečně! Proof-of-concept ukázal svou sílu, konečně jsem se v single-threadu dostal na čísla, která vypadají rozumně (a konečně chápu, proč to v Pascalu šlo skoro stejně rychle jako mě v asm). Teď už to jenom lehce zoptimalizovat a mělo by to být OK!

pepak

21.2.2011 23:42:38 #

HonzaK

Chtel jsem se Radku zeptat, jak prislo zadani zrovna na takovouto kominaci tagu? To je priklad z praxe? Ptam se proto, jakoby ty tagy byly poskladany tak akorat, aby sel dobre napsat algoritmus.

HonzaK

22.2.2011 0:12:25 #

radekc

Není to z praxe (resp. je to vzdáleně z praxe). Přemýšlel jsem nad nějakou úlohou, která je dostatečně rychlá na základní naprogramování, má potenciál na optimalizaci a která by se dala nějak paralelně zpracovávat i průměrným programátorem.  

Přišlo mi, že je zde spousta možností i tím, jak jsou přesně definované podmínky a že se tak dá napsat velmi rychlý algoritmus i bez asm - pokud člověk ví jak na to (čemuž i výsledky odpovídají). A nakonec jsem vymyslel tento bastl.

Ohledně tagů: tagy jsem skládal tak, abych spíše zkomplikoval některé jednoduché optimalizace, proto mají různou délku a schválně začínají některé stejným písmenem (a proto i ten ukončovací tag). Ale tím, že jich je jen pár jsem chtěl umožnit potencionálnímu hledači najít nějakou možnost optimalizace.

Chtěl jsem aby to byla hlavně zábava jak pro průměrné programátory (at si to aspoň mohou zkusit i když třeba nebudou nejlepší), tak pro ty kdo jako ty půjdou na kost.

radekc

22.2.2011 16:32:48 #

NkD

Muzu poprosit o opetovne zverejneni aktualnich "mezivysledku" ? Takhle mi to prijde mene napinave. Min se dikutuje apod.

NkD

22.2.2011 19:15:58 #

pepak

Nepřekvapilo by mě, kdyby zatím žádné nové výsledky nebyly. Nevím jak ostatní, ale já si svůj druhý pokus šetřím až na poslední chvíli (kvůli pravidlu, že každý má jen dva pokusy - co kdyby mě ještě něco geniálního napadlo, ale už jsem měl oba pokusy odeslané?).

Jako mezivýsledek můžu říct, že jsem se dost přiblížil Honzovi Královi - jeho řešení je konzistentně lepší než moje, ale s rozdíly se pohybujeme v řádu milisekund (aspoň na mém notebooku).

pepak

22.2.2011 21:46:43 #

radekc

OK, mezivýsledky jsou zpátky, pořadí se změnilo a jelikož to zde někoho tak trápí, tak změna ze 2 řešení na 3 řešení. Ať je větší sranda.

Jsem rád, že je první řešení v čistém Pascalu. A opakuji - počítá se minimální čas (podle mne logicky).

radekc

22.2.2011 21:47:16 #

NkD

Diky moc za mezivysledky. A ano spravne fandim Jirkovi Jelinku :-D. Hrnicek je Tvuuuuuuuuuj :-D

NkD

23.2.2011 23:50:15 #

HonzaK

Jirkovi gratuluji, na jeho reseni se potvrzuje to co jsem uz psal, protoze na mem stroji je jeho reseni za 45ms proti memu ktere je za 40ms. To je rozdil 10% a u Radka to udela 10% na druhou stranu. Tzn. ze skutecne dost zasadni roli hraje to jak jsou pomocne promenne rozlozene v pameti a jakym zpusobem se nasledne s pameti pracuje. U takto nasponovanych uloh hraje roli skutecne kazda instrukce, kazdy byte v pameti a jejich vzajemny pomer. Proto nevahejte a posilejte sva reseni, protoze az do konce neni nic jisteho.
Radkovi kazdopadne dekuji za skvely namet na premysleni o algoritmu a sam se tesim na vyhravajici algoritmus, i kdyz si myslim, ze to bude zrejme stejne jako muj, jen jinak rozlozene v pameti.

HonzaK

23.2.2011 23:57:16 #

HonzaK

Jeste me napada: ktere casove vysledky budou brany do uvahy pro vysledkovou listinu? Ty ktere vrati programy nad zverejnenymi daty nebo nad temi, ktere budou podle zadani jina viz (výsledný běh bude nad kapánek jinými daty)?

HonzaK

24.2.2011 0:34:59 #

radekc

Mimochodem mám DDR3 paměti. Jen doufám, že ten generátor generuje stejné data na všech počítačích - u mne se jedná o tyto - http://delphi.cz/img/soutez2/app/data.zip (on je to ve skutečnosti 7z, ale nějak mi to nejde přemluvit server, tak si to přejmenujte). Nechám to tedy jako i finální data.

Honzo: co máš za procesor?

radekc

24.2.2011 18:36:12 #

HonzaK

Spravce zarizeni me pise Intel (R) Core(TM)CPU 920 @2,67, pameti jsou DDR3 na 1333MHz. Rekl bych, ze ruzne pametove narocne aplikace budou davat ruzne vysledky v zavislosti na rychlosti sbernice.

HonzaK

24.2.2011 21:22:51 #

HonzaK

Podle vysledku poctu jednotlivych tagu bych rekl, ze tvoje data jsou malinko jina nez treba na mem stroji. Na vysledky v casech to vsak nema vliv.

HonzaK

26.2.2011 15:03:42 #

pepak

Ještě si trochu hraju s optimalizací. Něco málo jsem ještě ubral, ale i přes IMHO dost drsně optimalizovaný assembler se stále ani neblížím k momentálně vedoucímu řešení, které je dokonce "v čistém Pascalu". Musím přiznat, že jsem na něj moc zvědavý - v tom svém řešení sice stále ještě mám možnosti úprav, ale zdaleka toho nevidím tolik, aby to dokázalo způsobit takový náskok - i kdyby to dělal sebegeniálnější kompilátor...

pepak

26.2.2011 19:28:05 #

pepak

Až to skončí, tak každopádně uvítám, když mi někdo vysvětlí, co to proboha procesor v mém kódu "verze 6 build 6" provádí - jak funguje pipelining je mi jasné, ale tady se to chová úplně protismyslně (čím víc naruším pipelining, tím rychleji to běží - WTF???).

pepak

27.2.2011 11:59:33 #

HonzaK

Pepo, zatim vitezny program dela v podstate to same jako ty (lisi se jen mnozstvim potrebne pameti a jejim rozlozeníim), jen ty delas neco zbytecne navic, byt to muze vypadat, ze tim procesoru usetris nejakou namahu, ale opak je pravdou. Navic ten pascal nepreklada az tak neefektivne, i kdyz jsou po nem v kodu urcite nelogicnosti, ale je otazkou, zda to ma vliv na rychlost diky jiz zminenemu pipeliningu.
Ja jen doufam, ze klid zde na foru znamena, ze lidi piluji programy ze se jeste neco objevi. Za sebe muzu rict, ze se me povedlo najit stroj na kterem ma zatim zverejnena verze bezi v k Jirkove verzi v podobnych relacich jako na Radkove PC, takze mam sanci najit algoritmus, ktery by mohl byt rychlejsi nez Jirkuv a ktery jsem pri ladeni na svem PC mohl i vyloucit jako min efektivni.

HonzaK

27.2.2011 12:08:28 #

pepak

Koukám, že někdo neodolal a otevřel výsledné exáče v debuggeru, aby se podíval, jak to dělají :-). Tak to já ne, sice jsem na ten Pascal zvědavý, ale zase ne tolik, abych se chtěl zbavit potěšení z vlastních objevů a inspiroval se někým jiným. Kromě toho je to irelevantní, protože se mi už z mé publikované verze podařilo srazit tolik času, že bych se na Radkově PC měl dostat na nějakých 30-31 milisekund. Plus mínus - jak píšu, mám tam části, které se podle mě chovají zcela protismyslně a pořád se mi nechce věřit, že se to tak bude chovat stabilně i na jiném procesoru (byť ze stejné rodiny). Nicméně fakt je, že i na mém čtyřjádru dostávám obdobné výsledky.

pepak

27.2.2011 13:16:00 #

HonzaK

Zvedavej jsem sice byl, ale nikdy bych se nesnizil k tomu, abych pouzil cizi myslenku pri soutezi jako svou vyhodu. Pro me bylo podstatne dulezitejsi, ze jsem si nasel PC, ktere dava podobne vysledky jako Radkovo. To je podstatne dulezitejsi, protoze jsem pri puvodnim optimalizacnim vyberu vychazel z vysledku, ktere jsou diametralne jine, nez na Radkove PC, cimz mohlo dojit k tomu, ze jsem nejake reseni mohl vyloucit neopravnene.

HonzaK

27.2.2011 13:30:46 #

pepak

Ani tě nepodezřívám, že bys snad ty myšlenky chtěl používat do soutěže. Ale právě proto jsem se na ty exáče nedíval - už by nemělo přemýšlet na dalším zlepšením, protože bych to stejně nemohl poslat a necítit se přitom jako podvodník.

Já mám kliku, že můj notebook dává poměrně podobné výsledky jako Radkův, tedy aspoň většinou a v relativním pojetí (jeho je o dost rychlejší).

pepak

27.2.2011 13:55:25 #

HonzaK

Sice si Radek "postezoval" ze zverejnovani vysledku melo za nasledek, ze ma malo prihlasenych algoritmu, ale zase na druhou stranu to postrkuje k tomu, aby se clovek nespokojil s vysledkem, ktereho dosahl, ale snazil se udelat jeste lepsi vysledek nez ten kdo je prvni.
Co se tyka studia (a schvalne to nazyvam studiem) ciziho kodu, tak samozrejme, ze kdyby me mel cizi kod zavest na cestu, o ktere jsem dosud neuvazoval nebo dokonce ji jiz nevyzkousel, tak bych se samozrejme s takovou myslenkou rovnez neprihlasil, ale vzhledem k tomu, co vsechno jsem vyzkousel pred tim, nez jsem svou verzi poslal, by me to ani nemrzelo, dokonce bych byl rad ze jsem se poucil od ciziho.

HonzaK

27.2.2011 14:23:51 #

radekc

Jen bych rád uvedl, že Delphi (resp. Delphi 2006 +) používají některé optimalizace i pro počítače generace Pentium Pro a Athlon. Cílem je aby výsledný program běžel co nejrychleji na co největším množství počítačů.

Proto mohou být v kódu zajímavé konstrukce, např. REP RET (jedna z těch co znám). Samozřejmě, že někdy optimizer by mohl být lepší - ale celkově si myslím, že výsledek je slušný (pokud se nepočítá s floating point, kdy ty optimalizace jsou celkem špatné - resp. skoro žádné).

radekc

27.2.2011 14:50:35 #

pepak

Faktem je, že když jsi se teď tak pochvalně vyjádřil o optimalizátoru (REP RET třeba vůbec neznám...), tak jsem experimentálně svůj ASM kód přepsal do Pascalu, nechal to Delphami 2009 přeložit a málem jsem spadl pod stůl, když vyprodukovaly stejně rychlý výsledek. Ale pak jsem pochopil, čím to bylo - používám pro odlišení jazyka, který chci použít, direktivu {$DEFINE ASSEMBLER}, a Delphi 2009 to bůhvíproč měly zapnuté (takže se vlastně prováděl můj optimalizovaný assemblerový kód). Když jsem to přeložil opravdu v Pascalu, tak už nadšení poměrně opadlo - kód se nijak zvlášť neliší od toho, co bych napsal sám, kdybych chtěl napsat assemblerovskou rutinu, hlavně abych ji měl rychle a bez nějakého zvláštního přemýšlení. Tomu odpovídal i čas - 56 milisekund. (Pro srovnání: zde publikované řešení má 55 milisekund a moje současné nejlepší řešení má 38 milisekund).

pepak

28.2.2011 18:48:59 #

DAB

Tak jsem taky přispěl, a to s řešením v Pascalu, protože ASM už jde dávno mimo mě. Osobně bych rád viděl použití čistého Pascalu jako podmínku, znalci assembleru by byli ve výhodě tak jako tak. No nicméně k vítězství mám daleko, 34ms J.J. je moc zajímavý čas. Ale pravda, já se dostal i pod 30ms (na 4jádrovém PC :-) ).

DAB

28.2.2011 20:42:01 #

pepak

Na jednu stranu tech požadavek chápu, na druhou stranu - nástroj je nástroj, to už by se stejně dobře mohlo zakazovat použití konkrétních algoritmů ("já quicksort neznám, ostatní mají unfair výhodu") nebo programů ("proč mám být znevýhodněn jen proto, že nemám peníze na edici Delphi, která obsahuje profiler?").

A zrovna v tomto případě, kdy vedoucí řešení je napsané v pascalu, je vidět, že assembler není pro vítězství nutnou podmínkou...

pepak

28.2.2011 23:51:46 #

radekc

Mimochodem dobrý free profiler je http://delphitools.info/samplingprofiler/ - už jsem to tady psal.

Jinak jsou dostupné už výsledky.

radekc

Komentování ukončeno

Naše nabídka

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).

love Delphi

O Delphi.cz

Delphi je moderní RAD nástroj podporující tvorbu nativních aplikací pro platformu Win32, Win64, Mac OSX, Linux a na iPhone a Android.

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.

Poslední komentáře

Comment RSS

Dle měsíců