Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Update AMT / HAMT libraries to allow for ranged iteration #186

Closed
alexytsu opened this issue Jan 18, 2023 · 4 comments
Closed

Update AMT / HAMT libraries to allow for ranged iteration #186

alexytsu opened this issue Jan 18, 2023 · 4 comments

Comments

@alexytsu
Copy link
Member

Currently the only way to iterate through the contents of a HAMT / AMT is via a for_each that explores every node in the tree.

This is prohibitively expensive in gas costs and disallows paginated APIs to be developed on top of these data structures. In particular the motivating use case of enumerating tokens, owners and balances in the FRC53 NFT standard is not feasible without a paginated API. Therefore, enumeration needs to be scoped to a certain predictable set of ranges.

For both the HAMT and AMT the main gas cost comes from expansion of CID -> Nodes during tree traversal. A limit on the number of blocks expanded/explored will put a limit on gas costs.

By specifying a start range and end range for indexes when iterating through AMTs it is possible to limit the number of nodes explored and thus limit the gas costs.

@alexytsu
Copy link
Member Author

POC implementations are found:
#185
helix-onchain/ref-fvm#1

@alexytsu
Copy link
Member Author

unresolved API question/design decision: should the range of iteration be specified by:

  • index which is potentially a less specific estimation of gas costs but more aligned with high level use cases
  • blocks expanded/read which potentially corresponds closer to incurred gas costs but leads to less predictable ranges being specified

@anorth
Copy link
Collaborator

anorth commented Jan 18, 2023

I propose letting the caller decide, by providing both values to a predicate that indicates whether to keep gooing

@alexytsu
Copy link
Member Author

alexytsu commented Mar 21, 2023

Closed along with filecoin-project/ref-fvm#1514

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants