Checkpoints Optimizations#

We noticed three small gas inefficiencies in the checkpoints library.

1. The getAtTime function calculates an average with (low & high) + (low ^ high) / 2 which could be cheaper with (low & high) + ((low ^ high) >> 1). Right shift is cheaper than division and achieves the same result of divide by two.

2. In the push function pos > 0 can be modified to pos != 0 as pos is unsigned and inequality is cheaper than comparison.

3. Normal binary search may not be the most efficient algorithm for finding the desired past checkpoint in practice. For the governance checkpointing use case, old checkpoints are likely less relevant as governance proposals have finite time periods before they are either executed or defeated. Thus you may save users gas by choosing an algorithm that is more biased toward recent blocks. Open zeppelin exposes such an algorithm in their latest checkpointing lib via getAtProbablyRecentBlock which uses len - Math.sqrt(len); for the midpoint on large checkpointing sets. Note that making such a change may not be worth it if you don't foresee a high frequency of delegation as it adds some overhead.