Edit: I just realized that CI is already failing because of it:

the size of this (96) should not exceed 80 as it affects overall memory consumption

Maybe we can give it a try and see what would happen if this was a boolean instead?

Thanks for taking a look. Yes, on reflection I agree it makes sense to be cautious about adding that extra field to the EntryData struct. I've had a bit of a think about the right way to proceed here.

Alternative 1 - Still try to add directory inode size in set_entry_info_or_panic, but without storing the own_size field on EntryData

I see what you are suggesting regarding the boolean flag: if we know that an entry is a directory, we can add the directory inode's size to the size field whenever we update our tree of EntryData nodes, without having to also store the extra own_size field. Actually, we don't even need to check a boolean flag, since we only ever call set_entry_info_or_panic for directories anyway. The problem is that its not straightforward to compute the directory inode's size when we need it.

For example we might try using a constant as in the following

pub fn set_entry_info_or_panic(...) {
    ...
    // Doesn't work as directory inodes can vary in size
    node.size = size + DIR_INODE_SIZE_CONSTANT;
   ...
}

but the directory inode size may vary depending on the number of children it has. I also thought about grabbing the inode size from the file metadata here e.g. like this

pub fn set_entry_info_or_panic(...) {
   ...
   let node_own_size = std::fs::metadata(&node.name)
        .map(|m| m.len())
        .expect("This panics because node.name is the immediate directory name not a path")
    as u128;
   
    node.size = size + node_own_size;
    ...
}

but we need a proper path here, not just the directory's name. Presumably we don't want to start storing that on the EntryData structure for the same reasons we don't want to start storing own_size. Also, computing the directory entry size like this seems redundant, since we already process the directory metadata once the TraversalEvent for that directory arrives.

Alternative 2 - Track directory inode sizes during recursive traversal of the filesystem

The original PR changes and Alternative 1 both leave untouched the algorithm which recursively computes the size of the directory's contents. This approach would add three fields to the BackgroundTraversal struct to augment the existing recursive traversal:

• parent_node_size_per_depth_level, is a stack of directory inode sizes for ancestor nodes along the current branch
• parent_node_size, analogous to parent_node_idx, is the size of the parent node of the entry we are walking
• previous_node_size, analogous to previous_node_idx, used to updated parent_node_size when we descend a level in the recursive traversal

We then are able to pass the parent_node_size to set_entry_info_or_panic alongside the current_directory_at_depth, to correctly calculate the size of the tree entry.

Using this approach, the extra cost we pay for storing the directory sizes is linear in the height of the file tree, rather than paying a cost for every single file in the file-system. This seems more reasonable to me.

I have created another branch using this approach here. Happy to take your thoughts on any of this - if you agree that alternative 2 looks good then I will finalise this version, update the PR and go about adding that journey test you mentioned. Cheers!

That's great, if you prefer option 2 I will happily go with that. There might be an option 3, which is to real-world test the impact of the added 16 bytes. As option 2 will add complexity, I think we should benchmark the memory usage first, and then see what by what percentage the consumption rises.

Also, please feel free to push these changes here right away, preferably in their own commit, then it's more straightforward to keep this endeavour in one place.
Thanks again.

Sorry, I may have just pushed my changes onto yours with the adjustments of numbers, but I am done now.
It's much easier to see what fails now.

Thank you - once the numbers for Windows are adjusted, could you please squash the commits down into one?
Then there should be nothing in the way of merging it.
Thanks again.

Cool thank you. To me these updated tests capture the fact that directories now have size, so no new journey test is needed. Do you agree?
As for the memory usage issue, I did some memory profiling and found that the peak heap utilisation for the original implementation was ~15% higher than the latest release of dua, compared to only a 2-3% increase for the improved implementation, so I think the slight added complexity is worth it. This was running against my own $HOME directory of around 560k files - I can share the script I used to do this profiling if you would like to take a look.
I see that the tests are now passing on linux but still failing on windows - I'll take a look as to why.

Fixed and squashed - hopefully good to go now. Cheers.

And here is the new release: https://github.com/Byron/dua-cli/releases/tag/v2.30.1 .