Explore more efficient data structure for Wthdrawal Queue about yearn-vaults

[Niraj-Kamdar]

I can open up a PR if you want to include it.

[fubuloubu]

I can open up a PR if you want to include it.

Yes please!

The first part of this issue is solved by #299

[Niraj-Kamdar]

I have created an in-memory set data-structure with simple hash function which can be used to remove duplicates from an array.
You can checkout the gist at: https://gist.github.com/Niraj-Kamdar/25d47ae6773ea702cc583a1403627cdd

I will profile it for gas cost and if it seems better than the current solution then we can replace it.

@Niraj-Kamdar in our case, this needs to be on our vault, it's written in Vyper.

[Niraj-Kamdar]

I think I will be able to convert this into a Vyper code.

[fubuloubu]

I have created an in-memory set data-structure with simple hash function which can be used to remove duplicates from an array.
You can checkout the gist at: https://gist.github.com/Niraj-Kamdar/25d47ae6773ea702cc583a1403627cdd

I will profile it for gas cost and if it seems better than the current solution then we can replace it.

Thanks for sharing! As @steffenix said, in order to work for us it would need to be implemented in Vyper. but could also explore the idea of set membership to maintain proper use of the queue.

[Niraj-Kamdar]

I will try to convert it into vyper and make it work out for yearn vault

[Niraj-Kamdar]

I have converted the code in Vyper and benchmarked it and it seems promising:

Without Set (current):

TestStrategy <Contract>
   └─ constructor             -  avg: 2927246  avg (confirmed): 2927246  low: 2926947  high: 2927375
Vault <Contract>
   ├─ constructor             -  avg: 4650568  avg (confirmed): 4650568  low: 4650568  high: 4650568
   ├─ initialize              -  avg:  354550  avg (confirmed):  354550  low:  354468  high:  354579
   ├─ addStrategy             -  avg:  197132  avg (confirmed):  205796  low:   23914  high:  220661
   ├─ setWithdrawalQueue      -  avg:  115595  avg (confirmed):  289094  low:   28438  high:  289094
   ├─ removeStrategyFromQueue -  avg:   85318  avg (confirmed):  146051  low:   24588  high:  146051
   ├─ setDepositLimit         -  avg:   43852  avg (confirmed):   43852  low:   43852  high:   43852
   ├─ addStrategyToQueue      -  avg:   41719  avg (confirmed):   87202  low:   24562  high:   87202
   ├─ setManagement           -  avg:   28659  avg (confirmed):   28659  low:   28659  high:   28659
   └─ withdrawalQueue         -  avg:   23955  avg (confirmed):   23955  low:   23955  high:   23967



With Set (proposed solution)

TestStrategy <Contract>
   └─ constructor             -  avg: 2927246  avg (confirmed): 2927246  low: 2926947  high: 2927375
Vault <Contract>
   ├─ constructor             -  avg: 4774516  avg (confirmed): 4774516  low: 4774516  high: 4774516
   ├─ initialize              -  avg:  354550  avg (confirmed):  354550  low:  354468  high:  354579
   ├─ addStrategy             -  avg:  197132  avg (confirmed):  205796  low:   23914  high:  220661
   ├─ removeStrategyFromQueue -  avg:   85318  avg (confirmed):  146051  low:   24588  high:  146051
   ├─ setWithdrawalQueue      -  avg:   79069  avg (confirmed):  200065  low:   28438  high:  200065
   ├─ setDepositLimit         -  avg:   43852  avg (confirmed):   43852  low:   43852  high:   43852
   ├─ addStrategyToQueue      -  avg:   41719  avg (confirmed):   87202  low:   24562  high:   87202
   ├─ setManagement           -  avg:   28659  avg (confirmed):   28659  low:   28659  high:   28659
   └─ withdrawalQueue         -  avg:   23955  avg (confirmed):   23955  low:   23955  high:   23967

As you can see, in proposed solution setWithdrawalQueue is only consuming 79069 compared to 115595 gas cost of current solution. This ofcourse comes with slightly high gas cost of constructor from 4650568 to 4774516.