Repository: stellar/rs-soroban-env
Pull request #561 (2022-11-03 21:13:00)

Restructure benchmark framework, add calibration code for all `CostType`s.
### What

**Restructure the bench framework.** 
This PR splits the previous `HostCostMeasurement` into two places:
1. `soroban-env-host/src/cost_runner`: contains the runner of each cost type, as well as the structural definitions of the sample data. 
2. `soroban-env-host/benches`: contains the data generator for each cost type. 
Information dependency goes from 2-->1 but not the other way around. 

**Implement calibration for basically all cost types.** Except a few, see limitations. 

**Cleaned up, consolidated, and reindexed `CostType`.** 
See "Why" section for which types were removed and the reasoning. 

### Why
The main reason for the restructuring to run non-public functions in the host for calibration.
The current calibration/benchmark framework consist of roughly three parts:
1. Generation of data, whose structure requirement is defined by a particular cost type. 
2. The bench harness, dispatchers for kicking off a measurement for a (bench type, cost type, iteration) combination. 
3. Running a cost entity in the host. 
 
Previously all these sit with the "benches", which is outside of the host crate.  However, the host runner should belong to the host, since it needs access to the (non-public) host components. Same for the data structural definitions.

Removed `CostType`s:
- `*AllocCell`: such as `HostVecAllocCell`. The cost of adding a host object has already been covered by `HostObjAllocSlot` , and the cost of producing a particular host object has been covered elsewhere. 
- `BytesSlice`: this is essentially cloning, covered by `BytesClone`
- `BytesConcat`: covered by `BytesAppend`
- `PushFrame` and `PopFrame`: too granular. The cost of frame pushing and popping has been covered by `GuardFrame`, and push/pop are always paird. 
- `CallArgsUnpack`: this is too granular. The work of converting a guest function call argument from `ScVal` to a `RawVal` has been covered elsewhere. This operation just collects `RawVal`s into a `Vec`. 
- `CloneVm`: this is just a `Rc` clone, should be free. 

### Known limitations
Several types were not calibrated because we need to know the size limits of its data, in order to approximate the cost with a constant (upper bound) cost term:
- `CloneEvents`
- `ScVecFromHostVec`
- `ScMapFromHostMap`
- Storage related: need to know the size limit of keys which are LedgerKeys


jayz22: @graydon I pushed another change to construct and pass in `Vec<SampleType>` instead of `&mut SampleType` to the runner. Mainly because we want to remove internal cloning from the measurements. Now it constructs a vector by cloning sample data from the outside and then passes it into the runner to run the host, without accounting for sample cloning. 

During this change I discovered an issue. Previously the the mem_tracker start happened right before calling the `HCM::run`, and it was underflowing the `AtomicU64` counter after I made the above switch. I believe it's because the memory deallocation of the sample data container was being counted while the allocation (which happens before the tracker started) was not. I moved that call before the data setup, and it seem to give the correct results. I've left a comment in the code. Please let me know if my assessment is correct and if there is a better pattern to solve such issue (rearranging the code this way feels too subtle and error-prone). 
jayz22: > @graydon I pushed another change to construct and pass in `Vec<SampleType>` instead of `&mut SampleType` to the runner. Mainly because we want to remove internal cloning from the measurements. Now it constructs a vector by cloning sample data from the outside and then passes it into the runner to run the host, without accounting for sample cloning.
> 
> During this change I discovered an issue. Previously the the mem_tracker start happened right before calling the `HCM::run`, and it was underflowing the `AtomicU64` counter after I made the above switch. I believe it's because the memory deallocation of the sample data container was being counted while the allocation (which happens before the tracker started) was not. I moved that call before the data setup, and it seem to give the correct results. I've left a comment in the code. Please let me know if my assessment is correct and if there is a better pattern to solve such issue (rearranging the code this way feels too subtle and error-prone).

Addressed in https://github.com/stellar/rs-soroban-env/pull/561#discussion_r1019815009

Patch:
diff --git a/Cargo.lock b/Cargo.lock
index e5dfb953..4606b05f 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -1099,6 +1099,7 @@ dependencies = [
  "thousands",
  "tinyvec",
  "tracking-allocator",
+ "wasmprinter",
 ]
 
 [[package]]
diff --git a/soroban-env-common/src/env.rs b/soroban-env-common/src/env.rs
index 01526b37..4c42c11f 100644
--- a/soroban-env-common/src/env.rs
+++ b/soroban-env-common/src/env.rs
@@ -481,6 +481,13 @@ macro_rules! call_macro_with_all_host_functions {
                 /// it exists. Returns (SCStatic) TRUE/FALSE.
                 {"3", fn account_exists(a:Object) -> RawVal}
             }
+
+            mod test "t" {
+                /// A dummy function taking 0 arguments and performs no-op.
+                /// This function is for test purpose only, for measuring the roundtrip cost of
+                /// invoking a host function, i.e. host->Vm->host.
+                {"_", fn dummy0() -> RawVal}
+            }
         }
     };
 }
diff --git a/soroban-env-common/src/meta.rs b/soroban-env-common/src/meta.rs
index 8a4fc1a2..e1d58a7d 100644
--- a/soroban-env-common/src/meta.rs
+++ b/soroban-env-common/src/meta.rs
@@ -58,5 +58,5 @@
 pub const ENV_META_V0_SECTION_NAME: &'static str = "contractenvmetav0";
 
 soroban_env_macros::generate_env_meta_consts!(
-    interface_version: 23,
+    interface_version: 24,
 );
diff --git a/soroban-env-host/Cargo.toml b/soroban-env-host/Cargo.toml
index cd2ff9fc..94aec0b8 100644
--- a/soroban-env-host/Cargo.toml
+++ b/soroban-env-host/Cargo.toml
@@ -12,13 +12,15 @@ rust-version = "1.65"
 
 [dependencies]
 soroban-native-sdk-macros = { workspace = true }
-soroban-env-common = { workspace = true, features = [ "std" ] }
+soroban-env-common = { workspace = true, features = ["std"] }
 wasmi = { workspace = true, optional = true }
 static_assertions = "1.1.0"
 im-rc = "15.0.0"
 num-bigint = "0.4"
 sha2 = "0.10.2"
 ed25519-dalek = "1.0.1"
+# NB: this must match the same curve25519 version used by ed25519-dalek above
+curve25519-dalek = "3.0.0"
 hex = "0.4.3"
 num-traits = "0.2.15"
 num-integer = "0.1.45"
@@ -40,8 +42,8 @@ rand = "0.7.3"
 soroban-test-wasms = { package = "soroban-test-wasms", path = "../soroban-test-wasms" }
 soroban-synth-wasm = { package = "soroban-synth-wasm", path = "../soroban-synth-wasm" }
 bytes-lit = "0.0.4"
-curve25519-dalek = "3.2.1"
 textplots = "0.8.0"
+wasmprinter = "0.2.41"
 
 [features]
 vm = ["wasmi", "soroban-env-common/vm"]
diff --git a/soroban-env-host/benches/common/cost_types/bigint_div_rem.rs b/soroban-env-host/benches/common/cost_types/bigint_div_rem.rs
deleted file mode 100644
index d3d10c7b..00000000
--- a/soroban-env-host/benches/common/cost_types/bigint_div_rem.rs
+++ /dev/null
@@ -1,62 +0,0 @@
-use crate::common::HostCostMeasurement;
-use num_bigint::{BigInt, Sign};
-use num_integer::Integer;
-use rand::{rngs::StdRng, Rng};
-use soroban_env_host::{budget::CostType, Host};
-
-pub(crate) struct BigIntDivRemRun {
-    a: BigInt,
-    b: BigInt,
-    input: u64,
-}
-
-// This measures the costs of doing div_rem on the bigint type. The input value
-// is the number of bits. The underlying code is variable-time in the bit size,
-// but we expect that by bounding the bit size we can make a reasonably tight
-// constant or linear-function upper bound. Examine the table and histogram.
-impl HostCostMeasurement for BigIntDivRemRun {
-    const COST_TYPE: CostType = CostType::BigIntDivRem;
-    const RUN_ITERATIONS: u64 = 100;
-
-    fn new_best_case(_host: &Host, _rng: &mut StdRng) -> Self {
-        let a: BigInt = 1u64.into();
-        let b: BigInt = 1u64.into();
-        Self { a, b, input: 1 }
-    }
-
-    fn new_worst_case(_host: &Host, _rng: &mut StdRng, input: u64) -> Self {
-        let input = input * 256;
-        fn repeating_byte_bigint(byte: u8, input: u64) -> BigInt {
-            let buf: Vec<u8> = (0..input / 8).map(|_| byte).collect();
-            let a = BigInt::from_bytes_be(Sign::Plus, &buf);
-            let one: BigInt = 1.into();
-            a + one
-        }
-        // TODO: unclear if this really represents "worst case", it's
-        // just a guess.
-        let a: BigInt = repeating_byte_bigint(0xf7, input);
-        let b: BigInt = repeating_byte_bigint(0xf6, 1 + (input / 2));
-        Self { a, b, input }
-    }
-
-    fn new_random_case(_host: &Host, rng: &mut StdRng, input: u64) -> Self {
-        let input = input * 256;
-        fn random_bigint(rng: &mut StdRng, input: u64) -> BigInt {
-            let buf: Vec<u8> = (0..input / 8).map(|_| rng.gen::<u8>()).collect();
-            let a = BigInt::from_bytes_be(Sign::Plus, &buf);
-            let one: BigInt = 1.into();
-            a + one
-        }
-        let a: BigInt = random_bigint(rng, input);
-        let b: BigInt = random_bigint(rng, input);
-        Self { a, b, input }
-    }
-
-    fn get_input(&self, _host: &Host) -> u64 {
-        self.input
-    }
-
-    fn run(&mut self, _iter: u64, _host: &Host) {
-        self.a.div_rem(&self.b);
-    }
-}
diff --git a/soroban-env-host/benches/common/cost_types/bigint_ops.rs b/soroban-env-host/benches/common/cost_types/bigint_ops.rs
new file mode 100644
index 00000000..903e3cee
--- /dev/null
+++ b/soroban-env-host/benches/common/cost_types/bigint_ops.rs
@@ -0,0 +1,275 @@
+use crate::common::{util, HostCostMeasurement};
+use num_bigint::BigInt;
+use rand::{rngs::StdRng, Rng, RngCore};
+use soroban_env_host::{cost_runner::*, Host, MeteredBigInt};
+
+pub(crate) struct BigIntNewMeasure;
+impl HostCostMeasurement for BigIntNewMeasure {
+    type Runner = BigIntNewRun;
+
+    fn new_random_case(_host: &Host, rng: &mut StdRng, _input: u64) -> u64 {
+        rng.next_u64()
+    }
+}
+
+pub(crate) struct BigIntAddSubMeasure;
+impl HostCostMeasurement for BigIntAddSubMeasure {
+    type Runner = BigIntAddSubRun;
+
+    fn new_best_case(host: &Host, _rng: &mut StdRng) -> (MeteredBigInt, MeteredBigInt) {
+        let a = MeteredBigInt::from_u64(host.budget_cloned(), 1).unwrap();
+        let b = MeteredBigInt::from_u64(host.budget_cloned(), 1).unwrap();
+        (a, b)
+    }
+
+    fn new_worst_case(
+        host: &Host,
+        _rng: &mut StdRng,
+        input: u64,
+    ) -> (MeteredBigInt, MeteredBigInt) {
+        let input = input * 256;
+        // TODO: unclear if this really represents "worst case", it's
+        // just a guess.
+        let a: BigInt = util::repeating_byte_bigint(0xf7, input);
+        let b: BigInt = util::repeating_byte_bigint(0xf7, input);
+        (
+            MeteredBigInt::from_bigint(host.budget_cloned(), a),
+            MeteredBigInt::from_bigint(host.budget_cloned(), b),
+        )
+    }
+
+    fn new_random_case(
+        host: &Host,
+        rng: &mut StdRng,
+        input: u64,
+    ) -> (MeteredBigInt, MeteredBigInt) {
+        let input = input * 256;
+        let a: BigInt = util::random_bigint(rng, input);
+        let b: BigInt = util::random_bigint(rng, input);
+        (
+            MeteredBigInt::from_bigint(host.budget_cloned(), a),
+            MeteredBigInt::from_bigint(host.budget_cloned(), b),
+        )
+    }
+}
+
+pub(crate) struct BigIntMulMeasure;
+impl HostCostMeasurement for BigIntMulMeasure {
+    type Runner = BigIntMulRun;
+
+    fn new_best_case(host: &Host, rng: &mut StdRng) -> (MeteredBigInt, MeteredBigInt) {
+        BigIntAddSubMeasure::new_best_case(host, rng)
+    }
+
+    fn new_worst_case(host: &Host, rng: &mut StdRng, input: u64) -> (MeteredBigInt, MeteredBigInt) {
+        BigIntAddSubMeasure::new_worst_case(host, rng, input)
+    }
+
+    fn new_random_case(
+        host: &Host,
+        rng: &mut StdRng,
+        input: u64,
+    ) -> (MeteredBigInt, MeteredBigInt) {
+        BigIntAddSubMeasure::new_random_case(host, rng, input)
+    }
+}
+
+// This measures the costs of doing div_rem on the bigint type. The input value
+// is the number of bits. The underlying code is variable-time in the bit size,
+// but we expect that by bounding the bit size we can make a reasonably tight
+// constant or linear-function upper bound. Examine the table and histogram.
+pub(crate) struct BigIntDivRemMeasure;
+impl HostCostMeasurement for BigIntDivRemMeasure {
+    type Runner = BigIntDivRemRun;
+
+    fn new_best_case(host: &Host, rng: &mut StdRng) -> (MeteredBigInt, MeteredBigInt) {
+        BigIntAddSubMeasure::new_best_case(host, rng)
+    }
+
+    fn new_worst_case(
+        host: &Host,
+        _rng: &mut StdRng,
+        input: u64,
+    ) -> (MeteredBigInt, MeteredBigInt) {
+        let input = input * 256;
+        // TODO: unclear if this really represents "worst case", it's
+        // just a guess.
+        let a: BigInt = util::repeating_byte_bigint(0xf7, input);
+        let b: BigInt = util::repeating_byte_bigint(0xf6, 1 + (input / 2));
+        (
+            MeteredBigInt::from_bigint(host.budget_cloned(), a),
+            MeteredBigInt::from_bigint(host.budget_cloned(), b),
+        )
+    }
+
+    fn new_random_case(
+        host: &Host,
+        rng: &mut StdRng,
+        input: u64,
+    ) -> (MeteredBigInt, MeteredBigInt) {
+        BigIntAddSubMeasure::new_random_case(host, rng, input)
+    }
+}
+
+pub(crate) struct BigIntBitwiseOpMeasure;
+impl HostCostMeasurement for BigIntBitwiseOpMeasure {
+    type Runner = BigIntBitwiseOpRun;
+
+    fn new_best_case(host: &Host, rng: &mut StdRng) -> (MeteredBigInt, MeteredBigInt) {
+        BigIntAddSubMeasure::new_best_case(host, rng)
+    }
+
+    fn new_worst_case(host: &Host, rng: &mut StdRng, input: u64) -> (MeteredBigInt, MeteredBigInt) {
+        BigIntAddSubMeasure::new_worst_case(host, rng, input)
+    }
+
+    fn new_random_case(
+        host: &Host,
+        rng: &mut StdRng,
+        input: u64,
+    ) -> (MeteredBigInt, MeteredBigInt) {
+        BigIntAddSubMeasure::new_random_case(host, rng, input)
+    }
+}
+
+pub(crate) struct BigIntShiftMeasure;
+impl HostCostMeasurement for BigIntShiftMeasure {
+    type Runner = BigIntShiftRun;
+
+    fn new_random_case(
+        host: &Host,
+        rng: &mut StdRng,
+        input: u64,
+    ) -> (MeteredBigInt, MeteredBigInt) {
+        let a: BigInt = util::random_bigint(rng, input * 256);
+        let b: BigInt = util::random_bigint(rng, input);
+        (
+            MeteredBigInt::from_bigint(host.budget_cloned(), a),
+            MeteredBigInt::from_bigint(host.budget_cloned(), b),
+        )
+    }
+}
+
+pub(crate) struct BigIntCmpMeasure;
+impl HostCostMeasurement for BigIntCmpMeasure {
+    type Runner = BigIntCmpRun;
+
+    fn new_best_case(host: &Host, rng: &mut StdRng) -> (MeteredBigInt, MeteredBigInt) {
+        BigIntAddSubMeasure::new_best_case(host, rng)
+    }
+
+    fn new_worst_case(host: &Host, rng: &mut StdRng, input: u64) -> (MeteredBigInt, MeteredBigInt) {
+        BigIntAddSubMeasure::new_worst_case(host, rng, input)
+    }
+
+    fn new_random_case(
+        host: &Host,
+        rng: &mut StdRng,
+        input: u64,
+    ) -> (MeteredBigInt, MeteredBigInt) {
+        BigIntAddSubMeasure::new_random_case(host, rng, input)
+    }
+}
+
+pub(crate) struct BigIntGcdLcmMeasure;
+impl HostCostMeasurement for BigIntGcdLcmMeasure {
+    type Runner = BigIntGcdLcmRun;
+
+    fn new_best_case(host: &Host, rng: &mut StdRng) -> (MeteredBigInt, MeteredBigInt) {
+        BigIntDivRemMeasure::new_best_case(host, rng)
+    }
+
+    fn new_worst_case(host: &Host, rng: &mut StdRng, input: u64) -> (MeteredBigInt, MeteredBigInt) {
+        BigIntDivRemMeasure::new_worst_case(host, rng, input)
+    }
+
+    fn new_random_case(
+        host: &Host,
+        rng: &mut StdRng,
+        input: u64,
+    ) -> (MeteredBigInt, MeteredBigInt) {
+        BigIntDivRemMeasure::new_random_case(host, rng, input)
+    }
+}
+
+// TODO: this is not constant or linear
+pub(crate) struct BigIntPowMeasure;
+impl HostCostMeasurement for BigIntPowMeasure {
+    type Runner = BigIntPowRun;
+
+    fn new_random_case(
+        host: &Host,
+        rng: &mut StdRng,
+        input: u64,
+    ) -> (MeteredBigInt, MeteredBigInt) {
+        let a: BigInt = util::random_bigint(rng, input * 256);
+        let pow = rng.next_u64() % 0xFF;
+        (
+            MeteredBigInt::from_bigint(host.budget_cloned(), a),
+            MeteredBigInt::from_u64(host.budget_cloned(), pow).unwrap(),
+        )
+    }
+}
+
+// TODO: this is not constant or linear
+pub(crate) struct BigIntPowModMeasure;
+impl HostCostMeasurement for BigIntPowModMeasure {
+    type Runner = BigIntPowModRun;
+
+    fn new_random_case(
+        host: &Host,
+        rng: &mut StdRng,
+        input: u64,
+    ) -> (MeteredBigInt, MeteredBigInt, MeteredBigInt) {
+        let a: BigInt = util::random_bigint(rng, input * 256);
+        let pow = rng.next_u64() % 0xFF;
+        let c: BigInt = util::random_bigint(rng, input * 256);
+        (
+            MeteredBigInt::from_bigint(host.budget_cloned(), a),
+            MeteredBigInt::from_u64(host.budget_cloned(), pow).unwrap(),
+            MeteredBigInt::from_bigint(host.budget_cloned(), c),
+        )
+    }
+}
+
+pub(crate) struct BigIntSqrtMeasure;
+impl HostCostMeasurement for BigIntSqrtMeasure {
+    type Runner = BigIntSqrtRun;
+
+    fn new_random_case(host: &Host, rng: &mut StdRng, input: u64) -> MeteredBigInt {
+        let a: BigInt = util::random_bigint(rng, input * 256);
+        MeteredBigInt::from_bigint(host.budget_cloned(), a)
+    }
+}
+
+pub(crate) struct BigIntFromBytesMeasure;
+impl HostCostMeasurement for BigIntFromBytesMeasure {
+    type Runner = BigIntFromBytesRun;
+
+    fn new_random_case(_host: &Host, rng: &mut StdRng, input: u64) -> Vec<u8> {
+        let input = input * 256;
+        (0..input / 8).map(|_| rng.gen::<u8>()).collect()
+    }
+}
+
+pub(crate) struct BigIntToBytesMeasure;
+impl HostCostMeasurement for BigIntToBytesMeasure {
+    type Runner = BigIntToBytesRun;
+
+    fn new_random_case(host: &Host, rng: &mut StdRng, input: u64) -> MeteredBigInt {
+        BigIntSqrtMeasure::new_random_case(host, rng, input)
+    }
+}
+
+pub(crate) struct BigIntToRadixMeasure;
+impl HostCostMeasurement for BigIntToRadixMeasure {
+    type Runner = BigIntToRadixRun;
+
+    fn new_random_case(host: &Host, rng: &mut StdRng, input: u64) -> (MeteredBigInt, u32) {
+        let radix = (rng.next_u32() as u8) + 1;
+        (
+            BigIntSqrtMeasure::new_random_case(host, rng, input),
+            radix as u32,
+        )
+    }
+}
diff --git a/soroban-env-host/benches/common/cost_types/bytes_ops.rs b/soroban-env-host/benches/common/cost_types/bytes_ops.rs
new file mode 100644
index 00000000..51bd00f0
--- /dev/null
+++ b/soroban-env-host/benches/common/cost_types/bytes_ops.rs
@@ -0,0 +1,120 @@
+use crate::HostCostMeasurement;
+use rand::{rngs::StdRng, RngCore};
+use soroban_env_host::{cost_runner::*, Host};
+pub struct BytesCloneMeasure;
+impl HostCostMeasurement for BytesCloneMeasure {
+    type Runner = BytesCloneRun;
+
+    fn new_random_case(
+        _host: &Host,
+        rng: &mut StdRng,
+        input: u64,
+    ) -> <Self::Runner as CostRunner>::SampleType {
+        let input = 1 + input * 100;
+        let mut res: Vec<u8> = vec![0; input as usize];
+        rng.fill_bytes(res.as_mut_slice());
+        res
+    }
+}
+pub struct BytesDelMeasure;
+impl HostCostMeasurement for BytesDelMeasure {
+    type Runner = BytesDelRun;
+
+    fn new_random_case(
+        host: &Host,
+        rng: &mut StdRng,
+        input: u64,
+    ) -> <Self::Runner as CostRunner>::SampleType {
+        let v = BytesCloneMeasure::new_random_case(host, rng, input);
+        let i = rng.next_u32() as usize % v.len();
+        (v, i)
+    }
+
+    fn new_worst_case(
+        host: &Host,
+        rng: &mut StdRng,
+        input: u64,
+    ) -> <Self::Runner as CostRunner>::SampleType {
+        let v = BytesCloneMeasure::new_random_case(host, rng, input);
+        (v, 0)
+    }
+}
+pub struct BytesPushMeasure;
+impl HostCostMeasurement for BytesPushMeasure {
+    type Runner = BytesPushRun;
+
+    fn new_random_case(
+        host: &Host,
+        rng: &mut StdRng,
+        input: u64,
+    ) -> <Self::Runner as CostRunner>::SampleType {
+        BytesCloneMeasure::new_random_case(host, rng, input)
+    }
+}
+pub struct BytesPopMeasure;
+impl HostCostMeasurement for BytesPopMeasure {
+    type Runner = BytesPopRun;
+
+    fn new_random_case(
+        host: &Host,
+        rng: &mut StdRng,
+        input: u64,
+    ) -> <Self::Runner as CostRunner>::SampleType {
+        BytesCloneMeasure::new_random_case(host, rng, input)
+    }
+}
+pub struct BytesInsertMeasure;
+impl HostCostMeasurement for BytesInsertMeasure {
+    type Runner = BytesInsertRun;
+
+    fn new_random_case(
+        host: &Host,
+        rng: &mut StdRng,
+        input: u64,
+    ) -> <Self::Runner as CostRunner>::SampleType {
+        BytesDelMeasure::new_random_case(host, rng, input)
+    }
+
+    fn new_worst_case(
+        host: &Host,
+        rng: &mut StdRng,
+        input: u64,
+    ) -> <Self::Runner as CostRunner>::SampleType {
+        BytesDelMeasure::new_worst_case(host, rng, input)
+    }
+}
+pub struct BytesAppendMeasure;
+impl HostCostMeasurement for BytesAppendMeasure {
+    type Runner = BytesAppendRun;
+
+    fn new_random_case(
+        host: &Host,
+        rng: &mut StdRng,
+        input: u64,
+    ) -> <Self::Runner as CostRunner>::SampleType {
+        let a = BytesCloneMeasure::new_random_case(host, rng, input);
+        let b = BytesCloneMeasure::new_random_case(host, rng, input);
+        (a, b)
+    }
+}
+pub struct BytesCmpMeasure;
+impl HostCostMeasurement for BytesCmpMeasure {
+    type Runner = BytesCmpRun;
+
+    fn new_random_case(
+        host: &Host,
+        rng: &mut StdRng,
+        input: u64,
+    ) -> <Self::Runner as CostRunner>::SampleType {
+        BytesAppendMeasure::new_random_case(host, rng, input)
+    }
+
+    fn new_worst_case(
+        host: &Host,
+        rng: &mut StdRng,
+        input: u64,
+    ) -> <Self::Runner as CostRunner>::SampleType {
+        let a = BytesCloneMeasure::new_random_case(host, rng, input);
+        (a.clone(), a)
+    }
+}
diff --git a/soroban-env-host/benches/common/cost_types/charge_budget.rs b/soroban-env-host/benches/common/cost_types/charge_budget.rs
new file mode 100644
index 00000000..96dcb3cb
--- /dev/null
+++ b/soroban-env-host/benches/common/cost_types/charge_budget.rs
@@ -0,0 +1,21 @@
+use crate::common::HostCostMeasurement;
+use rand::RngCore;
+use soroban_env_host::{budget::Budget, cost_runner::ChargeBudgetRun, Host};
+
+pub(crate) struct ChargeBudgetMeasure;
+
+// Measures the cost of invoking the budget charging machineary.
+// Should have constant cpu cost and zero mem cost.
+impl HostCostMeasurement for ChargeBudgetMeasure {
+    type Runner = ChargeBudgetRun;
+
+    fn new_random_case(
+        _host: &Host,
+        rng: &mut rand::prelude::StdRng,
+        _input: u64,
+    ) -> (Budget, u64) {
+        let b = Budget::default();
+        b.reset_unlimited();
+        (b, rng.next_u64())
+    }
+}
diff --git a/soroban-env-host/benches/common/cost_types/compute_ed25519_pubkey.rs b/soroban-env-host/benches/common/cost_types/compute_ed25519_pubkey.rs
index 01dcd099..0978189c 100644
--- a/soroban-env-host/benches/common/cost_types/compute_ed25519_pubkey.rs
+++ b/soroban-env-host/benches/common/cost_types/compute_ed25519_pubkey.rs
@@ -1,30 +1,20 @@
 use crate::common::HostCostMeasurement;
 use ed25519_dalek::{PublicKey, SecretKey};
 use rand::rngs::StdRng;
