Random brojevi u C# nisu nimalo random

Je li ovo kraj bisera nadovezanih na očitu stvar da treba alocirati random seed prije ulaska u petlju, a onda kroz petlju Next() metodom dobiti sekvencu slučajnh brojeva.

Malo me podsjeća na one beskorisne opće forume kad se ovakvi svađaju o tom mogu li krave biti ljubičaste, pa neki pametnjaković primjeti da netko nije stavio zarez na pravo mjesto, pa nadmoćno optuži sve druge za "nepismenoist".

Uglavnom, kao što reče pokojni pjesnik Anton Šoljan: "miroljubiv čovjek sam, a pomalo već i star", pa mi nije ni do gorespomenutih općih foruma, niti bih volio da se razina njihove komunikacije primjeni ovdje.

Iliti drukčije rečeno:

"dokazuj se kodom, a ne ovakvim rečenicama".

U C# stvari su postavljene malo drukčije nego u C i C++,

Postoje vrijednosni i referencni tipovi čije je ponašanje ovakvo:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class ReferencniTip
    {
        public int broj;
    }
    struct VrijednosniTip
    {
        public int broj;
    }
    class Program
    {
        static void Main(string[] args)
        {
            ReferencniTip referencniTip = new ReferencniTip();  //instanca ref tipa
            VrijednosniTip vrijednosniTip = new VrijednosniTip(); //instanca vrijed. tipa

            referencniTip.broj = 5; //dodjela vrijednosti člana ref tipa
            vrijednosniTip.broj = 5; //dodjela vrijednosti članu vrijednosnog tipa

            ReferencniTip noviReferencniTip = referencniTip; // instanca dodjeljivanjem
            VrijednosniTip noviVrijednosniTip = vrijednosniTip; // instanca dodjeljivanjem

            noviReferencniTip.broj = 10; //promjena vrijednosti člana ref tipa
            noviVrijednosniTip.broj = 10; //promjena vrijednosti člana vrijednosnog tipa

            Console.WriteLine(referencniTip.broj); //ispis je 10 jer se promjenom vrijednosti člana u noviReferencniTip promjenio i ovaj
            Console.WriteLine(vrijednosniTip.broj); //ispis je 5 jer za vrijednosne tipove vrijedi semantika kopiranja
        }
    }
}

Još kad se ovom dodaju ključne riječi out i ref koje se mogu dodati vrijednosnim tipovima, pa tako zahvatiti vrijednost iz metoda promjenom u referencni tip, ili s out jednostavno označiti parametar izlaznim:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{

    class Program
    {
        static void Metod(out int broj)
        {
            broj = 10;
        }
        static void Main(string[] args)
        {
            int broj;
            Metod(out broj);
            Console.WriteLine(broj); //ispis je 10

        }
    }
}

U stvari, pokazivači i reference, koji se koriste u C i C++.  kod ovog načina rada nam ne trebaju.

U stvari, ovo je čak lakše od pokazivača

čim imaš referencni tip, ne trebaš pokazivače, a za vrijednosni staviš keyword ref ukoliko treba i gotovo.

Uf, stvarno sam si uzeo vremena...

Dakle..
Zaboravio sam dodati u proslom postu - pipelining pomaze tome da svaki tick mozes odraditi vise instrukcija zbog toga jer ako si prefetchao tocne instrukcije, onda dijelovi pipelinea odradjuju drugacije stvari - dok recimo prvi pipe izvrsava instrukcije, pipe prije njega cita memoriju, a pipe prije toga dekodira slije-slijedecu instrukciju.

Da bi prefetch radio punom parom, bitno je pametno organizirati podatke u memoriji, dva najbitnija koncepta su kolokacija i poravnavanje (alignment).

