Cache Oriented Design

theGiallo

Sì, è DOD, ma Cache Oriented Design mi piace di più.
SEO: Data Oriented Design
Relativo al post di @encelo ~~ora linko~~ http://forum.gameloop.it/d/10-alcuni-miei-appunti-di-studio/ .

Domanda scritta per @encelo ma diretta a chiunque.
Ho letto fino a "concurrency" il libro online dataorienteddesign, ho sfogliato le parti dopo e ho leggiucchiato la prima parte di bitsquid. avevo già visto un talk di acton e l'intervista handmadecon 2015 di acton. Hai qualche documento su implementazioni delle tabelle di cui parla dod? Bitsquid usa stl mi pare. Ho scritto una tabella generica non tipata con chiave l'id e N colonne ( che poi sono righe ( SoA ) ) di dimensioni arbitrarie. Per ora non ci ho messo una struttura per accelerare l'accesso. Ho solo una funzione per compattare la tabella e un bitvector per la presenza. Nel caso avessi ricerche solo in una fase senza inserimenti potrei ordinare la tabella e fare una ricerca in un array ordinato ( gli id stanno in un loro array ovviamente ). Altrimenti potrei avere una hash table con liste per cella o un b-tree. L'hash da calcolare sarebbe triviale, in quanto l'id è già random. Comunque bisognerebbe seguire dei puntatori, a memoria contigua certo, madovrei averne tanti e quindi sarebbe una bella zona di memoria. A parte tutte queste parole ovviamente il piano è di implementare entrambi e benchmarkare.

theGiallo

Che silenzio.

Ho implementato una hash table con storage fissato.
Il test che faccio:

ho la tabella con 1024*1024 di capacità
faccio 1M iterazioni e per ognuna scelgo
- con il 75% di probabilità di inserire un elemento nuovo
- con il 25% di cancellare un elemento inserito in precedenza, scelto a caso
ogni tot iterazioni compatto la tabella ( 1, 10k o 100k )
prendo i tempi delle varie funzioni della tabella (insert, remove e compact) e guardo il tempo medio. Sarebbe meglio guardare il tempo massimo, ma vabbe'.

Con l'hash table ora ho l'inserimento che ci mette circa 2500 cicli, remove 300, e compact 11/12M cicli. La frequenza di clock è 3.2GHz, quindi i tempi sono circa 0.00078ms per l'inserimento, 0.00009ms per la rimozione e 3.5ms per la compattazione. La compattazione non distrugge e ricrea la hash table, ma modifica i valori già presenti. Il problema è che per compattare una tabella con 500k elementi deve visitare un casino di memoria. La ricerca non è testata, ma dovrebbe essere molto simile alla rimozione.
Il codice si trova qua:

theGiallo

Non capisco come un albero potrebbe essere meglio di quella hash table. Bisognerebbe bilanciarlo e rincorrere puntatori circa log2(n) 😐 Mi sta passando la voglia di implementarlo, dannazione ^_^;

theGiallo

OK, ho macrofonato™ con @encelo e ha detto che non si capisce quello di cui sto scrivendo. Questo medium è obsoleto, servono immagini e suoni e tempo. Dovrei fare un videino spiegando e disegnando. Uploadarlo con la mia connessione potrebbe essere traumatico.