-use soroban_env_host::{budget::CostType, Host};
+use soroban_env_host::{cost_runner::ComputeEd25519PubKeyRun, Host};
 
 // This measures the costs to turn one byte buffer into an Ed25519
 // pubkey, which should be constant time. The input value is ignored.
-pub(crate) struct ComputeEd25519PubKeyRun {
+pub(crate) struct ComputeEd25519PubKeyMeasure {
     key: Vec<u8>,
 }
 
-impl HostCostMeasurement for ComputeEd25519PubKeyRun {
-    const COST_TYPE: CostType = CostType::ComputeEd25519PubKey;
-    const RUN_ITERATIONS: u64 = 100;
+impl HostCostMeasurement for ComputeEd25519PubKeyMeasure {
+    type Runner = ComputeEd25519PubKeyRun;
 
-    fn new_random_case(_host: &Host, rng: &mut StdRng, _input: u64) -> Self {
+    fn new_random_case(_host: &Host, rng: &mut StdRng, _input: u64) -> Vec<u8> {
         let secret = SecretKey::generate(rng);
         let public: PublicKey = (&secret).into();
-        let key = public.as_bytes().as_slice().into();
-        Self { key }
-    }
-
-    fn get_input(&self, _host: &Host) -> u64 {
-        1
-    }
-
-    fn run(&mut self, _iter: u64, _host: &Host) {
-        ed25519_dalek::PublicKey::from_bytes(self.key.as_slice()).expect("publickey");
+        public.as_bytes().as_slice().into()
     }
 }
diff --git a/soroban-env-host/benches/common/cost_types/compute_sha256_hash.rs b/soroban-env-host/benches/common/cost_types/compute_sha256_hash.rs
index 1c35f86b..82302530 100644
--- a/soroban-env-host/benches/common/cost_types/compute_sha256_hash.rs
+++ b/soroban-env-host/benches/common/cost_types/compute_sha256_hash.rs
@@ -1,29 +1,17 @@
 use crate::common::HostCostMeasurement;
 use rand::rngs::StdRng;
-use sha2::{Digest, Sha256};
-use soroban_env_host::{budget::CostType, Host};
+use soroban_env_host::{cost_runner::ComputeSha256HashRun, Host};
 
 // This measures the costs of performing a sha256 hash on a variable-sized
 // byte buffer. The input value is the size of the buffer. It should be
 // linear time.
-pub(crate) struct ComputeSha256HashRun {
-    buf: Vec<u8>,
-}
+pub(crate) struct ComputeSha256HashMeasure;
 
-impl HostCostMeasurement for ComputeSha256HashRun {
-    const COST_TYPE: CostType = CostType::ComputeSha256Hash;
+impl HostCostMeasurement for ComputeSha256HashMeasure {
+    type Runner = ComputeSha256HashRun;
 
-    fn new_random_case(_host: &Host, _rng: &mut StdRng, input: u64) -> Self {
+    fn new_random_case(_host: &Host, _rng: &mut StdRng, input: u64) -> Vec<u8> {
         let size = input * 100;
-        let buf: Vec<u8> = (0..size).map(|n| n as u8).collect();
-        Self { buf }
-    }
-
-    fn get_input(&self, _host: &Host) -> u64 {
-        self.buf.len() as u64
-    }
-
-    fn run(&mut self, _iter: u64, _host: &Host) {
-        Sha256::digest(&self.buf).as_slice().to_vec();
+        (0..size).map(|n| n as u8).collect()
     }
 }
diff --git a/soroban-env-host/benches/common/cost_types/ed25519_scalar_mul.rs b/soroban-env-host/benches/common/cost_types/ed25519_scalar_mul.rs
index 9ad83ede..fc797c46 100644
--- a/soroban-env-host/benches/common/cost_types/ed25519_scalar_mul.rs
+++ b/soroban-env-host/benches/common/cost_types/ed25519_scalar_mul.rs
@@ -1,7 +1,10 @@
 use crate::common::HostCostMeasurement;
 use curve25519_dalek::{constants, edwards, scalar};
 use rand::{rngs::StdRng, Rng, RngCore};
-use soroban_env_host::{budget::CostType, Host};
+use soroban_env_host::{
+    cost_runner::{Ed25519ScalarMulRun, Ed25519ScalarMulSample},
+    Host,
+};
 
 // This measures the costs of doing an Ed25519 scalar multiply, which is a
 // component of signature verification and is the only part advertised as
@@ -9,39 +12,34 @@ use soroban_env_host::{budget::CostType, Host};
 // nonlinear and the point of this measurement is to investigate how wide the
 // variation is in the histogram.
 #[allow(non_snake_case)]
-pub(crate) struct EdwardsPointCurve25519ScalarMulRun {
+pub(crate) struct Ed25519ScalarMulMeasure {
     a: scalar::Scalar,
     A: edwards::EdwardsPoint,
     b: scalar::Scalar,
 }
 #[allow(non_snake_case)]
-impl HostCostMeasurement for EdwardsPointCurve25519ScalarMulRun {
-    const COST_TYPE: CostType = CostType::EdwardsPointCurve25519ScalarMul;
-    const RUN_ITERATIONS: u64 = 100;
+impl HostCostMeasurement for Ed25519ScalarMulMeasure {
+    type Runner = Ed25519ScalarMulRun;
 
-    fn run(&mut self, _iter: u64, _host: &Host) {
-        edwards::EdwardsPoint::vartime_double_scalar_mul_basepoint(&self.a, &self.A, &self.b);
-    }
-
-    fn new_best_case(_host: &Host, _rng: &mut StdRng) -> Self {
+    fn new_best_case(_host: &Host, _rng: &mut StdRng) -> Ed25519ScalarMulSample {
         let a = scalar::Scalar::one();
         let b = scalar::Scalar::one();
         let A = constants::ED25519_BASEPOINT_COMPRESSED
             .decompress()
             .unwrap();
-        Self { a, b, A }
+        Ed25519ScalarMulSample { a, b, A }
     }
 
-    fn new_worst_case(_host: &Host, _rng: &mut StdRng, _input: u64) -> Self {
+    fn new_worst_case(_host: &Host, _rng: &mut StdRng, _input: u64) -> Ed25519ScalarMulSample {
         let a = scalar::Scalar::from_bytes_mod_order([0xff; 32]);
         let b = a.clone();
         let A = constants::ED25519_BASEPOINT_COMPRESSED
             .decompress()
             .unwrap();
-        Self { a, b, A }
+        Ed25519ScalarMulSample { a, b, A }
     }
 
-    fn new_random_case(_host: &Host, rng: &mut StdRng, _input: u64) -> Self {
+    fn new_random_case(_host: &Host, rng: &mut StdRng, _input: u64) -> Ed25519ScalarMulSample {
         fn random_scalar(rng: &mut StdRng) -> scalar::Scalar {
             let mut buf: [u8; 32] = [0; 32];
             rng.fill_bytes(&mut buf);
@@ -59,10 +57,6 @@ impl HostCostMeasurement for EdwardsPointCurve25519ScalarMulRun {
         let A = constants::ED25519_BASEPOINT_COMPRESSED
             .decompress()
             .unwrap();
-        Self { a, b, A }
-    }
-
-    fn get_input(&self, _host: &Host) -> u64 {
-        1
+        Ed25519ScalarMulSample { a, b, A }
     }
 }
diff --git a/soroban-env-host/benches/common/cost_types/guard_frame.rs b/soroban-env-host/benches/common/cost_types/guard_frame.rs
new file mode 100644
index 00000000..959f6a08
--- /dev/null
+++ b/soroban-env-host/benches/common/cost_types/guard_frame.rs
@@ -0,0 +1,25 @@
+use crate::common::HostCostMeasurement;
+use soroban_env_host::{cost_runner::GuardFrameRun, xdr::Hash, Symbol};
+
+pub(crate) struct GuardFrameMeasure;
+
+impl HostCostMeasurement for GuardFrameMeasure {
+    type Runner = GuardFrameRun;
+
+    fn new_best_case(
+        _host: &soroban_env_host::Host,
+        _rng: &mut rand::prelude::StdRng,
+    ) -> (Hash, Symbol) {
+        let id: Hash = [0; 32].into();
+        let fun: Symbol = Symbol::from_str("add");
+        (id, fun)
+    }
+
+    fn new_random_case(
+        host: &soroban_env_host::Host,
+        rng: &mut rand::prelude::StdRng,
+        _input: u64,
+    ) -> (Hash, Symbol) {
+        Self::new_best_case(host, rng)
+    }
+}
diff --git a/soroban-env-host/benches/common/cost_types/host_obj_alloc_slot.rs b/soroban-env-host/benches/common/cost_types/host_obj_alloc_slot.rs
index 6d9ff2c2..6551dc22 100644
--- a/soroban-env-host/benches/common/cost_types/host_obj_alloc_slot.rs
+++ b/soroban-env-host/benches/common/cost_types/host_obj_alloc_slot.rs
@@ -1,7 +1,7 @@
 use crate::common::HostCostMeasurement;
-use rand::rngs::StdRng;
+use rand::{rngs::StdRng, RngCore};
 use soroban_env_host::{
-    budget::CostType,
+    cost_runner::HostObjAllocSlotRun,
     xdr::{ScObject, ScVal},
     Host,
 };
@@ -10,17 +10,12 @@ use soroban_env_host::{
 // which is pretty much just the cost of doing a vector-grow operation in
 // rust. It should be _amortized_ constant-time. The input value is the
 // new object handle number, which is the size of the existing object array.
-pub(crate) struct HostObjAllocSlotRun {
-    val: ScVal,
-}
-
-impl HostCostMeasurement for HostObjAllocSlotRun {
-    const COST_TYPE: CostType = CostType::HostObjAllocSlot;
+pub(crate) struct HostObjAllocSlotMeasure;
 
-    // We iterate a bunch of times so that we cross a reallocation boundary.
-    const RUN_ITERATIONS: u64 = 100;
+impl HostCostMeasurement for HostObjAllocSlotMeasure {
+    type Runner = HostObjAllocSlotRun;
 
-    fn new_random_case(host: &Host, _rng: &mut StdRng, input: u64) -> Self {
+    fn new_random_case(host: &Host, rng: &mut StdRng, input: u64) -> Vec<u8> {
         // During setup we inject a bunch of copies of the object to make
         // the host object array large.
         let size = input * 100;
@@ -28,12 +23,9 @@ impl HostCostMeasurement for HostObjAllocSlotRun {
         for _ in 0..size {
             host.inject_val(&val).unwrap();
         }
-        Self { val }
-    }
-
-    fn run(&mut self, _iter: u64, host: &Host) {
-        // When measuring, we just inject a single copy to see what
-        // the cost of "one more" is at the given size.
-        host.inject_val(&self.val).unwrap();
+        // here we insert a pre-constructed bytes of various sizes to show that
+        // the cost of inserting one additional host object is constant w.r.t.
+        // the actual object size.
+        (0..input).map(|_| rng.next_u32() as u8).collect()
     }
 }
diff --git a/soroban-env-host/benches/common/cost_types/im_map_immut_entry.rs b/soroban-env-host/benches/common/cost_types/im_map_immut_entry.rs
deleted file mode 100644
index 314db5a3..00000000
--- a/soroban-env-host/benches/common/cost_types/im_map_immut_entry.rs
+++ /dev/null
@@ -1,49 +0,0 @@
-use crate::common::HostCostMeasurement;
-use rand::{rngs::StdRng, seq::SliceRandom};
-use soroban_env_host::{budget::CostType, EnvVal, Host, RawVal};
-
-use super::util;
-
-pub(crate) struct ImMapImmutEntryRun {
-    pub(crate) map: im_rc::OrdMap<EnvVal<Host, RawVal>, EnvVal<Host, RawVal>>,
-    pub(crate) keys: Vec<EnvVal<Host, RawVal>>,
-}
-
-// Measures the costs of accessing maps of varying sizes. It should have zero
-// memory cost and logarithmic cpu cost, which we will approximate as constant
-// with an upper bound on map size. The input value is the size of the map.
-impl HostCostMeasurement for ImMapImmutEntryRun {
-    const RUN_ITERATIONS: u64 = 100;
-    const COST_TYPE: CostType = CostType::ImMapImmutEntry;
-
-    fn new_random_case(host: &Host, rng: &mut StdRng, input: u64) -> Self {
-        let input = input * 100;
-        let mut keys: Vec<_> = util::to_envval_u32(host, 0..(input as u32)).collect();
-        keys.shuffle(rng);
-        let map = keys.iter().cloned().zip(keys.iter().cloned()).collect();
-        keys.shuffle(rng);
-        Self { map, keys }
-    }
-
-    fn new_worst_case(host: &Host, _rng: &mut StdRng, input: u64) -> Self {
-        let input = input * 100;
-        let keys: Vec<_> = util::to_envval_u32(host, 0..(input as u32)).collect();
-        let map = keys.iter().cloned().zip(keys.iter().cloned()).collect();
-        let keys = util::to_envval_u32(host, [0, u32::MAX].iter().cloned()).collect();
-        Self { map, keys }
-    }
-
-    fn new_best_case(host: &Host, _rng: &mut StdRng) -> Self {
-        let keys: Vec<_> = util::to_envval_u32(host, [0].iter().cloned()).collect();
-        let map = keys.iter().cloned().zip(keys.iter().cloned()).collect();
-        Self { map, keys }
-    }
-
-    fn run(&mut self, iter: u64, _host: &Host) {
-        let _ = self.map.get(&self.keys[iter as usize % self.keys.len()]);
-    }
-
-    fn get_input(&self, _host: &Host) -> u64 {
-        self.map.len() as u64
-    }
-}
diff --git a/soroban-env-host/benches/common/cost_types/im_map_mut_entry.rs b/soroban-env-host/benches/common/cost_types/im_map_mut_entry.rs
deleted file mode 100644
index 9e64ff2a..00000000
--- a/soroban-env-host/benches/common/cost_types/im_map_mut_entry.rs
+++ /dev/null
@@ -1,47 +0,0 @@
-use crate::common::HostCostMeasurement;
-use rand::rngs::StdRng;
-use soroban_env_host::{budget::CostType, EnvVal, Host, RawVal};
-
-use super::im_map_immut_entry::ImMapImmutEntryRun;
-
-pub(crate) struct ImMapMutEntryRun {
-    im: ImMapImmutEntryRun,
-    second_map_ref: im_rc::OrdMap<EnvVal<Host, RawVal>, EnvVal<Host, RawVal>>,
-}
-
-// This is just a variant of ImMapImmutEntryRun that calls the get_mut method on
-// a multiply-referenced map, causing a copy-on-write of some nodes. It should
-// cost a nearly-constant (perhaps very-slow-log) amount of memory and CPU.
-impl HostCostMeasurement for ImMapMutEntryRun {
-    const COST_TYPE: CostType = CostType::ImMapMutEntry;
-    const RUN_ITERATIONS: u64 = ImMapImmutEntryRun::RUN_ITERATIONS;
-
-    fn new_best_case(host: &Host, rng: &mut StdRng) -> Self {
-        let im = ImMapImmutEntryRun::new_best_case(host, rng);
-        let second_map_ref = im.map.clone();
-        Self { im, second_map_ref }
-    }
-
-    fn new_worst_case(host: &Host, rng: &mut StdRng, input: u64) -> Self {
-        let im = ImMapImmutEntryRun::new_worst_case(host, rng, input);
-        let second_map_ref = im.map.clone();
-        Self { im, second_map_ref }
-    }
-
-    fn new_random_case(host: &Host, rng: &mut StdRng, input: u64) -> Self {
-        let im = ImMapImmutEntryRun::new_random_case(host, rng, input);
-        let second_map_ref = im.map.clone();
-        Self { im, second_map_ref }
-    }
-
-    fn run(&mut self, iter: u64, _host: &Host) {
-        let _ = self
-            .im
-            .map
-            .get_mut(&self.im.keys[iter as usize % self.im.keys.len()]);
-    }
-
-    fn get_input(&self, host: &Host) -> u64 {
-        self.im.get_input(host)
-    }
-}
diff --git a/soroban-env-host/benches/common/cost_types/im_map_ops.rs b/soroban-env-host/benches/common/cost_types/im_map_ops.rs
new file mode 100644
index 00000000..2a1b6a31
--- /dev/null
+++ b/soroban-env-host/benches/common/cost_types/im_map_ops.rs
@@ -0,0 +1,101 @@
+use crate::common::{util, HostCostMeasurement};
+use rand::{rngs::StdRng, seq::SliceRandom};
+use soroban_env_host::{
+    cost_runner::{
+        ImMapCmpRun, ImMapCmpSample, ImMapImmutEntryRun, ImMapImmutEntrySample, ImMapMutEntryRun,
+        ImMapMutEntrySample, ImMapNewRun,
+    },
+    Host, MeteredOrdMap,
+};
+
+pub(crate) struct ImMapNewMeasure;
+// Measures the overhead cost of creating a new map, without inserting into the host storage.
+impl HostCostMeasurement for ImMapNewMeasure {
+    type Runner = ImMapNewRun;
+
+    fn new_random_case(_host: &Host, _rng: &mut StdRng, _input: u64) {
+        ()
+    }
+}
+
+pub(crate) struct ImMapImmutEntryMeasure;
+// Measures the costs of accessing maps of varying sizes. It should have zero
+// memory cost and logarithmic cpu cost, which we will approximate as constant
+// with an upper bound on map size. The input value is the size of the map.
+impl HostCostMeasurement for ImMapImmutEntryMeasure {
+    type Runner = ImMapImmutEntryRun;
+
+    fn new_random_case(host: &Host, rng: &mut StdRng, input: u64) -> ImMapImmutEntrySample {
+        let input = input * 100;
+        let mut keys: Vec<_> = util::to_envval_u32(host, 0..(input as u32)).collect();
+        keys.shuffle(rng);
+        let om = keys.iter().cloned().zip(keys.iter().cloned()).collect();
+        let map: MeteredOrdMap<_, _> = MeteredOrdMap::from_map(host.budget_cloned(), om).unwrap();
+        keys.shuffle(rng);
+        ImMapImmutEntrySample { map, keys }
+    }
+
+    fn new_worst_case(host: &Host, _rng: &mut StdRng, input: u64) -> ImMapImmutEntrySample {
+        let input = input * 100;
+        let keys: Vec<_> = util::to_envval_u32(host, 0..(input as u32)).collect();
+        let om = keys.iter().cloned().zip(keys.iter().cloned()).collect();
+        let map: MeteredOrdMap<_, _> = MeteredOrdMap::from_map(host.budget_cloned(), om).unwrap();
+        let keys = util::to_envval_u32(host, [0, u32::MAX].iter().cloned()).collect();
+        ImMapImmutEntrySample { map, keys }
+    }
+
+    fn new_best_case(host: &Host, _rng: &mut StdRng) -> ImMapImmutEntrySample {
+        let keys: Vec<_> = util::to_envval_u32(host, [0].iter().cloned()).collect();
+        let om = keys.iter().cloned().zip(keys.iter().cloned()).collect();
+        let map: MeteredOrdMap<_, _> = MeteredOrdMap::from_map(host.budget_cloned(), om).unwrap();
+        ImMapImmutEntrySample { map, keys }
+    }
+}
+
+pub(crate) struct ImMapMutEntryMeasure;
+// This is just a variant of ImMapImmutEntryRun that calls the get_mut method on
+// a multiply-referenced map, causing a copy-on-write of some nodes. It should
+// cost a nearly-constant (perhaps very-slow-log) amount of memory and CPU.
+impl HostCostMeasurement for ImMapMutEntryMeasure {
+    type Runner = ImMapMutEntryRun;
+
+    fn new_best_case(host: &Host, rng: &mut StdRng) -> ImMapMutEntrySample {
+        let im = ImMapImmutEntryMeasure::new_best_case(host, rng);
+        let second_map_ref = im.map.clone();
+        ImMapMutEntrySample { im, second_map_ref }
+    }
+
+    fn new_worst_case(host: &Host, rng: &mut StdRng, input: u64) -> ImMapMutEntrySample {
+        let im = ImMapImmutEntryMeasure::new_worst_case(host, rng, input);
+        let second_map_ref = im.map.clone();
+        ImMapMutEntrySample { im, second_map_ref }
+    }
+
+    fn new_random_case(host: &Host, rng: &mut StdRng, input: u64) -> ImMapMutEntrySample {
+        let im = ImMapImmutEntryMeasure::new_random_case(host, rng, input);
+        let second_map_ref = im.map.clone();
+        ImMapMutEntrySample { im, second_map_ref }
+    }
+}
+
+pub(crate) struct ImMapCmpMeasure;
+// Measures the cost of comparing two OrdMaps. The worst case grows n*log(n) whereas
+// the average cost is close to constant.
+impl HostCostMeasurement for ImMapCmpMeasure {
+    type Runner = ImMapCmpRun;
+
+    fn new_random_case(host: &Host, rng: &mut StdRng, input: u64) -> ImMapCmpSample {
+        let input = input * 100;
+        let oa = util::random_ord_map(host, rng, input);
+        let ob = util::random_ord_map(host, rng, input);
+        let a = MeteredOrdMap::from_map(host.budget_cloned(), oa).unwrap();
+        let b = MeteredOrdMap::from_map(host.budget_cloned(), ob).unwrap();
+        ImMapCmpSample { a, b }
+    }
+
+    fn new_worst_case(host: &Host, rng: &mut StdRng, input: u64) -> ImMapCmpSample {
+        let a = ImMapImmutEntryMeasure::new_random_case(host, rng, input).map;
+        let b = a.clone();
+        ImMapCmpSample { a, b }
+    }
+}
diff --git a/soroban-env-host/benches/common/cost_types/im_vec_immut_entry.rs b/soroban-env-host/benches/common/cost_types/im_vec_immut_entry.rs
deleted file mode 100644
index 505764e8..00000000
--- a/soroban-env-host/benches/common/cost_types/im_vec_immut_entry.rs
+++ /dev/null
@@ -1,41 +0,0 @@
-use crate::common::HostCostMeasurement;
-use rand::{rngs::StdRng, seq::SliceRandom};
-use soroban_env_host::{budget::CostType, EnvVal, Host, RawVal};
-
-use super::util;
-
-pub(crate) struct ImVecImmutEntryRun {
-    pub(crate) vec: im_rc::Vector<EnvVal<Host, RawVal>>,
-    pub(crate) idxs: Vec<usize>,
-}
-
-// Measures the costs of accessing vectors of various sizes. It should have zero
-// memory cost and logarithmic cpu cost, which we will approximate with an upper
-// bound on vector size.
-impl HostCostMeasurement for ImVecImmutEntryRun {
-    const COST_TYPE: CostType = CostType::ImVecImmutEntry;
-    const RUN_ITERATIONS: u64 = 100;
-
-    fn new_best_case(host: &Host, _rng: &mut StdRng) -> Self {
-        let vec = util::to_envval_u32(host, 0..1).collect();
-        let idxs = [0].to_vec();
-        Self { vec, idxs }
-    }
-
-    // Random case is worst case.
-    fn new_random_case(host: &Host, rng: &mut StdRng, input: u64) -> Self {
-        let input = 1 + (input * 10000);
-        let vec = util::to_envval_u32(host, 0..(input as u32)).collect();
-        let mut idxs: Vec<usize> = (0..input as usize).collect();
-        idxs.shuffle(rng);
-        Self { vec, idxs }
-    }
-
-    fn run(&mut self, iter: u64, _host: &Host) {
-        let _ = self.vec.get(self.idxs[iter as usize % self.idxs.len()]);
-    }
-
-    fn get_input(&self, _host: &Host) -> u64 {
-        self.vec.len() as u64
-    }
-}
diff --git a/soroban-env-host/benches/common/cost_types/im_vec_mut_entry.rs b/soroban-env-host/benches/common/cost_types/im_vec_mut_entry.rs
deleted file mode 100644
index e7e93d67..00000000
--- a/soroban-env-host/benches/common/cost_types/im_vec_mut_entry.rs
+++ /dev/null
@@ -1,42 +0,0 @@
-use crate::common::HostCostMeasurement;
-use rand::rngs::StdRng;
-use soroban_env_host::{budget::CostType, EnvVal, Host, RawVal};
-
-use super::im_vec_immut_entry::ImVecImmutEntryRun;
-
-pub(crate) struct ImVecMutEntryRun {
-    im: ImVecImmutEntryRun,
-    second_vec_ref: im_rc::Vector<EnvVal<Host, RawVal>>,
-}
-
-// This is just a variant of ImVecImmutEntryRun that calls the get_mut method on
-// a multiply-referenced vec, causing a copy-on-write of some nodes. It should
-// cost a nearly-constant (perhaps very-slow-log) amount of memory and CPU.
-impl HostCostMeasurement for ImVecMutEntryRun {
-    const COST_TYPE: CostType = CostType::ImVecMutEntry;
-    const RUN_ITERATIONS: u64 = ImVecImmutEntryRun::RUN_ITERATIONS;
-
-    fn new_best_case(host: &Host, rng: &mut StdRng) -> Self {
-        let im = ImVecImmutEntryRun::new_best_case(host, rng);
-        let second_vec_ref = im.vec.clone();
-        Self { im, second_vec_ref }
-    }
-
-    // Random case is worst case.
-    fn new_random_case(host: &Host, rng: &mut StdRng, input: u64) -> Self {
-        let im = ImVecImmutEntryRun::new_random_case(host, rng, input);
-        let second_vec_ref = im.vec.clone();
-        Self { im, second_vec_ref }
-    }
-
-    fn run(&mut self, iter: u64, _host: &Host) {
-        let _ = self
-            .im
-            .vec
-            .get_mut(self.im.idxs[iter as usize % self.im.idxs.len()]);
-    }
-
-    fn get_input(&self, host: &Host) -> u64 {
-        self.im.get_input(host)
-    }
-}
diff --git a/soroban-env-host/benches/common/cost_types/im_vec_new.rs b/soroban-env-host/benches/common/cost_types/im_vec_new.rs
deleted file mode 100644
index a5854753..00000000
--- a/soroban-env-host/benches/common/cost_types/im_vec_new.rs
+++ /dev/null
@@ -1,28 +0,0 @@
-use crate::common::HostCostMeasurement;
-use rand::rngs::StdRng;
-use soroban_env_host::{
-    budget::CostType,
-    xdr::{ScObject, ScVal, ScVec},
-    Host,
-};
-
-pub(crate) struct ImVecNewRun {
-    val: ScVal,
-}
-
-/// Measures the costs of allocating 0-sized vectors.
-impl HostCostMeasurement for ImVecNewRun {
-    const COST_TYPE: CostType = CostType::ImVecNew;
-    const RUN_ITERATIONS: u64 = 1000;
-
-    // All cases are the random case, which is a constant-effort operation.
-    fn new_random_case(_host: &Host, _rng: &mut StdRng, _input: u64) -> Self {
-        let scvec: ScVec = ScVec(vec![].try_into().unwrap());
-        let val = ScVal::Object(Some(ScObject::Vec(scvec)));
-        Self { val }
-    }
-
-    fn run(&mut self, _iter: u64, host: &Host) {
-        host.inject_val(&self.val).unwrap();
-    }
-}
diff --git a/soroban-env-host/benches/common/cost_types/im_vec_ops.rs b/soroban-env-host/benches/common/cost_types/im_vec_ops.rs
new file mode 100644
index 00000000..388e1352
--- /dev/null
+++ b/soroban-env-host/benches/common/cost_types/im_vec_ops.rs
@@ -0,0 +1,87 @@
+use crate::common::{util, HostCostMeasurement};
+use rand::{rngs::StdRng, seq::SliceRandom};
+use soroban_env_host::{
+    cost_runner::{
+        ImVecCmpRun, ImVecCmpSample, ImVecImmutEntryRun, ImVecImmutEntrySample, ImVecMutEntryRun,
+        ImVecMutEntrySample, ImVecNewRun,
+    },
+    Host, MeteredVector,
+};
+
+pub(crate) struct ImVecNewMeasure;
+/// Measures the costs of allocating 0-sized vectors, without injecting to the host storage.
+impl HostCostMeasurement for ImVecNewMeasure {
+    type Runner = ImVecNewRun;
+
+    fn new_random_case(_host: &Host, _rng: &mut StdRng, _input: u64) {
+        ()
+    }
+}
+
+pub(crate) struct ImVecImmutEntryMeasure;
+// Measures the costs of accessing vectors of various sizes. It should have zero
+// memory cost and logarithmic cpu cost, which we will approximate with an upper
+// bound on vector size.
+impl HostCostMeasurement for ImVecImmutEntryMeasure {
+    type Runner = ImVecImmutEntryRun;
+
+    fn new_best_case(host: &Host, _rng: &mut StdRng) -> ImVecImmutEntrySample {
+        let ov = util::to_envval_u32(host, 0..1).collect();
+        let vec: MeteredVector<_> = MeteredVector::from_vec(host.budget_cloned(), ov).unwrap();
+        let idxs = [0].to_vec();
+        ImVecImmutEntrySample { vec, idxs }
+    }
+
+    // Random case is worst case.
+    fn new_random_case(host: &Host, rng: &mut StdRng, input: u64) -> ImVecImmutEntrySample {
+        let input = 1 + (input * 100);
+        let ov = util::to_envval_u32(host, 0..(input as u32)).collect();
+        let vec: MeteredVector<_> = MeteredVector::from_vec(host.budget_cloned(), ov).unwrap();
+        let mut idxs: Vec<usize> = (0..input as usize).collect();
+        idxs.shuffle(rng);
+        ImVecImmutEntrySample { vec, idxs }
+    }
+}
+
+pub(crate) struct ImVecMutEntryMeasure;
+// This is just a variant of ImVecImmutEntryRun that calls the get_mut method on
+// a multiply-referenced vec, causing a copy-on-write of some nodes. It should
+// cost a nearly-constant (perhaps very-slow-log) amount of memory and CPU.
+impl HostCostMeasurement for ImVecMutEntryMeasure {
+    type Runner = ImVecMutEntryRun;
+
+    fn new_best_case(host: &Host, rng: &mut StdRng) -> ImVecMutEntrySample {
+        let im = ImVecImmutEntryMeasure::new_best_case(host, rng);
+        let second_vec_ref = im.vec.clone();
+        ImVecMutEntrySample { im, second_vec_ref }
+    }
+
+    // Random case is worst case.
+    fn new_random_case(host: &Host, rng: &mut StdRng, input: u64) -> ImVecMutEntrySample {
+        let im = ImVecImmutEntryMeasure::new_random_case(host, rng, input);
+        let second_vec_ref = im.vec.clone();
+        ImVecMutEntrySample { im, second_vec_ref }
+    }
+}
+
+pub(crate) struct ImVecCmpMeasure;
+// Measures the cost of comparing two Vectors. The worst case grows n*log(n) whereas
+// the average cost is close to constant.
+impl HostCostMeasurement for ImVecCmpMeasure {
+    type Runner = ImVecCmpRun;
+
+    fn new_random_case(host: &Host, rng: &mut StdRng, input: u64) -> ImVecCmpSample {
+        let input = input * 100;
+        let oa = util::random_im_vector(host, rng, input);
+        let ob = util::random_im_vector(host, rng, input);
+        let a = MeteredVector::from_vec(host.budget_cloned(), oa).unwrap();
+        let b = MeteredVector::from_vec(host.budget_cloned(), ob).unwrap();
+        ImVecCmpSample { a, b }
+    }
+
+    fn new_worst_case(host: &Host, rng: &mut StdRng, input: u64) -> ImVecCmpSample {
+        let a = ImVecImmutEntryMeasure::new_random_case(host, rng, input).vec;
+        let b = a.clone();
+        ImVecCmpSample { a, b }
+    }
+}
diff --git a/soroban-env-host/benches/common/cost_types/invoke.rs b/soroban-env-host/benches/common/cost_types/invoke.rs
new file mode 100644
index 00000000..ca603c84
--- /dev/null
+++ b/soroban-env-host/benches/common/cost_types/invoke.rs
@@ -0,0 +1,59 @@
+use std::rc::Rc;
+
+use crate::common::HostCostMeasurement;
+use rand::rngs::StdRng;
+use soroban_env_host::{
+    cost_runner::{InvokeHostFunctionRun, InvokeVmFunctionRun},
+    xdr::Hash,
+    Host, Symbol, Vm,
+};
+use soroban_synth_wasm::{Arity, ModEmitter};
+
+fn wasm_module_with_empty_invoke() -> Vec<u8> {
+    let mut fe = ModEmitter::new().func(Arity(0), 0);
+    fe.push(Symbol::from_str("pass"));
+    fe.finish_and_export("test").finish()
+}
+
+fn wasm_module_with_dummy_hostfn_invoke(repeat: u64) -> Vec<u8> {
+    let mut fe = ModEmitter::new().func(Arity(0), 0);
+    for _ in 0..repeat {
+        fe.dummy0();
+        fe.drop();
+    }
+    fe.push(Symbol::from_str("pass"));
+    fe.finish_and_export("test").finish()
+}
+
+pub(crate) struct InvokeVmFunctionMeasure;
+
+// This measures the roundtrip cost of invoking a VM (guest) function from the host.
+// The guest function receives 0 args and does no-op. Both the CPU and mem cost should
+// be constant.
+impl HostCostMeasurement for InvokeVmFunctionMeasure {
+    type Runner = InvokeVmFunctionRun;
+
+    fn new_random_case(host: &Host, _rng: &mut StdRng, _input: u64) -> Rc<Vm> {
+        let id: Hash = [0; 32].into();
+        let code = wasm_module_with_empty_invoke();
+        Vm::new(&host, id, &code).unwrap()
+    }
+}
+
+pub(crate) struct InvokeHostFunctionMeasure;
+
+// Measures the cost of host function invocation inside an VM.
+// The wasm code repeatly calls an empty host function. Input is number of Vm->host invocations,
+// the cpu cost should be linear wrt the input and mem cost should be constant.
+// The setup here also includes an initial host->Vm call which has `CostType: InvokeVmFunction`.
+// We therefore use a large input such that its cost is averaged out.
+impl HostCostMeasurement for InvokeHostFunctionMeasure {
+    type Runner = InvokeHostFunctionRun;
+
+    fn new_random_case(host: &Host, _rng: &mut StdRng, input: u64) -> Rc<Vm> {
+        let input = input * 1000;
+        let id: Hash = [0; 32].into();
+        let code = wasm_module_with_dummy_hostfn_invoke(input);
+        Vm::new(&host, id, &code).unwrap()
+    }
+}
diff --git a/soroban-env-host/benches/common/cost_types/mod.rs b/soroban-env-host/benches/common/cost_types/mod.rs
index 325ff431..d9674c51 100644
--- a/soroban-env-host/benches/common/cost_types/mod.rs
+++ b/soroban-env-host/benches/common/cost_types/mod.rs
@@ -1,87 +1,45 @@
-mod bigint_div_rem;
+mod bigint_ops;
+mod bytes_ops;
+mod charge_budget;
 mod compute_ed25519_pubkey;
 mod compute_sha256_hash;
 mod ed25519_scalar_mul;
+mod guard_frame;
 mod host_obj_alloc_slot;
-mod im_map_immut_entry;
-mod im_map_mut_entry;
-mod im_vec_immut_entry;
-mod im_vec_mut_entry;
-mod im_vec_new;
+mod im_map_ops;
+mod im_vec_ops;
+mod invoke;
+mod record_contract_event;
+mod record_debug_event;
 mod scmap_to_host_map;
 mod scvec_to_host_vec;
+mod val_deser;
+mod val_ser;
+mod val_xdr_conv;
 mod verify_ed25519_sig;
-mod vm_instantiation;
+mod visit_object;
+mod vm_ops;
 mod wasm_insn_exec;
 
-mod util;
-
-use std::collections::BTreeSet;
-
-use soroban_env_host::budget::CostType;
-
-use crate::common::HostCostMeasurement;
-
-pub trait Benchmark {
-    fn bench<HCM: HostCostMeasurement>() -> std::io::Result<()>;
-}
-
-fn get_explicit_bench_names() -> Option<Vec<String>> {
-    let bare_args: Vec<_> = std::env::args().filter(|x| !x.starts_with("-")).collect();
-    match bare_args.len() {
-        0 | 1 => None,
-        _ => Some(bare_args[1..].into()),
-    }
-}
-
-fn should_run<HCM: HostCostMeasurement>() -> bool {
-    if let Some(bench_names) = get_explicit_bench_names() {
-        let name = format!("{:?}", HCM::COST_TYPE)
-            .split("::")
-            .last()
-            .unwrap()
-            .to_string();
-        bench_names.into_iter().find(|arg| *arg == name).is_some()
-    } else {
-        true
-    }
-}
-
-fn call_bench<B: Benchmark, HCM: HostCostMeasurement>(
-    costs: &mut BTreeSet<CostType>,
-) -> std::io::Result<()> {
-    if should_run::<HCM>() {
-        B::bench::<HCM>()?;
-        costs.insert(HCM::COST_TYPE);
-    }
-    Ok(())
-}
-
-pub fn for_each_host_cost_measurement<B: Benchmark>() -> std::io::Result<()> {
-    let mut costs: BTreeSet<CostType> = BTreeSet::new();
-
-    call_bench::<B, bigint_div_rem::BigIntDivRemRun>(&mut costs)?;
-    call_bench::<B, compute_ed25519_pubkey::ComputeEd25519PubKeyRun>(&mut costs)?;
-    call_bench::<B, compute_sha256_hash::ComputeSha256HashRun>(&mut costs)?;
-    call_bench::<B, ed25519_scalar_mul::EdwardsPointCurve25519ScalarMulRun>(&mut costs)?;
-    call_bench::<B, host_obj_alloc_slot::HostObjAllocSlotRun>(&mut costs)?;
-    call_bench::<B, im_map_immut_entry::ImMapImmutEntryRun>(&mut costs)?;
-    call_bench::<B, im_map_mut_entry::ImMapMutEntryRun>(&mut costs)?;
-    call_bench::<B, im_vec_immut_entry::ImVecImmutEntryRun>(&mut costs)?;
-    call_bench::<B, im_vec_mut_entry::ImVecMutEntryRun>(&mut costs)?;
-    call_bench::<B, im_vec_new::ImVecNewRun>(&mut costs)?;
-    call_bench::<B, scmap_to_host_map::ScMapToHostMapRun>(&mut costs)?;
-    call_bench::<B, scvec_to_host_vec::ScVecToHostVecRun>(&mut costs)?;
-    call_bench::<B, verify_ed25519_sig::VerifyEd25519SigRun>(&mut costs)?;
-    call_bench::<B, vm_instantiation::VmInstantiationRun>(&mut costs)?;
-    call_bench::<B, wasm_insn_exec::WasmInsnExecRun>(&mut costs)?;
-
-    if get_explicit_bench_names().is_none() {
-        for cost in CostType::variants() {
-            if !costs.contains(cost) {
-                eprintln!("warning: missing cost measurement for {:?}", cost);
-            }
-        }
-    }
-    Ok(())
-}
+pub(crate) use bigint_ops::*;
+pub(crate) use bytes_ops::*;
+pub(crate) use charge_budget::*;
+pub(crate) use compute_ed25519_pubkey::*;
+pub(crate) use compute_sha256_hash::*;
+pub(crate) use ed25519_scalar_mul::*;
+pub(crate) use guard_frame::*;
+pub(crate) use host_obj_alloc_slot::*;
+pub(crate) use im_map_ops::*;
+pub(crate) use im_vec_ops::*;
+pub(crate) use invoke::*;
+pub(crate) use record_contract_event::*;
+pub(crate) use record_debug_event::*;
+pub(crate) use scmap_to_host_map::*;
+pub(crate) use scvec_to_host_vec::*;
+pub(crate) use val_deser::*;
+pub(crate) use val_ser::*;
+pub(crate) use val_xdr_conv::*;
+pub(crate) use verify_ed25519_sig::*;
+pub(crate) use visit_object::*;
+pub(crate) use vm_ops::*;
+pub(crate) use wasm_insn_exec::*;
diff --git a/soroban-env-host/benches/common/cost_types/record_contract_event.rs b/soroban-env-host/benches/common/cost_types/record_contract_event.rs
new file mode 100644
index 00000000..b5495f33
--- /dev/null
+++ b/soroban-env-host/benches/common/cost_types/record_contract_event.rs
@@ -0,0 +1,50 @@
+use crate::common::HostCostMeasurement;
+use soroban_env_host::cost_runner::CostRunner;
+use soroban_env_host::xdr::{
+    ContractEvent, ContractEventBody, ContractEventType, ContractEventV0, ExtensionPoint, Hash,
+    ScMap, ScMapEntry, ScObject::Map, ScVal,
+};
+use soroban_env_host::{
+    cost_runner::{RecordContractEventRun, RecordContractEventSample},
+    events::HostEvent,
+    Host,
+};
+
+pub(crate) struct RecordContractEventMeasure;
+
+impl HostCostMeasurement for RecordContractEventMeasure {
+    type Runner = RecordContractEventRun;
+
+    fn new_random_case(
+        host: &Host,
+        _rng: &mut rand::prelude::StdRng,
+        input: u64,
+    ) -> RecordContractEventSample {
+        let event = ContractEvent {
+            ext: ExtensionPoint::V0,
+            contract_id: Some(Hash([0; 32])),
+            type_: ContractEventType::Contract,
+            body: ContractEventBody::V0(ContractEventV0 {
+                topics: host
+                    .map_err(vec![ScVal::U32(0), ScVal::U32(1)].try_into())
+                    .unwrap(),
+                data: ScVal::Object(Some(Map(host
+                    .map_err(ScMap::try_from(vec![ScMapEntry {
+                        key: ScVal::U32(1),
+                        val: ScVal::U32(2),
+                    }]))
+                    .unwrap()))),
+            }),
+        };
+        let mut storage = Vec::new();
+        let mut events = Vec::new();
+        for _iter in 0..input {
+            storage.push(HostEvent::Contract(event.clone()));
+        }
+        for _iter in 0..<Self::Runner as CostRunner>::RUN_ITERATIONS {
+            events.push(event.clone())
+        }
+
+        RecordContractEventSample { storage, events }
+    }
+}
diff --git a/soroban-env-host/benches/common/cost_types/record_debug_event.rs b/soroban-env-host/benches/common/cost_types/record_debug_event.rs
new file mode 100644
index 00000000..d3434e37
--- /dev/null
+++ b/soroban-env-host/benches/common/cost_types/record_debug_event.rs
@@ -0,0 +1,33 @@
+use crate::common::{util, HostCostMeasurement};
+use soroban_env_host::{
+    cost_runner::{CreateRecordDebugEventRun, CreateRecordDebugEventSample},
+    Host,
+};
+
+pub(crate) struct CreateRecordDebugEventMeasure;
+
+impl HostCostMeasurement for CreateRecordDebugEventMeasure {
+    type Runner = CreateRecordDebugEventRun;
+
+    fn new_random_case(
+        host: &Host,
+        _rng: &mut rand::prelude::StdRng,
+        input: u64,
+    ) -> CreateRecordDebugEventSample {
+        let args = util::to_envval_u32(host, 0..(input as u32)).collect();
+        CreateRecordDebugEventSample {
+            msg: "this is a debug msg",
+            args,
+        }
+    }
+
+    fn new_best_case(
+        _host: &Host,
+        _rng: &mut rand::prelude::StdRng,
+    ) -> CreateRecordDebugEventSample {
+        CreateRecordDebugEventSample {
+            msg: "",
+            args: Vec::default(),
+        }
+    }
+}
diff --git a/soroban-env-host/benches/common/cost_types/scmap_to_host_map.rs b/soroban-env-host/benches/common/cost_types/scmap_to_host_map.rs
index 2a129fa6..a98eb9da 100644
--- a/soroban-env-host/benches/common/cost_types/scmap_to_host_map.rs
+++ b/soroban-env-host/benches/common/cost_types/scmap_to_host_map.rs
@@ -2,26 +2,21 @@ use std::collections::HashSet;
 
 use crate::common::HostCostMeasurement;
 use rand::{rngs::StdRng, Rng};
-use soroban_env_host::xdr::ScVal;
 use soroban_env_host::{
-    budget::CostType,
-    xdr::{ScMap, ScMapEntry, ScObject},
+    cost_runner::ScMapToHostMapRun,
+    xdr::{ScMap, ScMapEntry, ScObject, ScVal},
     Host,
 };
 
-pub(crate) struct ScMapToHostMapRun {
-    val: ScVal,
-    input: u64,
-}
+pub(crate) struct ScMapToHostMapMeasure;
 
 // This measures the costs of converting maps of varying sizes
 // from XDR to host format. The input is the size of the map,
 // the costs should be linear.
-impl HostCostMeasurement for ScMapToHostMapRun {
-    const COST_TYPE: CostType = CostType::ScMapToHostMap;
-    const RUN_ITERATIONS: u64 = 5;
+impl HostCostMeasurement for ScMapToHostMapMeasure {
+    type Runner = ScMapToHostMapRun;
 
-    fn new_random_case(_host: &Host, rng: &mut StdRng, input: u64) -> Self {
+    fn new_random_case(_host: &Host, rng: &mut StdRng, input: u64) -> ScVal {
         let input = input * 100;
         let mut hs: HashSet<u32> = HashSet::new();
         while hs.len() < (input as usize) {
@@ -37,15 +32,6 @@ impl HostCostMeasurement for ScMapToHostMapRun {
                 .try_into()
                 .unwrap(),
         );
-        let val = ScVal::Object(Some(ScObject::Map(scmap)));
-        Self { val, input }
-    }
-
-    fn get_input(&self, _host: &Host) -> u64 {
-        self.input
-    }
-
-    fn run(&mut self, _iter: u64, host: &Host) {
-        host.inject_val(&self.val).unwrap();
+        ScVal::Object(Some(ScObject::Map(scmap)))
     }
 }
diff --git a/soroban-env-host/benches/common/cost_types/scvec_to_host_vec.rs b/soroban-env-host/benches/common/cost_types/scvec_to_host_vec.rs
index 7363e1cd..f2caddc0 100644
--- a/soroban-env-host/benches/common/cost_types/scvec_to_host_vec.rs
+++ b/soroban-env-host/benches/common/cost_types/scvec_to_host_vec.rs
@@ -1,24 +1,19 @@
 use crate::common::HostCostMeasurement;
 use rand::rngs::StdRng;
-use soroban_env_host::xdr::ScVal;
 use soroban_env_host::{
-    budget::CostType,
-    xdr::{ScObject, ScVec},
+    cost_runner::ScVecToHostVecRun,
+    xdr::{ScObject, ScVal, ScVec},
     Host,
 };
 
-pub(crate) struct ScVecToHostVecRun {
-    input: u64,
-    val: ScVal,
-}
+pub(crate) struct ScVecToHostVecMeasure;
 
 // This measures the costs of converting vectors of varying sizes from XDR to
 // host format. The input is the size of the map, the costs should be linear.
-impl HostCostMeasurement for ScVecToHostVecRun {
-    const COST_TYPE: CostType = CostType::ScVecToHostVec;
-    const RUN_ITERATIONS: u64 = 5;
+impl HostCostMeasurement for ScVecToHostVecMeasure {
+    type Runner = ScVecToHostVecRun;
 
-    fn new_random_case(_host: &Host, _rng: &mut StdRng, input: u64) -> Self {
+    fn new_random_case(_host: &Host, _rng: &mut StdRng, input: u64) -> ScVal {
         let input = input * 100;
         let scvec: ScVec = ScVec(
             (0..input)
@@ -27,15 +22,6 @@ impl HostCostMeasurement for ScVecToHostVecRun {
                 .try_into()
                 .unwrap(),
         );
-        let val = ScVal::Object(Some(ScObject::Vec(scvec)));
-        Self { input, val }
-    }
-
-    fn get_input(&self, _host: &Host) -> u64 {
-        self.input
-    }
-
-    fn run(&mut self, _iter: u64, host: &Host) {
-        host.inject_val(&self.val).unwrap();
+        ScVal::Object(Some(ScObject::Vec(scvec)))
     }
 }
diff --git a/soroban-env-host/benches/common/cost_types/util.rs b/soroban-env-host/benches/common/cost_types/util.rs
deleted file mode 100644
index 1207d9ec..00000000
--- a/soroban-env-host/benches/common/cost_types/util.rs
+++ /dev/null
@@ -1,12 +0,0 @@
-use soroban_env_host::{EnvVal, Host, RawVal};
-
-pub(crate) fn to_envval_u32<I: Iterator<Item = u32>>(
-    host: &Host,
-    vals: I,
-) -> impl Iterator<Item = EnvVal<Host, RawVal>> {
-    let host = host.clone();
-    vals.map(move |v| EnvVal {
-        env: host.clone(),
-        val: RawVal::from_u32(v),
-    })
-}
diff --git a/soroban-env-host/benches/common/cost_types/val_deser.rs b/soroban-env-host/benches/common/cost_types/val_deser.rs
new file mode 100644
index 00000000..0342448b
--- /dev/null
+++ b/soroban-env-host/benches/common/cost_types/val_deser.rs
@@ -0,0 +1,19 @@
+use soroban_env_host::{cost_runner::ValDeserRun, xdr::WriteXdr};
+
+use super::ValSerMeasure;
+use crate::common::HostCostMeasurement;
+
+pub(crate) struct ValDeserMeasure;
+
+impl HostCostMeasurement for ValDeserMeasure {
+    type Runner = ValDeserRun;
+
+    fn new_random_case(
+        host: &soroban_env_host::Host,
+        rng: &mut rand::prelude::StdRng,
+        input: u64,
+    ) -> Vec<u8> {
+        let scval = ValSerMeasure::new_random_case(host, rng, input);
+        scval.to_xdr().unwrap()
+    }
+}
diff --git a/soroban-env-host/benches/common/cost_types/val_ser.rs b/soroban-env-host/benches/common/cost_types/val_ser.rs
new file mode 100644
index 00000000..f12c005c
--- /dev/null
+++ b/soroban-env-host/benches/common/cost_types/val_ser.rs
@@ -0,0 +1,35 @@
+use std::collections::HashSet;
+
+use crate::common::HostCostMeasurement;
+use rand::{rngs::StdRng, Rng};
+use soroban_env_host::{
+    cost_runner::ValSerRun,
+    xdr::{ScMap, ScMapEntry, ScObject, ScVal},
+    Host,
+};
+
+pub(crate) struct ValSerMeasure;
+
+// This measures the costs of converting an ScVal into bytes.
+impl HostCostMeasurement for ValSerMeasure {
+    type Runner = ValSerRun;
+
+    fn new_random_case(_host: &Host, rng: &mut StdRng, input: u64) -> ScVal {
+        let input = input * 100;
+        let mut hs: HashSet<u32> = HashSet::new();
+        while hs.len() < (input as usize) {
+            hs.insert(rng.gen());
+        }
+        let scmap: ScMap = ScMap(
+            hs.iter()
+                .map(|i| ScMapEntry {
+                    key: ScVal::U32(*i),
+                    val: ScVal::U32(*i),
+                })
+                .collect::<Vec<ScMapEntry>>()
+                .try_into()
+                .unwrap(),
+        );
+        ScVal::Object(Some(ScObject::Map(scmap)))
+    }
+}
diff --git a/soroban-env-host/benches/common/cost_types/val_xdr_conv.rs b/soroban-env-host/benches/common/cost_types/val_xdr_conv.rs
new file mode 100644
index 00000000..5b0fa180
--- /dev/null
+++ b/soroban-env-host/benches/common/cost_types/val_xdr_conv.rs
@@ -0,0 +1,17 @@
+use crate::common::HostCostMeasurement;
+use rand::{rngs::StdRng, RngCore};
+use soroban_env_host::{cost_runner::ValXdrConvRun, xdr::ScVal, Host, RawVal};
+
+pub(crate) struct ValXdrConvMeasure;
+
+// This measures the costs of conversion of one non-object RawVal type to and from XDR.
+impl HostCostMeasurement for ValXdrConvMeasure {
+    type Runner = ValXdrConvRun;
+
+    fn new_random_case(_host: &Host, rng: &mut StdRng, _input: u64) -> (RawVal, ScVal) {
+        let v = rng.next_u32();
+        let rv: RawVal = v.into();
+        let scv: ScVal = ScVal::U32(v as u32);
+        (rv, scv)
+    }
+}
diff --git a/soroban-env-host/benches/common/cost_types/verify_ed25519_sig.rs b/soroban-env-host/benches/common/cost_types/verify_ed25519_sig.rs
index 0842d687..e2894b65 100644
--- a/soroban-env-host/benches/common/cost_types/verify_ed25519_sig.rs
+++ b/soroban-env-host/benches/common/cost_types/verify_ed25519_sig.rs
@@ -1,37 +1,25 @@
 use crate::common::HostCostMeasurement;
-use ed25519_dalek::{Keypair, PublicKey, Signature, Signer, Verifier};
+use ed25519_dalek::{Keypair, PublicKey, Signature, Signer};
 use rand::rngs::StdRng;
-use soroban_env_host::{budget::CostType, Host};
+use soroban_env_host::{
+    cost_runner::{VerifyEd25519SigRun, VerifyEd25519SigSample},
+    Host,
+};
 
-pub(crate) struct VerifyEd25519SigRun {
-    key: PublicKey,
-    msg: Vec<u8>,
-    sig: Signature,
-}
+pub(crate) struct VerifyEd25519SigMeasure;
 
 // This measures the cost of verifying an Ed25519 signature of varying-length
 // messages. The input value is the length of the signed message. It should cost
 // linear CPU (for hashing) and zero heap memory.
-impl HostCostMeasurement for VerifyEd25519SigRun {
-    const COST_TYPE: CostType = CostType::VerifyEd25519Sig;
-    const RUN_ITERATIONS: u64 = 3;
+impl HostCostMeasurement for VerifyEd25519SigMeasure {
+    type Runner = VerifyEd25519SigRun;
 
-    fn new_random_case(_host: &Host, rng: &mut StdRng, input: u64) -> Self {
+    fn new_random_case(_host: &Host, rng: &mut StdRng, input: u64) -> VerifyEd25519SigSample {
         let size = input * 10000;
         let keypair: Keypair = Keypair::generate(rng);
         let key: PublicKey = keypair.public.clone();
         let msg: Vec<u8> = (0..size).map(|x| x as u8).collect();
         let sig: Signature = keypair.sign(msg.as_slice());
-        Self { key, msg, sig }
-    }
-
-    fn get_input(&self, _host: &Host) -> u64 {
-        self.msg.len() as u64
-    }
-
-    fn run(&mut self, _iter: u64, _host: &Host) {
-        self.key
-            .verify(self.msg.as_slice(), &self.sig)
-            .expect("verify")
+        VerifyEd25519SigSample { key, msg, sig }
     }
 }
diff --git a/soroban-env-host/benches/common/cost_types/visit_object.rs b/soroban-env-host/benches/common/cost_types/visit_object.rs
new file mode 100644
index 00000000..ab50987d
--- /dev/null
+++ b/soroban-env-host/benches/common/cost_types/visit_object.rs
@@ -0,0 +1,24 @@
+use crate::common::HostCostMeasurement;
+use soroban_env_host::{
+    cost_runner::VisitObjectRun,
+    xdr::{ScObject, ScVal},
+    Host, RawVal,
+};
+
+pub(crate) struct VisitObjectMeasure;
+
+impl HostCostMeasurement for VisitObjectMeasure {
+    type Runner = VisitObjectRun;
+
+    fn new_random_case(host: &Host, _rng: &mut rand::prelude::StdRng, input: u64) -> Vec<RawVal> {
+        // During setup we inject a bunch of copies of the object to make
+        // the host object array large.
+        let size = 1 + input * 100;
+        let mut vec = Vec::with_capacity(size as usize);
+        let val = ScVal::Object(Some(ScObject::I64(0)));
+        for _ in 0..size {
+            vec.push(host.inject_val(&val).unwrap());
+        }
+        vec
+    }
+}
diff --git a/soroban-env-host/benches/common/cost_types/vm_instantiation.rs b/soroban-env-host/benches/common/cost_types/vm_instantiation.rs
deleted file mode 100644
index bb98bf8e..00000000
--- a/soroban-env-host/benches/common/cost_types/vm_instantiation.rs
+++ /dev/null
@@ -1,55 +0,0 @@
-use crate::common::HostCostMeasurement;
-use rand::{rngs::StdRng, Rng};
-use soroban_env_host::{budget::CostType, xdr, Host, Vm};
-
-pub(crate) struct VmInstantiationRun {
-    id: xdr::Hash,
-    wasm: Vec<u8>,
-}
-
-// This measures the cost of instantiating a host::Vm on a variety of possible
-// wasm modules, of different sizes. The input value should be the size of the
-// module, though for now we're just selecting modules from the fixed example
-// repertoire. Costs should be linear.
-impl HostCostMeasurement for VmInstantiationRun {
-    const COST_TYPE: CostType = CostType::VmInstantiation;
-    const RUN_ITERATIONS: u64 = 10;
-
-    fn new_best_case(_host: &Host, _rng: &mut StdRng) -> Self {
-        let id: xdr::Hash = [0; 32].into();
-        let wasm: Vec<u8> = soroban_test_wasms::ADD_I32.clone().into();
-        Self { id, wasm }
-    }
-
-    fn new_worst_case(_host: &Host, _rng: &mut StdRng, _input: u64) -> Self {
-        let id: xdr::Hash = [0; 32].into();
-        let wasm: Vec<u8> = soroban_test_wasms::COMPLEX.clone().into();
-        Self { id, wasm }
-    }
-
-    fn new_random_case(_host: &Host, rng: &mut StdRng, _input: u64) -> Self {
-        let id: xdr::Hash = [0; 32].into();
-        let wasm = match rng.gen_range(0, 9) {
-            0 => soroban_test_wasms::ADD_I32,
-            1 => soroban_test_wasms::COMPLEX,
-            2 => soroban_test_wasms::CONTRACT_DATA,
-            3 => soroban_test_wasms::CREATE_CONTRACT,
-            4 => soroban_test_wasms::FANNKUCH,
-            5 => soroban_test_wasms::FIB,
-            6 => soroban_test_wasms::HOSTILE,
-            7 => soroban_test_wasms::LINEAR_MEMORY,
-            8 => soroban_test_wasms::VEC,
-            _ => unreachable!(),
-        };
-        let wasm: Vec<u8> = wasm.clone().into();
-        Self { id, wasm }
-    }
-
-    fn get_input(&self, _host: &Host) -> u64 {
-        self.wasm.len() as u64
-    }
-
-    fn run(&mut self, _iter: u64, host: &Host) {
-        Vm::new(host, self.id.clone(), &self.wasm[..]).unwrap();
-    }
-}
diff --git a/soroban-env-host/benches/common/cost_types/vm_ops.rs b/soroban-env-host/benches/common/cost_types/vm_ops.rs
new file mode 100644
index 00000000..c176cf8b
--- /dev/null
+++ b/soroban-env-host/benches/common/cost_types/vm_ops.rs
@@ -0,0 +1,81 @@
+use crate::common::HostCostMeasurement;
+use rand::{rngs::StdRng, Rng, RngCore};
+use soroban_env_host::{
+    cost_runner::{VmInstantiationRun, VmInstantiationSample, VmMemReadRun, VmMemWriteRun},
+    xdr, Host, Vm,
+};
+use std::rc::Rc;
+
+pub(crate) struct VmInstantiationMeasure;
+
+// This measures the cost of instantiating a host::Vm on a variety of possible
+// wasm modules, of different sizes. The input value should be the size of the
+// module, though for now we're just selecting modules from the fixed example
+// repertoire. Costs should be linear.
+impl HostCostMeasurement for VmInstantiationMeasure {
+    type Runner = VmInstantiationRun;
+
+    fn new_best_case(_host: &Host, _rng: &mut StdRng) -> VmInstantiationSample {
+        let id: xdr::Hash = [0; 32].into();
+        let wasm: Vec<u8> = soroban_test_wasms::ADD_I32.clone().into();
+        VmInstantiationSample { id, wasm }
+    }
+
+    fn new_worst_case(_host: &Host, _rng: &mut StdRng, _input: u64) -> VmInstantiationSample {
+        let id: xdr::Hash = [0; 32].into();
+        let wasm: Vec<u8> = soroban_test_wasms::COMPLEX.clone().into();
+        VmInstantiationSample { id, wasm }
+    }
+
+    fn new_random_case(_host: &Host, rng: &mut StdRng, _input: u64) -> VmInstantiationSample {
+        let id: xdr::Hash = [0; 32].into();
+        let wasm = match rng.gen_range(0, 9) {
+            0 => soroban_test_wasms::ADD_I32,
+            1 => soroban_test_wasms::COMPLEX,
+            2 => soroban_test_wasms::CONTRACT_DATA,
+            3 => soroban_test_wasms::CREATE_CONTRACT,
+            4 => soroban_test_wasms::FANNKUCH,
+            5 => soroban_test_wasms::FIB,
+            6 => soroban_test_wasms::HOSTILE,
+            7 => soroban_test_wasms::LINEAR_MEMORY,
+            8 => soroban_test_wasms::VEC,
+            _ => unreachable!(),
+        };
+        let wasm: Vec<u8> = wasm.clone().into();
+        VmInstantiationSample { id, wasm }
+    }
+}
+
+// Measures the cost of reading a slice of VM linear memory into a buffer.
+// Input is bytes to read. CPU and memory cost should both be linear.
+// TODO: does this run grow memory if the input exceeds 64kB?
+pub(crate) struct VmMemReadMeasure;
+impl HostCostMeasurement for VmMemReadMeasure {
+    type Runner = VmMemReadRun;
+
+    fn new_random_case(host: &Host, _rng: &mut StdRng, input: u64) -> (Rc<Vm>, usize) {
+        let input = (input * 1000) as usize;
+        let id: xdr::Hash = [0; 32].into();
+        let code = soroban_test_wasms::ADD_I32;
+        let vm = Vm::new(&host, id, &code).unwrap();
+        (vm, input)
+    }
+}
+
+// Measures the cost of writing into a slice of VM linear memory.
+// Input is bytes to write. CPU and memory cost should both be linear.
+// TODO: does this run grow memory if the input exceeds 64kB?
+pub(crate) struct VmMemWriteMeasure;
+impl HostCostMeasurement for VmMemWriteMeasure {
+    type Runner = VmMemWriteRun;
+
+    fn new_random_case(host: &Host, rng: &mut StdRng, input: u64) -> (Rc<Vm>, Vec<u8>) {
+        let input = (input * 1000) as usize;
+        let mut buf = vec![0; input];
+        rng.fill_bytes(buf.as_mut_slice());
+        let id: xdr::Hash = [0; 32].into();
+        let code = soroban_test_wasms::ADD_I32;
+        let vm = Vm::new(&host, id, &code).unwrap();
+        (vm, buf)
+    }
+}
diff --git a/soroban-env-host/benches/common/cost_types/wasm_insn_exec.rs b/soroban-env-host/benches/common/cost_types/wasm_insn_exec.rs
index 298a0759..e5d463e2 100644
--- a/soroban-env-host/benches/common/cost_types/wasm_insn_exec.rs
+++ b/soroban-env-host/benches/common/cost_types/wasm_insn_exec.rs
@@ -1,10 +1,11 @@
 use crate::common::HostCostMeasurement;
 use rand::rngs::StdRng;
-use soroban_env_host::budget::CostType;
-use soroban_env_host::xdr::{Hash, ScVal, ScVec};
-use soroban_env_host::{Host, Symbol, Vm};
-use soroban_synth_wasm::{Arity, ModEmitter, Operand};
-use std::rc::Rc;
+use soroban_env_host::{
+    cost_runner::{WasmInsnExecRun, WasmInsnExecSample, WasmMemAllocRun},
+    xdr::{Hash, ScVal, ScVec},
+    Host, Symbol, Vm,
+};
+use soroban_synth_wasm::{Arity, LocalRef, ModEmitter, Operand};
 
 fn wasm_module_with_4n_insns(n: usize) -> Vec<u8> {
     let mut fe = ModEmitter::new().func(Arity(1), 0);
@@ -21,33 +22,51 @@ fn wasm_module_with_4n_insns(n: usize) -> Vec<u8> {
     fe.finish_and_export("test").finish()
 }
 
-pub(crate) struct WasmInsnExecRun {
-    insns: u64,
-    args: ScVec,
-    vm: Rc<Vm>,
+fn wasm_module_with_mem_grow(n_pages: usize) -> Vec<u8> {
+    let mut fe = ModEmitter::new().func(Arity(0), 0);
+    fe.push(Operand::Const32(n_pages as i32));
+    fe.mem_grow(LocalRef(0));
+    // need to drop the return value on the stack because it's an i32
+    // and the function needs an i64 return value.
+    fe.drop();
+    fe.push(Symbol::from_str("pass"));
+    fe.finish_and_export("test").finish()
 }
 
+pub(crate) struct WasmInsnExecMeasure;
+
 // This measures the cost of executing a block of WASM instructions. The
 // input value is the length of the instruction block. The CPU cost should
 // be linear in the length and the memory should be zero.
-impl HostCostMeasurement for WasmInsnExecRun {
-    const COST_TYPE: CostType = CostType::WasmInsnExec;
+impl HostCostMeasurement for WasmInsnExecMeasure {
+    type Runner = WasmInsnExecRun;
 
-    fn new_random_case(host: &Host, _rng: &mut StdRng, step: u64) -> Self {
+    fn new_random_case(host: &Host, _rng: &mut StdRng, step: u64) -> WasmInsnExecSample {
         let insns = step * 1000;
         let args = ScVec(vec![ScVal::U63(5)].try_into().unwrap());
         let id: Hash = [0; 32].into();
         let code = wasm_module_with_4n_insns(insns as usize);
         let vm = Vm::new(&host, id, &code).unwrap();
-        Self { insns, args, vm }
+        WasmInsnExecSample { insns, args, vm }
     }
+}
 
-    fn get_input(&self, _host: &Host) -> u64 {
-        self.insns * 4
-    }
+// Measures the cost of growing VM's linear memory. The input value is the number of pages
+// to grow the memory by, where each pages is 64kB (65536). The memory cost should
+// be linear and the CPU cost should be constant.
+pub(crate) struct WasmMemAllocMeasure;
+impl HostCostMeasurement for WasmMemAllocMeasure {
+    type Runner = WasmMemAllocRun;
 
-    fn run(&mut self, _iter: u64, host: &Host) {
-        let scval = self.vm.invoke_function(host, "test", &self.args).unwrap();
-        assert_eq!(scval, ScVal::Symbol("pass".try_into().unwrap()));
+    fn new_random_case(
+        host: &Host,
+        _rng: &mut StdRng,
+        input: u64,
+    ) -> <Self::Runner as soroban_env_host::cost_runner::CostRunner>::SampleType {
+        let n_pages = input as usize;
+        let id: Hash = [0; 32].into();
+        let code = wasm_module_with_mem_grow(n_pages);
+        let vm = Vm::new(&host, id, &code).unwrap();
+        (vm, n_pages)
     }
 }
diff --git a/soroban-env-host/benches/common/measure.rs b/soroban-env-host/benches/common/measure.rs
index 0f0cbe40..9b4f0322 100644
--- a/soroban-env-host/benches/common/measure.rs
+++ b/soroban-env-host/benches/common/measure.rs
@@ -1,5 +1,5 @@
 use rand::{rngs::StdRng, Rng, SeedableRng};
-use soroban_env_host::{budget::CostType, Host};
+use soroban_env_host::{cost_runner::CostRunner, Host};
 use std::{
     alloc::System,
     ops::Range,
@@ -30,15 +30,21 @@ impl AllocationTracker for MemTracker {
         self.0.fetch_add(wrapped_input as u64, Ordering::SeqCst);
     }
 
+    // We do not count memory deallocation because we are trying to estimate the worst-case
+    // memory cost under a variety of possible memory allocation models. This mimics the arena
+    // model, where memory deallocations do not happen until the very end. This is not perfect
+    // as any transient objects are counted as actual memory cost, but it is the worst-case
+    // estimate.
     fn deallocated(
         &self,
         _addr: usize,
         _object_input: usize,
-        wrapped_input: usize,
+        _wrapped_input: usize,
         _source_group_id: tracking_allocator::AllocationGroupId,
         _current_group_id: tracking_allocator::AllocationGroupId,
     ) {
-        self.0.fetch_sub(wrapped_input as u64, Ordering::SeqCst);
+        // No-Op, see comment above.
+        ()
     }
 }
 
@@ -181,14 +187,8 @@ impl Measurements {
 /// HostCostMeasurement is an interface to measuring the memory and CPU
 /// costs of a CostType: usually a block of WASM bytecode or a host function.
 pub trait HostCostMeasurement: Sized {
-    /// The type of cost we're measuring.
-    const COST_TYPE: CostType;
-
-    /// Number of times the harness calls `run`, used to divide the resulting
-    /// measured values. Defaults to 1 but if you find your measurements are
-    /// finishing too fast and you're getting noise or zero-sized measurements,
-    /// set to some larger value and then use in a loop inside `run`.
-    const RUN_ITERATIONS: u64 = 1;
+    /// The type of host runner we're using. Uniquely identifies a `CostType`.
+    type Runner: CostRunner;
 
     /// Initialize a new instance of a HostMeasurement at a given input _hint_, for
     /// the run; the HostMeasurement can choose a precise input for a given hint
@@ -197,29 +197,32 @@ pub trait HostCostMeasurement: Sized {
     ///
     /// All setup should happen in the `new` function here; `run` should be
     /// reserved for the "actual event" you're trying to measure.
-    fn new_random_case(host: &Host, rng: &mut StdRng, input: u64) -> Self;
+    fn new_random_case(
+        host: &Host,
+        rng: &mut StdRng,
+        input: u64,
+    ) -> <Self::Runner as CostRunner>::SampleType;
 
     /// Initialize a best-case (cheapest) instance. Defaults to random with input=1.
-    fn new_best_case(host: &Host, rng: &mut StdRng) -> Self {
+    fn new_best_case(host: &Host, rng: &mut StdRng) -> <Self::Runner as CostRunner>::SampleType {
         Self::new_random_case(host, rng, 1)
     }
 
     /// Initialize a worst-case (most-expensive) instance at a given size. Defaults to random.
-    fn new_worst_case(host: &Host, rng: &mut StdRng, input: u64) -> Self {
+    fn new_worst_case(
+        host: &Host,
+        rng: &mut StdRng,
+        input: u64,
+    ) -> <Self::Runner as CostRunner>::SampleType {
         Self::new_random_case(host, rng, input)
     }
 
-    /// Run the HostMeasurement. This method is called under CPU-and-memory tracking
-    /// machinery, so anything that happens during it will be considered part of
-    /// the cost for running the HostMeasurement at the returned input. Will be
-    /// called with iter set to each number in 0..RUN_ITERATIONS.
-    fn run(&mut self, iter: u64, host: &Host);
+    fn run(host: &Host, sample: Vec<<Self::Runner as CostRunner>::SampleType>) {
+        <Self::Runner as CostRunner>::run(host, sample)
+    }
 
-    /// Return the _actual_ input chosen, rather than the hint passed to `new`.
-    /// Defaults to asking the host, which you might need to override if the host
-    /// was not actually involved in the measurement.
-    fn get_input(&self, host: &Host) -> u64 {
-        host.with_budget(|budget| budget.get_input(Self::COST_TYPE))
+    fn get_total_input(host: &Host, sample: &<Self::Runner as CostRunner>::SampleType) -> u64 {
+        <Self::Runner as CostRunner>::get_total_input(host, sample)
     }
 }
 
@@ -279,10 +282,10 @@ mod cpu {
 }
 
 fn measure_costs_inner<HCM: HostCostMeasurement, F>(
-    mut next_hcm: F,
+    mut next_sample: F,
 ) -> Result<Measurements, std::io::Error>
 where
-    F: FnMut(&Host) -> Option<HCM>,
+    F: FnMut(&Host) -> Option<<HCM::Runner as CostRunner>::SampleType>,
 {
     let mut cpu_insn_counter = cpu::InstructionCounter::new();
     let mem_tracker = MemTracker(Arc::new(AtomicU64::new(0)));
@@ -292,34 +295,40 @@ where
     let mut alloc_group_token =
         AllocationGroupToken::register().expect("failed to register allocation group");
     let mut ret = Vec::new();
-    eprintln!("\nMeasuring costs for CostType::{:?}\n", HCM::COST_TYPE);
+    eprintln!(
+        "\nMeasuring costs for CostType::{:?}\n",
+        <HCM::Runner as CostRunner>::COST_TYPE
+    );
     loop {
+        // prepare the measurement
         let host = Host::default();
         host.with_budget(|budget| budget.reset_unlimited());
-        let mut m = match next_hcm(&host) {
-            Some(m) => m,
+        let sample = match next_sample(&host) {
+            Some(s) => s,
             None => break,
         };
+        let iterations = <HCM::Runner as CostRunner>::RUN_ITERATIONS;
+        let mvec = (0..iterations).map(|_| sample.clone()).collect();
+        // start the cpu and mem measurement
         let start = Instant::now();
         mem_tracker.0.store(0, Ordering::SeqCst);
         let alloc_guard = alloc_group_token.enter();
         host.with_budget(|budget| budget.reset_inputs());
         cpu_insn_counter.begin();
-        for iter in 0..HCM::RUN_ITERATIONS {
-            m.run(iter, &host);
-        }
-        let cpu_insns = cpu_insn_counter.end_and_count() / HCM::RUN_ITERATIONS;
+        HCM::run(&host, mvec);
+        // collect the metrics
+        let cpu_insns = cpu_insn_counter.end_and_count() / iterations;
         drop(alloc_guard);
         let stop = Instant::now();
-        let input = m.get_input(&host) / HCM::RUN_ITERATIONS;
-        let mem_bytes = mem_tracker.0.load(Ordering::SeqCst) / HCM::RUN_ITERATIONS;
-        let time_nsecs = stop.duration_since(start).as_nanos() as u64 / HCM::RUN_ITERATIONS;
+        let input = HCM::get_total_input(&host, &sample) / iterations;
+        let mem_bytes = mem_tracker.0.load(Ordering::SeqCst) / iterations;
+        let time_nsecs = stop.duration_since(start).as_nanos() as u64 / iterations;
         ret.push(Measurement {
             input,
             cpu_insns,
             mem_bytes,
             time_nsecs,
-        })
+        });
     }
     AllocationRegistry::disable_tracking();
     unsafe {
diff --git a/soroban-env-host/benches/common/mod.rs b/soroban-env-host/benches/common/mod.rs
index 01926d00..15173e26 100644
--- a/soroban-env-host/benches/common/mod.rs
+++ b/soroban-env-host/benches/common/mod.rs
@@ -3,7 +3,116 @@
 mod cost_types;
 mod measure;
 mod modelfit;
+mod util;
 
-pub use cost_types::{for_each_host_cost_measurement, Benchmark};
+use cost_types::*;
 pub use measure::*;
 pub use modelfit::*;
+
+use soroban_env_host::{budget::CostType, cost_runner::CostRunner};
+use std::collections::BTreeSet;
+
+pub(crate) trait Benchmark {
+    fn bench<HCM: HostCostMeasurement>() -> std::io::Result<()>;
+}
+
+fn get_explicit_bench_names() -> Option<Vec<String>> {
+    let bare_args: Vec<_> = std::env::args().filter(|x| !x.starts_with("-")).collect();
+    match bare_args.len() {
+        0 | 1 => None,
+        _ => Some(bare_args[1..].into()),
+    }
+}
+
+fn should_run<HCM: HostCostMeasurement>() -> bool {
+    if let Some(bench_names) = get_explicit_bench_names() {
+        let name = format!("{:?}", <HCM::Runner as CostRunner>::COST_TYPE)
+            .split("::")
+            .last()
+            .unwrap()
+            .to_string();
+        bench_names.into_iter().find(|arg| *arg == name).is_some()
+    } else {
+        true
+    }
+}
+
+fn call_bench<B: Benchmark, HCM: HostCostMeasurement>(
+    costs: &mut BTreeSet<CostType>,
+) -> std::io::Result<()> {
+    if should_run::<HCM>() {
+        B::bench::<HCM>()?;
+        costs.insert(<HCM::Runner as CostRunner>::COST_TYPE);
+    }
+    Ok(())
+}
+
+pub(crate) fn for_each_host_cost_measurement<B: Benchmark>() -> std::io::Result<()> {
+    let mut costs: BTreeSet<CostType> = BTreeSet::new();
+
+    call_bench::<B, ComputeEd25519PubKeyMeasure>(&mut costs)?;
+    call_bench::<B, ComputeSha256HashMeasure>(&mut costs)?;
+    call_bench::<B, Ed25519ScalarMulMeasure>(&mut costs)?;
+    call_bench::<B, ScMapToHostMapMeasure>(&mut costs)?;
+    call_bench::<B, ScVecToHostVecMeasure>(&mut costs)?;
+    call_bench::<B, VerifyEd25519SigMeasure>(&mut costs)?;
+    call_bench::<B, VmInstantiationMeasure>(&mut costs)?;
+    call_bench::<B, VmMemReadMeasure>(&mut costs)?;
+    call_bench::<B, VmMemWriteMeasure>(&mut costs)?;
+    call_bench::<B, WasmInsnExecMeasure>(&mut costs)?;
+    call_bench::<B, WasmMemAllocMeasure>(&mut costs)?;
+    call_bench::<B, CreateRecordDebugEventMeasure>(&mut costs)?;
+    call_bench::<B, RecordContractEventMeasure>(&mut costs)?;
+    call_bench::<B, VisitObjectMeasure>(&mut costs)?;
+    call_bench::<B, GuardFrameMeasure>(&mut costs)?;
+    call_bench::<B, ValXdrConvMeasure>(&mut costs)?;
+    call_bench::<B, ValSerMeasure>(&mut costs)?;
+    call_bench::<B, ValDeserMeasure>(&mut costs)?;
+    call_bench::<B, HostObjAllocSlotMeasure>(&mut costs)?;
+    call_bench::<B, BigIntNewMeasure>(&mut costs)?;
+    call_bench::<B, BigIntAddSubMeasure>(&mut costs)?;
+    call_bench::<B, BigIntMulMeasure>(&mut costs)?;
+    call_bench::<B, BigIntDivRemMeasure>(&mut costs)?;
+    call_bench::<B, BigIntBitwiseOpMeasure>(&mut costs)?;
+    call_bench::<B, BigIntShiftMeasure>(&mut costs)?;
+    call_bench::<B, BigIntCmpMeasure>(&mut costs)?;
+    call_bench::<B, BigIntGcdLcmMeasure>(&mut costs)?;
+    call_bench::<B, BigIntPowMeasure>(&mut costs)?;
+    call_bench::<B, BigIntPowModMeasure>(&mut costs)?;
+    call_bench::<B, BigIntSqrtMeasure>(&mut costs)?;
+    call_bench::<B, BigIntFromBytesMeasure>(&mut costs)?;
+    call_bench::<B, BigIntToBytesMeasure>(&mut costs)?;
+    call_bench::<B, BigIntToRadixMeasure>(&mut costs)?;
+    call_bench::<B, ImMapNewMeasure>(&mut costs)?;
+    call_bench::<B, ImMapImmutEntryMeasure>(&mut costs)?;
+    call_bench::<B, ImMapMutEntryMeasure>(&mut costs)?;
+    call_bench::<B, ImMapCmpMeasure>(&mut costs)?;
+    call_bench::<B, ImVecNewMeasure>(&mut costs)?;
+    call_bench::<B, ImVecImmutEntryMeasure>(&mut costs)?;
+    call_bench::<B, ImVecMutEntryMeasure>(&mut costs)?;
+    call_bench::<B, ImVecCmpMeasure>(&mut costs)?;
+    call_bench::<B, BytesAppendMeasure>(&mut costs)?;
+    call_bench::<B, BytesCmpMeasure>(&mut costs)?;
+    call_bench::<B, BytesCloneMeasure>(&mut costs)?;
+    call_bench::<B, BytesDelMeasure>(&mut costs)?;
+    call_bench::<B, BytesInsertMeasure>(&mut costs)?;
+    call_bench::<B, BytesPopMeasure>(&mut costs)?;
+    call_bench::<B, BytesPushMeasure>(&mut costs)?;
+    call_bench::<B, InvokeVmFunctionMeasure>(&mut costs)?;
+    call_bench::<B, InvokeHostFunctionMeasure>(&mut costs)?;
+    call_bench::<B, ChargeBudgetMeasure>(&mut costs)?;
+
+    if get_explicit_bench_names().is_none() {
+        for cost in CostType::variants() {
+            if !costs.contains(cost) {
+                eprintln!("warning: missing cost measurement for {:?}", cost);
+            }
+        }
+        // Missing because we need some kind of size limits:
+        // CloneEvents
+        // ScVecFromHostVec
+        // ScMapFromHostMap
+        // Storage related: need to know the size limit of keys which are LedgerKeys
+    }
+    Ok(())
+}
diff --git a/soroban-env-host/benches/common/util.rs b/soroban-env-host/benches/common/util.rs
new file mode 100644
index 00000000..74895a6d
--- /dev/null
+++ b/soroban-env-host/benches/common/util.rs
@@ -0,0 +1,63 @@
+use im_rc::{OrdMap, Vector};
+use num_bigint::{BigInt, Sign};
+use rand::{rngs::StdRng, Rng, RngCore};
+use soroban_env_host::{EnvVal, Host, RawVal};
+
+type HostVal = EnvVal<Host, RawVal>;
+
+pub(crate) fn to_envval_u32<I: Iterator<Item = u32>>(
+    host: &Host,
+    vals: I,
+) -> impl Iterator<Item = HostVal> {
+    let host = host.clone();
+    vals.map(move |v| EnvVal {
+        env: host.clone(),
+        val: RawVal::from_u32(v),
+    })
+}
+
+pub(crate) fn repeating_byte_bigint(byte: u8, input: u64) -> BigInt {
+    let buf: Vec<u8> = (0..input / 8).map(|_| byte).collect();
+    let a = BigInt::from_bytes_be(Sign::Plus, &buf);
+    let one: BigInt = 1.into();
+    a + one
+}
+
+pub(crate) fn random_bigint(rng: &mut StdRng, input: u64) -> BigInt {
+    let buf: Vec<u8> = (0..input / 8).map(|_| rng.gen::<u8>()).collect();
+    let a = BigInt::from_bytes_be(Sign::Plus, &buf);
+    let one: BigInt = 1.into();
+    a + one
+}
+
+pub(crate) fn random_ord_map(
+    host: &Host,
+    rng: &mut StdRng,
+    input: u64,
+) -> OrdMap<HostVal, HostVal> {
+    let mut kv: Vec<(HostVal, HostVal)> = Vec::with_capacity(input as usize);
+    for _i in 0..input {
+        let k = EnvVal {
+            env: host.clone(),
+            val: RawVal::from_u32(rng.next_u32()),
+        };
+        let v = EnvVal {
+            env: host.clone(),
+            val: RawVal::from_u32(rng.next_u32()),
+        };
+        kv.push((k, v));
+    }
+    kv.into()
+}
+
+pub(crate) fn random_im_vector(host: &Host, rng: &mut StdRng, input: u64) -> Vector<HostVal> {
+    let mut res: Vector<HostVal> = Vector::new();
+    for _i in 0..input {
+        let v = EnvVal {
+            env: host.clone(),
+            val: RawVal::from_u32(rng.next_u32()),
+        };
+        res.push_back(v)
+    }
+    res
+}
diff --git a/soroban-env-host/src/budget.rs b/soroban-env-host/src/budget.rs
index a6e497b5..be6de4ca 100644
--- a/soroban-env-host/src/budget.rs
+++ b/soroban-env-host/src/budget.rs
@@ -11,144 +11,124 @@ use crate::{xdr::ScVmErrorCode, HostError};
 pub enum CostType {
     // Cost of running 1 wasm interpreter loop
     WasmInsnExec = 0,
+    // Cost of growing wasm linear memory by 1 page
     WasmMemAlloc = 1,
     // Cost of forming a debug event and pushing it into the event storage
     HostEventDebug = 2,
-    // Cost of forming a contract event and pushing it into the event storage
+    // Cost of pushing a contract event it into the event storage
     HostEventContract = 3,
     // Cost of a host function invocation, not including the actual work done by the function
-    HostFunction = 4,
+    InvokeHostFunction = 4,
     // Cost of visiting a host object from the host object storage
+    // TODO: consider removing. This is just indexing into an array. Fixed cost around 400 insns.
+    // Only thing to make sure is the guest can't visitObject repeatly without incurring some charges elsewhere.
     VisitObject = 5,
-    // Cost of pushing a frame into the context
-    PushFrame = 6,
-    // Cost of poping a frame out of the context
-    PopFrame = 7,
     // Tracks a single Val (RawVal or primative Object like U64) <=> ScVal
     // conversion cost. Most of these Val counterparts in ScVal (except e.g.
     // Symbol) consumes a single int64 and therefore is a constant overhead.
-    ValXdrConv = 8,
+    ValXdrConv = 6,
     // Cost of serializing an xdr object to bytes
-    ValSer = 9,
+    ValSer = 7,
     // Cost of deserializing an xdr object from bytes
-    ValDeser = 10,
+    ValDeser = 8,
     // Cost of cloning events
-    CloneEvents = 11,
+    CloneEvents = 9,
     // Cost of occupying a host object slot
-    HostObjAllocSlot = 12,
-    // Cost of pushing a new `Vec` object to the object storage.
-    HostVecAllocCell = 13,
-    // Cost of pushing a new `Map` object to the object storage.
-    HostMapAllocCell = 14,
-    // Cost of pushing a new `U64` object to the object storage.
-    HostU64AllocCell = 15,
-    // Cost of pushing a new `I64` object to the object storage.
-    HostI64AllocCell = 16,
-    // Cost of pushing a new `Bytes` object to the object storage.
-    HostBytesAllocCell = 17,
-    // Cost of pushing a new `BigInt` object to the object storage.
-    HostBigIntAllocCell = 18,
+    HostObjAllocSlot = 10,
     // Cost of computing the sha256 hash from bytes
-    ComputeSha256Hash = 19,
+    ComputeSha256Hash = 11,
     // Cost of computing the ed25519 pubkey from bytes
-    ComputeEd25519PubKey = 20,
+    ComputeEd25519PubKey = 12,
     // Cost of constructing an empty new OrdMap
-    ImMapNew = 21,
+    ImMapNew = 13,
     // Cost of (mutably) accessing an entry in an OrdMap
-    ImMapMutEntry = 22,
+    ImMapMutEntry = 14,
     // Cost of (immutably) accessing an entry in an OrdMap
-    ImMapImmutEntry = 23,
+    ImMapImmutEntry = 15,
+    // Cost of comparison of two OrdMaps
+    ImMapCmp = 16,
     // Cost of constructing an empty new Vector
-    ImVecNew = 24,
+    ImVecNew = 17,
     // Cost of (mutably) accessing an entry in a Vector
-    ImVecMutEntry = 25,
+    ImVecMutEntry = 18,
     // Cost of (immutably) accessing an entry in a Vector
-    ImVecImmutEntry = 26,
+    ImVecImmutEntry = 19,
+    // Cost of comparison of two Vectors
+    ImVecCmp = 20,
+    //TODO: 27-30 are probably redundent.They are covered elsewhere.
     // Cost of work needed to collect elements from a HostVec into a ScVec. This does not account for the
     // conversion of the elements into its ScVal form.
-    ScVecFromHostVec = 27,
+    ScVecFromHostVec = 21,
     // Cost of work needed to collect elements from a HostMap into a ScMap. This does not account for the
     // conversion of the elements into its ScVal form.
-    ScMapFromHostMap = 28,
+    ScMapFromHostMap = 22,
     // Cost of work needed to collect elements from an ScVec into a HostVec. This does not account for the
     // conversion of the elements from its ScVal form.
-    ScVecToHostVec = 29,
+    ScVecToHostVec = 23,
     // Cost of work needed to collect elements from an ScMap into a HostMap. This does not account for the
     // conversion of the elements from its ScVal form.
-    ScMapToHostMap = 30,
+    ScMapToHostMap = 24,
     // Cost of guarding a frame, which involves pushing and poping a frame and capturing a rollback point.
-    GuardFrame = 31,
-    // Cost of cloning a VM.
-    CloneVm = 32,
+    GuardFrame = 25,
     // Cost of verifying ed25519 signature of a payload.
-    VerifyEd25519Sig = 33,
+    VerifyEd25519Sig = 26,
+    //TODO: bigints are to be deprecated
     // Cost of creating a new bigint.
-    BigIntNew = 34,
+    BigIntNew = 27,
     // Cost of bigint's add, sub ops.
-    BigIntAddSub = 35,
+    BigIntAddSub = 28,
     // Cost of bigint's mul op.
-    BigIntMul = 36,
+    BigIntMul = 29,
     // Cost of bigint's div and rem ops.
-    BigIntDivRem = 37,
+    BigIntDivRem = 30,
     // Cost of bigint's bitwise ops (and, or, xor).
-    BigIntBitwiseOp = 38,
+    BigIntBitwiseOp = 31,
     // Cost of bigint's shl and shr ops.
-    BigIntShift = 39,
+    BigIntShift = 32,
     // Cost of bigint's cmp op.
-    BigIntCmp = 40,
+    BigIntCmp = 33,
     // Cost of bigint's gcd, lcm ops.
-    BigIntGcdLcm = 41,
+    BigIntGcdLcm = 34,
     // Cost of bigint's pow op.
-    BigIntPow = 42,
+    BigIntPow = 35,
     // Cost of bigint's powmod op.
-    BigIntPowMod = 43,
+    BigIntPowMod = 36,
     // Cost of bigint's sqrt op.
-    BigIntSqrt = 44,
+    BigIntSqrt = 37,
     // Cost of constructing a bigint from bytes.
-    BigIntFromBytes = 45,
+    BigIntFromBytes = 38,
     // Cost of constructing bytes from a bigint.
-    BigIntToBytes = 46,
+    BigIntToBytes = 39,
     // Cost of converting a bigint to a byte array where each byte is a digit in some pre-determined base.
-    BigIntToRadix = 47,
-    // Cost of accessing vm lineary memory
-    VmMemCpy = 48,
+    BigIntToRadix = 40,
+    // Cost of reading a slice of vm linear memory
+    VmMemRead = 41,
+    // Cost of writing to a slice of vm linear memory
+    VmMemWrite = 42,
     // Cost of instantiation a VM from wasm bytes code.
-    VmInstantiation = 49,
-    // The overhead cost of invoking a host function.
-    // TODO: this is somewhat duplicate from HostFunction
-    VmInvokeFunction = 50,
+    VmInstantiation = 43,
+    // Roundtrip cost of invoking a VM function from the host.
+    InvokeVmFunction = 44,
     // Cost of cloning bytes.
-    BytesClone = 51,
+    BytesClone = 45,
     // Cost of deleting a byte from a bytes array,
-    BytesDel = 52,
+    BytesDel = 46,
     // Cost of pushing a byte
-    BytesPush = 53,
+    BytesPush = 47,
     // Cost of poping a byte
-    BytesPop = 54,
+    BytesPop = 48,
     // Cost of inserting a byte into a bytes array at some index
-    BytesInsert = 55,
+    BytesInsert = 49,
     // Cost of appending a byte to the end of a bytes array
-    BytesAppend = 56,
-    // Cost of slicing a bytes array
-    BytesSlice = 57,
-    // Cost of concatenating two bytes arrays
-    BytesConcat = 58,
-    // Cost of unpacking args from a HostVec into a Vec<RawVal>
-    CallArgsUnpack = 59,
+    BytesAppend = 50,
+    // Cost of comparing two bytes arrays
+    BytesCmp = 51,
     // Cost of charging a value to the budgeting system.
-    ChargeBudget = 60,
-    // TODO: reshuffle to bring the "AllocCell" types together
-    // Cost of pushing a new `ContractCode` object to the object storage.
-    HostContractCodeAllocCell = 61,
-    // Cost of pushing a new `AccountId` object to the object storage.
-    HostAccountIdAllocCell = 62,
-    ImMapCmp = 63,
-    ImVecCmp = 64,
-    BytesCmp = 65,
+    ChargeBudget = 52,
     // Cost of a 25519 scalar multiplication in the Ed25519 library,
     // here for exploring calibration, not a long-term cost we surface
     // separately from signature verification.
-    EdwardsPointCurve25519ScalarMul = 66,
+    EdwardsPointCurve25519ScalarMul = 53,
 }
 
 // TODO: add XDR support for iterating over all the elements of an enum
@@ -159,35 +139,28 @@ impl CostType {
             CostType::WasmMemAlloc,
             CostType::HostEventDebug,
             CostType::HostEventContract,
-            CostType::HostFunction,
+            CostType::InvokeHostFunction,
             CostType::VisitObject,
-            CostType::PushFrame,
-            CostType::PopFrame,
             CostType::ValXdrConv,
             CostType::ValSer,
             CostType::ValDeser,
             CostType::CloneEvents,
             CostType::HostObjAllocSlot,
-            CostType::HostVecAllocCell,
-            CostType::HostMapAllocCell,
-            CostType::HostU64AllocCell,
-            CostType::HostI64AllocCell,
-            CostType::HostBytesAllocCell,
-            CostType::HostBigIntAllocCell,
             CostType::ComputeSha256Hash,
             CostType::ComputeEd25519PubKey,
             CostType::ImMapNew,
             CostType::ImMapMutEntry,
             CostType::ImMapImmutEntry,
+            CostType::ImMapCmp,
             CostType::ImVecNew,
             CostType::ImVecMutEntry,
             CostType::ImVecImmutEntry,
+            CostType::ImVecCmp,
             CostType::ScVecFromHostVec,
             CostType::ScMapFromHostMap,
             CostType::ScVecToHostVec,
             CostType::ScMapToHostMap,
             CostType::GuardFrame,
-            CostType::CloneVm,
             CostType::VerifyEd25519Sig,
             CostType::BigIntNew,
             CostType::BigIntAddSub,
@@ -203,24 +176,18 @@ impl CostType {
             CostType::BigIntFromBytes,
             CostType::BigIntToBytes,
             CostType::BigIntToRadix,
-            CostType::VmMemCpy,
+            CostType::VmMemRead,
+            CostType::VmMemWrite,
             CostType::VmInstantiation,
-            CostType::VmInvokeFunction,
+            CostType::InvokeVmFunction,
             CostType::BytesClone,
             CostType::BytesDel,
             CostType::BytesPush,
             CostType::BytesPop,
             CostType::BytesInsert,
             CostType::BytesAppend,
-            CostType::BytesSlice,
-            CostType::BytesConcat,
-            CostType::CallArgsUnpack,
-            CostType::ChargeBudget,
-            CostType::HostContractCodeAllocCell,
-            CostType::HostAccountIdAllocCell,
-            CostType::ImMapCmp,
-            CostType::ImVecCmp,
             CostType::BytesCmp,
+            CostType::ChargeBudget,
             CostType::EdwardsPointCurve25519ScalarMul,
         ];
         VARIANTS.iter()
@@ -525,24 +492,13 @@ impl Default for BudgetImpl {
                 // this and some are much less.
                 CostType::WasmInsnExec => cpu.lin_param = 32,
                 CostType::WasmMemAlloc => cpu.lin_param = 1000,
-                CostType::HostEventDebug | CostType::HostEventContract | CostType::HostFunction => {
-                    cpu.const_param = 1000
-                }
-                CostType::VisitObject | CostType::PushFrame | CostType::PopFrame => {
-                    cpu.const_param = 100
-                }
+                CostType::HostEventDebug
+                | CostType::HostEventContract
+                | CostType::InvokeHostFunction => cpu.const_param = 1000,
+                CostType::VisitObject => cpu.const_param = 100,
                 CostType::ValXdrConv | CostType::ValSer | CostType::ValDeser => cpu.lin_param = 10,
                 CostType::CloneEvents => cpu.lin_param = 10,
                 CostType::HostObjAllocSlot => cpu.const_param = 1000,
-                CostType::HostVecAllocCell => cpu.lin_param = 300,
-                CostType::HostMapAllocCell => {
-                    cpu.const_param = 2000;
-                    cpu.log_base_param = 64;
-                    cpu.log_param = 1;
-                }
-                CostType::HostU64AllocCell | CostType::HostI64AllocCell => (), // counted in HostObjAllocSlot
-                CostType::HostBytesAllocCell => cpu.lin_param = 10,
-                CostType::HostBigIntAllocCell => cpu.lin_param = 10,
 
                 CostType::ComputeSha256Hash => {
                     cpu.const_param = 3000;
@@ -561,15 +517,16 @@ impl Default for BudgetImpl {
                     cpu.log_base_param = 64;
                     cpu.log_param = 10;
                 }
+                CostType::ImMapCmp => cpu.lin_param = 10,
 
                 CostType::ImVecNew => cpu.const_param = 1500,
                 CostType::ImVecMutEntry | CostType::ImVecImmutEntry => cpu.const_param = 300,
+                CostType::ImVecCmp => cpu.lin_param = 10,
                 CostType::ScVecFromHostVec => cpu.lin_param = 10,
                 CostType::ScMapFromHostMap => cpu.lin_param = 10,
                 CostType::ScVecToHostVec => cpu.lin_param = 300,
                 CostType::ScMapToHostMap => cpu.lin_param = 2500,
                 CostType::GuardFrame => cpu.lin_param = 10,
-                CostType::CloneVm => cpu.const_param = 1000,
 
                 CostType::BigIntNew
                 | CostType::BigIntAddSub
@@ -588,24 +545,18 @@ impl Default for BudgetImpl {
                 CostType::BigIntToBytes => cpu.lin_param = 10,
                 CostType::BigIntToRadix => cpu.lin_param = 10,
 
-                CostType::VmMemCpy => cpu.lin_param = 10,
+                CostType::VmMemRead => cpu.lin_param = 10,
+                CostType::VmMemWrite => cpu.lin_param = 10,
                 CostType::VmInstantiation => cpu.const_param = 100_000,
-                CostType::VmInvokeFunction => cpu.const_param = 10_000,
+                CostType::InvokeVmFunction => cpu.const_param = 10_000,
                 CostType::BytesClone
                 | CostType::BytesDel
                 | CostType::BytesPush
                 | CostType::BytesPop
                 | CostType::BytesInsert
-                | CostType::BytesAppend
-                | CostType::BytesSlice
-                | CostType::BytesConcat => cpu.lin_param = 10,
-                CostType::CallArgsUnpack => cpu.lin_param = 10,
-                CostType::ChargeBudget => cpu.const_param = 50,
-                CostType::HostContractCodeAllocCell => cpu.lin_param = 10,
-                CostType::HostAccountIdAllocCell => cpu.lin_param = 320,
-                CostType::ImMapCmp => cpu.lin_param = 10,
-                CostType::ImVecCmp => cpu.lin_param = 10,
+                | CostType::BytesAppend => cpu.lin_param = 10,
                 CostType::BytesCmp => cpu.lin_param = 10,
+                CostType::ChargeBudget => cpu.const_param = 50,
                 CostType::EdwardsPointCurve25519ScalarMul => cpu.const_param = 10,
             }
 
@@ -614,29 +565,22 @@ impl Default for BudgetImpl {
                 CostType::WasmInsnExec => (),
                 CostType::WasmMemAlloc => mem.lin_param = 1,
                 CostType::HostEventDebug | CostType::HostEventContract => mem.const_param = 100,
-                CostType::HostFunction
-                | CostType::VisitObject
-                | CostType::PushFrame
-                | CostType::PopFrame => mem.const_param = 100,
+                CostType::InvokeHostFunction | CostType::VisitObject => mem.const_param = 100,
                 CostType::ValXdrConv | CostType::ValSer | CostType::ValDeser => mem.lin_param = 1,
                 CostType::CloneEvents => mem.lin_param = 100,
                 CostType::HostObjAllocSlot => mem.const_param = 100,
-                CostType::HostVecAllocCell
-                | CostType::HostMapAllocCell
-                | CostType::HostU64AllocCell
-                | CostType::HostI64AllocCell => (), // counted in ObjAllocSlot
-                CostType::HostBytesAllocCell => mem.lin_param = 1,
-                CostType::HostBigIntAllocCell => mem.lin_param = 1,
                 CostType::ComputeSha256Hash | CostType::ComputeEd25519PubKey => (),
                 CostType::ImMapNew => mem.const_param = 3000,
                 CostType::ImMapMutEntry | CostType::ImMapImmutEntry => (),
+                CostType::ImMapCmp => mem.lin_param = 1,
                 CostType::ImVecNew => mem.const_param = 100,
                 CostType::ImVecMutEntry | CostType::ImVecImmutEntry => (),
+                CostType::ImVecCmp => mem.lin_param = 1,
                 CostType::ScVecFromHostVec
                 | CostType::ScMapFromHostMap
                 | CostType::ScVecToHostVec
                 | CostType::ScMapToHostMap => mem.lin_param = 100,
-                CostType::GuardFrame | CostType::CloneVm => mem.const_param = 100,
+                CostType::GuardFrame => mem.const_param = 100,
                 CostType::VerifyEd25519Sig => (),
                 CostType::BigIntNew
                 | CostType::BigIntAddSub
@@ -652,23 +596,18 @@ impl Default for BudgetImpl {
                 | CostType::BigIntFromBytes
                 | CostType::BigIntToBytes
                 | CostType::BigIntToRadix => mem.lin_param = 10,
-                CostType::VmMemCpy
+                CostType::VmMemRead
+                | CostType::VmMemWrite
                 | CostType::VmInstantiation
-                | CostType::VmInvokeFunction
+                | CostType::InvokeVmFunction
                 | CostType::BytesClone
                 | CostType::BytesDel
                 | CostType::BytesPush
                 | CostType::BytesPop
                 | CostType::BytesInsert
-                | CostType::BytesAppend
-                | CostType::BytesSlice
-                | CostType::BytesConcat => mem.lin_param = 1,
-                CostType::CallArgsUnpack | CostType::ChargeBudget => (),
-                CostType::HostContractCodeAllocCell => mem.lin_param = 1,
-                CostType::HostAccountIdAllocCell => mem.lin_param = 32,
-                CostType::ImMapCmp => mem.lin_param = 1,
-                CostType::ImVecCmp => mem.lin_param = 1,
+                | CostType::BytesAppend => mem.lin_param = 1,
                 CostType::BytesCmp => mem.lin_param = 1,
+                CostType::ChargeBudget => (),
                 CostType::EdwardsPointCurve25519ScalarMul => mem.const_param = 1,
             }
         }
diff --git a/soroban-env-host/src/cost_runner/cost_types/bigint_ops.rs b/soroban-env-host/src/cost_runner/cost_types/bigint_ops.rs
new file mode 100644
index 00000000..90688570
--- /dev/null
+++ b/soroban-env-host/src/cost_runner/cost_types/bigint_ops.rs
@@ -0,0 +1,157 @@
+use num_bigint::Sign;
+
+use crate::{
+    budget::CostType, cost_runner::CostRunner, host::metered_cmp::MeteredCmp, MeteredBigInt,
+};
+
+pub struct BigIntNewRun;
+impl CostRunner for BigIntNewRun {
+    const COST_TYPE: CostType = CostType::BigIntNew;
+    type SampleType = u64;
+    const RUN_ITERATIONS: u64 = 1000;
+
+    fn run_iter(host: &crate::Host, _iter: u64, sample: Self::SampleType) {
+        MeteredBigInt::from_u64(host.budget_cloned(), sample).unwrap();
+    }
+}
+
+pub struct BigIntAddSubRun;
+impl CostRunner for BigIntAddSubRun {
+    const COST_TYPE: CostType = CostType::BigIntAddSub;
+    type SampleType = (MeteredBigInt, MeteredBigInt);
+
+    fn run_iter(_host: &crate::Host, _iter: u64, sample: Self::SampleType) {
+        sample.0.add(&sample.1).unwrap();
+    }
+}
+
+pub struct BigIntMulRun;
+impl CostRunner for BigIntMulRun {
+    const COST_TYPE: CostType = CostType::BigIntMul;
+    type SampleType = (MeteredBigInt, MeteredBigInt);
+
+    fn run_iter(_host: &crate::Host, _iter: u64, sample: Self::SampleType) {
+        sample.0.mul(&sample.1).unwrap();
+    }
+}
+
+pub struct BigIntDivRemRun;
+impl CostRunner for BigIntDivRemRun {
+    const COST_TYPE: CostType = CostType::BigIntDivRem;
+    type SampleType = (MeteredBigInt, MeteredBigInt);
+
+    fn run_iter(_host: &crate::Host, _iter: u64, sample: Self::SampleType) {
+        sample.0.div(&sample.1).unwrap();
+    }
+}
+
+pub struct BigIntBitwiseOpRun;
+impl CostRunner for BigIntBitwiseOpRun {
+    const COST_TYPE: CostType = CostType::BigIntBitwiseOp;
+    type SampleType = (MeteredBigInt, MeteredBigInt);
+
+    fn run_iter(_host: &crate::Host, iter: u64, sample: Self::SampleType) {
+        match iter % 3 {
+            0 => sample.0.bitand(&sample.1).unwrap(),
+            1 => sample.0.bitor(&sample.1).unwrap(),
+            2 => sample.0.bitxor(&sample.1).unwrap(),
+            _ => panic!(),
+        };
+    }
+}
+
+pub struct BigIntShiftRun;
+impl CostRunner for BigIntShiftRun {
+    const COST_TYPE: CostType = CostType::BigIntShift;
+    type SampleType = (MeteredBigInt, MeteredBigInt);
+
+    fn run_iter(_host: &crate::Host, _iter: u64, sample: Self::SampleType) {
+        sample.0.shl(&sample.1).unwrap();
+    }
+}
+
+pub struct BigIntCmpRun;
+impl CostRunner for BigIntCmpRun {
+    const COST_TYPE: CostType = CostType::BigIntCmp;
+    type SampleType = (MeteredBigInt, MeteredBigInt);
+
+    fn run_iter(host: &crate::Host, _iter: u64, sample: Self::SampleType) {
+        sample
+            .0
+            .metered_cmp(&sample.1, &host.budget_cloned())
+            .unwrap();
+    }
+}
+
+pub struct BigIntGcdLcmRun;
+impl CostRunner for BigIntGcdLcmRun {
+    const COST_TYPE: CostType = CostType::BigIntGcdLcm;
+    type SampleType = (MeteredBigInt, MeteredBigInt);
+
+    fn run_iter(_host: &crate::Host, _iter: u64, sample: Self::SampleType) {
+        sample.0.lcm(&sample.1).unwrap();
+    }
+}
+
+pub struct BigIntPowRun;
+impl CostRunner for BigIntPowRun {
+    const RUN_ITERATIONS: u64 = 1;
+    const COST_TYPE: CostType = CostType::BigIntPow;
+    type SampleType = (MeteredBigInt, MeteredBigInt);
+
+    fn run_iter(_host: &crate::Host, _iter: u64, sample: Self::SampleType) {
+        sample.0.pow(&sample.1).unwrap();
+    }
+}
+
+pub struct BigIntPowModRun;
+impl CostRunner for BigIntPowModRun {
+    const RUN_ITERATIONS: u64 = 1;
+    const COST_TYPE: CostType = CostType::BigIntPowMod;
+    type SampleType = (MeteredBigInt, MeteredBigInt, MeteredBigInt);
+
+    fn run_iter(_host: &crate::Host, _iter: u64, sample: Self::SampleType) {
+        sample.0.modpow(&sample.1, &sample.2).unwrap();
+    }
+}
+
+pub struct BigIntSqrtRun;
+impl CostRunner for BigIntSqrtRun {
+    const COST_TYPE: CostType = CostType::BigIntSqrt;
+    type SampleType = MeteredBigInt;
+
+    fn run_iter(_host: &crate::Host, _iter: u64, sample: Self::SampleType) {
+        sample.sqrt().unwrap();
+    }
+}
+
+pub struct BigIntFromBytesRun;
+impl CostRunner for BigIntFromBytesRun {
+    const COST_TYPE: CostType = CostType::BigIntFromBytes;
+    type SampleType = Vec<u8>;
+
+    fn run_iter(host: &crate::Host, _iter: u64, sample: Self::SampleType) {
+        MeteredBigInt::from_bytes_be(host.budget_cloned(), Sign::Plus, &sample.as_slice()).unwrap();
+    }
+}
+
+pub struct BigIntToBytesRun;
+impl CostRunner for BigIntToBytesRun {
+    const COST_TYPE: CostType = CostType::BigIntToBytes;
+    type SampleType = MeteredBigInt;
+
+    fn run_iter(_host: &crate::Host, _iter: u64, sample: Self::SampleType) {
+        sample.to_bytes_be().unwrap();
+    }
+}
+
+pub struct BigIntToRadixRun;
+impl CostRunner for BigIntToRadixRun {
+    const COST_TYPE: CostType = CostType::BigIntToRadix;
+    const RUN_ITERATIONS: u64 = 1;
+    type SampleType = (MeteredBigInt, u32);
+
+    fn run_iter(_host: &crate::Host, _iter: u64, sample: Self::SampleType) {
+        sample.0.to_radix_be(sample.1).unwrap();
+    }
+}
diff --git a/soroban-env-host/src/cost_runner/cost_types/bytes_ops.rs b/soroban-env-host/src/cost_runner/cost_types/bytes_ops.rs
new file mode 100644
index 00000000..d97cb12e
--- /dev/null
+++ b/soroban-env-host/src/cost_runner/cost_types/bytes_ops.rs
@@ -0,0 +1,98 @@
+use crate::{
+    budget::CostType,
+    cost_runner::CostRunner,
+    host::{metered_clone::MeteredClone, metered_cmp::MeteredCmp},
+};
+
+pub struct BytesCloneRun;
+impl CostRunner for BytesCloneRun {
+    const COST_TYPE: CostType = CostType::BytesClone;
+    type SampleType = Vec<u8>;
+
+    fn run_iter(host: &crate::Host, _iter: u64, sample: Self::SampleType) {
+        sample.metered_clone(&host.budget_cloned()).unwrap();
+    }
+}
+
+pub struct BytesDelRun;
+impl CostRunner for BytesDelRun {
+    const COST_TYPE: CostType = CostType::BytesDel;
+    type SampleType = (Vec<u8>, usize);
+
+    fn run_iter(_host: &crate::Host, _iter: u64, mut sample: Self::SampleType) {
+        sample.0.remove(sample.1);
+    }
+
+    fn get_total_input(_host: &crate::Host, sample: &Self::SampleType) -> u64 {
+        (sample.0.len() as u64) * Self::RUN_ITERATIONS
+    }
+}
+
+pub struct BytesPushRun;
+impl CostRunner for BytesPushRun {
+    const COST_TYPE: CostType = CostType::BytesPush;
+    type SampleType = Vec<u8>;
+
+    fn run_iter(_host: &crate::Host, iter: u64, mut sample: Self::SampleType) {
+        sample.push(iter as u8);
+    }
+
+    fn get_total_input(_host: &crate::Host, sample: &Self::SampleType) -> u64 {
+        (sample.len() as u64) * Self::RUN_ITERATIONS
+    }
+}
+
+pub struct BytesPopRun;
+impl CostRunner for BytesPopRun {
+    const COST_TYPE: CostType = CostType::BytesPop;
+    type SampleType = Vec<u8>;
+
+    fn run_iter(_host: &crate::Host, _iter: u64, mut sample: Self::SampleType) {
+        sample.pop();
+    }
+
+    fn get_total_input(_host: &crate::Host, sample: &Self::SampleType) -> u64 {
+        (sample.len() as u64) * Self::RUN_ITERATIONS
+    }
+}
+
+pub struct BytesInsertRun;
+impl CostRunner for BytesInsertRun {
+    const COST_TYPE: CostType = CostType::BytesInsert;
+    type SampleType = (Vec<u8>, usize);
+
+    fn run_iter(_host: &crate::Host, iter: u64, mut sample: Self::SampleType) {
+        sample.0.insert(sample.1, iter as u8);
+    }
+
+    fn get_total_input(_host: &crate::Host, sample: &Self::SampleType) -> u64 {
+        (sample.0.len() as u64) * Self::RUN_ITERATIONS
+    }
+}
+
+pub struct BytesAppendRun;
+impl CostRunner for BytesAppendRun {
+    const COST_TYPE: CostType = CostType::BytesAppend;
+    type SampleType = (Vec<u8>, Vec<u8>);
+
+    fn run_iter(_host: &crate::Host, _iter: u64, mut sample: Self::SampleType) {
+        sample.0.append(&mut sample.1);
+    }
+
+    fn get_total_input(_host: &crate::Host, sample: &Self::SampleType) -> u64 {
+        ((sample.0.len() + sample.1.len()) as u64) * Self::RUN_ITERATIONS
+    }
+}
+
+pub struct BytesCmpRun;
+impl CostRunner for BytesCmpRun {
+    const COST_TYPE: CostType = CostType::BytesCmp;
+    type SampleType = (Vec<u8>, Vec<u8>);
+
+    fn run_iter(host: &crate::Host, _iter: u64, sample: Self::SampleType) {
+        sample
+            .0
+            .metered_cmp(&sample.1, &host.budget_cloned())
+            .unwrap();
+    }
+}
diff --git a/soroban-env-host/src/cost_runner/cost_types/charge_budget.rs b/soroban-env-host/src/cost_runner/cost_types/charge_budget.rs
new file mode 100644
index 00000000..f99c57d0
--- /dev/null
+++ b/soroban-env-host/src/cost_runner/cost_types/charge_budget.rs
@@ -0,0 +1,20 @@
+use crate::{budget::Budget, budget::CostType, cost_runner::CostRunner};
+
+pub struct ChargeBudgetRun;
+
+impl CostRunner for ChargeBudgetRun {
+    const COST_TYPE: CostType = CostType::ChargeBudget;
+
+    const RUN_ITERATIONS: u64 = 1000;
+
+    type SampleType = (Budget, u64);
+
+    fn run_iter(_host: &crate::Host, _iter: u64, sample: Self::SampleType) {
+        // The `CostType` here is irrelevant, can pass in any type except `CostType::ChargeBudget`.
+        sample.0.charge(CostType::WasmInsnExec, sample.1).unwrap();
+    }
+
+    fn get_total_input(_host: &crate::Host, _sample: &Self::SampleType) -> u64 {
+        Self::RUN_ITERATIONS
+    }
+}
diff --git a/soroban-env-host/src/cost_runner/cost_types/compute_ed25519_pubkey.rs b/soroban-env-host/src/cost_runner/cost_types/compute_ed25519_pubkey.rs
new file mode 100644
index 00000000..99a46d93
--- /dev/null
+++ b/soroban-env-host/src/cost_runner/cost_types/compute_ed25519_pubkey.rs
@@ -0,0 +1,17 @@
+use crate::{budget::CostType, cost_runner::CostRunner};
+
+pub struct ComputeEd25519PubKeyRun;
+
+impl CostRunner for ComputeEd25519PubKeyRun {
+    const COST_TYPE: CostType = CostType::ComputeEd25519PubKey;
+    type SampleType = Vec<u8>;
+
+    fn run_iter(_host: &crate::Host, _iter: u64, sample: Self::SampleType) {
+        ed25519_dalek::PublicKey::from_bytes(sample.as_slice()).expect("publickey");
+    }
+
+    fn get_total_input(_host: &crate::Host, _sample: &Self::SampleType) -> u64 {
+        // input is ignored
+        Self::RUN_ITERATIONS
+    }
+}
diff --git a/soroban-env-host/src/cost_runner/cost_types/compute_sha256_hash.rs b/soroban-env-host/src/cost_runner/cost_types/compute_sha256_hash.rs
new file mode 100644
index 00000000..08ceb746
--- /dev/null
+++ b/soroban-env-host/src/cost_runner/cost_types/compute_sha256_hash.rs
@@ -0,0 +1,17 @@
+use crate::{budget::CostType, cost_runner::CostRunner};
+use sha2::{Digest, Sha256};
+
+pub struct ComputeSha256HashRun;
+
+impl CostRunner for ComputeSha256HashRun {
+    const COST_TYPE: CostType = CostType::ComputeSha256Hash;
+    type SampleType = Vec<u8>;
+
+    fn run_iter(_host: &crate::Host, _iter: u64, sample: Self::SampleType) {
+        Sha256::digest(sample).as_slice().to_vec();
+    }
+
+    fn get_total_input(_host: &crate::Host, sample: &Self::SampleType) -> u64 {
+        (sample.len() as u64) * Self::RUN_ITERATIONS
+    }
+}
diff --git a/soroban-env-host/src/cost_runner/cost_types/ed25519_scalar_mul.rs b/soroban-env-host/src/cost_runner/cost_types/ed25519_scalar_mul.rs
new file mode 100644
index 00000000..2d53ae53
--- /dev/null
+++ b/soroban-env-host/src/cost_runner/cost_types/ed25519_scalar_mul.rs
@@ -0,0 +1,26 @@
+use crate::{budget::CostType, cost_runner::CostRunner};
+use curve25519_dalek::{edwards, scalar};
+
+pub struct Ed25519ScalarMulRun;
+
+#[allow(non_snake_case)]
+#[derive(Clone)]
+pub struct Ed25519ScalarMulSample {
+    pub a: scalar::Scalar,
+    pub A: edwards::EdwardsPoint,
+    pub b: scalar::Scalar,
+}
+
+impl CostRunner for Ed25519ScalarMulRun {
+    const COST_TYPE: CostType = CostType::EdwardsPointCurve25519ScalarMul;
+    type SampleType = Ed25519ScalarMulSample;
+
+    fn run_iter(_host: &crate::Host, _iter: u64, sample: Self::SampleType) {
+        edwards::EdwardsPoint::vartime_double_scalar_mul_basepoint(&sample.a, &sample.A, &sample.b);
+    }
+
+    fn get_total_input(_host: &crate::Host, _sample: &Self::SampleType) -> u64 {
+        // input is ignored
+        Self::RUN_ITERATIONS
+    }
+}
diff --git a/soroban-env-host/src/cost_runner/cost_types/guard_frame.rs b/soroban-env-host/src/cost_runner/cost_types/guard_frame.rs
new file mode 100644
index 00000000..3070d1b4
--- /dev/null
+++ b/soroban-env-host/src/cost_runner/cost_types/guard_frame.rs
@@ -0,0 +1,14 @@
+use crate::{budget::CostType, cost_runner::CostRunner, host::Frame, xdr::Hash, Status, Symbol};
+
+pub struct GuardFrameRun;
+
+impl CostRunner for GuardFrameRun {
+    const COST_TYPE: CostType = CostType::GuardFrame;
+
+    type SampleType = (Hash, Symbol);
+
+    fn run_iter(host: &crate::Host, _iter: u64, sample: Self::SampleType) {
+        host.with_frame(Frame::Token(sample.0, sample.1), || Ok(Status::OK.to_raw()))
+            .unwrap();
+    }
+}
diff --git a/soroban-env-host/src/cost_runner/cost_types/host_obj_alloc_slot.rs b/soroban-env-host/src/cost_runner/cost_types/host_obj_alloc_slot.rs
new file mode 100644
index 00000000..dea02296
--- /dev/null
+++ b/soroban-env-host/src/cost_runner/cost_types/host_obj_alloc_slot.rs
@@ -0,0 +1,15 @@
+use crate::{budget::CostType, cost_runner::CostRunner};
+
+pub struct HostObjAllocSlotRun;
+
+impl CostRunner for HostObjAllocSlotRun {
+    const COST_TYPE: CostType = CostType::HostObjAllocSlot;
+    type SampleType = Vec<u8>;
+
+    fn run_iter(host: &crate::Host, _iter: u64, sample: Self::SampleType) {
+        // When measuring, we just inject a single copy to see what
+        // the cost of "one more" is at the given size.
+        // host.to_host_obj(sample).unwrap();
+        host.add_host_object(sample).unwrap();
+    }
+}
diff --git a/soroban-env-host/src/cost_runner/cost_types/im_map_ops.rs b/soroban-env-host/src/cost_runner/cost_types/im_map_ops.rs
new file mode 100644
index 00000000..e9d02453
--- /dev/null
+++ b/soroban-env-host/src/cost_runner/cost_types/im_map_ops.rs
@@ -0,0 +1,71 @@
+use crate::{
+    budget::CostType, cost_runner::CostRunner, host::metered_cmp::MeteredCmp, EnvVal, Host,
+    MeteredOrdMap, RawVal,
+};
+
+type HostMap = MeteredOrdMap<EnvVal<Host, RawVal>, EnvVal<Host, RawVal>>;
+
+pub struct ImMapNewRun;
+impl CostRunner for ImMapNewRun {
+    const COST_TYPE: CostType = CostType::ImMapNew;
+    type SampleType = ();
+
+    fn run_iter(host: &Host, _iter: u64, _sample: Self::SampleType) {
+        HostMap::new(host.budget_cloned()).unwrap();
+    }
+}
+
+pub struct ImMapImmutEntryRun;
+#[derive(Clone)]
+pub struct ImMapImmutEntrySample {
+    pub map: HostMap,
+    pub keys: Vec<EnvVal<Host, RawVal>>,
+}
+impl CostRunner for ImMapImmutEntryRun {
+    const COST_TYPE: CostType = CostType::ImMapImmutEntry;
+    type SampleType = ImMapImmutEntrySample;
+
+    fn run_iter(_host: &crate::Host, iter: u64, sample: Self::SampleType) {
+        let _ = sample
+            .map
+            .get(&sample.keys[iter as usize % sample.keys.len()])
+            .unwrap();
+    }
+}
+
+pub struct ImMapMutEntryRun;
+#[derive(Clone)]
+pub struct ImMapMutEntrySample {
+    pub im: ImMapImmutEntrySample,
+    pub second_map_ref: HostMap,
+}
+impl CostRunner for ImMapMutEntryRun {
+    const COST_TYPE: CostType = CostType::ImMapMutEntry;
+    type SampleType = ImMapMutEntrySample;
+
+    fn run_iter(_host: &crate::Host, iter: u64, mut sample: Self::SampleType) {
+        let _ = sample
+            .im
+            .map
+            .get_mut(&sample.im.keys[iter as usize % sample.im.keys.len()])
+            .unwrap();
+    }
+}
+
+pub struct ImMapCmpRun;
+#[derive(Clone)]
+pub struct ImMapCmpSample {
+    pub a: HostMap,
+    pub b: HostMap,
+}
+impl CostRunner for ImMapCmpRun {
+    const COST_TYPE: CostType = CostType::ImMapCmp;
+    type SampleType = ImMapCmpSample;
+
+    fn run_iter(host: &Host, _iter: u64, sample: Self::SampleType) {
+        sample
+            .a
+            .metered_cmp(&sample.b, &host.budget_cloned())
+            .unwrap();
+    }
+}
diff --git a/soroban-env-host/src/cost_runner/cost_types/im_vec_ops.rs b/soroban-env-host/src/cost_runner/cost_types/im_vec_ops.rs
new file mode 100644
index 00000000..5c1bec82
--- /dev/null
+++ b/soroban-env-host/src/cost_runner/cost_types/im_vec_ops.rs
@@ -0,0 +1,71 @@
+use crate::{
+    budget::CostType, cost_runner::CostRunner, host::metered_cmp::MeteredCmp, EnvVal, Host,
+    MeteredVector, RawVal,
+};
+
+type HostVec = MeteredVector<EnvVal<Host, RawVal>>;
+
+pub struct ImVecNewRun;
+impl CostRunner for ImVecNewRun {
+    const COST_TYPE: CostType = CostType::ImVecNew;
+    type SampleType = ();
+
+    fn run_iter(host: &crate::Host, _iter: u64, _sample: Self::SampleType) {
+        HostVec::new(host.budget_cloned()).unwrap();
+    }
+}
+
+pub struct ImVecImmutEntryRun;
+#[derive(Clone)]
+pub struct ImVecImmutEntrySample {
+    pub vec: HostVec,
+    pub idxs: Vec<usize>,
+}
+impl CostRunner for ImVecImmutEntryRun {
+    const COST_TYPE: CostType = CostType::ImVecImmutEntry;
+    type SampleType = ImVecImmutEntrySample;
+
+    fn run_iter(_host: &Host, iter: u64, sample: Self::SampleType) {
+        let _ = sample
+            .vec
+            .get(sample.idxs[iter as usize % sample.idxs.len()])
+            .unwrap();
+    }
+}
+
+pub struct ImVecMutEntryRun;
+#[derive(Clone)]
+pub struct ImVecMutEntrySample {
+    pub im: ImVecImmutEntrySample,
+    pub second_vec_ref: HostVec,
+}
+impl CostRunner for ImVecMutEntryRun {
+    const COST_TYPE: CostType = CostType::ImVecMutEntry;
+    type SampleType = ImVecMutEntrySample;
+
+    fn run_iter(_host: &Host, iter: u64, mut sample: Self::SampleType) {
+        let _ = sample
+            .im
+            .vec
+            .get_mut(sample.im.idxs[iter as usize % sample.im.idxs.len()])
+            .unwrap();
+    }
+}
+
+pub struct ImVecCmpRun;
+#[derive(Clone)]
+pub struct ImVecCmpSample {
+    pub a: HostVec,
+    pub b: HostVec,
+}
+impl CostRunner for ImVecCmpRun {
+    const COST_TYPE: CostType = CostType::ImVecCmp;
+    type SampleType = ImVecCmpSample;
+
+    fn run_iter(host: &Host, _iter: u64, sample: Self::SampleType) {
+        sample
+            .a
+            .metered_cmp(&sample.b, &host.budget_cloned())
+            .unwrap();
+    }
+}
diff --git a/soroban-env-host/src/cost_runner/cost_types/invoke.rs b/soroban-env-host/src/cost_runner/cost_types/invoke.rs
new file mode 100644
index 00000000..2798114f
--- /dev/null
+++ b/soroban-env-host/src/cost_runner/cost_types/invoke.rs
@@ -0,0 +1,29 @@
+use crate::{budget::CostType, cost_runner::CostRunner, Vm};
+use std::rc::Rc;
+
+pub struct InvokeVmFunctionRun;
+
+impl CostRunner for InvokeVmFunctionRun {
+    const COST_TYPE: CostType = CostType::InvokeVmFunction;
+    type SampleType = Rc<Vm>;
+
+    const RUN_ITERATIONS: u64 = 100;
+
+    fn run_iter(host: &crate::Host, _iter: u64, sample: Self::SampleType) {
+        sample.invoke_function_raw(host, "test", &[]).unwrap();
+    }
+}
+
+pub struct InvokeHostFunctionRun;
+
+impl CostRunner for InvokeHostFunctionRun {
+    const COST_TYPE: CostType = CostType::InvokeHostFunction;
+
+    const RUN_ITERATIONS: u64 = 1;
+
+    type SampleType = Rc<Vm>;
+
+    fn run_iter(host: &crate::Host, _iter: u64, sample: Self::SampleType) {
+        sample.invoke_function_raw(host, "test", &[]).unwrap();
+    }
+}
diff --git a/soroban-env-host/src/cost_runner/cost_types/mod.rs b/soroban-env-host/src/cost_runner/cost_types/mod.rs
new file mode 100644
index 00000000..e8427a29
--- /dev/null
+++ b/soroban-env-host/src/cost_runner/cost_types/mod.rs
@@ -0,0 +1,51 @@
+mod bigint_ops;
+mod bytes_ops;
+mod charge_budget;
+mod compute_ed25519_pubkey;
+mod compute_sha256_hash;
+mod ed25519_scalar_mul;
+mod guard_frame;
+mod host_obj_alloc_slot;
+mod im_map_ops;
+mod im_vec_ops;
+#[cfg(feature = "vm")]
+mod invoke;
+mod record_contract_event;
+mod record_debug_event;
+mod scmap_to_host_map;
+mod scvec_to_host_vec;
+mod val_deser;
+mod val_ser;
+mod val_xdr_conv;
+mod verify_ed25519_sig;
+mod visit_object;
+#[cfg(feature = "vm")]
+mod vm_ops;
+#[cfg(feature = "vm")]
+mod wasm_insn_exec;
+
+pub use bigint_ops::*;
+pub use bytes_ops::*;
+pub use charge_budget::*;
+pub use compute_ed25519_pubkey::*;
+pub use compute_sha256_hash::*;
+pub use ed25519_scalar_mul::*;
+pub use guard_frame::*;
+pub use host_obj_alloc_slot::*;
+pub use im_map_ops::*;
+pub use im_vec_ops::*;
+#[cfg(feature = "vm")]
+pub use invoke::*;
+pub use record_contract_event::*;
+pub use record_debug_event::*;
+pub use scmap_to_host_map::*;
+pub use scvec_to_host_vec::*;
+pub use val_deser::*;
+pub use val_ser::*;
+pub use val_xdr_conv::*;
+pub use verify_ed25519_sig::*;
+pub use visit_object::*;
+#[cfg(feature = "vm")]
+pub use vm_ops::*;
+#[cfg(feature = "vm")]
+pub use wasm_insn_exec::*;
diff --git a/soroban-env-host/src/cost_runner/cost_types/record_contract_event.rs b/soroban-env-host/src/cost_runner/cost_types/record_contract_event.rs
new file mode 100644
index 00000000..77af9c47
--- /dev/null
+++ b/soroban-env-host/src/cost_runner/cost_types/record_contract_event.rs
@@ -0,0 +1,24 @@
+use crate::{budget::CostType, cost_runner::CostRunner, events::HostEvent, xdr::ContractEvent};
+
+pub struct RecordContractEventRun;
+
+#[derive(Clone)]
+pub struct RecordContractEventSample {
+    pub storage: Vec<HostEvent>,
+    pub events: Vec<ContractEvent>,
+}
+
+impl CostRunner for RecordContractEventRun {
+    const COST_TYPE: CostType = CostType::HostEventContract;
+    type SampleType = RecordContractEventSample;
+
+    fn run_iter(_host: &crate::Host, _iter: u64, mut sample: Self::SampleType) {
+        sample
+            .storage
+            .push(HostEvent::Contract(sample.events.pop().unwrap()));
+    }
+
+    fn get_total_input(_host: &crate::Host, _sample: &Self::SampleType) -> u64 {
+        Self::RUN_ITERATIONS
+    }
+}
diff --git a/soroban-env-host/src/cost_runner/cost_types/record_debug_event.rs b/soroban-env-host/src/cost_runner/cost_types/record_debug_event.rs
new file mode 100644
index 00000000..0ef25b58
--- /dev/null
+++ b/soroban-env-host/src/cost_runner/cost_types/record_debug_event.rs
@@ -0,0 +1,22 @@
+use crate::{budget::CostType, cost_runner::CostRunner, events::DebugEvent, EnvVal, Host, RawVal};
+
+pub struct CreateRecordDebugEventRun;
+
+#[derive(Clone)]
+pub struct CreateRecordDebugEventSample {
+    pub msg: &'static str,
+    pub args: Vec<EnvVal<Host, RawVal>>,
+}
+
+impl CostRunner for CreateRecordDebugEventRun {
+    const COST_TYPE: CostType = CostType::HostEventDebug;
+    type SampleType = CreateRecordDebugEventSample;
+
+    fn run_iter(host: &Host, _iter: u64, sample: Self::SampleType) {
+        let mut de = DebugEvent::new().msg(sample.msg);
+        for arg in sample.args {
+            de = de.arg(arg.to_raw());
+        }
+        host.record_debug_event(de).unwrap();
+    }
+}
diff --git a/soroban-env-host/src/cost_runner/cost_types/scmap_to_host_map.rs b/soroban-env-host/src/cost_runner/cost_types/scmap_to_host_map.rs
new file mode 100644
index 00000000..6338ac6b
--- /dev/null
+++ b/soroban-env-host/src/cost_runner/cost_types/scmap_to_host_map.rs
@@ -0,0 +1,12 @@
+use crate::{budget::CostType, cost_runner::CostRunner, xdr::ScVal};
+
+pub struct ScMapToHostMapRun;
+
+impl CostRunner for ScMapToHostMapRun {
+    const COST_TYPE: CostType = CostType::ScMapToHostMap;
+    type SampleType = ScVal;
+
+    fn run_iter(host: &crate::Host, _iter: u64, sample: Self::SampleType) {
+        host.inject_val(&sample).unwrap();
+    }
+}
diff --git a/soroban-env-host/src/cost_runner/cost_types/scvec_to_host_vec.rs b/soroban-env-host/src/cost_runner/cost_types/scvec_to_host_vec.rs
new file mode 100644
index 00000000..6f2f8ae2
--- /dev/null
+++ b/soroban-env-host/src/cost_runner/cost_types/scvec_to_host_vec.rs
@@ -0,0 +1,12 @@
+use crate::{budget::CostType, cost_runner::CostRunner, xdr::ScVal};
+
+pub struct ScVecToHostVecRun;
+
+impl CostRunner for ScVecToHostVecRun {
+    const COST_TYPE: CostType = CostType::ScVecToHostVec;
+    type SampleType = ScVal;
+
+    fn run_iter(host: &crate::Host, _iter: u64, sample: Self::SampleType) {
+        host.inject_val(&sample).unwrap();
+    }
+}
diff --git a/soroban-env-host/src/cost_runner/cost_types/val_deser.rs b/soroban-env-host/src/cost_runner/cost_types/val_deser.rs
new file mode 100644
index 00000000..b43aca74
--- /dev/null
+++ b/soroban-env-host/src/cost_runner/cost_types/val_deser.rs
@@ -0,0 +1,12 @@
+use crate::{budget::CostType, cost_runner::CostRunner, xdr::ScVal};
+
+pub struct ValDeserRun;
+
+impl CostRunner for ValDeserRun {
+    const COST_TYPE: CostType = CostType::ValDeser;
+    type SampleType = Vec<u8>;
+
+    fn run_iter(host: &crate::Host, _iter: u64, sample: Self::SampleType) {
+        host.metered_from_xdr::<ScVal>(&sample).unwrap();
+    }
+}
diff --git a/soroban-env-host/src/cost_runner/cost_types/val_ser.rs b/soroban-env-host/src/cost_runner/cost_types/val_ser.rs
new file mode 100644
index 00000000..850971a0
--- /dev/null
+++ b/soroban-env-host/src/cost_runner/cost_types/val_ser.rs
@@ -0,0 +1,13 @@
+use crate::{budget::CostType, cost_runner::CostRunner, xdr::ScVal};
+
+pub struct ValSerRun;
+
+impl CostRunner for ValSerRun {
+    const COST_TYPE: CostType = CostType::ValSer;
+    type SampleType = ScVal;
+
+    fn run_iter(host: &crate::Host, _iter: u64, sample: Self::SampleType) {
+        let mut buf = Vec::<u8>::new();
+        host.metered_write_xdr(&sample, &mut buf).unwrap()
+    }
+}
diff --git a/soroban-env-host/src/cost_runner/cost_types/val_xdr_conv.rs b/soroban-env-host/src/cost_runner/cost_types/val_xdr_conv.rs
new file mode 100644
index 00000000..8eafdd25
--- /dev/null
+++ b/soroban-env-host/src/cost_runner/cost_types/val_xdr_conv.rs
@@ -0,0 +1,13 @@
+use crate::{budget::CostType, cost_runner::CostRunner, xdr::ScVal, RawVal};
+
+pub struct ValXdrConvRun;
+
+impl CostRunner for ValXdrConvRun {
+    const COST_TYPE: CostType = CostType::ValXdrConv;
+    type SampleType = (RawVal, ScVal);
+
+    fn run_iter(host: &crate::Host, _iter: u64, sample: Self::SampleType) {
+        host.from_host_val(sample.0).unwrap();
+        host.to_host_val(&sample.1).unwrap();
+    }
+}
diff --git a/soroban-env-host/src/cost_runner/cost_types/verify_ed25519_sig.rs b/soroban-env-host/src/cost_runner/cost_types/verify_ed25519_sig.rs
new file mode 100644
index 00000000..057a0a9f
--- /dev/null
+++ b/soroban-env-host/src/cost_runner/cost_types/verify_ed25519_sig.rs
@@ -0,0 +1,23 @@
+use crate::{budget::CostType, cost_runner::CostRunner};
+use ed25519_dalek::{PublicKey, Signature, Verifier};
+
+pub struct VerifyEd25519SigRun;
+
+#[derive(Clone)]
+pub struct VerifyEd25519SigSample {
+    pub key: PublicKey,
+    pub msg: Vec<u8>,
+    pub sig: Signature,
+}
+
+impl CostRunner for VerifyEd25519SigRun {
+    const COST_TYPE: CostType = CostType::VerifyEd25519Sig;
+    type SampleType = VerifyEd25519SigSample;
+
+    fn run_iter(_host: &crate::Host, _iter: u64, sample: Self::SampleType) {
+        sample
+            .key
+            .verify(sample.msg.as_slice(), &sample.sig)
+            .expect("verify");
+    }
+}
diff --git a/soroban-env-host/src/cost_runner/cost_types/visit_object.rs b/soroban-env-host/src/cost_runner/cost_types/visit_object.rs
new file mode 100644
index 00000000..3014742f
--- /dev/null
+++ b/soroban-env-host/src/cost_runner/cost_types/visit_object.rs
@@ -0,0 +1,15 @@
+use crate::{budget::CostType, cost_runner::CostRunner, RawVal};
+
+pub struct VisitObjectRun;
+
+impl CostRunner for VisitObjectRun {
+    const COST_TYPE: CostType = CostType::VisitObject;
+    type SampleType = Vec<RawVal>;
+
+    fn run_iter(host: &crate::Host, iter: u64, sample: Self::SampleType) {
+        unsafe {
+            let obj = sample[iter as usize % sample.len()];
+            let _ = host.unchecked_visit_val_obj(obj, |_| Ok(()));
+        }
+    }
+}
diff --git a/soroban-env-host/src/cost_runner/cost_types/vm_ops.rs b/soroban-env-host/src/cost_runner/cost_types/vm_ops.rs
new file mode 100644
index 00000000..defdf5bc
--- /dev/null
+++ b/soroban-env-host/src/cost_runner/cost_types/vm_ops.rs
@@ -0,0 +1,52 @@
+use crate::{budget::CostType, cost_runner::CostRunner, xdr::Hash, Vm};
+use std::rc::Rc;
+
+pub struct VmInstantiationRun;
+
+#[derive(Clone)]
+pub struct VmInstantiationSample {
+    pub id: Hash,
+    pub wasm: Vec<u8>,
+}
+
+impl CostRunner for VmInstantiationRun {
+    const COST_TYPE: CostType = CostType::VmInstantiation;
+    const RUN_ITERATIONS: u64 = 10;
+    type SampleType = VmInstantiationSample;
+
+    fn run_iter(host: &crate::Host, _iter: u64, sample: Self::SampleType) {
+        Vm::new(host, sample.id, &sample.wasm[..]).unwrap();
+    }
+}
+
+pub struct VmMemReadRun;
+impl CostRunner for VmMemReadRun {
+    const COST_TYPE: CostType = CostType::VmMemRead;
+
+    type SampleType = (Rc<Vm>, usize);
+
+    fn run_iter(host: &crate::Host, _iter: u64, sample: Self::SampleType) {
+        let mut buf: Vec<u8> = vec![0; sample.1];
+        let vm = sample.0;
+        vm.with_vmcaller(|caller| {
+            host.metered_vm_mem_read(caller, vm.clone(), 0, 0..sample.1, &mut buf)
+                .unwrap()
+        })
+    }
+}
+
+pub struct VmMemWriteRun;
+impl CostRunner for VmMemWriteRun {
+    const COST_TYPE: CostType = CostType::VmMemWrite;
+
+    type SampleType = (Rc<Vm>, Vec<u8>);
+
+    fn run_iter(host: &crate::Host, _iter: u64, mut sample: Self::SampleType) {
+        let buf_range = 0..sample.1.len();
+        let vm = sample.0;
+        vm.with_vmcaller(|caller| {
+            host.metered_vm_mem_write(caller, vm.clone(), 0, buf_range, &mut sample.1)
+                .unwrap()
+        })
+    }
+}
diff --git a/soroban-env-host/src/cost_runner/cost_types/wasm_insn_exec.rs b/soroban-env-host/src/cost_runner/cost_types/wasm_insn_exec.rs
new file mode 100644
index 00000000..bc2ca151
--- /dev/null
+++ b/soroban-env-host/src/cost_runner/cost_types/wasm_insn_exec.rs
@@ -0,0 +1,50 @@
+use crate::{
+    budget::CostType,
+    cost_runner::CostRunner,
+    xdr::{ScVal, ScVec},
+    Vm,
+};
+use std::rc::Rc;
+
+pub struct WasmInsnExecRun;
+
+#[derive(Clone)]
+pub struct WasmInsnExecSample {
+    pub insns: u64,
+    pub args: ScVec,
+    pub vm: Rc<Vm>,
+}
+
+impl CostRunner for WasmInsnExecRun {
+    const COST_TYPE: CostType = CostType::WasmInsnExec;
+    type SampleType = WasmInsnExecSample;
+
+    fn run_iter(host: &crate::Host, _iter: u64, sample: Self::SampleType) {
+        let scval = sample
+            .vm
+            .invoke_function(host, "test", &sample.args)
+            .unwrap();
+        assert_eq!(scval, ScVal::Symbol("pass".try_into().unwrap()));
+    }
+
+    fn get_total_input(_host: &crate::Host, sample: &Self::SampleType) -> u64 {
+        sample.insns * 4 // TODO: avoid magic number
+    }
+}
+
+pub struct WasmMemAllocRun;
+impl CostRunner for WasmMemAllocRun {
+    const COST_TYPE: CostType = CostType::WasmMemAlloc;
+
+    const RUN_ITERATIONS: u64 = 1;
+
+    type SampleType = (Rc<Vm>, usize);
+
+    fn run_iter(host: &crate::Host, _iter: u64, sample: Self::SampleType) {
+        sample.0.invoke_function_raw(host, "test", &[]).unwrap();
+    }
+
+    fn get_total_input(_host: &crate::Host, sample: &Self::SampleType) -> u64 {
+        (sample.1 as u64) * Self::RUN_ITERATIONS * 65536
+    }
+}
diff --git a/soroban-env-host/src/cost_runner/mod.rs b/soroban-env-host/src/cost_runner/mod.rs
new file mode 100644
index 00000000..3f6e7c67
--- /dev/null
+++ b/soroban-env-host/src/cost_runner/mod.rs
@@ -0,0 +1,5 @@
+mod cost_types;
+mod runner;
+
+pub use cost_types::*;
+pub use runner::CostRunner;
diff --git a/soroban-env-host/src/cost_runner/runner.rs b/soroban-env-host/src/cost_runner/runner.rs
new file mode 100644
index 00000000..11374c77
--- /dev/null
+++ b/soroban-env-host/src/cost_runner/runner.rs
@@ -0,0 +1,37 @@
+use crate::{budget::CostType, Host};
+/// `CostRunner` is an interface to running a host cost entity of a `CostType` (usually a block of
+/// WASM bytecode or a host function), given a sample of `SampleType`.
+pub trait CostRunner: Sized {
+    /// The type of cost we're measuring.
+    const COST_TYPE: CostType;
+
+    /// Number of iterations to run, used to divide the resulting measured values.
+    /// Defaults to 100 to average out the measurement noises for fast-running cases.
+    /// If you find your measurements are finishing too slow, reduce this number.
+    const RUN_ITERATIONS: u64 = 100;
+
+    /// Data type of the sample running with.
+    type SampleType: Clone;
+
+    /// Run a iteration of the `CostRunner`, called by `run` for 0..RUN_ITERATIONS.
+    fn run_iter(host: &Host, iter: u64, sample: Self::SampleType);
+
+    /// Run the `CostRunner`. This method is called under CPU-and-memory tracking
+    /// machinery, so anything that happens during it will be considered part of
+    /// the cost for running the HostMeasurement at the returned input. Will call
+    /// `run_iter` with iter set to each number in 0..RUN_ITERATIONS.
+    fn run(host: &Host, samples: Vec<Self::SampleType>) {
+        for (iter, sample) in samples.into_iter().enumerate() {
+            Self::run_iter(host, iter as u64, sample)
+        }
+    }
+
+    /// Get the total input from this run. Default to asking the host. May be overridden
+    /// if host is not actually involved in the actual run. However, if overridden, there is
+    /// a risk of the computed input being diverged from the actual input from the host's
+    /// perspective. So use it carefully. This should be after the `run`, outside of the
+    /// CPU-and-memory tracking machineary.
+    fn get_total_input(host: &Host, _sample: &Self::SampleType) -> u64 {
+        host.0.budget.get_input(Self::COST_TYPE)
+    }
+}
diff --git a/soroban-env-host/src/events.rs b/soroban-env-host/src/events.rs
index ec4134d6..2a432e60 100644
--- a/soroban-env-host/src/events.rs
+++ b/soroban-env-host/src/events.rs
@@ -28,6 +28,7 @@ pub(crate) const TOPIC_BYTES_LENGTH_LIMIT: usize = 32;
 impl Events {
     // Records the smallest variant of a debug HostEvent it can, returning the size of the
     // in_args slice (for charging to a budget).
+    // Notes on metering: this is covered by the host. See `Host::record_debug_event` for details.
     pub fn record_debug_event(&mut self, de: DebugEvent) -> u64 {
         let len = de.args.len();
         self.0.push(HostEvent::Debug(de));
@@ -35,6 +36,7 @@ impl Events {
     }
 
     // Records a contract HostEvent.
+    // Notes on metering: this is covered by the host. See `Host::record_contract_event` for details.
     pub fn record_contract_event(&mut self, ce: ContractEvent) {
         self.0.push(HostEvent::Contract(ce))
     }
diff --git a/soroban-env-host/src/host.rs b/soroban-env-host/src/host.rs
index 3e8c0969..53179275 100644
--- a/soroban-env-host/src/host.rs
+++ b/soroban-env-host/src/host.rs
@@ -4,6 +4,7 @@
 use core::cell::RefCell;
 use core::cmp::Ordering;
 use core::fmt::Debug;
+use std::rc::Rc;
 
 use im_rc::{OrdMap, Vector};
 use num_bigint::Sign;
@@ -30,7 +31,6 @@ use crate::xdr::{
     ScBigInt, ScContractCode, ScHostContextErrorCode, ScHostFnErrorCode, ScHostObjErrorCode,
     ScHostStorageErrorCode, ScHostValErrorCode, ScMap, ScMapEntry, ScObject, ScVal, ScVec,
 };
-use std::rc::Rc;
 
 use crate::host_object::{HostMap, HostObj, HostObject, HostObjectType, HostVal, HostVec};
 #[cfg(feature = "vm")]
@@ -47,6 +47,8 @@ pub(crate) mod metered_bigint;
 pub(crate) mod metered_clone;
 pub(crate) mod metered_cmp;
 pub(crate) mod metered_map;
+#[cfg(feature = "vm")]
+mod metered_utils;
 pub(crate) mod metered_vector;
 pub(crate) mod metered_xdr;
 mod validity;
@@ -136,7 +138,7 @@ pub(crate) struct HostImpl {
     ledger: RefCell<Option<LedgerInfo>>,
     objects: RefCell<Vec<HostObject>>,
     storage: RefCell<Storage>,
-    context: RefCell<Vec<Frame>>,
+    pub(crate) context: RefCell<Vec<Frame>>,
     // Note: budget is refcounted and is _not_ deep-cloned when you call HostImpl::deep_clone,
     // mainly because it's not really possible to achieve (the same budget is connected to many
     // metered sub-objects) but also because it's plausible that the person calling deep_clone
@@ -262,7 +264,7 @@ impl Host {
         &self.0.budget
     }
 
-    pub(crate) fn budget_cloned(&self) -> Budget {
+    pub fn budget_cloned(&self) -> Budget {
         self.0.budget.clone()
     }
 
@@ -347,7 +349,6 @@ impl Host {
     /// operation fails, it can be used to roll the [`Host`] back to the state
     /// it had before its associated [`Frame`] was pushed.
     fn push_frame(&self, frame: Frame) -> Result<RollbackPoint, HostError> {
-        self.charge_budget(CostType::PushFrame, 1)?;
         self.0.context.borrow_mut().push(frame);
         Ok(RollbackPoint {
             objects: self.0.objects.borrow().len(),
@@ -359,7 +360,6 @@ impl Host {
     /// the current context and optionally rolls back the [`Host`]'s objects
     /// and storage map to the state in the provided [`RollbackPoint`].
     fn pop_frame(&self, orp: Option<RollbackPoint>) -> Result<(), HostError> {
-        self.charge_budget(CostType::PopFrame, 1)?;
         self.0
             .context
             .borrow_mut()
@@ -402,8 +402,8 @@ impl Host {
     /// if the closure returned an error. Returns the result that the closure
     /// returned (or any error caused during the frame push/pop).
     // Notes on metering: `GuardFrame` charges on the work done on protecting the `context`.
-    /// It does not cover the cost of the actual closure call. The closure needs to be
-    /// metered separately.
+    // It does not cover the cost of the actual closure call. The closure needs to be
+    // metered separately.
     pub(crate) fn with_frame<F>(&self, frame: Frame, f: F) -> Result<RawVal, HostError>
     where
         F: FnOnce() -> Result<RawVal, HostError>,
@@ -473,7 +473,11 @@ impl Host {
 
     // Notes on metering: closure call needs to be metered separatedly. `VisitObject` only covers
     /// the cost of visiting an object.
-    unsafe fn unchecked_visit_val_obj<F, U>(&self, val: RawVal, f: F) -> Result<U, HostError>
+    pub(crate) unsafe fn unchecked_visit_val_obj<F, U>(
+        &self,
+        val: RawVal,
+        f: F,
+    ) -> Result<U, HostError>
     where
         F: FnOnce(Option<&HostObject>) -> Result<U, HostError>,
     {
@@ -685,34 +689,6 @@ impl Host {
         ho: HostObject,
     ) -> Result<HostObject, HostError> {
         self.charge_budget(CostType::HostObjAllocSlot, prev_len as u64)?;
-        match &ho {
-            HostObject::Vec(v) => {
-                self.charge_budget(CostType::HostVecAllocCell, v.len() as u64)?;
-            }
-            HostObject::Map(m) => {
-                self.charge_budget(CostType::HostMapAllocCell, m.len() as u64)?;
-            }
-            HostObject::U64(_) => {
-                self.charge_budget(CostType::HostU64AllocCell, 1)?;
-            }
-            HostObject::I64(_) => {
-                self.charge_budget(CostType::HostI64AllocCell, 1)?;
-            }
-            HostObject::Bytes(b) => {
-                self.charge_budget(CostType::HostBytesAllocCell, b.len() as u64)?;
-            }
-            HostObject::BigInt(bi) => {
-                self.charge_budget(CostType::HostBigIntAllocCell, bi.bits() as u64)?;
-            }
-            HostObject::ContractCode(cc) => {
-                if let ScContractCode::Wasm(c) = cc {
-                    self.charge_budget(CostType::HostContractCodeAllocCell, c.len() as u64)?;
-                }
-            }
-            HostObject::AccountId(_) => {
-                self.charge_budget(CostType::HostAccountIdAllocCell, 1)?;
-            }
-        }
         Ok(ho)
     }
 
@@ -929,9 +905,11 @@ impl Host {
                     args.as_slice()
                 {
                     self.with_frame(Frame::HostFunction(hf), || {
+                        // Metering: conversions to host objects are covered. Cost of collecting
+                        // RawVals into Vec is ignored. Since 1. RawVals are cheap to clone 2. the
+                        // max number of args is fairly limited.
                         let object = self.to_host_obj(scobj)?.to_object();
                         let symbol = <Symbol>::try_from(scsym)?;
-                        self.charge_budget(CostType::CallArgsUnpack, rest.len() as u64)?;
                         let args = rest
                             .iter()
                             .map(|scv| self.to_host_val(scv).map(|hv| hv.val))
@@ -1915,7 +1893,7 @@ impl VmCallerCheckedEnv for Host {
             [separator.as_bytes(), salt_val.as_ref()].concat()
         };
         // Another charge-after-work. Easier to get the num bytes this way.
-        self.charge_budget(CostType::BytesConcat, params.len() as u64)?;
+        self.charge_budget(CostType::BytesAppend, params.len() as u64)?;
         let hash = self.compute_hash_sha256(vmcaller, self.add_host_object(params)?.into())?;
 
         self.verify_sig_ed25519(vmcaller, hash, key, sig)?;
@@ -2351,12 +2329,7 @@ impl VmCallerCheckedEnv for Host {
             let b_pos = u32::try_from(b_pos)?;
             self.visit_obj(b, move |hv: &Vec<u8>| {
                 let range = self.valid_range_from_start_span_bound(b_pos, len, hv.len())?;
-                let mem = vm.get_memory(self)?;
-                self.charge_budget(CostType::VmMemCpy, hv.len() as u64)?;
-                self.map_err(
-                    mem.write(vmcaller.try_mut()?, pos as usize, &hv.as_slice()[range])
-                        .map_err(|me| wasmi::Error::Memory(me)),
-                )?;
+                self.metered_vm_mem_write(vmcaller, vm, pos, range, hv)?;
                 Ok(().into())
             })
         }
@@ -2386,16 +2359,7 @@ impl VmCallerCheckedEnv for Host {
             if end_idx > vnew.len() {
                 vnew.resize(end_idx, 0);
             }
-            let mem = vm.get_memory(self)?;
-            self.charge_budget(CostType::VmMemCpy, len as u64)?;
-            self.map_err(
-                mem.read(
-                    vmcaller.try_mut()?,
-                    pos as usize,
-                    &mut vnew.as_mut_slice()[b_pos as usize..end_idx],
-                )
-                .map_err(|me| wasmi::Error::Memory(me)),
-            )?;
+            self.metered_vm_mem_read(vmcaller, vm, pos, b_pos as usize..end_idx, &mut vnew)?;
             Ok(self.add_host_object(vnew)?.into())
         }
     }
@@ -2412,12 +2376,7 @@ impl VmCallerCheckedEnv for Host {
         {
             let VmSlice { vm, pos, len } = self.decode_vmslice(lm_pos, len)?;
             let mut vnew: Vec<u8> = vec![0; len as usize];
-            let mem = vm.get_memory(self)?;
-            self.charge_budget(CostType::VmMemCpy, len as u64)?;
-            self.map_err(
-                mem.read(vmcaller.try_ref()?, pos as usize, vnew.as_mut_slice())
-                    .map_err(|me| wasmi::Error::Memory(me)),
-            )?;
+            self.metered_vm_mem_read(vmcaller, vm, pos, 0..len as usize, &mut vnew)?;
             Ok(self.add_host_object(vnew)?.into())
         }
     }
@@ -2583,7 +2542,7 @@ impl VmCallerCheckedEnv for Host {
         let end = self.u32_from_rawval_input("end", end)?;
         let vnew = self.visit_obj(b, move |hv: &Vec<u8>| {
             let range = self.valid_range_from_start_end_bound(start, end, hv.len())?;
-            self.charge_budget(CostType::BytesSlice, hv.len() as u64)?;
+            self.charge_budget(CostType::BytesClone, range.len() as u64)?;
             Ok(hv.as_slice()[range].to_vec())
         })?;
         Ok(self.add_host_object(vnew)?.into())
@@ -2797,4 +2756,8 @@ impl VmCallerCheckedEnv for Host {
             ))
         }
     }
+
+    fn dummy0(&self, vmcaller: &mut VmCaller<Self::VmUserState>) -> Result<RawVal, Self::Error> {
+        Ok(().into())
+    }
 }
diff --git a/soroban-env-host/src/host/conversion.rs b/soroban-env-host/src/host/conversion.rs
index fd07f66f..ff559665 100644
--- a/soroban-env-host/src/host/conversion.rs
+++ b/soroban-env-host/src/host/conversion.rs
@@ -296,7 +296,7 @@ impl Host {
 
     pub(crate) fn call_args_from_obj(&self, args: Object) -> Result<Vec<RawVal>, HostError> {
         self.visit_obj(args, |hv: &HostVec| {
-            self.charge_budget(CostType::CallArgsUnpack, hv.len() as u64)?;
+            // Metering: free
             Ok(hv.iter().map(|a| a.to_raw()).collect())
         })
     }
diff --git a/soroban-env-host/src/host/metered_bigint.rs b/soroban-env-host/src/host/metered_bigint.rs
index 3805fd66..1f0d8c7e 100644
--- a/soroban-env-host/src/host/metered_bigint.rs
+++ b/soroban-env-host/src/host/metered_bigint.rs
@@ -14,7 +14,7 @@ use std::{
     rc::Rc,
 };
 
-pub(crate) struct MeteredBigInt {
+pub struct MeteredBigInt {
     budget: Budget,
     num: BigInt,
 }
@@ -81,7 +81,7 @@ impl MeteredBigInt {
 }
 
 impl MeteredBigInt {
-    pub(crate) fn new(budget: Budget) -> Result<Self, HostError> {
+    pub fn new(budget: Budget) -> Result<Self, HostError> {
         budget.charge(CostType::BigIntNew, 1)?;
         Ok(Self {
             budget,
@@ -90,11 +90,11 @@ impl MeteredBigInt {
     }
 
     // Notes on mtering: free.
-    pub(crate) fn bits(&self) -> u64 {
+    pub fn bits(&self) -> u64 {
         self.num.bits()
     }
 
-    pub(crate) fn from_u64(budget: Budget, x: u64) -> Result<Self, HostError> {
+    pub fn from_u64(budget: Budget, x: u64) -> Result<Self, HostError> {
         budget.charge(CostType::BigIntNew, 1)?;
         Ok(Self {
             budget,
@@ -102,11 +102,11 @@ impl MeteredBigInt {
         })
     }
 
-    pub(crate) fn to_u64(&self) -> Option<u64> {
+    pub fn to_u64(&self) -> Option<u64> {
         self.num.to_u64()
     }
 
-    pub(crate) fn from_i64(budget: Budget, x: i64) -> Result<Self, HostError> {
+    pub fn from_i64(budget: Budget, x: i64) -> Result<Self, HostError> {
         budget.charge(CostType::BigIntNew, 1)?;
         Ok(Self {
             budget,
@@ -114,11 +114,15 @@ impl MeteredBigInt {
         })
     }
 
-    pub(crate) fn to_i64(&self) -> Option<i64> {
+    pub fn to_i64(&self) -> Option<i64> {
         self.num.to_i64()
     }
 
-    pub(crate) fn add(&self, other: &Self) -> Result<Self, HostError> {
+    pub fn from_bigint(budget: Budget, num: BigInt) -> Self {
+        Self { budget, num }
+    }
+
+    pub fn add(&self, other: &Self) -> Result<Self, HostError> {
         self.charge_add_sub(max(self.bits(), other.bits()))?;
         Ok(Self {
             budget: self.budget.clone(),
@@ -126,7 +130,7 @@ impl MeteredBigInt {
         })
     }
 
-    pub(crate) fn sub(&self, other: &Self) -> Result<Self, HostError> {
+    pub fn sub(&self, other: &Self) -> Result<Self, HostError> {
         self.charge_add_sub(max(self.bits(), other.bits()))?;
         Ok(Self {
             budget: self.budget.clone(),
@@ -134,7 +138,7 @@ impl MeteredBigInt {
         })
     }
 
-    pub(crate) fn mul(&self, other: &Self) -> Result<Self, HostError> {
+    pub fn mul(&self, other: &Self) -> Result<Self, HostError> {
         self.charge_mul(max(self.bits(), other.bits()))?;
         Ok(Self {
             budget: self.budget.clone(),
@@ -142,7 +146,7 @@ impl MeteredBigInt {
         })
     }
 
-    pub(crate) fn div(&self, other: &Self) -> Result<Self, HostError> {
+    pub fn div(&self, other: &Self) -> Result<Self, HostError> {
         debug_assert!(!other.is_zero());
         self.charge_div_rem(max(self.bits(), other.bits()))?;
         Ok(Self {
@@ -151,7 +155,7 @@ impl MeteredBigInt {
         })
     }
 
-    pub(crate) fn rem(&self, other: &Self) -> Result<Self, HostError> {
+    pub fn rem(&self, other: &Self) -> Result<Self, HostError> {
         debug_assert!(!other.is_zero());
         self.charge_div_rem(max(self.bits(), other.bits()))?;
         Ok(Self {
@@ -160,7 +164,7 @@ impl MeteredBigInt {
         })
     }
 
-    pub(crate) fn bitand(&self, other: &Self) -> Result<Self, HostError> {
+    pub fn bitand(&self, other: &Self) -> Result<Self, HostError> {
         self.charge_bitwise_op(max(self.bits(), other.bits()))?;
         Ok(Self {
             budget: self.budget.clone(),
@@ -168,7 +172,7 @@ impl MeteredBigInt {
         })
     }
 
-    pub(crate) fn bitor(&self, other: &Self) -> Result<Self, HostError> {
+    pub fn bitor(&self, other: &Self) -> Result<Self, HostError> {
         self.charge_bitwise_op(max(self.bits(), other.bits()))?;
         Ok(Self {
             budget: self.budget.clone(),
@@ -176,7 +180,7 @@ impl MeteredBigInt {
         })
     }
 
-    pub(crate) fn bitxor(&self, other: &Self) -> Result<Self, HostError> {
+    pub fn bitxor(&self, other: &Self) -> Result<Self, HostError> {
         self.charge_bitwise_op(max(self.bits(), other.bits()))?;
         Ok(Self {
             budget: self.budget.clone(),
@@ -184,7 +188,7 @@ impl MeteredBigInt {
         })
     }
 
-    pub(crate) fn shl(&self, rhs: &Self) -> Result<Self, HostError> {
+    pub fn shl(&self, rhs: &Self) -> Result<Self, HostError> {
         self.charge_shift(self.bits())?;
         if rhs.is_negative() {
             // TODO: Replace with proper err code "attempt to shift left with negative"
@@ -201,7 +205,7 @@ impl MeteredBigInt {
         }
     }
 
-    pub(crate) fn shr(&self, rhs: &Self) -> Result<Self, HostError> {
+    pub fn shr(&self, rhs: &Self) -> Result<Self, HostError> {
         self.charge_shift(self.bits())?;
         if rhs.is_negative() {
             // TODO: Replace with proper err code "attempt to shift right with negative"
@@ -218,29 +222,29 @@ impl MeteredBigInt {
         }
     }
 
-    pub(crate) fn is_zero(&self) -> bool {
+    pub fn is_zero(&self) -> bool {
         self.num.is_zero()
     }
 
-    pub(crate) fn is_negative(&self) -> bool {
+    pub fn is_negative(&self) -> bool {
         self.num.is_negative()
     }
 
-    pub(crate) fn neg(&self) -> Self {
+    pub fn neg(&self) -> Self {
         Self {
             budget: self.budget.clone(),
             num: (&self.num).neg(),
         }
     }
 
-    pub(crate) fn not(&self) -> Self {
+    pub fn not(&self) -> Self {
         Self {
             budget: self.budget.clone(),
             num: (&self.num).not(),
         }
     }
 
-    pub(crate) fn gcd(&self, other: &Self) -> Result<Self, HostError> {
+    pub fn gcd(&self, other: &Self) -> Result<Self, HostError> {
         self.charge_gcd_lcm(max((&self.num).bits(), other.num.bits()))?;
         Ok(Self {
             budget: self.budget.clone(),
@@ -248,7 +252,7 @@ impl MeteredBigInt {
         })
     }
 
-    pub(crate) fn lcm(&self, other: &Self) -> Result<Self, HostError> {
+    pub fn lcm(&self, other: &Self) -> Result<Self, HostError> {
         self.charge_gcd_lcm(max((&self.num).bits(), other.num.bits()))?;
         Ok(Self {
             budget: self.budget.clone(),
@@ -256,7 +260,7 @@ impl MeteredBigInt {
         })
     }
 
-    pub(crate) fn pow(&self, rhs: &Self) -> Result<Self, HostError> {
+    pub fn pow(&self, rhs: &Self) -> Result<Self, HostError> {
         if rhs.is_negative() {
             // TODO: Replace with proper err code "negative exponentiation not supported"
             return Err(ScUnknownErrorCode::General.into());
@@ -274,7 +278,7 @@ impl MeteredBigInt {
         }
     }
 
-    pub(crate) fn modpow(&self, exponent: &Self, modulus: &Self) -> Result<Self, HostError> {
+    pub fn modpow(&self, exponent: &Self, modulus: &Self) -> Result<Self, HostError> {
         // TODO: Replace with proper err code "negative exponentiation not supported"
         if exponent.is_negative() {
             return Err(ScUnknownErrorCode::General.into());
@@ -291,7 +295,7 @@ impl MeteredBigInt {
         })
     }
 
-    pub(crate) fn sqrt(&self) -> Result<Self, HostError> {
+    pub fn sqrt(&self) -> Result<Self, HostError> {
         // TODO: Replace with proper err code "sqrt is imaginary"
         if self.is_negative() {
             return Err(ScUnknownErrorCode::General.into());
@@ -303,11 +307,7 @@ impl MeteredBigInt {
         })
     }
 
-    pub(crate) fn from_bytes_be(
-        budget: Budget,
-        sign: Sign,
-        bytes: &[u8],
-    ) -> Result<Self, HostError> {
+    pub fn from_bytes_be(budget: Budget, sign: Sign, bytes: &[u8]) -> Result<Self, HostError> {
         budget.charge(CostType::BigIntFromBytes, bytes.len() as u64)?;
         Ok(Self {
             budget,
@@ -315,12 +315,12 @@ impl MeteredBigInt {
         })
     }
 
-    pub(crate) fn to_bytes_be(&self) -> Result<(Sign, Vec<u8>), HostError> {
+    pub fn to_bytes_be(&self) -> Result<(Sign, Vec<u8>), HostError> {
         self.charge_to_bytes(self.bits())?;
         Ok((&self.num).to_bytes_be())
     }
 
-    pub(crate) fn from_radix_be(
+    pub fn from_radix_be(
         budget: Budget,
         sign: Sign,
         buf: &[u8],
@@ -334,7 +334,7 @@ impl MeteredBigInt {
         Ok(Self { budget, num })
     }
 
-    pub(crate) fn to_radix_be(&self, r: u32) -> Result<(Sign, Vec<u8>), HostError> {
+    pub fn to_radix_be(&self, r: u32) -> Result<(Sign, Vec<u8>), HostError> {
         self.charge_to_radix(self.bits())?;
         Ok((&self.num).to_radix_be(r))
     }
diff --git a/soroban-env-host/src/host/metered_map.rs b/soroban-env-host/src/host/metered_map.rs
index bb86dea7..8d659543 100644
--- a/soroban-env-host/src/host/metered_map.rs
+++ b/soroban-env-host/src/host/metered_map.rs
@@ -88,6 +88,16 @@ where
         Ok(self.map.get(key))
     }
 
+    // Time: O(log n)
+    pub fn get_mut<BK>(&mut self, key: &BK) -> Result<Option<&mut V>, HostError>
+    where
+        BK: Ord + ?Sized,
+        K: Borrow<BK>,
+    {
+        self.charge_mut_access(self.map.len() as u64)?;
+        Ok(self.map.get_mut(key))
+    }
+
     // Time: O(log n)
     pub fn remove<BK>(&mut self, k: &BK) -> Result<Option<V>, HostError>
     where
diff --git a/soroban-env-host/src/host/metered_utils.rs b/soroban-env-host/src/host/metered_utils.rs
new file mode 100644
index 00000000..1f77712b
--- /dev/null
+++ b/soroban-env-host/src/host/metered_utils.rs
@@ -0,0 +1,40 @@
+use crate::{budget::CostType, Host, HostError, Vm, VmCaller};
+use std::{ops::Range, rc::Rc};
+
+impl Host {
+    pub(crate) fn metered_vm_mem_write(
+        &self,
+        vmcaller: &mut VmCaller<Host>,
+        vm: Rc<Vm>,
+        pos: u32,
+        range: Range<usize>,
+        buf: &Vec<u8>,
+    ) -> Result<(), HostError> {
+        self.charge_budget(CostType::VmMemWrite, range.len() as u64)?;
+        let mem = vm.get_memory(self)?;
+        self.map_err(
+            mem.write(vmcaller.try_mut()?, pos as usize, &buf.as_slice()[range])
+                .map_err(|me| wasmi::Error::Memory(me)),
+        )
+    }
+
+    pub(crate) fn metered_vm_mem_read(
+        &self,
+        vmcaller: &mut VmCaller<Host>,
+        vm: Rc<Vm>,
+        pos: u32,
+        range: Range<usize>,
+        buf: &mut Vec<u8>,
+    ) -> Result<(), HostError> {
+        self.charge_budget(CostType::VmMemRead, range.len() as u64)?;
+        let mem = vm.get_memory(self)?;
+        self.map_err(
+            mem.read(
+                vmcaller.try_mut()?,
+                pos as usize,
+                &mut buf.as_mut_slice()[range],
+            )
+            .map_err(|me| wasmi::Error::Memory(me)),
+        )
+    }
+}
diff --git a/soroban-env-host/src/host/metered_vector.rs b/soroban-env-host/src/host/metered_vector.rs
index e3f865d5..4e1d83f4 100644
--- a/soroban-env-host/src/host/metered_vector.rs
+++ b/soroban-env-host/src/host/metered_vector.rs
@@ -9,7 +9,7 @@ use std::cmp::{min, Ordering};
 use std::ops::RangeBounds;
 use std::rc::Rc;
 
-pub(crate) struct MeteredVector<A> {
+pub struct MeteredVector<A> {
     budget: Budget,
     vec: Vector<A>,
 }
@@ -69,6 +69,14 @@ impl<A: Clone> MeteredVector<A> {
             .ok_or_else(|| ScHostObjErrorCode::VecIndexOutOfBound.into())
     }
 
+    // Time: O(log n)
+    pub fn get_mut(&mut self, index: usize) -> Result<&mut A, HostError> {
+        self.charge_mut_access(self.len() as u64)?;
+        self.vec
+            .get_mut(index)
+            .ok_or_else(|| ScHostObjErrorCode::VecIndexOutOfBound.into())
+    }
+
     // Time: O(log n)
     pub fn remove(&mut self, index: usize) -> Result<A, HostError> {
         self.charge_mut_access(self.len() as u64)?;
diff --git a/soroban-env-host/src/lib.rs b/soroban-env-host/src/lib.rs
index 1a65ae01..007cfe95 100644
--- a/soroban-env-host/src/lib.rs
+++ b/soroban-env-host/src/lib.rs
@@ -44,8 +44,13 @@ pub mod storage;
 #[cfg(test)]
 mod test;
 
+pub mod cost_runner;
+
 #[cfg(any(test, feature = "testutils"))]
 pub use host::ContractFunctionSet;
-pub use host::{metered_map::MeteredOrdMap, Host, HostError, LedgerInfo};
+pub use host::{
+    metered_bigint::MeteredBigInt, metered_map::MeteredOrdMap, metered_vector::MeteredVector, Host,
+    HostError, LedgerInfo,
+};
 pub use im_rc;
 pub use soroban_env_common::*;
diff --git a/soroban-env-host/src/vm.rs b/soroban-env-host/src/vm.rs
index 1c926d57..acbb3561 100644
--- a/soroban-env-host/src/vm.rs
+++ b/soroban-env-host/src/vm.rs
@@ -14,7 +14,7 @@ mod func_info;
 use crate::{
     budget::CostType,
     host::{Frame, HostImpl},
-    HostError,
+    HostError, VmCaller,
 };
 use std::{cell::RefCell, io::Cursor, ops::RangeInclusive, rc::Rc};
 
@@ -29,8 +29,10 @@ use soroban_env_common::{
     ConversionError,
 };
 
-use wasmi::{core::Value, Memory};
-use wasmi::{Engine, Instance, Linker, Module, StepMeter, Store};
+use wasmi::{
+    core::Value, Caller, Engine, Instance, Linker, Memory, Module, StepMeter, Store,
+    StoreContextMut,
+};
 
 impl wasmi::core::HostError for HostError {}
 
@@ -230,7 +232,7 @@ impl Vm {
         func: &str,
         args: &[RawVal],
     ) -> Result<RawVal, HostError> {
-        host.charge_budget(CostType::VmInvokeFunction, args.len() as u64)?;
+        host.charge_budget(CostType::InvokeVmFunction, 1)?;
         host.with_frame(
             Frame::ContractVM(self.clone(), Symbol::from_str(func)),
             || {
@@ -320,4 +322,18 @@ impl Vm {
     pub fn custom_section(&self, name: impl AsRef<str>) -> Option<&[u8]> {
         Self::module_custom_section(&self.module, name)
     }
+
+    /// Utility function that synthesizes a `VmCaller<Host>` configured to point
+    /// to this VM's `Store` and `Instance`, and calls the provided function
+    /// back with it. Mainly used for testing.
+    pub fn with_vmcaller<F, T>(&self, f: F) -> T
+    where
+        F: FnOnce(&mut VmCaller<Host>) -> T,
+    {
+        let store: &mut Store<Host> = &mut *self.store.borrow_mut();
+        let mut ctx: StoreContextMut<Host> = store.into();
+        let caller: Caller<Host> = Caller::new(&mut ctx, Some(self.instance));
+        let mut vmcaller: VmCaller<Host> = VmCaller(Some(caller));
+        f(&mut vmcaller)
+    }
 }
diff --git a/soroban-env-host/src/vm/dispatch.rs b/soroban-env-host/src/vm/dispatch.rs
index 2d8e77b4..b293b26d 100644
--- a/soroban-env-host/src/vm/dispatch.rs
+++ b/soroban-env-host/src/vm/dispatch.rs
@@ -66,7 +66,7 @@ macro_rules! generate_dispatch_functions {
                     // This does not account for the actual work being done in those functions,
                     // which are accounted for individually at the operation level.
                     let host = caller.host_data().clone();
-                    host.charge_budget(CostType::HostFunction, 1)?;
+                    host.charge_budget(CostType::InvokeHostFunction, 1)?;
                     let mut vmcaller = VmCaller(Some(caller));
                     // The odd / seemingly-redundant use of `wasmi::Value` here
                     // as intermediates -- rather than just passing RawVals --
diff --git a/soroban-synth-wasm/src/func_emitter.rs b/soroban-synth-wasm/src/func_emitter.rs
index a28c1eed..44ef369a 100644
--- a/soroban-synth-wasm/src/func_emitter.rs
+++ b/soroban-synth-wasm/src/func_emitter.rs
@@ -262,7 +262,14 @@ impl FuncEmitter {
     pub fn drop(&mut self) -> &mut Self {
         self.insn(&Instruction::Drop)
     }
-
+    /// Emit an [`Instruction::MemoryGrow`]
+    pub fn mem_grow(&mut self, loc: LocalRef) -> &mut Self {
+        self.insn(&Instruction::MemoryGrow(loc.0))
+    }
+    /// Emit an [`Instruction::MemorySize`]
+    pub fn mem_size(&mut self, loc: LocalRef) -> &mut Self {
+        self.insn(&Instruction::MemorySize(loc.0))
+    }
     /// Emit an [`Instruction::End`] and finish emitting code for this function,
     /// defining it in its enclosing [`ModEmitter`] and returning that
     /// [`ModEmitter`] as well as a [`FuncRef`] referring to the newly-defined
diff --git a/soroban-synth-wasm/src/mod_emitter.rs b/soroban-synth-wasm/src/mod_emitter.rs
index e3cb0ced..15f86bc0 100644
--- a/soroban-synth-wasm/src/mod_emitter.rs
+++ b/soroban-synth-wasm/src/mod_emitter.rs
@@ -2,7 +2,7 @@ use crate::FuncEmitter;
 use std::collections::HashMap;
 use wasm_encoder::{
     CodeSection, CustomSection, EntityType, ExportSection, Function, FunctionSection,
-    ImportSection, Module, TypeSection, ValType,
+    ImportSection, MemorySection, MemoryType, Module, TypeSection, ValType,
 };
 
 /// Wrapper for a u32 that defines the arity of a function -- that is, the number of
@@ -40,6 +40,7 @@ pub struct ModEmitter {
     types: TypeSection,
     imports: ImportSection,
     funcs: FunctionSection,
+    memories: MemorySection,
     exports: ExportSection,
     codes: CodeSection,
 
@@ -60,9 +61,15 @@ impl ModEmitter {
         let types = TypeSection::new();
         let imports = ImportSection::new();
         let funcs = FunctionSection::new();
+        let mut memories = MemorySection::new();
+        memories.memory(MemoryType {
+            minimum: 1,
+            maximum: None,
+            memory64: false,
+            shared: false,
+        });
         let exports = ExportSection::new();
         let codes = CodeSection::new();
-
         let typerefs = HashMap::new();
         let importrefs = HashMap::new();
         Self {
@@ -70,6 +77,7 @@ impl ModEmitter {
             types,
             imports,
             funcs,
+            memories,
             exports,
             codes,
             type_refs: typerefs,
@@ -154,6 +162,9 @@ impl ModEmitter {
         if !self.funcs.is_empty() {
             self.module.section(&self.funcs);
         }
+        if !self.memories.is_empty() {
+            self.module.section(&self.memories);
+        }
         if !self.exports.is_empty() {
             self.module.section(&self.exports);
         }


Test patch:
diff --git a/soroban-env-host/src/test/budget_metering.rs b/soroban-env-host/src/test/budget_metering.rs
index 9291a1c1..4f9d50ea 100644
--- a/soroban-env-host/src/test/budget_metering.rs
+++ b/soroban-env-host/src/test/budget_metering.rs
@@ -42,20 +42,22 @@ fn vm_hostfn_invocation() -> Result<(), HostError> {
         Host::test_storage_with_contracts(vec![dummy_id.into()], vec![VEC], budget.clone());
     let host = Host::with_storage_and_budget(storage, budget)
         .test_budget(100_000, 100_000)
-        .enable_model(CostType::HostFunction);
+        .enable_model(CostType::InvokeVmFunction)
+        .enable_model(CostType::InvokeHostFunction);
 
     let obj = host.test_bin_obj(&dummy_id)?;
     // `vec_err` is a test contract function which calls `vec_new` (1 call)
-    // and `vec_put` (1 call) so total input of 2 to the budget from `CostType::HostFunction`.
+    // and `vec_put` (1 call) so total input of 2 to the budget from `CostType::InvokeHostFunction`.
     let sym = Symbol::from_str("vec_err");
     let args = host.test_vec_obj::<u32>(&[1])?;
 
     // try_call
     host.try_call(obj.to_object(), sym.into(), args.clone().into())?;
     host.with_budget(|budget| {
-        assert_eq!(budget.get_input(CostType::HostFunction), 2);
-        assert_eq!(budget.get_cpu_insns_count(), 20);
-        assert_eq!(budget.get_mem_bytes_count(), 2);
+        assert_eq!(budget.get_input(CostType::InvokeVmFunction), 1);
+        assert_eq!(budget.get_input(CostType::InvokeHostFunction), 2);
+        assert_eq!(budget.get_cpu_insns_count(), 30);
+        assert_eq!(budget.get_mem_bytes_count(), 3);
     });
 
     Ok(())
diff --git a/soroban-synth-wasm/src/test.rs b/soroban-synth-wasm/src/test.rs
index 3c02fa76..3143a116 100644
--- a/soroban-synth-wasm/src/test.rs
+++ b/soroban-synth-wasm/src/test.rs
@@ -52,6 +52,7 @@ fn test_synth_wasm() {
             local.get 0
             call 2
           )
+          (memory (;0;) 1)
           (export "test_map" (func 3))
         )"#]];
     expected.assert_eq(&printed);
diff --git a/soroban-test-wasms/wasm-workspace/Cargo.lock b/soroban-test-wasms/wasm-workspace/Cargo.lock
index 4dccf99b..aeec6247 100644
--- a/soroban-test-wasms/wasm-workspace/Cargo.lock
+++ b/soroban-test-wasms/wasm-workspace/Cargo.lock
@@ -915,6 +915,7 @@ name = "soroban-env-host"
 version = "0.0.9"
 dependencies = [
  "backtrace",
+ "curve25519-dalek",
  "dyn-fmt",
  "ed25519-dalek",
  "hex",
@@ -1279,6 +1280,37 @@ dependencies = [
  "indexmap-nostd",
 ]
 
+[[package]]
+name = "winapi"
+version = "0.3.9"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "5c839a674fcd7a98952e593242ea400abe93992746761e38641405d28b00f419"
+dependencies = [
+ "winapi-i686-pc-windows-gnu",
+ "winapi-x86_64-pc-windows-gnu",
+]
+
+[[package]]
+name = "winapi-i686-pc-windows-gnu"
+version = "0.4.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "ac3b87c63620426dd9b991e5ce0329eff545bccbbb34f3be09ff6fb6ab51b7b6"
+
+[[package]]
+name = "winapi-util"
+version = "0.1.5"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "70ec6ce85bb158151cae5e5c87f95a8e97d2c0c4b001223f33a334e3ce5de178"
+dependencies = [
+ "winapi",
+]
+
+[[package]]
+name = "winapi-x86_64-pc-windows-gnu"
+version = "0.4.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "712e227841d057c1ee1cd2fb22fa7e5a5461ae8e48fa2ca79ec42cfc1931183f"
+
 [[package]]
 name = "zeroize"
 version = "1.3.0"