libdvc for performance and interfacing

[iesahin]

One of the important issues that we aim to improve is DVC's performance in common tasks. Recently I began to wonder if moving certain parts, e.g., filesystem and networking to a libdvc written in C/Go/Rust improves performance. I'm not sure about this, as the current packages probably use some optimized compiled code and the investment may not worth it.

Another aspect may be to have a common library that can be used in other languages like R or Julia but this requires a rather full-featured libdvc, and that's another topic. What I ask here is rewriting stable functionality that won't change in the short term in C (or something that can export "extern C") and using ctypes or cffi to call that in Python.

I believe this idea was considered before, as "libdvc" is mentioned in a commit (#123) 4 years ago, but probably considered not worth it.

If it seems OK to test some functionality, e.g., add, checkout, get in a forked DVC and see whether if it's worth it, I can reserve some time for this.

[iesahin]

I did a pretty quick test with the following script which corresponds to dvc add in functionality. It doesn't do everything dvc add does and it doesn't use any advanced techniques. It's just a script I wrote in 30 minutes:

directory=${1}
out=/tmp/cache-${RANDOM}

mkdir -p ${out}

ls -1 $directory | while read -r f ; do
    md5s=$(md5sum "${directory}/${f}" | cut -f 1 -d ' ')
    cachedir="${md5s:0:2}"
    mkdir -p "${out}/${cachedir}"
    echo "${directory}/${f} -> ${out}/${cachedir}/${md5s}"
    cp ${directory}/${f} ${out}/${cachedir}/${md5s}
    cat > "${directory}/${f}.dvc" << EOF
    md5: ${md5s}
EOF

done

This is what I get for time

rdvc-add.zsh 1  1.60s user 0.77s system 66% cpu 3.570 total

and the similar command dvc add 1/* takes

dvc add 1/*  6.86s user 1.61s system 63% cpu 13.306 total

I used dvc add 1/* instead of the dir addition to compare apples to apples, writing individual .dvc files certainly takes time.

So for 1000 files, dvc add runs ~10 seconds slower from the script. I believe the amortized overhead will decrease as the number of files increase, so for 100000 files, the script and dvc add may not be that different. (or may be, I don't know actually, I need to do more tests.)

@shcheklein suggested that had the functionality added to DVC is added to another piece of software, it would also slow it down. So a full-fledged DVC clone with another language may have a similar performance.

It's true that there are theoretical boundaries to the algorithms. You can only find the minimum element of a list in $O(n\log(n))$ time. But I doubt the difference in the above comparison is because of this. We normally don't hit theoretical boundaries that often.

One problem is architecture I believe. AFAIU DVC loads all classes for all features for all commands. When I run dvc add, dvc command loads entire Repo class and its maternal uncles. This creates overhead but doesn't add any functionality, I'm just running a single command but the underlying class is ready to run all commands.. Had this been a machine code, that may not make much difference, compiler would probably optimize it, but here all these elements probably cause latency and more features means more latency. (I believe dvc add in version 0.5 would run faster but I didn't test this yet.)

It may not show up in profilers because I believe there is no single place the software waits. It runs something, very small tasks, checking this and that and all these add up to a significant amount. Our basic performance bug seems to be caused of this. Because individual functions, like calculating the hash of a file are certainly optimized. But when I type dvc add myfile.png and press enter, I want to have a snappy experience. It should at least be faster than adding it by the above script.

I have two initial observations:

• Repo class should be divided and the commands should be individualized. When I run dvc checkout, I shouldn't pay any dvc exp tax, and vice versa.
• Analytics should be aggregate and only submitted when the user runs a network-related command. We can remove it completely if the amount of information doesn't provide more value than the fuss it creates. The initial warning looks like "we are watching you!!!" written in blinking red. In my experience, we don't use that information at all in decisions and even a single ping adds latency.

[efiop]

Thanks for the suggestions, @iesahin 🙏 My 2c: this is not really about the language dvc is written in, we just didn't spend enough time optimizing it properly yet. We've done some optimizations before, but they were always crumbling because of the mess in the architecture that we've collected over the years. In the past few months, we've put significant effort into cleaning up data management architecture as well as some other subsystems, and we are now starting to carefully tweak it to improve the performance.

Also, it is important to remember that even though that bash script does a bunch of things like dvc add, dvc is much more complex, as it needs to handle not only data management, but also dvcfiles (currently we collect all of them recursively in the repo, which could be slow), pipelines, metrics, params, experiments, etc, which means that a bunch of our code is written in a more general form rather than being sharpened for a specific narrow scenario. One example is our filesystems, where we not only need download and upload methods, but also a bunch of other ones for working with remote files (exists, ls, walk, checksum, etc). But even there, we are far from reaching language limits, so before we consider investing time into creating libdvc, we should invest some more time into optimizing the current codebase.

[iesahin]

The reason I'm bringing forward this issue is this: You're doing great work in new features, adding data structures, YAML specifications, documentation and a sensible interface are all important and valuable work. You're opening a path in a jungle. These are all important for the ultimate success of DVC and the company behind it.

Nevertheless if the performance of the implementation is not where it can be, I believe someone can follow the path you are opening quickly, build a "DVC-compatible" tool and get all the hard work you have done so far, and all the users that use DVC for free. No one would use a 10x slower CLI tool if there is a drop-in alternative.

Also the success of other tools, CML, Studio or VSCode extension is all depending to DVC performance.

The current DVC code is very pleasant to read and understand. It's a textbook example of OOP. I really like it. If there is room for improvement and optimization, I'd like it to see before we can decide on a path. Thank you.

[karajan1001]

My test result
shell script: 1.36s
python script: 0.16s
dvc add: 7.05s

My script
creat.py

import os

os.makedirs("data", exist_ok=True)

for i in range(1000):
    with open(f"data/{i}", "wb") as f_w:
        f_w.write(os.urandom(2**15))

c.sh

directory=data
out=/tmp/cache-${RANDOM}


ls -1 $directory | while read -r f ; do
    md5s=$(md5sum "${directory}/${f}" | cut -f 1 -d ' ')
    cachedir="${md5s:0:2}"
    mkdir -p "${out}/${cachedir}"
    echo "${directory}/${f} -> ${out}/${cachedir}/${md5s:0:2}"
    cp ${directory}/${f} ${out}/${cachedir}/${md5s:0:2}
    cat > "${directory}/${f}.dvc" << EOF
    md5: ${md5s}
EOF

done

p.py

import os
import random
import shutil
import hashlib

directory='data'
out='/tmp/cache-{}'.format(random.randint(1,99999))

for file in os.listdir(directory):
    full_file = f'{directory}/{file}'
    hash_md5 = hashlib.md5()
    with open(full_file, 'rb') as f_r:
        hash_md5.update(f_r.read())
        md5s = hash_md5.hexdigest()
    cachedir=f'{out}/{md5s[:2]}'
    print(f"{full_file} -> '{cachedir}/{md5s[2:]}")
    os.makedirs(cachedir, exist_ok=True)
    shutil.copy(full_file, f'{cachedir}/{md5s[2:]}')
    with open(f'{full_file}.dvc', 'w') as f_w:
        f_w.write(f"md5:\n\t{md5s}")

So the speed difference mostly comes from the complex logic in DVC, not from the computations or data transfer.

Rewrite a go/c version of DVC could help, only part of the computations will not.

[shcheklein]

So, out of curiosity if we run the profiler (https://github.com/iterative/dvc/wiki/Debugging-DVC#profiling-dvc) where does that time go in DVC?

[karajan1001]

A little bit of fragmentation,

my.prof.zip