Kolokacija znaci da podaci koji se koriste zajedno budu pospremljeni blizu u memoriji, tako da ih se moze prefetchati. Primjerice, ako imas operaciju mnozenja velikog broja vektora sa matricom, onda je pametno poslagati vektore linearno u memoriju jedan za drugim, tako da prefetch moze pripremiti podatke u L1 cache za CPU prije nego instrukcija koja ih treba dodje na izvrsavanje - sto danas nije jednostavno s obzirom da za jedan takt sabirnice, procesor odradi visestrukto taktova (multiplier). Prvo da objasnim alignment tako da vidis kako podaci dolaze na cache, pa da ti objasnim kako kolocirati podatke tako da budu na cacheu cim ih procesor zatreba.

Poravnavanje znaci da podatke koji su u memoriji mozes povuci u minimalnom broju citanja. Primjerice, imas 3D float vektor i 4D vector, koji zauzimaju 12 i 16 byteova, floatovi su x,y,z, w. Ako alociras dva takva vektora u cistu memoriju, to znaci da kad CPU dohvaca drugi vektor, mora odraditi vise od dvije memory read operacije koliko je potrebno za vektor na boundaryu, zasto?

Jer prvi vektor lezi na adresi 0x0, i zauzima slijedecih 12 byteova. 64bitni procesor ce procitati 8 byteova u tiru, sto znaci prva dva floata (x i y), i onda opaliti jos jedan read da procita treci float (z) i prvi float drugog vektora (x2). Naravno, svi ovi readovi se odmah pisu i u L1 cache, efektivno ga thrashajuci s podacima koji su nam korisni (matrica npr) jer upisujemo vrijednosti koje su nam nepotrebne.

Drugi vektor lezi na adresi 0xC (12), a 12 ne mozes faktorizirati sa 8. To znaci da ce procesor prvo procitati 8 byteova pocevsi od adrese 0x8, i maskirati prva 4 bytea, ostavivsi samo x2. Nakon toga, slijedeci read cita y2 i z2 sa 0x10 (16), i onda jos jedan read koji cita w2 i smece. Vektori su mi nekakav realworld primjer, ali oni vec sadrze dosta velike datatipove (float). Uzmi za primjer char koji je velik samo 1 byte, i onda nakon njega neki veliki podatak (array 64 bitnih pointera), i vidjet ces kako zbog alignmenta, trebat ce ti dvostruko veci broj citanja iz memorije nego kad bi bili poravnati, a istovremeno thrashas cache kao veliki jer zbog tog jednog bytea van alignmenta (char), citas po 7 byteva smeca koje maskiras kasnije da bi podatak dosao u registar.

Sveukupno, 5 citanja iz memorije - 5 zauzetih cache linija (koje mogu biti 32 ili 64 bytea). Jedna cijela linija je thrashana zbog loseg alignmenta.

Kako rijesiti problem? Jednostavno - poravnas vec3 na boundary od 16 byteova, sto znaci da ce zadnjih 4 bytea biti padding, odnosno izgubljena memorija. No objekt koji slijedi vec3 u memoriji ce biti poravnan na boundary.

