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
>
