diff options
| -rw-r--r-- | ocaml/lib/nock.ml | 3 | ||||
| -rw-r--r-- | ocaml/lib/noun.ml | 54 | ||||
| -rw-r--r-- | ocaml/test/test_two_stage_boot.ml | 17 |
3 files changed, 67 insertions, 7 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 diff --git a/ocaml/test/test_two_stage_boot.ml b/ocaml/test/test_two_stage_boot.ml index da4f17b..62d262d 100644 --- a/ocaml/test/test_two_stage_boot.ml +++ b/ocaml/test/test_two_stage_boot.ml @@ -86,14 +86,25 @@ let stage1_ivory_boot env = (if Noun.is_cell poke_battery then "cell ✓" else "atom ✗") end; + (* Compute mugs of small sub-structures for verification *) + Printf.printf " Computing mugs of sub-structures:\n"; + let slot2_mug = Noun.mug slot2 in + let slot3_mug = Noun.mug slot3 in + let poke_mug = Noun.mug poke in + Printf.printf " Slot 2 mug: 0x%lx\n" slot2_mug; + Printf.printf " Slot 3 mug: 0x%lx\n" slot3_mug; + Printf.printf " Poke mug: 0x%lx\n" poke_mug; + Printf.printf "\n"; Printf.printf "╔═══════════════════════════════════════╗\n"; Printf.printf "║ ✓ STAGE 1 COMPLETE! ║\n"; Printf.printf "╚═══════════════════════════════════════╝\n\n"; - Printf.printf "⚠️ NOTE: Structural checks passed, but cannot verify\n"; - Printf.printf " kernels are identical without mug comparison.\n"; - Printf.printf " Need to implement mug caching first!\n\n"; + Printf.printf "⚠️ To verify correctness, compare these mugs with C:\n"; + Printf.printf " Run the C test and check if mugs match!\n\n"; + + (* Print cache stats *) + Noun.MugCache.stats (); Some kernel |