Speedup creation of FileTrees

[ghyatzo]

Hello,

I have quite a bit of files (~400k) and wanted to see how FileTree handled them. Unfortunately, trying to create the FileTree takes forever.
Interrupting the execution shows that most of the time is spent inside the stat function.

On my machine and for a file in that directory @time stat(file) takes approximately 0.005 seconds (it's not on the same machine). A back of the napkin calculation shows that building up the FileTree would then take roughly ~2000 seconds. Which seems a tad too much to even begin starting the work?

In contrast, a simple readdir(directory) takes a couple of seconds, would it be possible to also construct a FileTree in a "lazy" way without needing to stat every file and simply work with simple paths at first?

Thanks!

EDIT: Ok I jumped my guns a little bit, I tried to just wait and see how long it would take just for science. It took ~18-20 minutes.
I did use @time to try and get a better estimate, but I unfortunately forgot to put a ; at the end, so had to interrupt the printing (see #83). It's a bit better than what I feared, but it's still not as fast as I would have hoped seeing the performance of readdir.

PS: This package is very elegant, amazing job!

[DrChainsaw]

Yikes, even 20 minutes sounds like a very long time to just traverse the structure. Any idea how long it takes to just let the filesystem do it?

Looking at the constructor for a FileTree I guess the stat function might be called by isdir, but that cd call also looks superflous and might add significant overhead. I don't know if there is any particular thought behind it as I'm not the original author.

We could try to rewrite the constructor using walkdir (or maybe just remove the cd call) and see if that is faster.

I don't immediately see a simple solution to "simply work with simple paths at first" as the FileTree constructor needs to know if it is a directory to be able to recurse into it.

One option is to add a maxdepth parameter to the constructor. To get any benefits one probably also needs to do something like assuming everything at maxdepth is a file (so we don't need to stat it). It might open up for special handling needed elsewhere and maybe bugs when things that are Files in the FileTree are actually directories in the file system, but maybe it is ok.

Feel free to try out the above in a PR if you feel up for it. Otherwise, I'd appreciate if you try walkdir in your 400k file folder and report how long it took.

[ghyatzo]

julia> @time collect(walkdir(directory));
 17.454053 seconds (405.26 k allocations: 86.408 MiB, 3.92% gc time)

This seems more in line with my expectations, but I am unsure how much more work the constructor needs to do.
If I have some more time I'll try to run a proper profiler instead of just relying on a random Ctrl-C stacktrace.

Apologies for dropping the hot potato, I'll try to help out when I have some more bandwidth

[DrChainsaw]

No worries.

Here are three prototypes you can try to see if they improve things. They are about 10 times faster than the current constructor on my machine (and measly 20k files folder).

function walkfiletree(parent, dir; sort=false)
    root = FileTree(parent, dir, [])
    curr = root

    startlen = length(dir)+1
    first = true
    for (path, dirs, files) in walkdir(dir)  
        currpath =  @view(path[startlen:end])
        curr = (first) ? curr : root[currpath]
        first = false

        for dir in dirs
            push!(curr.children, FileTree(curr, dir, []))
        end
        for file in files
            push!(curr.children, File(curr, file))
        end
        if sort 
            sort!(curr.children; by=name)
        end
    end
    root
end

function walkfiletree2(parent, dir; sort=false)
    root = FileTree(parent, dir, [])
    stack = FileTree[root]

    for (path, dirs, files) in walkdir(dir)  

        curr = pop!(stack)
    
        for dir in dirs
            push!(curr.children, FileTree(curr, dir, []))
        end

        for ch in Iterators.reverse(curr.children)
            push!(stack, ch)
        end

        for file in files
            push!(curr.children, File(curr, file))
        end
        if sort
            sort!(curr.children; by=name)
        end
    end
    root
end

struct VecStack{T}
    ind::Int
    curr::T
    next::Union{VecStack{T}, Nothing}
end


append(s, ft) = VecStack(1, ft, s)
pop(s::VecStack) = (s.curr[s.ind], s.ind === lastindex(s.curr) ? s.next : VecStack(s.ind+1, s.curr, s.next))

function walkfiletree3(parent, dir; sort=false)
    root = FileTree(parent, dir, [])
    stack = append(nothing, @view(Any[root][1:end]))

    for (path, dirs, files) in walkdir(dir)  

        curr, stack = pop(stack)

        for dir in dirs
            push!(curr.children, FileTree(curr, dir, []))
        end
        if !isempty(curr.children)
            stack = append(stack, @view(curr.children[1:length(curr.children)]))
        end
        
        for file in files
            push!(curr.children, File(curr, file))
        end
    end

    if sort
        _sort_deep!(root.children)
    end

    root
end

_sort_deep!(::Tuple{}) = nothing
function _sort_deep!(chs)
    sort!(chs; by=name)
    for ch in chs
        _sort_deep!(children(ch))
    end
end

They should be runnable from outside of filetrees, just copy and paste into the repl and go (after using FileTrees ofc). The latter two depend on the ordering of walkdir so they are less than ideal.

The first one could have problems with the direct indexing, e.g. if someone passes a unicode dir. Not sure that is a thing that exists.

# Just the reference, probably don't want to do this on your 400k files folder :)
julia> reftree = FileTree(nothing, "/some/path/somewhere") 

julia> wt = @time walkfiletree(nothing, "/some/path/somewhere")

julia> wt2 = @time walkfiletree2(nothing, "/some/path/somewhere")

julia> wt3 = @time walkfiletree3(nothing, "/some/path/somewhere")

# Test that it produces the same result like this
julia> diff(reftree , wt)
/some/path/somewhere # Only root remains

The parent argument is probably superflous since none of the functions use recursion, but I kept it for backwards compatibility. Real constructor will ofc have the zero arg version as well.

[ghyatzo]

ok, here are some results. I've tried both on a smaller folder of 10k files and then on the big boy:
The small test was to also have the reference tree available. Although these folders are very much flat. it's litterally folder/<400k files> so the functionality test is not very complete. I'll try on more complex trees if needed.

small folder

julia> @btime readdir(griddir);
  59.967 ms (25943 allocations: 3.17 MiB)

julia> @btime FileTree(nothing, griddir);
  4.692 s (103732 allocations: 10.29 MiB)

julia> @btime walkfiletree(nothing, griddir);
  70.814 ms (51929 allocations: 5.57 MiB)

julia> @btime walkfiletree2(nothing, griddir);
  58.113 ms (51932 allocations: 5.57 MiB)

julia> @btime walkfiletree3(nothing, griddir);
  71.312 ms (51933 allocations: 5.57 MiB)

all trees match the reference tree.

Big folder:

julia> @btime readdir(biggriddir);
  11.558 s (401878 allocations: 58.34 MiB)

julia> @btime FileTree(nothing, biggriddir);
  Nope.

julia> @btime walkfiletree(nothing, biggriddir);
  12.456 s (803809 allocations: 107.76 MiB)

julia> @btime walkfiletree2(nothing, biggriddir);
  11.734 s (803812 allocations: 107.76 MiB)

julia> @btime walkfiletree3(nothing, biggriddir);
  12.363 s (803813 allocations: 107.76 MiB)

now we're talking!

It seems that option 2 is the fastest and basically matches the speed of readdir which seems pretty optimal.
Also in terms of implementation it looks the simplest. I like it.

[DrChainsaw]

I'm a bit worried that both option 2 and 3 assumes walkdir will visit the directories in the same order as dirs is ordered, and I don't see anything in the documentation which promises this.

I think option 1 is the most robust and since the speed is comparable I'm leaning towards something like it. One reason why it is a bit slower is that FileTrees getindex for full paths is a bit slow. Here is a version of option 1 which uses a Dict for caching created children instead which has the same performance as option 2 for me:

function walkfiletree5(parent, dir; sort=false)
    # normalize just to safeguard in case walkdir would decide to normalize
    # I also like that FileTrees created from the same dir are always the same, regardless of what format the path was given 
    ndir = normpath(dir) 
    root = FileTree(parent, ndir, [])
    cache = Dict(ndir => root)
    for (path, dirs, files) in walkdir(ndir) 
        curr = cache[path]

        for dir in dirs
            child = FileTree(curr, dir, [])
            push!(curr.children, child)
            cache[joinpath(path, dir)] = child
        end
        for file in files
            push!(curr.children, File(curr, file))
        end
        if sort 
            sort!(curr.children; by=name)
        end
    end
    root
end

I guess it assumes walkdir creates path in the same way joinpath does it (not relying on this is one reason why option 1 above is slower), but at least it will go out with a bang if this is not true rather than silently giving incorrect results (which is what option 2 and 3 above will do if their assumptions are violated).

[DrChainsaw]

Ok, here is probably the best attempt yet: We use walkdir only for faster separation between files and dirs and use the same type of recursion as the original to avoid making assumptions about what walkdir does in the next iteration (we just break the loop after first iter):

function walkfiletree6(parent, dir; sort=false, root="")
    parent′ = FileTree(parent, dir, [])
    for (path, dirs, files) in walkdir(joinpath(root, dir)) 
        for dir in dirs
            push!(parent′.children, walkfiletree6(parent′, dir; sort, root=path))
        end
        for file in files
            push!(parent′.children, File(parent′, file))
        end
        if sort 
            sort!(parent′.children; by=name)
        end
        break
    end
    parent′ 
end