Ca sa am un punct de referinta, o sa ma refer la un tabel cu porturile TCP si UDP. (64k entries fiecare)
Un tabel (array) ar fi unul dintre cele mai rapide, e O(1). Ideea este sa pot accesa cat se poate de rapid cateva elemente pe care nu o sa le cunosc pana la runtime (ie: chiar daca sunt doar cateva, nu stiu care acele cateva o sa fie). Chiar daca am un array continuu cu doar 3-4 elemente, worst-case inseamna sa parcurg 3 elemente, adica 3 jump-uri, e O(n).

O problema cu tabelul e ca prapadeste putina memorie. Intrebarea mea este legata de cache, si anume, daca am 3 elemente in 3 colturi diferite ale tabelului, atunci in cache o sa ajunga doar acele 3 zone, si nu tot tabelul, nu?

In alta ordine de idei, as putea sa folosesc cateva instructiuni ieftine in plus si sa compresez tabelul 4:1. In fiecare byte, am 4 grupe de cate 2 biti, unul pt TCP si celalalt pt UDP, adica 16kb in total, si nu e nevoie in plus decat de vre-un shift, fara jump, fara acces la memorie (lucreaza cu valoarea cititia deja in registru) fara nimica, deci aproape gratis; iar daca am un algoritm care trebuie sa treaca prin tot tabelul, atunci poate fi unrolled astfel incat citeste 32biti dintr-un foc, si face testul/actiunea/whatever de cate 8 ori unrolled.

Ce parere aveti?

Mai aveam o intrebare... m-am uitat peste headerul de hashmap din std, si am vazut ce e implementat ca vector pt keys + lista. Asta nu inseamna ca e defapt tot O(n), doar cu un access pattern mai eficient? (linear, fara jump-uri, fata de liste)

PS: complet offtopic, stie cineva -ca nu am gasit pe google- cum poti face ceva de genul mov es:[bx], ax in DOS/16bit/286? Pt ca sa citesc o valoare, sa schimb segmentul, scriu valoare, si schimb segmentul la loc, suna groaznic de incet.

Partea simpla intii: opcode-ul pentru mov es:[bx], ax este 268907 (in hex). 26 este prefixul cu care zici ca vrei sa folosesti "es", 89 e opcode-ul pentru mov mem16 <- reg16, 07 encodeaza ca vrei in [bx] din ax. Nu stiu cum convingi assembler-ul tau sa genereze chestia asta, fiecare are sintaxa lui.

Un hash map transforma o cautare liniara intr-un table look-up (urmat eventual de o cautare liniara scurta). Toata smecheria e ca ia chestii greu de comparat si care pot avea extrem de multe valori (string-uri, de exemplu) si le transforma in numere cu care poate indexa direct o tabela de cautare. De exemplu un string de 8 caractere ASCII are 18 miliarde de miliarde de valori posibile (ma rog, 7 milioane de miliarde daca iei doar caractere printabile), asa ca n-o sa poti sa le bagi pe toate intr-o tabela de cautare pe care s-o indexezi direct. Poti in schimb sa calculezi din orice string de intrare un numar intr-un anumit interval, sa spunem 0 .. 1023 (asta e hash-ul; o metoda banala ar fi sa aduni sau sa inmultesti octetii din string si sa faci un modulo, dar se poate mult mai bine). Acum tabela ta are 1024 de elemente (numite bucket-uri), asa ca poate incapea in RAM. In fiecare bucket ai o lista de string-uri, deoarece este posibil ca mai multe string-uri sa aiba acelasi hash.

Situatia cind mai multe string-uri ajung in acelasi bucket se numeste coliziune. In caz de coliziune trebuie sa faci o cautare liniara in lista de string-uri care genereaza hash-uri identice.

Ideea care face hash map-urile sa functioneze este ca, daca alegi o functie de hash buna, numarul coliziunilor este determinat de numarul de obiecte pe care le bagi in hash map, nu de valorile posibile ale chestiilor pe care le bagi (string-uri in exemplul de mai sus). Asta e foarte important. Daca urmeaza sa ai 100 de string-uri, o tabela cu 125 de bucket-uri si un hash bun inseamna ca sansele de a avea coliziuni sint foarte mici, deci toate cautarile tale vor fi O(1).

Probabilitatea de a avea coliziuni creste cind numarul de obiecte din map se apropie de numarul de bucket-uri si evident este imposibil sa NU dai de coliziuni cind ai mai multe obiecte decit bucket-uri. De aia toate implementarile de hash map care trebuie sa contina un numar necunoscut de obiecte se redimensioneaza atunci cind numarul de obiecte depaseste o proportie oarecare din numarul de bucket-uri (80%, de exemplu). Redimensionarea inseamna pur si simplu ca aloci mai multe bucket-uri, recalculezi hash-urile tuturor obiectelor prezente deja si le bagi in noile bucket-uri. Asta e banal deoarece de obicei se foloseste o functie de hash bine studiata (de exemplu Jenkins One-At-A-Time) si pentru hash-ul final se ia valoarea returnata de ea modulo numarul de bucket-uri. Cind se schimba numarul de bucket-uri nu trebuie sa faci nimic cu functia, modulo ala se ocupa.

Daca in cazul tau ai de cautat intr-o lista cu 5 numere (dintr-un domeniu de 64k valori posibile), probabil o cautare liniara va merge cel mai bine. Daca ai de cautat intr-o lista de 100 de numere, trebuie sa testezi intre un hash map si adresarea directa.

Cu adresarea directa, la asemenea raport de utilizare a tabelei (1:640), e posibil ca fiecare adresare sa fie un cache miss. Daca folosesti tabela intr-o bucla care nu necesita extrem de multa memorie pentru alte chestii, o sa ai miss-uri la prima tura si dupa aia va merge struna. Daca in schimb asta e o functie pe care o chemi din cind in cind, si intre apeluri se intimpla multe alte chestii care au treaba cu memoria, fiecare apel va fi un cache miss, deci fiecare lookup te va costa citeva sute de cicli.

Pentru ca hash map-ul sa fie mai rapid trebuie ca functia de hash sa dureze simtitor mai putin decit un cache miss (ceea ce e banal) si ca bucket-urile sa stea in hash. Avantajul e ca ai de tinut 120 de bucket-uri in hash, nu 64,000 de elemente, deci e mai probabil sa stea acolo. Chiar si asa, depinde de ce face restul programului, ca se poate sa-ti dea afara bucket-urile din cache din mai multe motive: aliasing (alte adrese de care are nevoie se mapeaza pe aceleasi cache line-uri) sau pur si simplu foloseste mai mult RAM decit ai cache, deci sigur o sa te dea afara.

E foarte greu de spus dinainte care o sa mearga mai bine (si imposibil cu informatiile pe care le-ai dat). Vestea buna e ca dureaza 10 minute sa implementezi un hash si sa vezi. Nu folosi chestia aia din STL din mai multe motive:

- nu e standard, fiecare implementare de STL o face cum vrea, o baga in ce namespace vrea (stdex vs. stdext vs. __gnu_cxx vs. ce li s-o mai nazari) si unele n-o au deloc.

- ca multe alte containere STL, face alocari de memorie in plus, ceea ce e incet si creste probabilitatea sa dai de miss-uri

- are o lista inlantuita in fiecare bucket, care aproape garanteaza miss-uri in caz de collision

Daca nu vrei sa scrii ceva de mina, poti folosi google hash map.

Acum despre asta:



Da, evident, dar vezi ca un cache line in zilele noastre e 64 de bytes. Procesorul aduce intotdeauna cite 64 de bytes din RAM, indiferent cit folosesti tu. Daca folosesti 2 (un short, pentru porturi cum ziceai) din aia 64, vei folosi 3% din banda disponibila cu RAM-ul.

LE: daca valorile alea ale tale nu sint cunoscute pina la runtime, dar sint fixe (sau aproape fixe) odata ce le cunosti, exista algoritmi (si cod pe net) care genereaza hash-uri perfecte, adica iti garanteaza ca n-o sa ai coliziuni. Problema e ca trebuie sa re-generezi tot hash-ul de fiecare data cind adaugi sau schimbi o valoare, si algoritmii astia pot fi destul de costisitori in functie de datele de intrare.

Uite ca darku nu e chiar atat de negru .

Doar o observatie despre cache as putea adauga.
In general, prima data cand procesorul are nevoie de o informatie dintr-o zona de memorie ne-cachata, se face fetch la o zona mai mare de RAM decat o linie de cache, in idea ca majoritatea datelor ce urmeaza sa fie accesate, vor fi, statistic vorbind, prezente in acea zona de memorie. Daca datele tale sunt la o mai mare distanta una fata de alta decat acel maximum de zona cachata, atunci ai cache-miss si suporti penalitatea asteptarii dupa un nou fetch de date din memoria principala.

Pe de alta parte nu sunt expert in procesoarele de ultima generatie asa ca s-ar putea sa gresesc.

Asa face, se cheama prefetch, dar nu se triggereaza imediat. In general se apuca sa faca asta dupa un numar de fetch-uri consecutive, si are grija si la directie, adica merge si daca accesezi un array de la coada la cap. Nu se apuca imediat pentru ca e foarte posibil ca programul sa nu vrea un array, asa ca banda aia consumata cu adusul liniilor in plus s-ar duce pe apa simbetei (si pentru ca nici n-ar sti in ce directie s-o ia, dintr-un singur fetch nu-si da seama daca o sa accesezi crescator sau descrescator). Oricum, mecanismul de prefetch difera de la un model de procesor la altul, asa ca detaliile nu-s foarte semnificative decit daca stii exact ca o sa rulezi pe un singur tip de procesor (de exemplu pe console). Semnificativ e ca exista acest mecanism si face ca accesul liniar la memorie sa fie eficient.

