sostituzione .net dizionario

Question

Given (descrizione semplificata)

Uno dei nostri servizi ha un sacco di istanze in memoria. Circa l'85% sono unici. Abbiamo bisogno di un molto veloce accesso basato su chiave a questi elementi come sono interrogati molto spesso in una singola pila/chiamata. Questo contesto unico è estremamente ottimizzato per le prestazioni.

Così abbiamo iniziato a inserirli in un dizionario. La performance è stata ok.

L'accesso agli articoli il più velocemente possibile è la cosa più importante in questo caso. Si garantisce che non ci siano operazioni di scrittura quando si verificano letture.

Problema

Nel frattempo abbiamo raggiunto i limiti del numero di elementi di un dizionario in grado di memorizzare.

Die Arraydimensionen haben den unterstützten Bereich überschritten. 
    bei System.Collections.Generic.Dictionary`2.Resize(Int32 newSize, Boolean forceNewHashCodes) 
    bei System.Collections.Generic.Dictionary`2.Insert(TKey key, TValue value, Boolean add) 

che si traduce in The array dimensions have exceeded the supported range.

Soluzioni come Memcached sono in questo caso specifico troppo lente. È un caso d'uso isolato molto specifico incapsulato in un singolo servizio

Quindi stiamo cercando una sostituzione del dizionario per questo specifico scenario.

Attualmente non riesco a trovarne uno che supporti questo. Mi sto perdendo qualcosa? Qualcuno può indicarmi uno?

In alternativa, se non ne esiste nessuno, stiamo pensando di implementarne uno da soli.

Abbiamo pensato a due possibilità. Costruiscila da zero o avvolgendo più dizionari.

Wrapping dizionari multipli

Quando un elemento viene cercato potremmo avere uno sguardo alla chiavi HasCode e utilizzare il suo numero di partenza come un indice per un elenco di involucri dizionari. Anche se questo sembra essere facile mi odora e significherebbe che l'hashcode viene calcolato due volte (una volta da noi una sola volta dal dizionario interno) (questo scenario è davvero molto performante).

So che scambiare un tipo di base come il dizionario è l'ultima possibilità assoluta e voglio evitarlo. Ma al momento sembra che non ci sia modo di rendere gli oggetti più unici o di ottenere le prestazioni di un dizionario da un database o di salvare le prestazioni da qualche altra parte.

Sono anche consapevole di "essere consapevoli delle ottimizzazioni", ma una prestazione inferiore avrebbe colpito molto seriamente i requisiti aziendali.

Answer 1

Prima di finire di leggere le vostre domande, mi sono venuti in mente i semplici dizionari multipli. Ma tu conosci già questa soluzione. Suppongo che tu stia davvero colpendo il numero massimo di elementi in un dizionario, non altri limiti.

Direi di provarci. Non penso che dovresti preoccuparti di contare un hash due volte.Se le chiavi sono in qualche modo lunghe e ottenere l'hash è un'operazione che richiede molto tempo (che dubito, ma non posso essere sicuro siccome non hai menzionato quali sono le chiavi), non hai bisogno di usare chiavi intere per la tua funzione hash . Prendi solo la parte che stai per elaborare nel tuo hashing e distribuisci l'articolo in base a ciò.

L'unica cosa che è necessario assicurarsi qui è di avere una distribuzione uniforme di elementi tra i tuoi dizionari multipli. Quanto è difficile ottenere questo dipende davvero dalle tue chiavi. Se fossero numeri completamente casuali, potresti semplicemente usare il primo byte e andrebbe bene (a meno che tu non abbia bisogno di più di 256 dizionari). Se non sono numeri casuali, devi pensare alla distribuzione nel loro dominio e codificare la tua prima funzione hash in modo tale da raggiungere l'obiettivo di una distribuzione uniforme.

Answer 2

Ho esaminato l'implementazione di .Net Dictionary e sembra che dovresti essere in grado di memorizzare 2^32 valori nel dizionario. (Accanto all'elenco di bucket, che sono essi stessi elenchi collegati, c'è un singolo array che memorizza tutti gli elementi, probabilmente per una rapida iterazione, che potrebbe essere il fattore limitante).

Se non sono stati aggiunti i valori 2^32, è possibile che vi sia un limite sugli elementi in un bucket (è un elenco collegato, quindi è probabilmente limitato alla dimensione massima dello stack frame). In tal caso, dovresti ricontrollare che la tua funzione di hashing diffonde gli articoli in modo uniforme sul dizionario. Vedere questa risposta per maggiori informazioni What is the best algorithm for an overridden System.Object.GetHashCode?