Kako odrediti alignment? Ovisi od compilera do compilera. Ako me sjecanje ne vara, u MSVC-u dodas qualifier __declspec(align(x)) ili nesto tako prije nego deklariras ime tipa (ex: struct __declspec(align(16)) Vec3 {};). U GCC-u na kraju tipa dodas __attribute__((aligned(x))) (ex: struct Vec3 { ... } __attribute__((aligned(16)));

Dakle, kako onda kolocirati poravnane podatke da odmah budu na cacheu? U C-u ili C++u, dosta jednostavno - napises svoj alokator, po mogucnosti po uzoru na STL (preko templatea) umjesto in-place alokatora. U svojem alokatoru odredis memory poolove za tipove podataka za koje znas da moraju lezati jedan uz drugi i te adrese vracas, primjerice, uzmes u startu 64MB za vektore i 64MB za matrice. Sve alocirane vektore slazes u prvi pool, jedan za drugim, a sve matrice u drugi. Kad krene mnozenje, CPU ce u prvom tiru traziti matricu koju ce zakaciti negdje u cache, a nakon toga kad krene mnozenje (ex: modelviewmatrix * obj.vertexArray), prefetch moze bez pardona samo kupiti vektore i pisati ih na cache. Umjesto da idlea jer nema podataka, CPU ce doslovce svaki takt odraditi sve cetiri faze pipelinea.

Pritom, imaj na umu takodjer da procesor ne poznaje pointer kao specijalni tip podatka. Iako korisni, pointeri nemaju sto traziti u optimiziranom kodu, zasto? Jer CPU mora prvo procitati pointer, a nakon toga ga dereferencirati.

Prakticno, ako mozes saznati velicinu svoje kolekcije unaprijed - prealociraj memoriju i napravi array, i ako treba fasadiraj ga s nekim custom templatiziranim vektorom - mislim da cak mozes koristiti i STL vector<> ako gurnes u template vlastiti alokator, jer default implementacija koristi copy constructor.

Isto dosta bitno, a vezuje se na prosli post o jumpovima je tipican 'isDirty' check koji ljudi znaju ugurati tu i tamo jer misle da pomaze.

Zabluda.

"isDirty" je jump, i moze bez pardona unistiti prefetch jer CPU ne moze zakljuciti da li su podaci dirty ili ne prije nego evaluira jump, i ako je pogrijesio u predikciji - dovidjenja do slijedeceg bus cyclea. Ako je taman pokupio instrukcije, i recimo da imas neki moderni procesor sa multiplierom ~20x (nemam dume koliko se multiplieri krecu danas :-)) - znaci da ce vec treci tick procesor odustati jer je krivo prediktirao instrukcije i ostalih 17 tickova ce idleati bez posla.

Danas ljudi ne mare previse za ovo, ali PowerPC-evi su, primjerice, bacali Exception kad bi podaci bili van alignmenta. PS3 ne baca exception, ali pravilno poravnavanje podataka i kolokacija cine razliku izmedju 12FPS-a i 60FPS-a. Zato devovi 'mrze' PS3, jer ne znaju efektivno iskoristiti njegov cell processor, a sve se vrti upravo oko ovih jednostavnih stvari. Uopce nije tesko izracunati alignment za faktor od 8 (ili 4 na 32bitnom procesoru) i dodati alignment u svoj datatip. Vec to ce pomoci oho-ho kod vecine aplikacija. Ako se radi serijska obrada podataka, dakle processing nad nekakvim arrayem ili kolekcijom - napisati alokator nije tako tesko a moze ubrzati stvar i do 30% bez izmjene algoritma!

BTW - sorry autoru na offtopic i na tldr. Nisam imao pojma u koju drugu temu staviti.

Koristeci hrvatske termine, definitivno cu shvatiti o cemu govoris :-P Govori engleski pal, so that the whole world understands ;-)

CPU instruction pipeline: http://en.wikipedia.org/wiki/Instruction_pipeline

Ne idem u arhitekturu CPU-a, vec samo u granicama kako maximalno iskoristiti moderni CPU. Dodaj ako imas stogod da sam propustio!

Btw - mozda da netko zatrazi mijenjanje naslova, jer smo ga debelo zaglavili u sasvim drugo podrucje.

Steta sto nema gorkya da nas malo poduci o ovome i da par VisualBasic primjera, kad smo svi neznalice.

Ma super je post! Nisam citao detalje o arhitekturi CPU-a valjda 10 godina... planiras biti CPU designer?

Apropos RISC-ova i CISC-ova: kao sto sigurno znas, razlikuju se samo u instruction setu (reduced vs. complex). No, ako izuzmes "velike" CPU-ove - vecina PIC-ova i AVR-ova danas su RISC procesori :-) Ali cuo sam da je neki link uspio scompilirati neki Linux micro kernel za ATmega16 :-)

To si ti kriv! Rekao si da se neces brinuti o alokacijama i vidi sta si izazvao!!! :-D

