Alternativa basata sull'identità fisica a Hashtbl.hash

Question

Sto provando a ricavare un file Graphviz che descrive un valore strutturato. Questo è per scopi diagnostici, quindi voglio che il mio grafico rispecchi il più possibile la struttura reale nella memoria. Sto utilizzando il seguente per mappare i valori per i vertici graphviz modo che io possa riutilizzare un vertice quando un valore è dotato di due o più riferimenti in entrata:

let same = (==) 

module StateIdentity : Hashtbl.HashedType = struct 
    type t = R.meta_t state 
    let hash = Hashtbl.hash 
    let equal = same 
end 

module StateHashtbl = Hashtbl.Make (StateIdentity) 

La documentazione per Hashtbl.hash suggerisce che è adatto per l'uso sia quando StateIdentity.equal = (=) e quando StateIdentity.equal = (==) ma mi piacerebbe assicurarmi che l'accesso alla tabella hash sia il più vicino possibile a O (1), quindi preferisco non avere Hashtbl.hash un grafico di oggetti (potenzialmente grandi in questo caso) su ogni ricerca.

So che Ocaml sposta i riferimenti in giro, ma esiste un proxy O (1) per l'identità di riferimento disponibile in Ocaml?

La risposta a Hashtable of mutable variable in Ocaml non suggerisce.

Sono dispiaciuto di allegare numeri seriali agli stati, poiché si tratta di codice diagnostico, quindi qualsiasi errore che faccio è potenzialmente in grado di mascherare altri bug.

Answer 1

Se si utilizza la parola "oggetto" nel senso dei tipi di oggetto <...> di OCaml, è possibile utilizzare Oo.id per ottenere un'identità intera univoca per ogni istanza. Altrimenti la risposta a "c'è un proxy generale per l'identità del valore" è "no". In questo caso, il mio consiglio è di iniziare con Hashtbl.hash, valutare se si adatta alle tue necessità e comunque progettare la tua funzione di hashing.

È anche possibile giocare con Hashtbl.hash_param (vedere documentation) per ruotare la manopola sugli attraversamenti dei valori durante l'hashing. Tieni presente che il codice Hashtbl utilizza elenchi collegati per bucket di valori hash uguali, quindi avere molti conflitti di hash attiverà il comportamento di ricerca lineare. Potrebbe essere meglio passare ad altre implementazioni usando gli alberi di ricerca binari per i bucket di conflitto. Ma poi di nuovo, dovresti valutare la tua situazione prima di passare a soluzioni più complesse (e con prestazioni peggiori nelle "buone case").

Answer 2

Ho trovato molto difficile usare l'uguaglianza fisica per fare l'hashing. Certamente non puoi usare qualcosa come l'indirizzo del valore come chiave hash, perché (come dici tu) le cose vengono spostate da GC. Una volta che hai una chiave hash, sembra che tu possa usare l'uguaglianza fisica per fare confronti fino a quando i tuoi valori sono mutabili. Se i tuoi valori non sono mutabili, OCaml non garantisce molto sul significato di (==). In termini pratici, gli oggetti immutabili che sono uguali (=) possono teoricamente essere uniti in un singolo oggetto fisico se il compilatore o il runtime OCaml lo desiderano (o viceversa).

Quando lavoro tra le varie possibilità, di solito finisco per inserire un numero di sequenza nei miei valori quando ho bisogno di un ID univoco. Come dice gasche, puoi usare Oo.id se i tuoi valori sono oggetti stile OO effettivi.

Answer 3

Come altri, penso che ID univoci siano la strada da percorrere.

Gli ID univoci non sono difficili da generare in modo sicuro. Una soluzione consiste nell'utilizzare un cosiddetto record privato come segue. Esso impedisce agli utenti del modulo di copiare il campo ID:

 
module type Intf = 
sig 
    type t = private { 
    id : int; 
    foo : string; 
    } 

    val create_t : foo: string -> t 
end 

module Impl : Intf = 
struct 
    type t = { 
    id : int; 
    foo : string; 
    } 

    let create_id = 
    let n = ref 0 in 
    fun() -> 
     if !n = -1 then 
     failwith "Out of unique IDs" 
     else (
     incr n; 
     !n 
    ) 

    let create_t ~foo = { 
    id = create_id(); 
    foo 
    } 
end 

Answer 4

Ci scusiamo per il brutto hack, ma ho fatto qualcosa di simile qualche tempo fa.

Il trucco è garantire che i valori non vengano spostati in memoria dopo l'inserimento nella tabella.Esistono due situazioni in cui è possibile spostare i valori nella memoria: copia dal minore all'heap principale e alla compattazione dell'heap principale. Ciò significa che quando si inserisce un valore nella tabella, deve trovarsi nell'heap principale e tra due operazioni sulla tabella è necessario assicurarsi che non si sia verificata alcuna compattazione.

Controllare che il valore sia nell'heap secondario può essere eseguito utilizzando la funzione C is_young, se è il caso, è possibile forzare il valore a migrare all'heap principale utilizzando Gc.minor().

Per il secondo problema, è possibile disattivare completamente le compazioni o ricostruire la tabella sulle compattazioni. Disabilitarlo può essere fatto utilizzando

Gc.set { Gc.get() with Gc.max_overhead = max_int } 

Rilevare che un compattamento è accaduto può essere fatto confrontando ad ogni accesso alla tabella il numero restituito da

(Gc.quick_stat()).Gc.compactions 

Si noti che è necessario essere disattivare la compattazione prima di accedere la tavola. Se si disabilita la compattazione, si dovrebbe anche considerare di cambiare la politica di allocazione per evitare la frammentazione illimitata dell'heap.

Gc.set {(Gc.get()) with Gc.allocation_policy = 1} 

Se volete qualcosa di veramente brutto in vecchie versioni di OCaml (prima 4,00) la compattazione mantenuto il valore nello stesso ordine in memoria, così si potrebbe implementare un set o una mappa in base all'indirizzo fisico senza preoccuparsi.