ipld/unixfs: concurrent dag.Walk does a BFS when unsharding
- Dominant language
- Go
- Stars
- 316
- Forks
- 163
- Avg merge
- 4d 12h
- Merged PRs (30d)
- 8
Description
Spawned from https://github.com/ipfs/go-unixfs/pull/106. As explained there, [`WalkDepth`](https://github.com/ipfs/go-merkledag/blob/4a8891d5ef68f0711656579672d17f8533100add/merkledag.go#L397) does a BFS when called with the concurrent option, which is what we do in the HAMT when enumerating all links (`(*Shard).EnumLinksAsync()`).
Depending on the distribution of the shards in the HAMT this _might_ mean that we will unnecessarily fetch more nodes/shards than we need to. This is currently exemplified in the test in https://github.com/ipfs/go-unixfs/pull/106:
* we traverse a complete HAMT to fetch enough directory entries to reach the threshold
* the _artificial_ HAMT used in the test is complete in the sense that every node has the maximum number of children allowed per `DefaultShardWidth` and all leaf nodes have the same depth
* to reach the directory entries ('value' links) we need to reach the leaf nodes in the base of the tree
* in a BFS to do that we need to fetch *every* node above that last layer
cc @aschmahmann @Stebalien
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.