diff --git a/src/proto_alpha/lib_benchmarks_proto/interpreter_benchmarks.ml b/src/proto_alpha/lib_benchmarks_proto/interpreter_benchmarks.ml
index be44ccb10c423b99408b1fa5d6880834549c1d35..ca498837c1f077ff294e20edd57f581133702ba1 100644
--- a/src/proto_alpha/lib_benchmarks_proto/interpreter_benchmarks.ml
+++ b/src/proto_alpha/lib_benchmarks_proto/interpreter_benchmarks.ml
@@ -787,10 +787,10 @@ let alloc_benchmark_from_continuation :
       ~error:(fun _ -> 0.0)
       ~ok:(fun (stack_top, stack, _, _) ->
         let size_after =
-          Obj.reachable_words (Obj.repr (stack_top, stack, bef_top, bef))
+          Obj.reachable_words (Obj.repr (stack_top, stack, bef_top, bef, cont))
         in
         let size_before =
-          Obj.reachable_words (Obj.repr (bef_top, bef, bef_top, bef))
+          Obj.reachable_words (Obj.repr (bef_top, bef, bef_top, bef, cont))
         in
 
         float_of_int (size_after - size_before))
@@ -1699,6 +1699,25 @@ module Registration_section = struct
       in
       (key, map)
 
+    let generate_map_and_key_not_in_map (cfg : Default_config.config) rng_state
+        =
+      (* [adversarial_ints] could return a non-distinct list,
+         so the returned [key] may be bound in the [map] in a low probability. *)
+      let n =
+        Base_samplers.sample_in_interval rng_state ~range:cfg.sampler.set_size
+      in
+      let keys = adversarial_ints rng_state cfg n in
+      let key, keys =
+        match keys with [] -> assert false | x :: xs -> (x, xs)
+      in
+      let map =
+        List.fold_left
+          (fun map i -> Script_map.update i (Some ()) map)
+          (Script_map.empty int)
+          keys
+      in
+      (key, map)
+
     let () =
       simple_time_alloc_benchmark
         ~name:Interpreter_workload.N_IEmpty_map
@@ -1822,7 +1841,7 @@ module Registration_section = struct
           (let map = Script_map.empty int in
            (Script_int.zero, (None, (map, eos))))
         ~stack_sampler:(fun cfg rng_state () ->
-          let key, map = generate_map_and_key_in_map cfg rng_state in
+          let key, map = generate_map_and_key_not_in_map cfg rng_state in
           (key, (Some (), (map, eos))))
         ()
 
@@ -1841,7 +1860,7 @@ module Registration_section = struct
           (let map = Script_map.empty int in
            (Script_int.zero, (None, (map, eos))))
         ~stack_sampler:(fun cfg rng_state () ->
-          let key, map = generate_map_and_key_in_map cfg rng_state in
+          let key, map = generate_map_and_key_not_in_map cfg rng_state in
           (key, (Some (), (map, eos))))
         ()
 
@@ -1870,16 +1889,8 @@ module Registration_section = struct
         Base_samplers.sample_in_interval rng_state ~range:cfg.sampler.set_size
       in
       let keys = adversarial_ints rng_state cfg n in
-      let map =
-        List.fold_left
-          (fun map i -> Script_map.update i (Some (Some ())) map)
-          (Script_map.empty int)
-          keys
-      in
-      let (module M) = Script_map.get_module map in
-      let key =
-        M.OPS.fold (fun k _ -> function None -> Some k | x -> x) M.boxed None
-        |> WithExceptions.Option.get ~loc:__LOC__
+      let key, keys =
+        match keys with [] -> assert false | hd :: tl -> (hd, tl)
       in
       let big_map =
         raise_if_error
@@ -1888,12 +1899,11 @@ module Registration_section = struct
               let big_map = Script_big_map.empty int unit_t in
               let* big_map, _ =
                 let*! result =
-                  Script_map.fold
-                    (fun k v acc ->
-                      let* bm, ctxt_acc = acc in
-                      Script_big_map.update ctxt_acc k v bm)
-                    map
-                    (return (big_map, ctxt))
+                  List.fold_left_es
+                    (fun (bm, ctxt_acc) k ->
+                      Script_big_map.update ctxt_acc k (Some ()) bm)
+                    (big_map, ctxt)
+                    keys
                 in
                 Lwt.return (Environment.wrap_tzresult result)
               in
@@ -4141,7 +4151,7 @@ module Registration_section = struct
           let kbody = ICdr (dummy_loc, halt) in
           fun () ->
             let ty = map int unit in
-            let key, map = Maps.generate_map_and_key_in_map cfg rng_state in
+            let key, map = Maps.generate_map_and_key_not_in_map cfg rng_state in
             let cont = KMap_exit_body (kbody, [], map, key, Some ty, KNil) in
             Ex_stack_and_cont
               {stack = ((), ((), eos)); stack_type = unit @$ unit @$ bot; cont})
diff --git a/src/proto_alpha/lib_benchmarks_proto/interpreter_model.ml b/src/proto_alpha/lib_benchmarks_proto/interpreter_model.ml
index 5d1fb41131386c78059269aee69cda3589754ede..92ef50daec8742132f14db3e97dcf93b158dab69 100644
--- a/src/proto_alpha/lib_benchmarks_proto/interpreter_model.ml
+++ b/src/proto_alpha/lib_benchmarks_proto/interpreter_model.ml
@@ -750,7 +750,7 @@ let ir_model instr_or_cont =
           (list_enter_body_model, list_enter_body_model) |> m2 name
       | N_KList_exit_body -> (const1_model, const1_model) |> m2 name
       | N_KMap_enter_body -> (empty_branch_model, empty_branch_model) |> m2 name
-      | N_KMap_exit_body -> (nlogm_model, nlogm_model) |> m2 name
+      | N_KMap_exit_body -> (nlogm_model, update_alloc_model) |> m2 name
       | N_KLog -> (const1_model, const1_model) |> m2 name)
 
 let gas_unit_per_allocation_word = 4