È una cache ( memoization ), quindi progettala come una cache.
One approach is to store a map inside the valuator.
Penso che questo sia l'approccio corretto, o almeno la prima scelta. Qualsiasi altro approccio avrebbe richiesto modifiche o allocazioni aggiuntive con Object . "Mappa" si riferisce al concetto generale che, data una "chiave" estratta da un "Oggetto", si può recuperare un "valore" memorizzato da qualche struttura dati.
Quando usi questo approccio, assicurati che ci sia una robusta "garbage collection" per rimuovere i dati memorizzati nella cache da ogni Processor per gli oggetti che non esistono più. In caso contrario, la cache verrà riempita con dati inutili. Questa è una forma di perdita di memoria / risorse.
In alcune situazioni, potrebbe essere necessario un approccio leggermente ibrido. Considerare il caso in cui non tutti gli oggetti hanno associato i dati memorizzati nella cache. Vorresti evitare una ricerca della mappa hash se non ci sarà. In questo caso, puoi utilizzare un singolo bit (flag) nell'oggetto per indicare l'esistenza di dati memorizzati nella cache in ogni Processor . Questo è un aumento più basso e più prevedibile delle dimensioni della memoria di Object . È conveniente riservare, ad esempio, un limite hard-coded di 64 bit (8 byte) in Object per questo scopo. Per esempio, vedi std::bitset (en.cppreference.com) .
Every time, an object is passed to foo, a look up is required that harms performance.
Risolvi i problemi di prestazioni; non rifiutare questo approccio.
Devi iniziare con ( std::unordered_map en.cppreference.com ). Se in precedenza hai utilizzato std::map , puoi passare a std::unordered_map e non devi preoccuparti del problema di prestazioni.
Se std::unordered_map non è abbastanza veloce, vorrai conoscere a fondo l'implementazione sottostante che stai utilizzando. Verifica se una ricerca è O(1) o O(log N) . Controlla la funzione hash. Controlla i tassi di collisione. Controlla come gestisce la collisione. Verifica i criteri che utilizza per crescere.
Dovrai imparare a leggere il codice di disassemblaggio compilato e utilizzare gli strumenti di profilatura della CPU (più correttamente campionamento della CPU ) per verificare se la mappa hash si qualifica come hotspot e merita le ottimizzazioni delle prestazioni Sei disposto a investire.
Se sei preoccupato per i problemi di localizzazione della cache della CPU, tieni presente quanto segue:
- Se gli oggetti
Object sono disposti sequenzialmente in memoria e sono accessibili in sequenza, e Processor visita anche oggetti nello stesso ordine sequenziale, puoi progettare la cache per disporre i dati memorizzati nella cache nello stesso ordine sequenziale come i tuoi oggetti. Qui è utile la personalizzazione della mappa di hash.
- Se uno dei precedenti non è vero, cioè non tutto è ordinato sequenzialmente, l'efficienza della cache sarà ridotta a "ciò che è popolare" (oggetti visitati più frequentemente di altri) e "ciò che è recente". Questo è il livello base di prestazioni che puoi aspettarti; non devi fare alcuna ottimizzazione del codice per raggiungere questo livello di prestazioni. Ottimizza solo all'interno di ciascun oggetto.