HeapOrdering Code Style Findings

HOG-01C: Downward Traversal Optimization

Type	Severity	Location
Gas Optimization		HeapOrdering.sol:L151, L154

Description:

The shiftDown downward traversal mechanism of the heap structure is sub-optimal as it computes the result of getAccount operations duplicate times in all cases.

Example:

Copy
147while (childRank <= size) {
148    // Compute the rank of the child with largest value.
149    if (
150        childRank < size &&
151        getAccount(_heap, childRank + 1).value > getAccount(_heap, childRank).value
152    ) childRank++;
153
154    childAccount = getAccount(_heap, childRank);
155
156    if (childAccount.value > initialValue) {
157        setAccount(_heap, _rank, childAccount);
158        _rank = childRank;
159        childRank <<= 1;
160    } else break;
161}

Recommendation:

We advise the result of the first getAccount invocation within the while loop to be cached and overwritten in the if block by the next child's account lookup if the condition is met, thus ensuring getAccount is at most invoked a single time per child.

Alleviation:

The optimization has been applied as optimally as possible, enhancing the legibility of the codebase and optimizing its gas cost.

HOG-02C: Increase Swap Optimization

Type	Severity	Location
Gas Optimization		HeapOrdering.sol:L230

Description:

The swap operation performed during an increase operation can be optimized by performing it conditionally only when nextSize != rank as otherwise the heap will replace an element with itself.

Example:

Copy
210/// @notice Increases the amount of an account in the `_heap`.
211/// @dev Only call this function when `_id` is in the `_heap` with a smaller value than `_newValue`.
212/// @param _heap The heap to modify.
213/// @param _id The address of the account to increase the amount.
214/// @param _newValue The new value of the account.
215/// @param _maxSortedUsers The maximum size of the heap.
216function increase(
217    HeapArray storage _heap,
218    address _id,
219    uint256 _newValue,
220    uint256 _maxSortedUsers
221) private {
222    uint256 rank = _heap.ranks[_id];
223    Account memory account = getAccount(_heap, rank);
224    account.value = _newValue;
225    setAccountValue(_heap, rank, _newValue);
226    uint256 nextSize = _heap.size + 1;
227
228    if (rank < nextSize) shiftUp(_heap, rank);
229    else {
230        swap(_heap, nextSize, rank);
231        shiftUp(_heap, nextSize);
232        _heap.size = computeSize(nextSize, _maxSortedUsers);
233    }
234}

Recommendation:

We advise this conditional to be introduced optimizing the best-case gas cost of the function with minimal impact on the worst-case scenario.

Alleviation:

The optimization has been properly applied at the swap function level instead of the calling code, ensuring that swaps are only performed as necessary.

HOG-03C: Insertion Swap Optimization

Type	Severity	Location
Gas Optimization		HeapOrdering.sol:L188

Description:

The swap operation performed during an insertion operation can be optimized by performing it conditionally only when newSize != accountsLength as otherwise the heap will replace an element with itself.

Example:

Copy
165/// @notice Inserts an account in the `_heap`.
166/// @dev Only call this function when `_id` is not in the `_heap`.
167/// @dev Reverts with AddressIsZero if `_value` is 0.
168/// @param _heap The heap to modify.
169/// @param _id The address of the account to insert.
170/// @param _value The value of the account to insert.
171/// @param _maxSortedUsers The maximum size of the heap.
172function insert(
173    HeapArray storage _heap,
174    address _id,
175    uint256 _value,
176    uint256 _maxSortedUsers
177) private {
178    // `_heap` cannot contain the 0 address.
179    if (_id == address(0)) revert AddressIsZero();
180
181    // Put the account at the end of accounts.
182    _heap.accounts.push(Account(_id, _value));
183    uint256 accountsLength = _heap.accounts.length;
184    _heap.ranks[_id] = accountsLength;
185
186    // Move the account at the end of the heap and restore the invariant.
187    uint256 newSize = _heap.size + 1;
188    swap(_heap, newSize, accountsLength);
189    shiftUp(_heap, newSize);
190    _heap.size = computeSize(newSize, _maxSortedUsers);
191}

Recommendation:

We advise this conditional to be introduced optimizing the best-case gas cost of the function with minimal impact on the worst-case scenario.

Alleviation:

The optimization has been properly applied at the swap function level instead of the calling code, ensuring that swaps are only performed as necessary.

HOG-04C: Potential Significant Optimization

Type	Severity	Location
Gas Optimization		HeapOrdering.sol:L7

Description:

Depending on the needs of the application that will ultimately utilize the library, the Account data structure can be significantly optimized by reducing its value member's accuracy from 256-bits to 96-bits, thereby permitting the address variable to be tight-packed with the uint96 into a single 32-byte slot. This will reduce all storage reads and writes for Account entries to one SLOAD / SSTORE operation regardless of whether both members are written to or read from in the same action.

Example:

