Digitalna evolucija

Na vsak način. O tem sem razmišljal kot o spin offu, derivativu iz Critticalla. Ampak sem ravno v enih drugih njegovih derivativih.

Razmišljam tudi o enem Theorem Finderju ...

> Razmišljam tudi o enem Theorem Finderju ...

Mersenne ne da miru?

Dej mi pastaj kodo sem, please. Pri meni je hitrejši.

 
 // nextpow.cpp : Defines the entry point for the console application.
 //
 
 #include "stdafx.h"
 
 #include <math.h>
 #include <stdio.h>
 #include <windows.h>
 
 // definiraj BITS 9 za kodo za 9 bitna stevila
 // definiraj BITS 16 za kodo za 16 bitna stevila
 #define BITS 16
 // 
 //
 
 unsigned NextPow2( unsigned n ) {
 int MantissaMask = (1<<23) - 1;
 (*(float*)&n) = (float) n;
 n = n + MantissaMask & ~MantissaMask;
 n = (unsigned) (*(float*)&n);
 return n;
 } 
 
 
 
 int NextPow2_Critticall( int n ) {
 
 // ************* CR code begins ****************
 int p2=0;
 
 
 #if BITS==9
 p2=1;
 int i=n;
 
 p2=16;
 if (i<=p2) {
 p2=1;
 if (i<=p2) {
 goto label;
 }
 }
 p2=p2+p2;
 if (i>p2) {
 p2=p2+p2;
 if (p2<i) {
 p2=p2+p2;
 if (i>p2) {
 p2=p2+p2;
 if (p2<i) {
 p2=p2+p2;
 }
 }
 }
 }
 
 label:;
 
 #elif BITS==16
 
 p2=0;int i=0;
 int critticall3=512;
 if (i<=critticall3) {
 p2=critticall3;
 critticall3=64;
 if (i<critticall3) {
 p2=critticall3;
 critticall3=8;
 if (i<=critticall3) {
 p2=critticall3;
 critticall3=1;
 if (i==critticall3) {
 p2=1;
 }
 goto dol;
 }
 critticall3*=4;
 if (i<=critticall3) {
 p2=critticall3;
 critticall3/=2;
 if (i<critticall3) {
 p2=critticall3;
 }
 }
 goto dol;
 }
 critticall3*=4;
 if (i<critticall3) {
 p2=critticall3;
 critticall3/=2;
 if (i<=critticall3) {
 p2=critticall3;
 }
 }
 goto dol;
 }
 critticall3=16384;
 if (i<=critticall3) {
 p2=critticall3;
 critticall3/=4;
 if (i<critticall3) {
 p2=critticall3;
 critticall3/=4;
 if (i<critticall3) {
 goto labelcritticall15;
 }
 }
 critticall3=critticall3+critticall3;
 if (i<critticall3) {
 labelcritticall15:;
 p2=critticall3;
 }
 } else {
 critticall3=critticall3+critticall3;
 if (i>critticall3) {
 critticall3=critticall3+critticall3;
 }
 p2=critticall3;
 }
 dol:;
 
 #endif
 
 return p2;
 
 }
 
 int main(int argc, char* argv[])
 {
 
 int t=GetTickCount();
 for (int n=0; n<100000000; n++) {
 #if BITS==9
 NextPow2(n%512);
 #elif BITS==16
 NextPow2(n%65536);
 #endif
 }
 
 printf("time NextPow2 %d miliseconds. ",GetTickCount()-t);
 system("pause");
 
 t=GetTickCount();
 for (n=0; n<100000000; n++) {
 #if BITS==9
 NextPow2_Critticall(n%512);
 #elif BITS==16
 NextPow2_Critticall(n%65536);
 #endif
 }
 
 printf("time NextPow2_Critticall %d miliseconds. ",GetTickCount()-t);
 system("pause");
 
 return 0;
 }
 
 
 

Tkole. Dopuščam sicer, da je kje kakšna napaka, vendar je ne vidimo.

BITS 9 pomeni, da oba programa delata z 9 bitnimi števili, BITS 16 pa da s 16 bitnimi. Ti dve vrednosti sta pokriti in tudi spodaj se potem generira 100 milijonov teh ali onih števil. To spreminjajte.

Najprej se požene koda ki jo je dal Vesoljc, potem pa Critticallovi dve. Ali včerajšnja za 9, ali današnja 16 bitna števila. Odvisno, kako je definiran BITS.

Kar se tiče algoritma za Rubikovo kocko, bi samo dopolnil snowa.

Evolucija poteka v dveh fazah. V prvi iz random postavitev zevoluiramo take transformacije, da zreducirajo število raznobarvnih sosed. Se pratvi, tiste sekvence transformacij so bolj fit, ki zmanjšajo pisanost.

