2

It appears in substrate this is O(n), but want to confirm since I believe hashbrown just wipes control bytes, which appears O(1).


Side note:

The problem I'm trying to solve is tracking a number of free calls (u16) an account gets per era.

Data structures are stored like:

  type FreeCalls = u16;

  #[pallet::pallet]
  #[pallet::generate_store(pub(super) trait Store)]
  pub struct Pallet<T>(_);

  /// To disable free calls, set this to `None` or leave it unitialized.
  #[pallet::storage]
  #[pallet::getter(fn free_calls_per_era)]
  pub type FreeCallsPerEra<T> = StorageValue<_, FreeCalls>;

  /// Stores how many calls a user has left for this era.
  ///
  /// `Some(n)` : user has n free calls left
  /// `Some(0)` : user has zero free calls left
  /// `None` : user has not used any free calls yet this era (so set it to FreeCallsPerEra)
  #[pallet::storage]
  #[pallet::getter(fn free_calls_left)]
  pub type FreeCallsLeft<T> = StorageMap<_, Blake2_128Concat, T::AccountId, FreeCalls, OptionQuery>;

As the comments in the above code explain, we can check the number of free calls an account has left by querying FreeCallsLeft<T>. If None, they have free_calls_per_era() calls left, and Some(0) means they've used them all. To reset this, we clear() the map, and we would do it every era.

Is there a better approach to this, or do we just deal with O(n) clear() every era? Sure, the map value could be (free_calls_left, era_index) and reset the free calls and current era when queried, but then we basically store every account forever until we prune it.

1 Answer 1

3

It appears in substrate this is O(n), but want to confirm since I believe hashbrown just wipes control bytes, which appears O(1).

It is O(n). hashbrown is a in memory hash map and there you only need to delete the inner structure, while for our storage map you need to iterate over all elements and set them as deleted.

To your other question. You could use a StorageDoubleMap:

type FreeCallsLeft = StorageDoubleMap<EraIndex, AccountId, Value>;
type EraToClean = StorageValue<EraIndex>;

Then you could leverage on_idle:

fn on_idle(block_number, weight_left_in_block) {
    let era_to_clean = EraToClean::get();
    
    if era_to_clean < CurrentEra::get() {
         let res = FreeCallsLeft::clear_prefix(
           // Clear everything under the given first key
           era_to_clean, 
           // Every call to this function, aka at most once per block,
           // we will delete 100 elements.
           // This should actually be calculated based on the remaining weight
           // of the block to ensure we don't overuse our budget
           100,
           None,
         );

         if res.maybe_cursor.is_none() {
           EraToClean::put(era_to_clean + 1);
         }
    }
}

Be aware that the code above is very pseudo and needs some adjustments here and there :P However, to convey the idea it should be enough. The given logic would also not really work if FreeCallsLeft is unlimited. Aka there could be too many elements in it to delete in on era.

5
  • Thanks for the explanation on hashbrown and elaboriating on another solution! on_idle is perfect. Aug 23, 2022 at 15:22
  • From the docs for clear_prefix: "The maybe_cursor parameter should be None for the first call to initial removal. If the resultant maybe_cursor is Some, then another call is required to complete the removal operation. This value must be passed in as the subsequent call’s maybe_cursor parameter." However I noticed this solution never passes the cursor back in - is this intentional? Can you explain? Thanks. Sep 5, 2022 at 8:22
  • 1
    I'm cheating a little bit, as I know how it works. Basically when you call this only once per block, it is fine to not pass the cursor.
    – bkchr
    Sep 5, 2022 at 14:17
  • Call this clear_prefix for one prefix once per block OR could I call it on multiple different prefixes once per block without passing the last cursor? So in example: clear_prefix(prefix_1, half_limit, None) AND clear_prefix(prefix_2, half_limit, None) once per block?
    – Chralt
    Sep 15, 2022 at 9:57
  • Maybe some documentation for this would be nice to use this simpler approach as an API user.
    – Chralt
    Sep 15, 2022 at 10:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.