Optimize Tree.length

[art-w]

The rollups code is using the Tree.length operation in a way that wasn't optimized and resulted in terrible performances:

• They update and query the tree repeatedly, fully in memory (from an existing tree on disk)
• Each tree update is represented in memory by the irmin frontend as the on-disk irmin-pack backend node representation + a map of changes to be committed (removes/adds)
• The Tree.length query needs to flush the map of changes to the irmin-pack backend in order to compute the true length (since otherwise, we don't know if a remove is targeting an existing file or not, and if an add is creating or replacing something) The flushing is actually doing too much for Tree.length, as it also flushes the children nodes recursively: this gets crazy slow for rollups where a lot of updates are accumulated!
• Since flushing the changes is expensive, Tree.length attempts to cache the resulting backend representation -- but this is only possible when the outcome is non-portable to avoid breaking the merkle proofs (non-portable ~= no new inodes... so it's mostly uncached for the rollups)

We can however cache the length! In the end, I went with a lazy incremental solution which seems to bring the most performances for this use case:

• lazy because we only want to compute the length if requested (and then keep it cached)
• incremental because otherwise the next Tree.length query wouldn't be able to reuse the previous result: This is specific to the rollup usage, since they do a bunch of Tree.length => tree update => Tree.length (where the last Tree.length builds on top of a previously sized tree) ... Without this, we would have to recheck all the pending changes with the backend (and it's too slow)

(Note that this PR is targeting irmin 3.6 to ease testing in the rollups code -- issue https://github.com/mirage/irmin/issues/2251 )

[codecov-commenter]

Codecov Report

:exclamation: No coverage uploaded for pull request base (3.6@0d241e6). Click here to learn what that means. The diff coverage is n/a.

:exclamation: Current head 4b50581 differs from pull request most recent head ab3edd9. Consider uploading reports for the commit ab3edd9 to get more accurate results

:exclamation: Your organization is not using the GitHub App Integration. As a result you may experience degraded service beginning May 15th. Please install the Github App Integration for your organization. Read more.

@@          Coverage Diff           @@
##             3.6    #2253   +/-   ##
======================================
  Coverage       ?   68.11%           
======================================
  Files          ?      134           
  Lines          ?    16178           
  Branches       ?        0           
======================================
  Hits           ?    11019           
  Misses         ?     5159           
  Partials       ?        0           

:mega: We’re building smart automated test selection to slash your CI/CD build times. Learn more

[art-w]

Closing in favor of releasing this fix in Irmin 3.7 with #2258