Re: [PATCH] btrfs-progs: dump-tree: Introduce --breadth-first option

[David Sterba <dsterba@suse.cz>]

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.