Reduce Binary sizes

[sanket1729]

There are a lot of things we can do in the longer term to help this. We can split out the crates into multiple separate crates like psbt, interpreter, descriptor and policy. This would reduce the compilation time and memory usage by offering flexibility.

As pointed by benma , this is because we use a lot of generics. In particular, almost every single function is being monomorphized for each Ctx.
There are 4 types of Contexts (Bare, Legacyp2sh, Segwitv0, Taproot) that are compiled for each descriptor method. One idea might be to define Terminal without the Context. Guard Miniscript with appropriate Context while in the constructor Miniscript::from_ast. This should significantly reduce the code duplication and have a good impact on binary sizes.

Originally posted by @sanket1729 in #584 (comment)

[sanket1729]

Using a third party tool cargo-bloat, indeed monomorphization is the cause for this.

sanket1729:~/rust-miniscript/examples$ cargo bloat --release --example parse -n 100 --filter=miniscript --full-fn
    Finished release [optimized] target(s) in 0.02s
    Analyzing target/release/examples/parse

File .text     Size      Crate Name
0.2%  1.5%   9.9KiB miniscript miniscript::miniscript::astelem::<impl miniscript::expression::FromTree for miniscript::miniscript::decode::Terminal<Pk,Ctx>>::from_tree::hf7cabd7b5ae86e5f
0.2%  1.4%   9.7KiB miniscript miniscript::miniscript::astelem::<impl miniscript::expression::FromTree for miniscript::miniscript::decode::Terminal<Pk,Ctx>>::from_tree::h252a38afb9bfe9a7
0.2%  1.4%   9.5KiB miniscript miniscript::miniscript::astelem::<impl miniscript::expression::FromTree for miniscript::miniscript::decode::Terminal<Pk,Ctx>>::from_tree::hc8530801dfa8e9a7
0.2%  1.4%   9.5KiB miniscript miniscript::miniscript::astelem::<impl miniscript::expression::FromTree for miniscript::miniscript::decode::Terminal<Pk,Ctx>>::from_tree::h1e2d92ae3f2f5e67
0.1%  0.8%   5.7KiB miniscript miniscript::descriptor::tr::Tr<Pk>::script_pubkey::h411db1856768cd27
0.1%  0.6%   4.1KiB miniscript miniscript::miniscript::astelem::<impl miniscript::miniscript::decode::Terminal<Pk,Ctx>>::encode::hc780c981e4af3066
0.1%  0.6%   4.1KiB miniscript miniscript::miniscript::astelem::<impl miniscript::miniscript::decode::Terminal<Pk,Ctx>>::encode::ha6bb98535a3f1d23
0.1%  0.6%   4.1KiB miniscript miniscript::miniscript::astelem::<impl miniscript::miniscript::decode::Terminal<Pk,Ctx>>::encode::h1b1c4ea55afdf05a
0.1%  0.6%   4.1KiB miniscript miniscript::miniscript::astelem::<impl miniscript::miniscript::decode::Terminal<Pk,Ctx>>::encode::h1048523d61cd6482
0.1%  0.5%   3.4KiB miniscript <miniscript::miniscript::types::extra_props::ExtData as miniscript::miniscript::types::Property>::type_check::he0e005cc44ffaef5
0.1%  0.5%   3.4KiB miniscript <miniscript::miniscript::types::extra_props::ExtData as miniscript::miniscript::types::Property>::type_check::he0bb0bb03a8c988f
0.1%  0.5%   3.4KiB miniscript <miniscript::miniscript::types::extra_props::ExtData as miniscript::miniscript::types::Property>::type_check::hbbe183b46053f973
0.1%  0.5%   3.4KiB miniscript <miniscript::miniscript::types::extra_props::ExtData as miniscript::miniscript::types::Property>::type_check::h55cf55507009c200
0.1%  0.5%   3.3KiB miniscript <miniscript::miniscript::types::extra_props::ExtData as miniscript::miniscript::types::Property>::threshold::h39405ea660688245
0.0%  0.4%   2.7KiB miniscript miniscript::miniscript::astelem::<impl core::fmt::Debug for miniscript::miniscript::decode::Terminal<Pk,Ctx>>::fmt::hfddb3b009d985bde
0.0%  0.4%   2.7KiB miniscript miniscript::miniscript::astelem::<impl core::fmt::Debug for miniscript::miniscript::decode::Terminal<Pk,Ctx>>::fmt::hec23b10ddd3645d9
0.0%  0.4%   2.7KiB miniscript miniscript::miniscript::astelem::<impl core::fmt::Debug for miniscript::miniscript::decode::Terminal<Pk,Ctx>>::fmt::h9565457e0b0a55fb
0.0%  0.4%   2.7KiB miniscript miniscript::miniscript::astelem::<impl core::fmt::Debug for miniscript::miniscript::decode::Terminal<Pk,Ctx>>::fmt::h70d98cbd16a857a4
0.0%  0.4%   2.6KiB miniscript miniscript::miniscript::astelem::<impl core::fmt::Display for miniscript::miniscript::decode::Terminal<Pk,Ctx>>::fmt::hd6a050c95d1e7fe8
0.0%  0.4%   2.6KiB miniscript miniscript::miniscript::astelem::<impl core::fmt::Display for miniscript::miniscript::decode::Terminal<Pk,Ctx>>::fmt::ha71ff389c9451f69
0.0%  0.4%   2.6KiB miniscript miniscript::miniscript::astelem::<impl core::fmt::Display for miniscript::miniscript::decode::Terminal<Pk,Ctx>>::fmt::h3746c006146980ea
0.0%  0.4%   2.6KiB miniscript miniscript::miniscript::astelem::<impl core::fmt::Display for miniscript::miniscript::decode::Terminal<Pk,Ctx>>::fmt::h0e36d10483a7a138
0.0%  0.3%   2.3KiB miniscript <miniscript::descriptor::sh::Sh<Pk> as miniscript::expression::FromTree>::from_tree::h3c9003188cff6c2f
0.0%  0.3%   2.3KiB miniscript <miniscript::miniscript::types::Type as miniscript::miniscript::types::Property>::type_check::hd7747b9cffabb885
0.0%  0.3%   2.3KiB miniscript <miniscript::miniscript::types::Type as miniscript::miniscript::types::Property>::type_check::hcbfa9735205d40e0
0.0%  0.3%   2.3KiB miniscript <miniscript::miniscript::types::Type as miniscript::miniscript::types::Property>::type_check::hcbdb9973dc3d68f2
0.0%  0.3%   2.3KiB miniscript <miniscript::miniscript::types::Type as miniscript::miniscript::types::Property>::type_check::hb542b64ed9dfb13a
0.0%  0.3%   2.3KiB miniscript <miniscript::miniscript::types::Type as miniscript::miniscript::types::Property>::type_check::h52e2a33bf426f7a2
0.0%  0.3%   2.3KiB miniscript <miniscript::miniscript::types::Type as miniscript::miniscript::types::Property>::type_check::h4632dba594469034
0.0%  0.3%   2.3KiB miniscript <miniscript::miniscript::types::Type as miniscript::miniscript::types::Property>::type_check::h2d918fc43f86a047
0.0%  0.3%   2.3KiB miniscript <miniscript::miniscript::types::Type as miniscript::miniscript::types::Property>::type_check::h2b30d3216ca1a7e1
0.0%  0.3%   1.9KiB miniscript miniscript::descriptor::tr::parse_tr_tree::h5af334089dd0a672
0.0%  0.3%   1.7KiB miniscript miniscript::expression::Tree::from_slice_delim::h90458f5ec70f5178
0.0%  0.2%   1.7KiB miniscript <miniscript::Error as core::fmt::Display>::fmt::h956f32630aa2fbc9
0.0%  0.2%   1.6KiB miniscript miniscript::descriptor::sortedmulti::SortedMultiVec<Pk,Ctx>::from_tree::hc38bac7d923f53d7
0.0%  0.2%   1.6KiB miniscript miniscript::descriptor::sortedmulti::SortedMultiVec<Pk,Ctx>::from_tree::h818f876f47b01283
0.0%  0.2%   1.5KiB miniscript <miniscript::descriptor::segwitv0::Wsh<Pk> as miniscript::expression::FromTree>::from_tree::h92504036f8ccce01
0.0%  0.2%   1.3KiB miniscript <miniscript::miniscript::types::extra_props::ExtData as miniscript::miniscript::types::Property>::and_or::h7952c25db21933df
0.0%  0.2%   1.3KiB miniscript miniscript::descriptor::tr::Tr<Pk>::parse_tr_script_spend::h34f82b5731bf960d

