Random generator

[LonelyMan]

67,5 millioner tall per sekund på numpy. Ikke dårlig

 

Jeg har sett c++ kode yte 30 ganger bedre enn det, men nå er dette bra for å være et scriptespråk.

Endret 21. desember 2012 av LonelyMan

[etse]

67,5 millioner tall per sekund på numpy. Ikke dårlig

 

Jeg har sett c++ kode yte 30 ganger bedre enn det, men nå er dette bra for å være et scriptespråk.

Kan bemerke at en av de største forskjellene med tanke på performance (generelt) er at numpy bruker vektorer og arrays, i stede for veldig generelle og dynamiske lister. Dette gjør at man tjener masse ytelse på bekostning av at de er litt mindre dynamiske.

[siDDis]

Numpy er C og ikkje Python.Det er bare implemenert med wrappere for å gjere det enkelt å kalle frå Python.

[LonelyMan]

Det er mye sløsing med ressurser i python om vi tar første eksemplet i tråden hvor han kjører 2.366 sekunder for 1 million tilfeldige numre. En c++ kode hvor de genererer 2 milliarder numre på 1,07 sekunder får vi dette:

 

422,6 tilfeldige numre per millisekund i python

1870907,3 tilfeldige numre per millisekund i c++

 

c++ varianten kjører 4426 ganger raskere. Dvs, python utnytter 1 av 4426 av prosessorens ressurser, resten går til spille.

 

Om du har en kurv med plommer i, og hele kurven representerer prosessorens potensiale, så utnytter du en plomme ut av 4426 plommer, så lite utnytter python seg av prosessorens potensiale, relativt til c++.

 

Nå har jeg ikke optimalisert min egen asm variant ennå, jeg tror jeg kan doble ytelsen, men foreløpig yter den 2,4 milliarder numre per sekund (32 bit) på en kjerne, og jeg holder i skrivende øyeblikk å implementere en smartere måte å kjøre den på.

 

Men om vi tar 2,4 milliarder som jeg genererer i asm og sammenlikner mot den første varianten i tråden med python:

 

Python: 422,6 tilfeldige numre per millisekund.

Asm: 2,4 millioner tilfeldige numre per millisekund

 

Som da blir 5679, i dette tilfellet yter python 1 av / 5679.

 

Det er kostbart å bruke scriptespråk, 1 syklus blir utnyttet og 5678 går til spille, rett i dass. Det er enormt mye cpu ressurser som aldri får bli utnyttet.

 

Dette speiler tilbake på min filosofi at, det er bedre for en bedrift å se etter et bedre skrevet program enn å bruke 10 tusen kroner ekstra på utstyr som kanskje øker ytelsen med en faktor av 2, når software kan øke ytelsen med en faktor på flere tusen

Endret 21. desember 2012 av LonelyMan

[Foxboron]

Men nå bruker ingen scriptspråk fordi det skal utnytte alle ressursene i en CPU. Det du har lavere språk som C, C++ og ASM til. Så personlig ser jeg ikke vitsen at du nevner noe de fleste alt vet om Python og effektivitet.

[siDDis]

Når det kjem til tallknusing så er ikkje Python det beste verktøyet...men det veit dei fleste. Skal du derimot skrive ein applikasjon med raffinert arbeidsflyt ,så er Python med ein gong eit mykje betre verktøy.

[LonelyMan]

Alle verktøy for sitt.

[etse]

Når det kjem til tallknusing så er ikkje Python det beste verktøyet...men det veit dei fleste. Skal du derimot skrive ein applikasjon med raffinert arbeidsflyt ,så er Python med ein gong eit mykje betre verktøy.

Det spørs hva slaks tallknusing. Skal du drive med tallknusing i python så er det nesten et krav at du vet optimaliseringer i python, samt at du tar i bruk numpy / scipy som er gode implementerte verktøy for å jobbe med fysikk og matematikk. Bibiliotekene er som siddis sier skrevet i C hovedsaklig, og dermed veldig effektive. Samt at de tar i bruk mye mer fornuftige datatyper. (Som jeg sa tidliggere blir lister veldig mye brukt i Python - mens numPy bruker Vektorer og Arrays som er mye raskere).

 

Og om man i tillegg kan C, så kan man slik som nevnt tidliggere i tråden skrive algoritmen sin i Python. Finne det kritiske punktet i algoritmen som tar mye tid, og implementere denne delen i C, og ende opp med god nok implementasjon.

 

Videre har du og mulighet til å drive tallknusing på GPU med CUDA, selv i Python. Her kan man få til enorm tallknusingskraft selv i Python. Dog krever også dette litt forståelse for C, da CUDA-kernelen fortsatt må skrives i C.

 

Men et viktig poeng som man må ha med seg når man skriver ulike programmer er at man egentlig kun er ute etter å skrive noe som er godt nok, og ikke optimalt. Rett og slett fordi å skrive optimal kode gjerne tar for lang tid (og tid er penger).

[LonelyMan]

I min random algoritme utnytter jeg 68,5% av prosessoren, eller litt over 2/3 av prosessorens potensiale, så jeg vil nok ikke klare å doble ytelsen, men jeg kan klare å få den til å yte bedre. Jeg har funnet en genial måte å kalkulere verdier i ett kjør istedet for i to separate deler der kan være mer å hente.

 

Men 2/3 er ekstremt bra utnyttelse av cpu'en. Det handler om å utnytte den til fulle. For at den skal yte bedre når man har nådd maks potensiale så må man forbedre algoritmen, der går ikke an å forbedre den på annen måte, prosessoren er mettet, da er det kun algoritme som kan videre forbedre den.

Endret 21. desember 2012 av LonelyMan

[etse]