In SSE s-a bagat si o instructiune speciala pentru prefetch, in caz ca access pattern-ul tau e prea complicat ca sa se prinda procesorul de el. De exemplu daca stii ca peste un timp vei avea nevoie de niste date dintr-o anumita locatie, dar mai ai treaba pina atunci, faci un prefetch, care incepe tranzactia cu memoria "non-blocking". Procesorul continua sa execute ce mai aveai de facut si e posibil ca datele sa ajunga in cache pina la fecth-ul propriu-zis. Abuzul instructiunii duce, evident, la banda irosita, daca faci prefetch-uri pentru locatii pe care nu le vei folosi, sau intirzie alte tranzactii care-ti trebuie inaintea adresei la care ai facut prefetch. D-aia trebuie folosita cu grija. Uneori beneficiile nu-s asa de spectaculoase pe cit s-ar spera deoarece PC-urile sint out-of-order si continua sa execute ce se poate (si chiar ce nu se poate, speculativ) si dupa un acces care rezulta intr-un cache miss, pina vin datele alea. Pe platformele in-order (console) avantajele sint mai clare, atunci cind e facut corect.

Exista si instructiuni care iau datele direct din RAM si nu le pun in cache. Astea sint utile cind stii ca nu vei mai avea nevoie de datele alea (sau cel putin nu prea curind), cum ar fi cind copiezi memorie. Daca de exemplu copiezi un buffer de 8 mega, n-are rost sa poluezi tot cache-ul nici cu sursa, nici cu destinatia (si oricum nu incap).

Instructiunile de prefetch si stream se gasesc si ca intrinsici in compilatoarele din era noastra - http://msdn.microsoft.com/en-us/library/cyxt4d09 (VS.80).aspx.

De cele mai multe ori instructiunea fetch se utilizeaza cu scopul declarat de a incetini programul . Adica e mult mai eficient sa te bazezi pe cpu sa faca treaba buna. Doar asha daca e chiar uber special modul tau de a accesa memoria sau daca nu mai stii ce sa-i faci sa mearga mai repede un inner loop.

Multumesc Dark!

268907h a mers, in programul "debug" de sub DOS se scrie intr-un mod mai ciudat:

Imi accepta acest input insa nu l-am testat. (probabil merge)

Imi facusem o idee gresita despre ce face un hashmap, pt ca ma uitasem la implementarea dintr-o librarie opensource, care e defapt un array redimensionat dinamic ce compara string-uri cu hash in loc de direct, deci nu e hashmap deloc. Mai bine ma uit pe sparsehash-ul de la Google.

Cat despre cealalta problema, daca stiu ca am un numar mic mai mereu, pot sa alochez un array de sa zicem 10 elemente, si il redimensionez in cazul rar in care da peste. (care oricum ocupa cam pe atata memorie ca 5 elemente intr-o lista inlantuita, dar nu mai jump-uieste)

/edit: err, defapt mov [bx], ax
Da' chiar, de ce nu pot folosi altceva decat [bx] ca destinatie? Orice alteceva, ax, cx, dx, sp nu ma lasa...

In 16 biti poti folosi ca pointeri registrii "SI", "DI", "BP" si "BX" si combinatiile "BX+SI", "BX+DI", "BP+SI", "BP+DI" (eventual plus un numar pe 8 sau 16 biti). De exemplu:



Pentru detalii vezi tabela 2-1 din PDF-ul asta (pagina 36 in versiunea curenta, da' se schimba des).

In 32 de biti e mai multa libertate de expresie, poti sa folosesti orice registru vrei, poti sa-l si inmultesti cu 2, 4 sau 8, poti sa aduni ce vrei etc. (tabelele 2-2 si 2-3, acelasi PDF).

Multumesc de informatii si de link! E tot ce am nevoie!
(daca nu cumva stii de ce liniile pare si cele impare din CGA sunt in 2 bucati diferite de memorie...)

PS: misto cum ai pus "A.D." acolo in semnatura...

Pentru ca sa poti sa pictezi interlaced mai usor, probabil. Daca nu aveai timp sa pictezi tot ecranul intr-un frame, pictai doar liniile pare, dupa care frame-ul urmator pictai doar liniile impare. Daca nu erau separate ar fi trebuit sa topai prin RAM, ceea ce costa.

Nu stiu cit de mult a fost folosit feature-ul, din 5 minute de Google observ ca nu prea l-a iubit lumea.

Makes sense. Mi-a luat juma de ora sa descopar cum merge CGAul, ca e impartit asa jumi-jumate, si fiecare jumatate e aliniata la 8KB. (total 620x200 1bit) Nu am gasit aproape nimic pe Google.

Scriu un joculet cu 'debug' si cu foaia de hartie langa mine, fun in 640KB!