Sto cercando una struttura dati consapevole della cache che non richieda l'hashing. Questo per evitare HashDoS senza bisogno di usare PRF crittografici come SipHash, che sono lenti (~ 1 ciclo / byte) - Penso che si possa fare di meglio.
Finora, ho trovato HAT-try, radix try e Judy array.
- HAT-try richiede ancora l'hashing, quindi il problema si ripresenta.
- I tentativi di radix sono ancora più lenti delle tabelle hash a causa di uno scarso utilizzo delle cache della CPU.
- Gli array Judy sono veloci, ma sono enormemente complessi (20k SLOC in C) e l'unica implementazione che so accetta solo stringhe, array di byte e parole macchina come chiavi. Inoltre, le loro caratteristiche prestazionali non sono portabili: la stessa libreria che funziona in modo eccellente su sistemi con linee cache da 64 byte può avere prestazioni molto peggiori su sistemi con linee cache da 32 byte.
Nessuno di questi risolve il problema. La semplicità è importante, poiché sarà molto probabile che utilizzerò questa struttura dati in lingue diverse da C o Java e quindi dovrò essere in grado di implementarla in una nuova lingua in un ragionevole lasso di tempo.
Si può presumere che sia disponibile una fonte di numeri casuali crittograficamente sicuri con prestazioni ragionevoli.
Sono interessanti solo le strutture di dati che non sono gravate da brevetti.
Le chiavi e i valori devono essere trattati come opachi (tranne forse per le dimensioni): tutti gli accessi devono essere (o essere in grado di essere) tramite accessors definiti dall'utente.
