diff options
Diffstat (limited to 'ocaml/lib')
| -rw-r--r-- | ocaml/lib/nock.ml | 3 | ||||
| -rw-r--r-- | ocaml/lib/noun.ml | 54 |
2 files changed, 53 insertions, 4 deletions
diff --git a/ocaml/lib/nock.ml b/ocaml/lib/nock.ml index 2f52922..ac6a2ad 100644 --- a/ocaml/lib/nock.ml +++ b/ocaml/lib/nock.ml @@ -28,7 +28,8 @@ open Noun let call_count = ref 0 let depth = ref 0 let max_calls = 100 -let max_mug_depth = -1 (* Disabled: need mug caching like C before enabling *) +let max_mug_depth = -1 (* Disabled: even cached, initial mug of huge ivory pill is slow *) +(* TODO: Enable selectively after verifying structural correctness *) (* Helper to generate indentation based on depth *) let indent () = diff --git a/ocaml/lib/noun.ml b/ocaml/lib/noun.ml index f706dca..b87aff5 100644 --- a/ocaml/lib/noun.ml +++ b/ocaml/lib/noun.ml @@ -86,15 +86,63 @@ let inc = function | Atom n -> Atom (Z.succ n) | Cell _ -> raise Exit -(** Compute mug (31-bit hash) of a noun +(** Mug cache using ephemeron (weak key-value table) + + This implements mug caching like C's u3 system: + - Uses physical equality (==) for lookups + - Weak keys allow GC to collect unused nouns + - Values (mugs) are int32, no GC needed + - Dramatically improves performance for repeated mug calls +*) +module MugCache = struct + (* Ephemeron table: weak keys, strong values *) + module E = Ephemeron.K1.Make(struct + type t = noun + let equal = (==) (* Physical equality - same noun object *) + let hash = Hashtbl.hash (* OCaml's built-in structural hash *) + end) + + let cache : int32 E.t = E.create 10000 (* Initial size *) + let hit_count = ref 0 + let miss_count = ref 0 + + let find noun = + match E.find_opt cache noun with + | Some mug -> + hit_count := !hit_count + 1; + Some mug + | None -> + miss_count := !miss_count + 1; + None + + let add noun mug = E.add cache noun mug + + let stats () = + let total = !hit_count + !miss_count in + if total > 0 then + Printf.eprintf "[MugCache] hits=%d misses=%d (%.1f%% hit rate)\n%!" + !hit_count !miss_count + (100.0 *. float_of_int !hit_count /. float_of_int total) +end + +(** Compute mug (31-bit hash) of a noun with caching This implements Urbit's mug hash function using FNV-1a. - The mug is cached in the C implementation but we compute it fresh each time. + Mugs are cached to avoid recomputation (critical for performance). For atoms: hash the bytes of the integer representation For cells: mix the mugs of head and tail *) let rec mug noun = + (* Check cache first (MugCache.find updates hit/miss counts) *) + match MugCache.find noun with + | Some cached_mug -> cached_mug + | None -> + let computed_mug = compute_mug_uncached noun in + MugCache.add noun computed_mug; + computed_mug + +and compute_mug_uncached noun = (* FNV-1a constants - using hex to avoid signed int32 overflow *) let fnv_prime = 16777619l in let fnv_basis = 0x811c9dc5l in (* 2166136261 in decimal *) @@ -129,7 +177,7 @@ let rec mug noun = hash_bytes (Bytes.of_string bytes) | Cell (h, t) -> - (* Mix the mugs of head and tail *) + (* Mix the mugs of head and tail (recursively cached) *) let h_mug = mug h in let t_mug = mug t in mix_mugs h_mug t_mug |