Copy
5struct Account {
6    address id; // The address of the account.
7    uint256 value; // The value of the account.
8}

Recommendation:

We advise this to be done so if the 96-bit accuracy is sufficient for the end-user application.

Alleviation:

The codebase has been updated to support the uint96 data type significantly optimizing the gas cost of all operations due to the substantially less SLOAD operations required.

HOG-05C: Potential Significant Utility Optimization

Type	Severity	Location
Gas Optimization		HeapOrdering.sol:L4

Description:

The heap data structure implemented by the library is usually utilized to implement priority queues and other similar mechanisms where a common use case is to "pop" the upper-most parent of the "queue" and insert a new item that should be queued for the next iteration. If this is an envisioned use case for the heap, a significant utility and gas optimization can be achieved by implementing a dedicated "replace" function that replaces the root of the tree and then ascertains order by performing a single shiftDown operation.

Example:

Copy
4library HeapOrdering {

Recommendation:

We advise this use-case to be evaluated and the function described to be implemented in case it is envisioned as frequent given that it will lead to significant gas optimizations.

Alleviation:

The Morpho team evaluated this exhibit and concluded that the additional utility is not valuable to their use-case of the heap library and as such they will not proceed with implementing it. As a result, we consider this exhibit nullified given that it does not match Morpho's use case.

HOG-06C: Removal Swap Optimization

Type	Severity	Location
Gas Optimization		HeapOrdering.sol:L250

Description:

The swap operation performed during an removal operation can be optimized by performing it conditionally only when rank != accountsLength as otherwise the heap will replace an element with itself.

Example:

Copy
236/// @notice Removes an account in the `_heap`.
237/// @dev Only call when this function `_id` is in the `_heap` with value `_removedValue`.
238/// @param _heap The heap to modify.
239/// @param _id The address of the account to remove.
240/// @param _removedValue The value of the account to remove.
241function remove(
242    HeapArray storage _heap,
243    address _id,
244    uint256 _removedValue
245) private {
246    uint256 rank = _heap.ranks[_id];
247    uint256 accountsLength = _heap.accounts.length;
248
249    // Swap the last account and the account to remove, then pop it.
250    swap(_heap, rank, accountsLength);
251    if (_heap.size == accountsLength) _heap.size--;
252    _heap.accounts.pop();
253    delete _heap.ranks[_id];
254
255    // If the swapped account is in the heap, restore the invariant: its value can be smaller or larger than the removed value.
256    if (rank <= _heap.size) {
257        if (_removedValue > getAccount(_heap, rank).value) shiftDown(_heap, rank);
258        else shiftUp(_heap, rank);
259    }
260}

Recommendation:

We advise this conditional to be introduced optimizing the best-case gas cost of the function with minimal impact on the worst-case scenario.

Alleviation:

The optimization has been properly applied at the swap function level instead of the calling code, ensuring that swaps are only performed as necessary.

HOG-07C: Removal Upward Shift Optimization

Type	Severity	Location
Gas Optimization		HeapOrdering.sol:L258

Description:

The shiftUp operation is performed unconditionally whilst a child and parent's value can indeed match, thus executing an upwards shift inefficiently if the element removed was next-to-last in the tree and its children had an equal value to it.

Example:

Copy
255// If the swapped account is in the heap, restore the invariant: its value can be smaller or larger than the removed value.
256if (rank <= _heap.size) {
257    if (_removedValue > getAccount(_heap, rank).value) shiftDown(_heap, rank);
258    else shiftUp(_heap, rank);
259}

Recommendation:

We advise the else statement to be adjusted to an else if (_removedValue < getAccount(_heap, rank).value) one, with the getAccount(_heap, rank).value value being cached to a local variable within the upper-most if clause to avoid the duplicate read gas cost between the if and else if conditional evaluations.

Alleviation:

The Morpho team stated that they do not believe an equality case to be frequent for their use-case of the heap structure and as such they will not proceed with applying the changes recommended by the exhibit instead acknowledging it.

HOG-08C: Upward Traversal Optimization

Type	Severity	Location
Gas Optimization		HeapOrdering.sol:L128, L129

Description:

The shiftUp upward traversal mechanism of the heap structure is sub-optimal as it computes the result of getAccount(_heap, _rank >> 1) twice redundantly.

Example:

Copy
128while (_rank > 1 && initialValue > getAccount(_heap, _rank >> 1).value) {
129    setAccount(_heap, _rank, getAccount(_heap, _rank >> 1));
130    _rank >>= 1;
131}

Recommendation:

We advise the result to be cached to a local variable that is consequently utilized for the while loop condition and setAccount execution thus optimizing the gas cost of the function significantly.

Alleviation:

After extensive discussions surrounding the validity of the optimization, the Morpho team properly evaluated and assimilated the optimization described by this exhibit in the codebase ensuring that the upward traversal of the binary tree is performed as optimally as possible.