Koji jezik da izaberem?

Treba da započnem rad na jednom projektu. U pitanju je primena jednog NP-kompletnog problema. Biće jako puno zauzimanja i oslobađanja memorije u malim porcijama (nekoliko desetina bajtova), ali, budući da će toga biti mnogo, zauzeće može da naraste i na nekoliko stotina megabajta. Najkritičnija mi je brzina izvršavanja. U nekim narednim verzijama će se koristiti višenitna obrada zbog iskorišćenja svih raspoloživih procesora. Ne dolazi u obzir nijedan jezik koji ne podržava objektno orjentisano programiranje. Takođe, bilo bi zgodno da mogu u fazi izvršavanja da "prebrojim" koliko ima procesora na mašini.

1. Koji programski jezik da izaberem? Da li bi brže radio C++ ili C#?
2. Koliko brzo radi mono u poređenju sa Majkrosoftovim .Net-om?
3. Šta se dešava "ispod haube" prilikom zaključavanja i otključavanja promenljive prilikom višenitne obrade, odnosno, kolika je vremenska složenost tih operacija?

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

1) C++ je naravno brži od C#a (radio sam dosta sa oba), a ako te interesuju još neki OO jezici koji proizvode brz izvršni kod, pogledaj D i OCaml.
2) Testiraj sam - ja sam se malo igrao sa Monom i nisam nešto posebno oduševljen, ali ne mogu reći da sam merio performanse.
3) Zavisi od vrste locka. Lično bih ti savetovao da izbegavaš locking i da komuniciraš među nitima tako što ćeš da šalješ poruke (proguglaj malo "Erlang" ili pogledaj ovo: http://www.novetehnologije.com...tervju-sa-autorom-Erlanga.aspx)

Potpis

IOCC

Pa, dobro. Koje vrste zaključavanja postoje i kakva im je efikasnost?

Nadam se da to nije vezano za Erlang.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Ovo je malo opširnija tema, ali generalno lockovi mogu da ubiju performanse na dva načina:

1) Sami lockovi mogu da budu skupi. Npr kad koristiš kernel objekte za locking kod Windowsa, plaćaš mnogo više nego kad koristiš Critical Sections. Ovo je obično manji problem.
2) Samo lockovanje može da upropasti performanse kad niti provode previše vremena čekajući na lock. Ovo je obično ozbiljniji problem.



Jeste vezano za Erlang, ali tehnika (poruke umesto lockovanja) je primenljiva i sa drugim programskim jezicima, mada ne tako lako kao u Erlangu.

Potpis

IOCC

Svako zaključvanje mutex-a, semafor, barijera, itd. i uopšte bilo kakva sinhronizacija je generalno loša za performanse i treba ih izbegavati. Sada ovo ne znači da trebaš da pišeš kod koji pristupa istoj memorji sa više niti, jer to vodi u druge probleme. Ali bilo kakva sihnronizacija znači da će jedna ili više niti provesti izvesno vreme čekajući druge niti da završe posao. Kod sa dosta mutex-a se može tretirati kao program koji ima samo jednu nit, jer će jedna nit uvek čekati na drugu da završi izvršavanje. Od prilike zamisli auto put sa 2 trake i samo jedna je otvorena za saobraćaj. Bolja varijanta od mutex-a je ako je moguće da koristiš tzv. atomic promenljive (problem je što se odnosi samo na jednu promenljivu u jednom momentu, a ne ceo život promenljive u funkciji), a idealna varijanta je da dve ili više niti tretiraš kao procese na odvojenim kompjuterima sa lošom vezom i da među njima komuniciraš preko poruka (npr. Lock Free FIFO). Ovo sa "lošom vezom" kažem jer kao i kod mreže ne želiš da ti slanje i primanje poruka postane glavni deo obrade podataka. Što se tiče memorije, ako je kritična brzina izvršavanja najbolje napraviti cache za svaku nit odvojeno za sitne dinamičke alokacije koje imaju relativno kratak životni vek. I onda u svakoj niti obrađivati samo podatke koji su alocirani u samoj niti. Ili da glavna nit vrši sve alokacije, a ostale niti vrše samo obradu podataka.

Potpis

https://github.com/bkaradzic/bgfx

Nije mi problem da u mom kodu minimizujem čekanja. Niti će uglavnom raditi nad različitim podacima, ali se može desiti da ponekad (nakratko) rade sa istim podatkom. Znam ja da prvo algoritam mora da se paralelizuje. Imam sada dva pitanja.

1. Koliko vremena "arči" zaključavanje jednog celog broja?
2. Kako ostvariti slanje poruka drugim nitima u jeziku C++?

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Sto se tice arcenja vremena, ne treba da se preterano brines, ukoliko ti je algoritam organizovan tako
da najveci deo vremena svaka nit provodi sa svojim podacima, ali ukoliko je u pitanju zakljucavanje jednog integera
svakako pogledaj atomic funkcije, najpogodnije su i najbrze ...

