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
u8value. This allows to store the heap part of the data-structure up to 128 elements. The_shiftUpand_shiftDownoperations 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
sizeor even the slot ofaccountsif we are not afraid of that)