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. I'll update the patchset to use a new (while a little more complex) to implement BFS with less memory usage. Thank your again for the idea, Qu > > So I still prefer to keep DFS as default and only provides BFS as a > niche option for weird guys like me. > > Thanks, > Qu >