Ali zato sa tim ludim instrukcijama lijepo pomnozis dva vektora u jednom ticku :-) Mene to odusevljava, jos da vidis kako se razgalim kad vidim da mi je compiler sam to skuzio i scompilirao assembly koji to koristi :-)

Ovo zadnje, da vec nemam sign koji volim, evo ga :-D Rofl :-D

Nedostaje ti na popisu bivša Motorola (sadašnji Freescale) i njihov 68k (sada se prodaje pod raznim HC i HCS verzijama)?

Mislim da još uvijek prestižu i Atmel i Microchip po broju prodanih komada.

Tu je još i gomila manjih firmi koje modificiraju 8051/8052 (prije par godina sam radio nešto s jednom varijantom 8051 na 100MHz :D ).

Uz to dolaze još firme koje sada više-manje čine Renesas (Hitachi, Mitsubishi, NEC).

Kod nas nisu toliko poznati, jer su Atmel i Microchip bili dovoljno jeftini za hobi razvoj pa su zbog toga i popularni, ali NEC procesori i mikrokontroleri su također imali dobar dio tržišta.

Za razliku od Atmela i Microchipa, kod njih ima i nešto CISC jezgri u upotrebi.

Uređaji gdje se još radi CPU dizajn za manje količine su raznorazni ZigBee, XBee i slični radiokomunikacijski uređaji male snage.

Radio sam nedavno nešto s jednim koji je kao CPU imao neku od IP jezgri sa OpenCores stranice. :)

A što se tiče PIC-eva i AVR-ova, zadnji "mali" PIC-evi su oni iz PIC24 obitelji (16-bitna jezgra sa dodanim DSP ekstenzijama), a PIC32 ima MIPS jezgru.

Atmel je napravio svoj AVR32 i kao i za PIC32, osim naziva firme to više nema veze s onim 8-bitašima.

Mikrokontroleri danas uglavnom koriste Harvard arhitekturu, ali donedavno najpopularniji ARM za embedded tržište (ARM7TDMI) je rađen po von Neumann-ovoj.

Ovo je sada debeli oftopik.

Ne razumijem bas teoriju?

Jel ideja ta da su sanse da pogodis 50/50, pa ako duplas ulog, eventually ces naletjeti na pogodak i tako otplatiti gubitak?

S obzirom da šanse nisu 50-50, uzalud ti trud :)

Pa ono, ako cemo uzeti u obzir zakon velikih brojeva u teoriji vjerojatnosti koji kaze da kod velikog broja npr. bacanja novcica omjer izmedu pojavljivanja glave i pisma ce teziti jednakom broju. Taj veliki broj bacanja je kad bacanja teze u beskonacnost :D, pa stoga sumnjam da Sum ima vremena igrati rulet u beskonacnost, stoga da, kuca ipak dobiva :P

Vjerojatnosti inace imaju veliku ulogu u kvantnoj mehanici, stvari zbilja postaju zanimljive kad se malo ude u dubinu. Iako strasno neintuitivne i zbrkane.

Krivo si shvatio. Nema veze novcic, primjer s novcicem je tek to, primjer.

Ovisi kako su ta polja na ruletu rasporedena, nisam se nikad zanimao za rulet pa ne znam. Ali po ovoj slici sto si stavio, moze se izracunati vjerojatnost da kuglica padne u zeleno podrucje ili da padne u crveno ili u neko od ova dva bijela, ili kak to vec ide. Kad bi igrali jako puno igara (ali bez nekakve manipulacije, da sloze mehanizam tako da se jedna vrijednost dobiva vise od druge i sl.), dobili bi upravo rezultate koje smo izracunali. Prema tom zakonu, jel.

Ali to ne znaci odigrati 5, 10, 20 igara. To nije velik broj. Mozda oko tisucu odigranih, par tisuca ili cak par stotina tisuca i onda ces poceti primjecivati u svoj toj masi igara da se pojavljuje "pravilnost" koju smo izracunali.

Same here.

Ionako je offtopic.