On Tue, Sep 04, 2018 at 08:39:55PM +0800, Qu Wenruo wrote: > > > On 2018/8/23 下午3:45, Qu Wenruo wrote: > > > > > > On 2018/8/23 下午3:36, Nikolay Borisov wrote: > >> > >> > >> On 23.08.2018 10:31, Qu Wenruo wrote: > >>> Introduce --breadth-first option to do breadth-first tree dump. > >>> This is especially handy to inspect high level trees, e.g. comparing > >>> tree reloc tree with its source tree. > >> > >> Will it make sense instead of exposing another option to just have a > >> heuristics check that will switch to the BFS if the tree is higher than, > >> say, 2 levels? > > > > BFS has one obvious disadvantage here, so it may not be a good idea to > > use it for default. > > Well, this is only true for my implementation. > > But there are other solutions to do BFS without that heavy memory usage. > > > > >>> More memory usage << > > It needs to alloc heap memory, and this can be pretty large for > > leaves. > > At level 1, it will need to alloc nr_leaves * sizeof(bfs_entry) > > memory at least. > > Compared to DFS, it only needs to iterate at most 8 times, and all of > > its memory usage is function call stack memory. > > > > It only makes sense for my niche use case (compare tree reloc tree with > > its source). > > For real world use case the default DFS should works fine without all > > the memory allocation burden. > > Since we have btrfs_path to show where our parents are, it's possible to > use btrfs_path and avoid current memory burden. > > And in that case, your idea of using BFS default for tree higher than 2 > levels completely make sense. No such games please, keep the default predictable. As DFS and BFS are quite well-known abbreviations, I'd rather add 2 options to set the the mode, ie --dfs and --bfs. Alternatively there could be a --traverse=bfs --traverse=dfs but for now I think the two options should be sufficient.
