Hashtbl.hashへの物理的なIDベースの代替

Question

私は構造化された値を記述するGraphvizファイルを派生させようとしています。これは診断目的のためです。実際の構造を可能な限り密接にメモリに反映させたいのです。私は、値が2つの以上のインバウンドの参照を持っているとき、私は頂点を再利用できるように、Graphvizの頂点に値をマッピングするには、以下の使用しています：

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) 

Hashtbl.hashのドキュメントは、それが使用の両方 StateIdentity.equal = (=)に適していることを示唆している

StateIdentity.equal = (==)だが、ハッシュテーブルへのアクセスができるだけO（1）に近いことを確認したいので、すべてのルックアップで（おそらくこの場合は大きな）オブジェクトグラフを歩くことは避けたい。

私はOcamlの動きの参照を知っていますが、Ocamlで利用可能な参照IDのためのO（1）プロキシがありますか？

Hashtable of mutable variable in Ocamlへの回答は示唆していません。

これは診断コードなので、シリアル番号をステートに添付するのは嫌です。エラーが発生すると、他のバグを隠す可能性があります。

Answer 1

OCamlの<...>オブジェクトタイプの意味で「オブジェクト」という単語を使用している場合は、Oo.idを使用して、各インスタンスに対して一意の整数IDを取得できます。それ以外の場合は、「バリュー・アイデンティティのための一般的なプロキシがある」という答えは「いいえ」です。この場合、私の助言はHashtbl.hashで始まり、あなたの必要性に合っているかどうかを評価し、そうでない場合は独自のハッシュ関数を設計することです。

また、ハッシュ中に値のトラバーサルをオンにするには、Hashtbl.hash_param（documentationを参照）で再生することもできます。 Hashtblコードでは、同じハッシュ値のバケットにリンクリストを使用するため、ハッシュコンフリクトが多く発生するとリニアな検索動作がトリガーされることに注意してください。競合バケットのバイナリ検索ツリーを使用して他の実装に移行する方が良いかもしれません。しかし、もう一度、あなたの状況を評価してから、より複雑な（そして「良い場合」のパフォーマンスが悪化する）ソリューションに移行する必要があります。

Answer 2

ハッシュを行うために物理的な平等を使用することは非常に難しいと感じました。あなたは確かにあなたのハッシュキーと同じ値のアドレスのようなものを使うことはできません。なぜなら（あなたの言うように）物事はGCによって動き回るからです。いったんハッシュ・キーを取得すると、値が変更可能である限り、物理的な等価性を使って比較を行うことができるようです。値が変更可能でない場合、OCamlは（==）の意味をあまり保証しません。実際には、OCamlコンパイラやランタイムが望むなら、理論的に等しい（=）不変のオブジェクトを単一の物理オブジェクトにマージすることができます（またはその逆）。

私はいろいろな可能性を考えていますが、一意のIDが必要な場合は通常、シーケンス番号を自分の値に入れてしまいます。 gascheが言うように、あなたの値が実際のオブジェクト指向スタイルのオブジェクトである場合は、Oo.idを使用できます。

Answer 3

他の人と同じように、ユニークなIDがあると思います。

一意のIDは安全に生成するのが難しくありません。 1つの解決法は、以下のようにいわゆるプライベートレコードを使用することである。醜いハックのために申し訳ありません

 
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

を、私はいくつかの時間前のようなものを作った：それは、idフィールドをコピーからモジュールのユーザーを防ぎます。

これは、テーブルに挿入した後に値がメモリ内に移動しないようにすることです。メモリ内の値を移動できる状況は、マイナーからメジャーヒープへのコピーとメジャーヒープ圧縮です。これは、テーブルに値を挿入するときに、それがメジャーヒープになければならず、テーブル上の2つの操作の間に、コンパクションが発生していないことを確認する必要があることを意味します。

マイナーヒープに値があることを確認するには、C関数is_youngを使用します。この場合、Gc.minor（）を使用して値を強制的にメジャーヒープに移行できます。

第2の問題は、コンパクションを完全に無効にするか、コンパクション時にテーブルを再構築することです。それは圧縮が数が

(Gc.quick_stat()).Gc.compactions 

お知らせによって返されたテーブルに各ACCESで比較することによって行うことができるが起こったことを検出

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

使用して行うことができます無効にするとは、アクセスする前に圧縮を無効にする必要があり、そのテーブル。 圧縮を無効にする場合は、割り当てポリシーを変更して、ヒープの無制限の断片化を避けることも検討する必要があります。

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

あなたは気にせず、物理アドレスに基づいて、セットまたはマップを実装することができるように圧縮は、メモリ内の同じ順序で値を保持（4.00以前）のOCamlの古いバージョンでは本当に醜い何かをしたい場合。