What is the time complexity of StorageMap::clear()?

Question

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.

Answer 1

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.