Tako v tej prvi fazi dobimo magari slab algoritem za sestavitev. V drugi fazi FITNESS postavimo kot manjše število operacij.

To je eden možnih načinov.

Bom dal, čim konsolidiram. Da torej pridem do vsaj 24 bitov in preženem šurke. Še vedno dam 10%, da je prav meril snow in ne jest.

BUT! Sem zgubu password od GameDev in še password od tistega maila, kamor ga lahko spet dobim. Rajtam. No, bom že.

Probaj še tole:

 n+=-1;
 t1=2;
 t2=n/t1;
 t2=n|t2;
 n=t2>>t1;
 n=n|t2;
 t1=8;
 t2=n/t1;
 t2=n|t2;
 t2=t2/t1;
 n=n|t2;
 n+=1;
 

Borland 5.5:
time NextPow2 7125
Press any key to continue . . .
time NextPow2_Critticall 719
Press any key to continue . . .
time NextPow2_Critticall_snow 6672
Press any key to continue . . .

gcc:
time NextPow2 94
Press any key to continue . . .
time NextPow2_Critticall 718
Press any key to continue . . .
time NextPow2_Critticall_snow 15
Press any key to continue . . .

Gre za isti file... source
Za tisto varianto do 512... sicer delata tista moja verzija tud za višje cifre...

Hehe gcc je lisjak!
Sem izklopu optimizacijo.. pol pride kot si rekel ja:

time NextPow2 4578
Press any key to continue . . .
time NextPow2_Critticall 1969
Press any key to continue . . .
time NextPow2_Critticall_snow 11062
Press any key to continue . . .

Tale gcc compiler optimizacija temelji na eliminaciji izračunavanja, ki potem nikoli ne pride na vrsto. Izumili so zadevo pri Borlandu za promocijo. Precej podobno, kot na QWERTY tipkovnici hitro izpišeš TYPEWRITER. Preveč globoko pa to ni.

Ja gremo snow. Tko kot se dogovarjava zasebno.

> Vsekakor boljse, da mi jo compiler v parih minutah optimizira kot da moram laufati criticall celo noc.

Ti sploh ne razumeš zadeve, kar me rahlo čudi. Bom razložil za vse.

Optimizacija compilerja je nekaj povsem drugega od tistega, kar dela Critticall. Ti lahko s compiler optimizacijo optimiziraš Bubble sort 100 milijard let, pa Several Unique Sorta ne boš nikoli dobil. Ali pa tistega Next_Power2_Critticall zgoraj, tudi ne!

Zakaj ne? V čem je caka?

Kar zna CO je metanje neuporabljenega izračunavanja ven in nič drugega.

Daleč premalo, da bi dobil karkoli drugega kot:

- pohoblanje slabo napisanih programov

- sabotaža benchmarkov

Za slednje je bilo to izumljeno. Uporabno je pa tudi za silo za prvo.

_{Aja, sej res, sem pozabu. Several Unique itak ne obstaja, oziroma "je Ukrajinski."}

Gandalfar, a si zavisten al kaj?

Na vsake toliko(kar frekventno) napišeš kak smešen(da ne rečem še kaj drugega) komentar.

Če kdo zavaja - ali je zaveden - si to ti.

Kaj je naredila optimizacija compilerja zgoraj?

Compiler je izvedel zanko manj kot 100 milijonkrat, kar mu je bilo ZARADI TESTA naročeno.

To seveda ni nobena optimizacija. Tako je včasih "šel na roko" Critticallu, včasih pa originalnemu algoritmu. Zadeva je pač približna in nas je le motila pri meritvah.

Ni pa potrebno izključevati optimizacije, ko zares kompiliraš Several Unique, ne pa za benchmark.

Takrat mu ta optimizacija lahko prinese še kakšen % in je koristna.

Če bi pa rad "zmagovalca s compiler optimizacijo", je pa to algoritem, ki ga je s Critticallom dobil snow. Je pa Critticallov izdelek "kozmično dober" - 15 milisekund za 100 milijonov next_power_2!

Samo vemo da ni tako. "Compiler optimizator" nam je skrivil realno sliko.

Štekaš?

Gandalfar in somišljeniki bodo pač trdili, da tegale algoritma:

 
 unsigned NextPow2( unsigned n ) {
 int MantissaMask = (1<<23) - 1;
 (*(float*)&n) = (float) n;
 n = n + MantissaMask & ~MantissaMask;
 n = (unsigned) (*(float*)&n);
 return n;
 } 
 
 
 

- ni mogoče izboljšati

- če ga že je mogoče, ga Critticall ne more

- če ga že more, to rutinsko dela tudi compiler optimizer

- če že compiler optimizer tega ne zna, potem to itak nima nobenega smisla

Heh, prav anekdotično!

