DVCFileSystem.find very slow with many files

[grahameth]

Bug Report

Calling find on DVCFileSystem with a repo of about 300,000 files takes about 70 seconds.

Description

Reproduce

This example retrieves all file paths and hashes in a given dataset directory:

from dvc.api import DVCFileSystem

fs = DVCFileSystem(repo_url, rev=rev)
files = fs.find("/Data", detail=True, dvc_only=True)
remote_files = {}
for file, info in files.items():
    hash = info['dvc_info']['md5']
    remote_files[file] = hash

Given that all this information is stored in a single internal json file, I'd expect this to take as long as downloading that file + a little housekeeping.
On a repo with 300,000 files, this takes about 70 seconds.

Expected

This example does the same, but accesses internal datastuctures to make it faster:

from dvc.api import DVCFileSystem
from dvc_data.hashfile.tree import Tree

fs = DVCFileSystem(repo_url, rev=rev)
key = fs._get_key_from_relative("Data")
_, dvc_fs, subkey = fs._get_subrepo_info(key)
entry = dvc_fs.fs.index._trie.get(subkey)
entry.obj = Tree.load(entry.remote, entry.hash_info)

remote_files = {}
for ikey, (_, hash_info) in entry.obj.iteritems():
    file = os.path.join(subkey[0], *ikey)
    hash = hash_info.value
    remote_files[file] = hash

On a repo with 300,000 files, this takes about 10 seconds. Most of that time is spent downloading.

A factor of 7 seems like too much overhead to me. Hopefully, this can be improved.

DVC version: 2.38.1 (conda)
---------------------------------
Platform: Python 3.9.15 on Windows-10-10.0.19045-SP0
Subprojects:
        dvc_data = 0.28.4
        dvc_objects = 0.14.0
        dvc_render = 0.0.15
        dvc_task = 0.1.8
        dvclive = 1.3.0
        scmrepo = 0.1.4
Supports:
        http (aiohttp = 3.8.3, aiohttp-retry = 2.8.3),
        https (aiohttp = 3.8.3, aiohttp-retry = 2.8.3),
        ssh (sshfs = 0.0.0)

[grahameth]

I just tried this with DVC version 3.6.0, and it seems to have gotten worse:
On a repo with 500000 tracked files:
DVCFileSystem.find("/", ...) takes about 170 seconds.

The code below which uses internal datastructures takes about 9 seconds. (The code in the first post no longer works on 3.6.0)

from dvc.api import DVCFileSystem
from dvc_data.hashfile.tree import Tree

fs = DVCFileSystem(repo_url, rev=rev)
remote_files = {}
for dir in fs.find("/", maxdepth=1, detail=False, withdirs=True, dvc_only=True):
    key = fs._get_key_from_relative(dir)
    repo, dvc_fs, subkey = fs._get_subrepo_info(key)
    entry = dvc_fs.fs.index._trie.get(subkey)
    storage = dvc_fs.fs.index.storage_map[key].remote
    obj = Tree.load(storage.odb, entry.hash_info, hash_name=storage.odb.hash_name)

    for ikey, (_, hash_info) in obj.iteritems():
        path = os.path.join(subkey[0], *ikey)
        path = path.replace("\\", "/")
        if path[0] == "/":
            path = path[1:]
        hash = hash_info.value
        remote_files[path] = hash

Here is the output of dvc doctor on the client side:

DVC version: 3.6.0 (conda)
--------------------------
Platform: Python 3.10.12 on Windows-10-10.0.19045-SP0
Subprojects:
        dvc_data = 2.6.0
        dvc_objects = 0.24.1
        dvc_render = 0.5.3
        dvc_task = 0.3.0
        scmrepo = 1.1.0
Supports:
        http (aiohttp = 3.8.5, aiohttp-retry = 2.8.3),
        https (aiohttp = 3.8.5, aiohttp-retry = 2.8.3),
        ssh (sshfs = 2023.7.0)
Config:
        Global: C:\Users\deeplearning\AppData\Local\iterative\dvc
        System: C:\ProgramData\iterative\dvc

[skshetry]

@grahameth, can you please share the cprofile data?

[grahameth]

Here you go:
fs_find_official.zip
This is the DVCFileSystem.find("/", detail=True, dvc_only=True) call that takes multiple minutes.

It looks like it is caching something in a sqlite database that takes most of the time. Maybe there is a way to batch these calls? Or maybe a parameter can be added to find() to omit this behavior.

For comparison, here is the profiledata of my Tree.load code:
fs_find_unofficial.zip

[dberenbaum]

Need to investigate if this is also causing performance issues for other operations like get, import, etc.

[grahameth]

Pretty much every operation in this repo feels too slow. Let me know if you want anything specific.

[dberenbaum]

@grahameth How large are the files in that directory?

@iterative/dvc Does anyone have a Windows machine to test the scenario? I don't see anything close to those times on my mac.

[efiop]

File size shouldn't matter.

The comparison of dvcfs and direct index manipulation is not totally fair though (DataFileSystem is closer to that). I started looking into it, but got distracted with other stuff. Still plan on taking a look.

[dberenbaum]

@efiop I see much faster times than what's reported, so I'm not sure it's worth a lot of time until we identify what's causing such slowness for @grahameth specifically.