[benma]

Removing monomorphization for the script context would be very welcome, I hope you can work on it soon.

Any thoughts about removing the Ctx type param in favor of dynamic dispatch, or maybe even passing the context as a simple enum argument?

[apoelstra]

Any thoughts about removing the Ctx type param in favor of dynamic dispatch

Let's see how much mileage we could get out of reducing monomorphization by moving it to the edges. Dynamic dispatch on every single descriptor-related function would be a pretty heavy price to pay I think.

I'm also not totally sure, technically, if we could do it. If all our uses of Ctx are done by calling functions on the Ctx itself that's straightforward but if we've got impl blocks on e.g. Descriptor<Ctx> for specific Ctx values that would require some refactoring.

[apoelstra]

https://jmmv.dev/2023/08/rust-static-dispatch-failed-experiment.html is maybe relevant to this discussion.

[benma]

@sanket1729 do you plan to pick this up? It would be very helpful now that minitapscript was merged to Bitcoin Core. I already use the Segwitv0 context and want to also use the Taproot context, but it adds too much binary code while I would expect the difference to be quite minimal.

[sanket1729]

@benma, I will take a stab at this today.

[benma]

@sanket1729 how did it go? 😄

[sanket1729]

@benma, not good. This was more invasive than I anticipated. I am still working on it.

@apoelstra, this is what I am attempting at a high level.

1. Change all the internal functions from Minsicript<Pk, Ctx> to MsUnchecked. Introduce APIs to convert from MsUnchecked<Pk> to Miniscript<Pk, Ctx>.
2. Our type checking currently is dependent on ScriptContext (some fragments are allowed in some contexts, different resource limit constraints, x-only, compressed etc). Instead of having a Ctx generic parameter, we will use a ScriptContext enum parameter to help with type checking.
3. Where required introduce context specific functions. For example,

#[derive(Clone)]
pub struct MsUnChecked<Pk: MiniscriptKey> {
    /// A node in the AST.
    pub node: Terminal<Pk>,
    /// The correctness and malleability type information for the AST node.
    pub ty: types::Type,
    /// Additional information helpful for extra analysis.
    pub ext: types::extra_props::ExtData,
}

#[derive(Clone)]
pub struct Miniscript<Pk: MiniscriptKey, Ctx: ScriptContext> {
    /// A node in the AST.
    pub inner: MsUnChecked<Pk>,
    /// Context PhantomData. Only accessible inside this crate
    phantom: PhantomData<Ctx>,
}

/// APIs that stay the same. Inside the same impl block Miniscript<Pk, Ctx>
impl Miniscript<Pk, Ctx> {
    fn encode(&self) -> Script {
       self.inner.encode()
    }
}

/// Special purpose APIs that are different for each context.
impl Miniscript<Pk, SegwitV0> {
   fn script_size(&self) -> usize {
      self.inner.script_size(Ctx::Segwitv0) // script_size would be function in MsUnchchecked that takes paramter instead of generic parametrization .
   }
}

@apoelstra, any comments on this approach?

[apoelstra]

@sanket1729 that sounds great! The hardest part (aside from this probably touching every single LOC in the library :)) sounds like the conversions. But maybe if our public API consists only of wrapper types, and all the recursive types stay as MsUnchecked and therefore don't need to be converted, it could work out.

Also cc #484 ... I think we're blocked on Rust language stuff to be able to move to a flat representation but wanted to remind people of that issue nonetheless. Since we're thinking about changing data representations.

[afilini]

Thanks for your hard work, just adding my experience here: I recently updated BDK in my project and the update also bumped rust-miniscript from v9.0.2 to v10.0.0. Between these two versions the code size for miniscript went from 72.0KiB to 129.7KiB!

Maybe before doing more "invasive" work just looking at the diff between these two versions could bring pretty big improvements..