# Weights for Pallet Functions

When designing and writing FRAME Pallets, it is important to keep in mind the complexity of dispatchable functions and the _weight_ of excuting those functions in a block.

This document describes best practices when writing FRAME pallets for determining the weight of your dispatchable functions.

## Background

### Weights

If you are unfamiliar with weights, the TL;DR is that a Substrate blockchains have limited resources when it comes to producing new blocks. Most notably, there is a limited window for block producers to create a block, limited amount of data that can be included per block ([`MaximumBlockLength`](https://substrate.dev/rustdocs/master/frame_system/trait.Trait.html#associatedtype.MaximumBlockLength)), and an overall practical limit to the storage footprint of the blockchain.

Substrate has introduced a Weight system that allows the runtime developer to tell the block production process how "heavy" an extrinsic is. Given some [`MaximumBlockWeight`](https://substrate.dev/rustdocs/master/frame_system/trait.Trait.html#associatedtype.MaximumBlockWeight), and the weight of the individual extrinsics in a transaction pool, we can select the set of extrinsics that allow us to saturate our block, while not going over the limits.

On top of this basic idea, Substrate has additionally introduced a configurable [`AvailableBlockRatio`](https://substrate.dev/rustdocs/master/frame_system/trait.Trait.html#associatedtype.AvailableBlockRatio) which ensures that only a portion of the total `MaximumBlockWeight` is used for regular transactions. This also introduces the concept of _operational transactions_ which are system critical operations that can use the rest of the available block weight.

#### Example

Let's say a `balance_transfer` has weight 1,000, and our Substrate chain is configured to a maximum block weight of 1,000,000, with an available block ratio of 20%.

This means we would be able to include at most:

1,000,000 * .20 / 1,000 = 200 transfers per block

For more details on weights, read our doc: https://substrate.dev/docs/en/conceptual/runtime/weight

### Fees

To bring the weight system to the users of our blockchain, Substrate introduces a tightly coupled fee system. In short, users will pay a transaction fee proportional to the weight of the call they are making.

total_fee = base_fee + length_fee + weight_fee

> **Note:** There is also a `length_fee` which takes into account the amount of data included in an extrinsic.

As a pallet developer writing new dispatchable functions, the fee system should mostly be abstract to you, and instead you should primarily think in terms of weights.

For more details on fees, read our doc: https://substrate.dev/docs/en/development/module/fees

## Goals

The goal of a runtime developer, with regard to weights and fees, is to:

* Minimize the computational and resource complexity of runtime functions.
* Accurately calculate the relative weight of your runtime functions.

### How

We accomplish this in three steps:

1. Follow best practices when writing a runtime.
2. Accurately document the computational complexity introduced by runtime functions.
3. Emperically measure the real world cost of running these functions, and associate those measurements back to our computational complexity.

## Runtime Best Practices

Probably outside of the scope of this document.

## Documentation of Weights

Dispatchable functions within a FRAME pallet should contain documentation about the computational and resource complexity of the function. The result of weight documentation is to arrive at a final [order of a function](https://en.wikipedia.org/wiki/Big_O_notation). Such as:

O(A + logA + BlogC)

This should serve as a resource to accurately measure the weight of different functions in the [final step](#measuring-weights).

### What to Document

Your weight documentation should include information about your runtime function which has notable execution costs. For example:

* Storage Operations (read, write, mutate, etc...)
* Codec Operations (serializing/deserializing vecs or large structs)
* Search / Sort / Notable Computation
* Calls to other pallet functions (i.e. reserving some balance through the Currency trait)

We will work off the following example function:

// Join a group of members.
fn join(origin) {
    let who = ensure_signed(origin)?;
    let deposit = T::Deposit::get(); // configuration constant
    let sorted_members: Vec<T::AccountId> = Self::members();
    ensure!(sorted_members.len() <= 100, "Membership Full");
    match sorted_members.binary_search(&who) {
        // User is not a member.
        Err(i) => {
            T::Currency::reserve(&who, deposit)?;
            members.insert(i, who.clone());
            <Members<T>>::put(sorted_members);
            Ok(())
        },
        // User is already a member, do nothing.
        Ok(_) => Ok(()),
    }
    Self::deposit_event(RawEvent::Joined(who));
}

#### Storage and Codec Operations

Accessing storage is a heavy operation, and one that should be well documented and optimized in favor writing "functional code". See [Best Practices](#best-practices).

The each storage operation should be documented with the relative codec complexity of interacting with that storage.

For example, if you are reading a vector of members from a single value storage item, the weight documentation should read:

- One storage read to get the members of this pallet: `O(M)`.

In this case reading the vector from storage has a codec complexity of `O(M)` to deserialize the `M` member accounts in the vector.

Later in your module, you might go ahead and write the data back into the runtime, which should also be documented:

- One storage write to update the members of this pallet: `O(M)`.

#### Search, Sort, and Notable Computations

If you need to search or sort in your runtime module, it is also important to note the relative complexity of those operations.

For example, if you are searching for an item in a sorted list, a `binary_search` operation should take `O(logM)`, while an unsorted list, should take `O(M)`.

So the documentation may look like:

- Insert a new member into sorted list: O(logM).

This kind of documentation should be present for any sort of notable heavy computation present in your logic.

#### Calls to Other Pallets and Traits

The computational complexity of your function may extend beyond your pallet. If you call other FRAME pallets either directly or through Trait configurations, you should take note of that, and assign these calls with their own variable.

For example, if you write a function which reserves some balance in the Balances pallet or emits an event through the System pallet, you should document:

- One balance reserve operation: O(B)
- One event emitted: O(E)

### Combining the Data

Once you have good documentation for your runtime function, you need to consolidate it into a _single overall order of the function_.Lets combine the different example operations to create a full end to end example.

# <weight>
Key: M (len of members), B (reserve balance), E (event)
- One storage read to get the members of this pallet: `O(M)`.
- One balance reserve operation: O(B)
- Insert a new member into sorted list: O(logM).
- One storage write to update the members of this pallet: `O(M)`.
- One event emitted: O(E)

Total Complexity: O(M + logM + B + E)
# </weight>

> **Note:** You may have introduced multiple different variables into your overall weight documentation, so be sure to document what these variables represent.

If you look at this example, you can see we had two operations that were O(M) (the storage read and write), but our overall order does not take this into account.

**When doing empirical testing, we are unable to separate complexities which have the same order**. This means that there could be many many more operations added to this function, of order `O(M)`, `O(logM`), etc.. but it would not change our final formula as a function of `M`, `B`, and `E`:

weight(M, B, E) = K_1 + K_2 * M + K_3 * logM + B + E

The difference between two functions with the same order will be empirically measured through on-chain tests. The goal of this step is to simply derive the coefficients (`K`) that we will be searching for when we do the [next step](#measuring-weights).

### Temporary Weight Annotation

Now that you have a reasonable understanding of the weight of your function, you may want to include a temporary weight value before you do empirical testing.

Most often, your extrinsics will be "normal transactions", and your weight annotation will look like:

#[weight = SimpleDispatchInfo::FixedNormal(YOUR_WEIGHT)]

To get an idea of what weight value you should pick, consider the following operations:

* System: Remark - No logic whatsoever. Lowest possible weight (10,000)

    /// Make some on-chain remark.
    #[weight = SimpleDispatchInfo::FixedNormal(10_000)]
    fn remark(origin, _remark: Vec<u8>) {
        ensure_signed(origin)?;
    }

* Staking: Set Controller - One fixed complexity storage read + write. (500,000).

    #[weight = SimpleDispatchInfo::FixedNormal(500_000)]
    fn set_payee(origin, payee: RewardDestination) {
        let controller = ensure_signed(origin)?;
        let ledger = Self::ledger(&controller).ok_or(Error::<T>::NotController)?;
        let stash = &ledger.stash;
        <Payee<T>>::insert(stash, payee);
    }

* Balances: Transfer - fixed time complexity. (1,000,000)

    #[weight = SimpleDispatchInfo::FixedNormal(1_000_000)]
    pub fn transfer(
        origin,
        dest: <T::Lookup as StaticLookup>::Source,
        #[compact] value: T::Balance
    ) {
        let transactor = ensure_signed(origin)?;
        let dest = T::Lookup::lookup(dest)?;
        <Self as Currency<_>>::transfer(&transactor, &dest, value, ExistenceRequirement::AllowDeath)?;
    }

* Elections: Present Winner - O(Voters) heavy compute and one storage write. (10,000,000)

    #[weight = SimpleDispatchInfo::FixedNormal(10_000_000)]
    fn present_winner( ... ) {
        //--lots-of-code--
    }

## Measuring Weights

> This is copy pasta and could be written better once understood better.

The way to figure out weights is to first figure out the [complexity](#documentation-of-weights) and then run benchmarks using properly constructed factory (i.e. one that ensures non-coherence of unstructured accesses).

**Q.** Should I be benchmarking within Rust/Runtime itself or externally through a running node and RPC?

**A.** Using the real runtime is the default way of doing things since it lets us use the Wasm executor. if you can come up with a more ergonomic way of benchmarking, so much the better.

**Q.** How do I create good test inputs?

**A.** Basically, we need to benchmark using lots of different inputs in order to get enough data to conduct a regression analysis. If a particular call that checks a sender account and inserts inserts their id into an ordered vec in storage would be `O(log N + N)`. we need to figure out `K1`, `K2` and `K3` such that time taken `T ~= K_1 + K_2 * log N + K_3 * N`.

### Approach

To measure weights, we would run with various states and inputs to effect different variables.

We must randomize what we can because some operations (like searching a sorted vec and inserting) can have dramatically different costs depending on the specific inputs.

For example, if an account happens to begin with `0xffff...` then it'll be inserted at the end of the vector, which might be very cheap (if the vector is over-allocated). If it goes in at the beginning, then it could be very expensive, needing a large mem-move.

We can't reasonably try all inputs, and it is too expensive to analyze the logic by hand to determine the worst case... so we throw in random data for individual values and use the worst time that comes out.

We should be strictly ensuring that subsequent calls do not benefit from earlier caching. This might be possible by just randomizing everything, but it is probably better to clear all caches (inside Substrate, RocksDB, etc.) between calls.