morpho-data-structures icon indicating copy to clipboard operation
morpho-data-structures copied to clipboard

Possible optimization in Heap and HeapOrdering storage

Open QGarchery opened this issue 1 year ago • 0 comments

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 of accounts if we are not afraid of that)

QGarchery avatar Jun 29 '23 08:06 QGarchery