> Ali obstaja kaksen nacin, da vem da je criticall pravilno optimiziral algoritem ne da bi pregledal z brute force vse rezultate funkcije in jih primerjal z rezultati neoptimizirane funkcije?

Ali obstaja kaksen nacin, da vem da je kdorkoli pravilno optimiziral (napisal) algoritem ne da bi pregledal z brute force vse rezultate funkcije in jih primerjal z rezultati neoptimizirane funkcije?

V obeh primerih je treba izpeljati matematičen dokaz.

Jaka,

Se morm samo strinjat. Testing gre zdej ven, širjenje gre pa not.

Ja.

Ja. Tako je. Zdej samo vprašanje, koliko racionalen je tale tabelaričen način.

Mam jest zdej eno kodo z nastavljivo bitnostjo števil. Kdor ne bi imel variabilnih BITS, lahko tudi zapeče.

 // nextpow.cpp : Defines the entry point for the console application.
 //
 
 #include "stdafx.h"
 
 #include <math.h>
 #include <stdio.h>
 #include <windows.h>
 
 // define bits. Don't go over 22, since the original code may fail.
 #define BITS 21
 // 
 //
 
 unsigned NextPow2( unsigned n ) {
 int MantissaMask = (1<<23) - 1;
 (*(float*)&n) = (float) n;
 n = n + MantissaMask & ~MantissaMask;
 n = (unsigned) (*(float*)&n);
 return n;
 } 
 
 
 
 int NextPow2_Critticall( int n ) {
 
 int p=0;
 int i=n;
 int limit=1;limit<<=(BITS-1);
 p=limit;
 // ************* (slightly) modified Critticall's code begins ****************
 while (p>8) {
 p>>=1;if (i>p) {p=p+p;goto over;}
 }
 p=5;
 if (i>=p) {
 p=8;
 } else {
 p=2;
 if (i>=p) {
 if (p==i) {
 goto over;
 }
 p=4;
 goto over;
 }
 p=1;
 }
 over:;
 
 // ************* (slightly) modified Critticall's code ends ****************
 
 
 return p;
 
 }
 
 int main(int argc, char* argv[])
 {
 
 int mode=1;mode<<=BITS;
 int t=GetTickCount();
 for (int n=0; n<100000000; n++) {
 NextPow2(n%mode);
 }
 
 printf("time NextPow2 %d miliseconds. ",GetTickCount()-t);
 system("pause");
 
 t=GetTickCount();
 for (n=0; n<100000000; n++) {
 NextPow2_Critticall(n%mode);
 }
 
 printf("time NextPow2_Critticall %d miliseconds. ",GetTickCount()-t);
 system("pause");
 
 return 0;
 }
 
 

> Evolve.

True.

Kot je reku Bedanc: Še bl noro! Še bl na poskok!

Mislim, da je v konkretno tem primeru še precej prostora. Optimalen algoritem je pa odvisen od verjetnostne porazdelive vhodnih podatkov. Takih, esencialno različnih porazdelitev je vsaj nekaj deset - po mojem - in zato nekaj deset različnih algoritmov za vzredit.

Potem v programu se pa kliče optimalni za pričakovan tip podatkov. Hkrati se (občasno) izvaja tudi light statistika in po potrebi zamenja algoritem. To statistiko je pa tudi treba zevoluirat.

Stvari so crazy, samo nekateri si (vede?) zatiskajo oči pred tem.

Bo kdo reku - pa se splača tolk evoluirat? A ni to tko, da se pridobi malo CPU, za evoluiranje pa ogromno izgubi?

Odgovor je: za nekatere reči, ki bodo tekle na milijonu procesorjev - zagotovo. Za druge reči, ki se bodo izvajale mnogo milijardokrat - zagotovo. Redke so stvari, ki se jih ne splača - težko najdeš!

Začel sem tkole:

$declareint i p t
$Weights commands=0 lines=1
$INVAR i(0)
$INVAR i(1)
$INVAR i(2)
$INVAR i(3)
$INVAR i(4)
$INVAR i(5)
$INVAR i(6)
$INVAR i(7)
$INVAR i(8)
$INVAR i(9)
$INVAR i(10)
$INVAR i(11)
$INVAR i(12)
$INVAR i(13)
$INVAR i(14)
$INVAR i(15)
$retvar p
$enhancing off
t=0;if (i==t) {p=1;}
t=1;if (i==t) {p=1;}
t=2;if (i==t) {p=2;}
t=3;if (i==t) {p=4;}
t=4;if (i==t) {p=4;}
t=5;if (i==t) {p=8;}
t=6;if (i==t) {p=8;}
t=7;if (i==t) {p=8;}
t=8;if (i==t) {p=8;}
t=9;if (i==t) {p=16;}
t=10;if (i==t) {p=16;}
t=11;if (i==t) {p=16;}
t=12;if (i==t) {p=16;}
t=13;if (i==t) {p=16;}
t=14;if (i==t) {p=16;}
t=15;if (i==t) {p=16;}