Hva slaks metode bruker du for å generere disse tilfeldige tallene? (Har du implementert den selv? Eller en ferdig implementert random-funksjon? Om den er implementert selv, hva slaks tall-teori baserer du deg på, og hvor "random" er den?

 

Å velge en lett random algoritme gjør at koden blir mye raskere - men tallene blir også mindre tilfeldige. Så det blir litt feil å putte fokuset direkte på antall random tall per sekund, om man ikke bruker samme type algoritme.

 

Vil og nevne at for en oppgave som å generere store mengder tilfeldige tall, kanskje ikke er helt det beste å gjøre på CPUen til å begynne med. Du kan jo fint lage implementasjoner som har langt større ytelse på GPU, uten å trenge å gjøre masse optimaliseringer. Spesielt siden oppgaven er embarrasingly parallel.

[LonelyMan]

Ja kodet den selv og den har en periode på 10^18. Gpu er fine greier, jeg har cuda selv her, men har ikke kodet det. Det er fint å bruke cuda men ikke alle som har det, og om du benytter ressursene på den til å beregne random tall så bruker du samtidig opp ressurser der som kunne vært brukt til bedre oppgaver relatert til grafikk. Så man må alltid veie opp hva man skal gjøre og om det er verdt det. Men cuda er raske saker det. Jeg har en gtx 680 amp edition her så der er nok av kraft å hente der.

Endret 21. desember 2012 av LonelyMan

[GeirGrusom]

Ja kodet den selv og den har en periode på 10^18. Gpu er fine greier, jeg har cuda selv her, men har ikke kodet det. Det er fint å bruke cuda men ikke alle som har det, og om du benytter ressursene på den til å beregne random tall så bruker du samtidig opp ressurser der som kunne vært brukt til bedre oppgaver relatert til grafikk. Så man må alltid veie opp hva man skal gjøre og om det er verdt det. Men cuda er raske saker det. Jeg har en gtx 680 amp edition her så der er nok av kraft å hente der.

"Alle" har OpenCL og DirectCompute

 

etse:

Jeg ser lite poeng i å bruke GPU-en til å generere tilfeldige tall egentlig. Det er kanskje en parallell prosess, men kun dersom du skal generere så mange tall som mulig. Tallene skal mest sannsynlig benyttes i en seriell algoritme, og delegere dette til GPU-en vil man mest sannsynlig da tape på, ettersom en enkel tråd for å generere ett heltall vil være tregere på GPU-en enn det CPU-en er.

 

GPU-en er power in numbers. Hver enkelt prosessor er relativt svak i forhold til CPU-en, spesielt til heltall.

Endret 21. desember 2012 av GeirGrusom

[etse]

Poenget her er jo at han skal ha en enorm mengde tilfeldige tall, og da ville jeg gjort det på GPU, siden man vil kunne få god ytelse om antallet man ønsker å generere er veldig stort. Hvilken praktisk nytteverdi dette vil ha blir en helt annen sak. Poenget var uansett at når man driver med veldig paralelliserbare algoritmer så blir det ofte bortkastet å sitte å optimalisere de på CPU - når en GPU kan gi så mye mer ytelse på slike problemer.

 

 

Selvfølgelig vil du tape masse på å bare generere et par tilfeldige tall på GPU om gangen. Så om du skal bruke masse tilfeldige tall må du generere en hau når du først gjør det, så mellomlagre de i minnet til når du trenger de. (Vil da gå på bekostning av en del minne selvfølgelig, som en seriell versjon ikke trenger å ta hensyn til).

 

Om du kun er ute etter å generere tilfeldige som en liten del av en seriell algoritme så skal du ha en veldig spesial case før de vanlige random-funksjonene er for trege - Men mange ganger hvor du har bruk for en så stor mengde tilfeldige tall, vil du også sitte med et problem som kan helt eller delvis parallellisere. Dermed kan du bare generere de tilfeldige tallene i den samme CUDA-tråden som, du løser en del av problemet i.

[GeirGrusom]

Poenget her er jo at han skal ha en enorm mengde tilfeldige tall, og da ville jeg gjort det på GPU, siden man vil kunne få god ytelse om antallet man ønsker å generere er veldig stort.

Ja absolutt. Bruk GPU-en dersom oppgaven passer til det, og skal man bare generere masse tall som dette er den perfekt.

[LonelyMan]

"Alle" har OpenCL og DirectCompute

 

Alle har også direct3d, men det betyr ikke at alle har hardware støtte for det. Interfaces er bare interfaces.

 

Vi snakker cuda her dog og ikke opencl, selv om du på en måte kan trekke paralleller mellom de, så er det like greit å være spesifik.

 

Apropos "store lagre med numre":

 

Å ha en rask random funksjon behøver ikke bety at en behøver store lagre med numre, det kan rett og slett bare bety at du ønsker å putte inn, f.eks i et spill, "Gi meg 100 random numre her, og gjør det så raskt at jeg ikke merker at du er her engang"

 

Det kan rett og slett bare handle om å implementere en funksjon som nesten er usynlig i prosessoren, nesten ingen kostnad. Det behøver ikke handle om store mengder tall, men at det handler om å være gjerrig, at man ikke ønsker å ofre så mye ressurser på random generering, kanskje er cpu'en allerede fullpakket med oppgaver.

 

Når det gjelder cuda med små mengder tall så blir det mye overhead å starte opp cuda vil jeg tro. En annen ting er at du må ha en kompatibilitetssjekk før du starter opp cuda, om cuda ikke støttes faller programmets ytelse plutselig med en faktor på 100, enten yter programmet ditt supergodt eller så yter det kanskje super dårlig, det kan være litt humbug reklame for et program, da er det godt å ha en standard ting som fungerer på det meste og hvor ytelsen er streamlinet, tilgjengelig right on time. Det ligger verdi i det.

 

En annen side av det er at mange pseudo random algoritmer ikke er thread safe, du får dårlig kvalitet eller korrupte tall om du kjører over flere tråder. Men det avhenger av algoritme.

Endret 21. desember 2012 av LonelyMan

[Terrasque]

dd if=/dev/urandom of=/dev/null bs=1M count=10

 

eat pancake

[LonelyMan]

dev/urandom genererer kryptografiske sikre numre. Det er mest brukbart i lotto programmer og andre plasser, men i spill så behøver ikke den være mere tilfeldig enn øye klarer å oppfatte.

 

Nå ville jeg brukt intel sin RdRand instruksjon, random feature direkte på prosessoren istedet for dev/urandom, intel sin versjon er mer kryptografisk sikker, og i tillegg genererer den mange ganger flere tall.