Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Reduce Binary sizes #585

Open
sanket1729 opened this issue Jul 31, 2023 · 11 comments
Open

Reduce Binary sizes #585

sanket1729 opened this issue Jul 31, 2023 · 11 comments

Comments

@sanket1729
Copy link
Member

sanket1729 commented Jul 31, 2023

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 sanket1729 changed the title 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. Reduce Binary sizes Jul 31, 2023
@sanket1729
Copy link
Member Author

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
Copy link
Contributor

benma commented Jul 31, 2023

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
Copy link
Member

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
Copy link
Member

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

@benma
Copy link
Contributor

benma commented Oct 8, 2023

@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
Copy link
Member Author

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

@benma
Copy link
Contributor

benma commented Jan 16, 2024

@sanket1729 how did it go? 😄

@sanket1729
Copy link
Member Author

@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
Copy link
Member

@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.

apoelstra added a commit that referenced this issue Mar 4, 2024
c8d3b9a fix formatting in big example (Riccardo Casatta)
bc47538 add taproot calls in big executable (Riccardo Casatta)
545bbbe add satisfy call in big executable (Riccardo Casatta)
959546b add psbt finalize call in big executable (Riccardo Casatta)
883132e add policy calls in big executable (Riccardo Casatta)
ec751fb Introduce an example binary useful for profiling (Riccardo Casatta)

Pull request description:

  Tools like `cargo bloat` don't work on libraries but on final executable.

  As seen in #585 and #584 the parse example is used as a base to profile binary bloat.

  However, since the parse example is not using all the API surface, we may have good optimization that are not recognized as such because the optimized function are not in the tree of the functions used.

  For benchmarking size optimization a specific binary that ideally touch all the API surface is needed and this MR introduce it.

  More coverage will be added if this seem a good idea for reviewers.

ACKs for top commit:
  apoelstra:
    ACK c8d3b9a thanks!

Tree-SHA512: 70ac51a222b59b5de76a2ef314be2f3d82b3f5831d90dd7110929a4956a27a6d1eaa4889525dbf54575fb7e07db60f19d67556f2539b61979b4ba681fec0523e
@afilini
Copy link
Contributor

afilini commented Mar 14, 2024

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..

@benma
Copy link
Contributor

benma commented Jun 14, 2024

@sanket1729 is there a way forward here? Would appreciate it. I am still kind of blocked from using additional contexts due to the binary bloat it incurs.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

4 participants