boxo
boxo copied to clipboard
ipld/unixfs: concurrent dag.Walk does a BFS when unsharding
Spawned from https://github.com/ipfs/go-unixfs/pull/106. As explained there, WalkDepth 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
DefaultShardWidthand 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