morpho-data-structures
morpho-data-structures copied to clipboard
Possible optimization in Heap and HeapOrdering storage
When doing the _shiftUp
and _shiftDown
operations, the path from the account to shift up to the root is potentially completely changed. This requires many storage writes which is gas intensive. To improve the efficiency of those operations, we could introduce an intermediate array of pointers, each one of them from an index to another. When doing any operation, this array would be updated without needing to update the actual data.
Notes:
- this solution is efficient if the array of pointer has a small overhead. One idea is to simply store it as a single word, where each byte represents an offset as given by the corresponding
u8
value. This allows to store the heap part of the data-structure up to 128 elements. The_shiftUp
and_shiftDown
operations would only need to update this word one time. - this idea is not compatible with the current way the size is used in the HeapOrdering, because dividing the size by 2 could lead to creating some invalid pointers in the array. To implement this idea in the HeapOrdering, it could wait for the implementation of https://github.com/morpho-org/morpho-data-structures/issues/63
- operations that do not change the data-structure may need to do one more storage access by going through the array of pointers. Tricks could be used to avoid that additional cost, such as packing the array with a storage slot that is always read (like the
size
or even the slot ofaccounts
if we are not afraid of that)