Esiste un'espressione delle prestazioni per un algoritmo o una struttura dati che tenta di considerare la cache e altri problemi relativi all'hardware?
Contesto: nella mia classe stiamo osservando gli alberi binari e sembra che sarebbe estremamente difficile ottimizzare il recupero dei dati con la struttura. So che B-Trees risolve questo problema, ma non ho visto un'analisi formale di quanto sia migliorata la velocità considerando una certa quantità di cache.
Non l'ho mai applicato per dimostrare rigorosamente il costo di qualche algoritmo o struttura dati, ma credo che quello che stai cercando sia Modello di cache idealizzato . L'idea è di eseguire un'analisi Big O in cui il costo è il numero di trasferimenti di blocchi della cache anziché le istruzioni della macchina atomica. Per esempio. Attraversare un array sotto quel modello è O(n/B) dove n è il numero di elementi e B è la dimensione del blocco di cache. (Tecnicamente n è il numero di byte occupati dagli elementi dell'array, ma la differenza tra quello e il numero di elementi è un fattore costante, che la notazione di Big O ignora).
Potresti leggere il documento Algoritmi funzionali efficienti per la cache , che applica questo tipo di analisi nel contesto di un linguaggio puramente funzionale. Sono sicuro che ci sono molti altri documenti; Le strutture e gli algoritmi di dati cache-efficient e cache-oblivious sono un argomento di ricerca attivo.
In una lingua con un garbage collector generazionale si fa uso dell'euristica che le cose che sono allocate sequenzialmente nel tempo finiranno generalmente adiacenti nella memoria. La ragione di ciò è che i garbage collector generazionali di solito allocano sequenzialmente nella generazione più giovane, e quando accade una collezione gli oggetti live saranno compattati e probabilmente spostati anche a una generazione più anziana. Quando ciò accade, il grafico degli oggetti sarà generalmente attraversato in ordine di profondità prima o larghezza, ma in entrambi i casi gli oggetti finiranno adiacenti ad altri oggetti a cui puntano.
Se il garbage collector della tua lingua non è generazionale e non è in movimento / copia / compattazione non so cosa faresti, ma le tue prestazioni sono probabilmente sbagliate in entrambi i modi poiché la tua memoria è frammentata.
Sugli alberi soggetti all'efficienza della cache, potresti leggere Migliorare le prestazioni degli alberi RRB attraverso Transience che parla di un vettore / elenco implementazione utilizzando alberi i cui nodi hanno 31 o 32 bambini ciascuno.
Che tipo di analisi formale intendi? Se osservi Notazione Big O , la complessità non cambia quando cambi un fattore costante. Quello che intendo è: una cache può essere più veloce della RAM, ma ciò non cambia la tua complessità da O (n) a O (log n).
Penso che il problema è che cose come l'ottimizzazione della cache dipendono così tanto dall'hardware specifico che un'analisi formale non è veramente utile.
Leggi altre domande sui tag runtime algorithms algorithm-analysis