Slanje poruka izmedju dva thread-a u C++ (mada to i ne zavisi od programskog jezika) se obicno moze
implementirati sa nekim queue-om ... gde ce operacije dodavanja, vadjenja i pregleda stanja queue-a
biti obezbedjene nekim lock mehanizmom.

Preporucio bih ti da sto se tice brzine algoritma mnogo vise vremena posvetis
optimizaciji samog algoritma nego li pitanjima vezanim za kompajlerske optimizacije i slicno ...

Ako ocekujes veliki broj alokacija/dealokacija memorije, preporucujem da implementiras neku vrstu
sopstvenog memory manager-a.

Primer bi bio sledeci:

Umesto da alociras memoriju i oslobadjas kada ti je potrebna za podatke, odradi alokaciju memorijskog
bloka maksimalne velicine (u zavisnosti od ulaznih podataka) i onda implementiraj neku hash funkciju
kako bi dobio lokacije koje ces koristiti za skladistenje podataka unutar vec alociranog bloka.

U startu razmisljaj o tome kako bi mogao da paralelizujes algoritam i razbijes ga na odgovarajuci broj procesora u masini
Idealno bi bilo paralelizujes obradu po nezavisnim grupama podataka (ukoliko to problem dozvoljava) kako bi redukovao
potrebnu sinhronizaciju izmedju threadova.

Sto se tice broja procesora, ako je u pitanju windowsxp onda baci pogled na
http://msdn2.microsoft.com/en-us/library/ms683194.aspx

Sasvim tačno, ali tu ima jedna začkoljica. Znajući Nedeljka, on će da pravi aplikaciju za Linux, a Linux nema user-mode atomic funkcije. Ako želi da se ograniči na Linux za x86, onda može da koristi inline assembly u te svrhe.



Ili još bolje, neki lock-free queue (ima implementacija - Guglaj malo).

Potpis

IOCC

Pseudo kod (i veoma pojednostavljeno):
Prve tri verzije moraju zaključati vrednosti i tokom čitanja. A npr. u ovom predzadnjem slucaju nit koja cita ove poruke ne mora da ima pristup RAM i ne mora da zaključa promenljivu tokom čitanja, ili cak ne mora da bude na istom procesoru, recimo ako kreiras interfejs koji šalje ove poruke preko mreže na drugi kompjuter koji obrađuje podatke i vraća samo rezultat...

Sada ovaj kod uopšte ne garantuje nikakvu sigurnost kada radiš sa više niti. Jedino što garantuje je da su promene tih vrednosti sigurne.

Recimo (mutex, lwmutex, atomic verzije, početno stanje g_x je 5):

Nit1
SetBlah(10);
SetBlah(20);
SetBlah(30);

Nit2
x = GetBlah(); // možda 5, 10, 20, 30
SetBlah(x+5);
x = GetBlah(); // možda 10, 15, 25, 35?
SetBlah(x+5);
x = GetBlah(); // možda 15, 20, 25, 30, 35, 40?
SetBlah(x+5);

LFFIFO verzija (2x LFFIFO, jedan za nit1->nit2 i jedan nit2->nit1):

Nit1
SetBlah(10);
SetBlah(20);
SetBlah(30);

Nit2
x = GetBlah(); // 10
SetBlah(x+5);
x = GetBlah(); // 20
SetBlah(x+5);
x = GetBlah(); // 30
SetBlah(x+5);

Zadnja verzija je u slučaju kada te promena stanja ne zanima, nego ti treba samo zadnje stanje:

Nit1
SetBlah(10);
SetBlah(20);
SetBlah(30);
Wait(Nit2 da završi);
Flip( zameni read i write buffer )

Nit2
x = GetBlah(); // 30
SetBlah(x+5);
x = GetBlah(); // 35
SetBlah(x+5);
x = GetBlah(); // 40
SetBlah(x+5);
Post(Nit2 kraj);


Lock Free FIFO. Lock Free znači da koristiš atomic operacije nad PUT i GET pointerom. Kod FIFO-a kada je PUT == GET to znači da je FIFO prazan. Sada možeš da tretiraš PUT i GET kao 16-bit vrednosti pa da pristupaš preko jedne 32-bitne atomic operacije, ili da ih tretiraš kao pointere i da pristupaš preko 64-bitne atomic operacije. Bitno je da uvek pristupaš PUT i GET zajedno sa jednom atomic operacijom jer se vrednost može promeniti između dve atomic operacije.

Potpis

https://github.com/bkaradzic/bgfx

Najviše bih voleo da mi program radi na raznim platformama. Za sada se oslanjam na Qt. Što se broja procesora tiče, nije mi zapravo bitan on, već idealan broj niti, što mi u slučaju Qt-a obezbeđuje funkcija static int QThread::idealThreadCount(). Nisam gadljiv ni na druge frejmvorke, pa ni na druge jezike i okruženja (Lazarus, Java, mono...) pod uslovima

1. Da su višeplatformski, što znači:

1.1 Da je podržan Windows.
1.2 Da je podržan GNU/Linux.
1.3 Po mogućstvu (mada, ne i obavezno) da su podržani MacOS X, Solaris, FreeBSD.

2. Da se kod može u celini menjati, kompajlirati i izvršavati korišćenjem 100% slobodnog softvera uključujući i operativni sistem.

3. Da se kod može u celini menjati, kompajlirati i izvršavati korišćenjem 100% slobodnog softvera, isključujući operativni sistem, na Windows-u.

Dakle, dolazi u obzir i MS Visual Studio.Net pod uslovom da posle toga mono može to da "poćera" sve od sorsa pa na dalje, uz eventualno ručno pravljenje Makefile datoteke ili nečeg sličnog. Ovo često radi. No, o tome bih sam vodio računa.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Ja nisam programer, ali kao off-the-shelf resenje, probaj SmartHeap biblioteku za alokaciju memorije bez previse lockovanja i u vise treadova...

http://www.microquill.com/

Mozda pomogne. Kosta lepe pare, ali bar mozes da pogledas...

Potpis

Please do not feed the Trolls!

Blasphemy? How can I blaspheme? I'm a god!'

"Atomic" dodele vrednosti promenljivih (uglavnom "CAS" instrukcije) moraju da budu podržane hardverski, a npr. Linux radi i na platformama koje nemaju tu mogućnost, pa zato i nema user-mode funkciju za tu svrhu. Doduše, uvek možeš da razdvojiš OS-specific kod u posebne fajlove pa da koristiš atomic funkcije tamo gde postoje, a gde ne postoje koristi mutex.

Potpis

IOCC

Ako su zahtevi ovakvi onda je Java dobra alternativa.

Što se tiče performansi...
C++ je brži kod operacija sa brojevima ali je Java brža kod alokacije memorije i IO operacija. U zavisnosti od toga koliko su ove operacije zastupljene u tvom algoritmu znaćeš šta je bolja alternativa.

Što se tiče multithreadinga...
Mutex zaključavanje je deo Java jezika, a od verzije 5 postoji i robusna biblioteka za konkurentno programiranje: http://java.sun.com/j2se/1.5.0/docs/guide/concurrency/overview.html
U C++ ne znam kako je to rešeno.

A, da li to onda važi i za C#?

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Važi ukoliko koristiš C++ standardnu iostream biblioteku za IO i podrazumevani "new" za alociranje dinamičke memorije. Međutim, ako su ti performanse bitne onda ionako nećeš to da radiš. Recimo, klasične C funkcije za IO su mnogo brže.

Interesantno bi bilo proveriti koliko je brz IO sa npr Qt objektima kao što je QFile.

Potpis

IOCC

Ja glasam za javu prvenstveno po principu "stick to what you know best".

Vidi umesto da alociras i dealociras brdo objekata, pokusaj da ih "recikliras", "ponovo inicijalizujes" odnosno "ponovo-koristis" (object reuse), eventualno da napravis neki dinamicki pool kao sto je neko ranije napomenuo, tada ti optimizacije kompajlera odnosno garbage collectora manje bitne i onda ti je svejedno manje vise da li pises u c++ ili u java/c#

Ja mislim da je. sto se sirove brzine tice za lepo napisan kod svejedno u cemu si ga pisao, ali mislim da ces sa javom ili c# najbrze videti rezultate.

Potpis

http://www.google.com/intl/en/jobs/index.html

@Dragi Tata

IO mi nije kritičan. Nema ga u toku izračunavanja, a ostali delovi programa ionako neće biti kritični. Problem je u sledećem:

1. Ne može se proceniti koliko će objekata moći da zatreba za dati ulaz. Zapravo, teorijski gledano može, ali su te procene toliko grube da su vrlo daleko od bilo kakve praktične primene.

2. Redosled stvaranja i uništavanja nisu niukakvoj vezi. Neće biti ni isti, ni obrnuti, ni u većini slučajeva. Tu ne važe nikakve "fine" pretpostavke.

Iz ovih razloga, ne vidim previše smisla u zaobilaženju standardnog new operatora. Zato sam pitao da li Java/C# mogu dati bolje performanse.

Još me zanima da li će višenitna obrada "upregnuti" više jezgara istog procesora, pod pretpostavkom da OS tako nešto podržava.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

kod mene je na ovom sample code-u java drasticno brza od mono-a


UPDATE:
probao kod keve na windowsu. to je sporija masina sempron 2400+ i java i .net rade za oko 7 sekundi (nemam alat za preciznije neko merenje tamo)

toliko o .net / c# portabilnosti

Potpis

http://www.google.com/intl/en/jobs/index.html

Hvala na korisnim informacijama. Međutim, ne bih se složio da ovaj primer pokazuje da C# i .Net nisu prenosivi (jer program radi svuda gde mono radi), već da je Majkrosoftova implementacija .Net-a dosta bolja od mono implementacije.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Ako te zanima Mono/.NET portabilnost, proveri ovo: http://www.novetehnologije.com...5/Mono-Migration-Analyzer.aspx

Potpis

IOCC