Potem sem dobil tole:

// The algorithm has been enhanced For 93.75%

$DECLAREINT i p

$INVAR i(0)
$INVAR i(1)
$INVAR i(2)
$INVAR i(3)
$INVAR i(4)
$INVAR i(5)
$INVAR i(6)
$INVAR i(7)
$INVAR i(8)
$INVAR i(9)
$INVAR i(10)
$INVAR i(11)
$INVAR i(12)
$INVAR i(13)
$INVAR i(14)
$INVAR i(15)
$ENHANCING OFF
$RETVAR p
$WEIGHTS commands=0 lines=1

// int i=0;int p=0;

$BES
p=1;
while (i>p) {
p<<=1;
}
$EES

Zakomentiramo:

// $WEIGHTS commands=0 lines=1

In potem smo dobili tisto zgoraj - ampak le do 15. To sem potem ročno postavil na BITS.

Link.

Že dva dni jih bombardiram tukajle, pa zaenkrat ni še noben nič izjavil.

Ja nič, zdej se eni tam še nekaj upirajo. Preideva na Rubikovo kocko, čim jih pokorim!

Zadeva s tabelo (1kb) dela hitreje.

Klik. Zadeva_s_tabelo.cpp

time NextPow2_Critticall 9203 miliseconds. Press any key to continue . . .
time NextPow2_table 7859 miliseconds. Press any key to continue . . .

Do 2²⁹.

Tu se moram delno strinjati z Gandalfarjem. Tale tema je mestoma res preveč "propagandno" zastavljena. Po eni strani bi naj moč Critticalla bila ravno v zapolnjevanju niš (recimo z SU), po drugi strani pa prevajalnik "goljufa", ko naredi nekaj podobnega (čeprav dokler smo samo pri optimizacijah s prevajalnikom, brez profilerja, niti ne tako zelo drastično). Critticall sam po sebi je sicer fascinantna zadevščina, ampak v vsakem primeru, kjer (v času, ki je na voljo) ne izvali hitrejše kode kot jo zmore konkurenca (kar se mene tiče Intel C++ Compiler 8 v vsem besu, po možnosti prevajujoč za Intelovo platformo), ima samo akademski pomen. Glede na to, da s Critticallom zgenerirana koda ni zelo berljiva, niti ni ne odpravi največje pomankljivosti preagresivnih optimizacij, preveč ozko usmerjene kode (ali manj fino rečeno, malih gozdnih živali), še vedno je potrebno testirati.
Druga grda stvar je sofistična uporaba izraza "strict C". Edino kar lahko nosi ime strict C je ANSI C99, kar to ni.

P.S. goto stavek ni pripomore niti malo k estetiki kode

je SAMO plod diverzije for zanke, ki jo je naredil gcc compiler.

Dokler je ta "samo" bolj učinkovit od Critticalla ...
Če zadostuje to (ali pa karkoli drugega iz njegove malhe, recimo data aligment, vektorizacija ...), da postane precej bolj naiven algoritem, ki pa je hkrati tudi precej bolj berljiv, najboljša rešitev, zakaj pa ne. Meni je povsem jasno v čem je razlika med obema pristopoma in si ne delam utvar, da lahko prevajalnik iz O^3 problema lahko naredi kaj drugega kot O^3 problem, ampak treba je upoštevati, da se v neki realni aplikaciji ne izvaja ta algoritem povsem ločeno, celo v abstraktnem sistemu.
Pri prevajalnikovih optimizacijah potegene Critticall večkrat "ta krajšo" verjetno ravno zaradi svoje najvčje varline, izvirnih (in človeku neintuitivnih) pristopov k reševanju problemov (kolikor sem gledal rešitve, ki jih uporabljajo, so precej "obrtniške").
Predpostavimo lahko, da se da vsak algoritem samo končno optimizirati, ni pa nujno, da bo matematično najboljša rešitev delovala najhitreje tudi na računalniku za katerega je namenjena, torej Critticallova rešitev po poljubno mnogo časa, pri tem ko je tekla vzporedno v poljubno mnogo instancah, ni nujno najboljša. Vsaj pri trenutni stopnji njega razvoja.

Če se komu zdi tole "preveč propagandno", naj se to pove, naj se politika Slotecha jasno izrazi: "Thomas ti ne bomo več pustili pisat tegale!" Bom vsaj vedel, pri čem sem.

Sploh ne gre za to, ampak za določen nivo debate, ki ne vklučuje preveč izrazitega prikrajanja dejstev, saj to je vendar standarden kriteri za teme v oddelku kot je Z&T, mar ne?