ccache-like caching

[CyberShadow]

ccache is a wrapper around C/C++ compilers and related tools which caches the result of compilation based on the file contents, so if you compile source code, then delete / redownload / unpack to the same location and recompile, the second compilation will be cached.

It would be useful to have something similar in rund, probably as a mode enabled with a switch. Its effect would be:

1. Include contents of files when calculating the cache directory
2. Stop looking at timestamps when deciding whether something should be rebuilt
3. Make the compilation target always be the cache directory, even with -od/-of, and then copy artifacts out if necessary.

ccache also has a maximum cache size limit (upon hitting which it starts deleting old results), but that can be managed outside of rund or added later.

What do you think?

[marler8997]

Using the contents would be more robust than using timestamps alone. The only concern would be performance.

There's no way to get caching right 100% of the time. A compilation could depend on many things like the current datetime, the kernel version, the temperature, the hardware installed, etc and there's no way rund could know every input that a program depends on. So coming up with the right set of inputs to the hash is a balancing act between performance and correctness.

Any new feature that makes the caching work in more cases would have to outweigh the performance cost. So I would try to identify the use cases this feature helps (i.e. the redownload use case you mentioned) and then implement it to see how it affects performance.

There may also be a way to use the timestamp sometimes and fallback to using the contents other times? I'd have to think the use cases though...

[CyberShadow]

I think that if you were to map all files that participate in the compilation to memory and use a fast hash, the performance overhead should be minimal. IO should not be impacted as the compiler will need to read the files anyway.

[marler8997]

The compiler would only need to read the files on a cache miss though, which happens less often than a cache hit. So the "cache hit" case which is supposed to be the fast path would now need to read in all the files and hash them on every invocation.

[CyberShadow]

Right, but it would still be much much faster than actually invoking the compiler.

Further optimizing that, e.g. saving the files' hashes (reusing them if the timestamp hasn't changed) and then using something like a Merkle tree, could be a future optimization.

[marler8997]

Right, but it would still be much much faster than actually invoking the compiler.

Sure but you wouldn't be invoking the compiler at all in the "cache hit" case.

Say you're project uses 100 files in compilation. Checking the timestamps may take a few milliseconds. If hashing all those files each time took half a second, that means you're adding half a second to every invocation with rund. In this theoretical case that doesn't sound like a win. And with the current implementation, the worst case is that a file's timestamp gets updated (which I think would happen very rarely) and you recompile everything. But that's the rare case. We don't want to make the rare cases faster at the cost of making the common cases slower.

But making the common cases negligably slower would be fine. I would need to see numbers.

[CyberShadow]

Checking the timestamps may take a few milliseconds. If hashing all those files each time took half a second, that means you're adding half a second to every invocation with rund.

There's no way that should take that much.

[vladimir@home phobos]$ find -name '*.d' -exec cat '{}' '+' | time md5sum
dae1d87d186480d983772e6da371be64  -
0.03user 0.00system 0:00.05elapsed 58%CPU (0avgtext+0avgdata 3220maxresident)k
0inputs+0outputs (0major+166minor)pagefaults 0swaps

All of Phobos takes 0.03 seconds to hash with just one CPU core.

[marler8997]

30 milliseconds for how many files?

[CyberShadow]

That would be for the 427 .d files in my Phobos checkout right now.

[marler8997]

Ok let's look at a real project. What was that project you had that was fairly big?

[CyberShadow]

I don't know what that would refer to, but it's 27 ms for vibe.d (288 .d files).

[marler8997]

You had a project that took like 4 to 5 seconds to compile. I'd like to see how many files we would need to hash in that case. All the files in the JSON that the compiler outputs.

[CyberShadow]

You had a project that took like 4 to 5 seconds to compile.

Sorry, I don't remember what that is. If it's the project from the "D compilation is too slow and I'm forking the compiler" post, then that project is actually pretty small (about a dozen files), it just did a lot of metaprogramming.

[marler8997]

Might have been digger.

Cache Miss Case: 7.9s
Cache Hit Case: .009s

There are about 220 .d files in the json file. so might take about 15 milliseconds to hash them each time.

So the issue I'm seeing with this is, for real projects, it's more than doubling the time it takes to run the project in the "happy path". 15 milliseconds is completely negligible in the slow path but it can be a big deal in the fast path. And the use case where this would save time seems to be pretty rare...? Not to mention that most tools use timestamps so it's expected behavior, i.e. I would expect that running touch myfile.d would cause it to be rebuilt.

[CyberShadow]

So the issue I'm seeing with this is, for real projects, it's more than doubling the time it takes to run the project in the "happy path".

If this is an issue, the implementation could use timestamps as the first check. If the timestamps haven't changed, we can safely assume that the contents and hashes haven't either. (It does mean saving the hashes somewhere so we know what the cache directory is, so extra complexity.)

And the use case where this would save time seems to be pretty rare...?

It should be about the same scenarios as for ccache, and I've been getting good mileage out of it.

Not to mention that most tools use timestamps so it's expected behavior, i.e. I would expect that running touch myfile.d would cause it to be rebuilt.

As with ccache, it should have the exact same effect as if it was rebuilt, except for things like __DATE__.

Anyway, the bigger problem for why this should probably be opt-in is that this will cause the cache directory to grow much much faster, i.e. every time the program is edited and built will create a new entry.

[marler8997]

If this is an issue, the implementation could use timestamps as the first check. If the timestamps haven't changed, we can safely assume that the contents and hashes haven't either. (It does mean saving the hashes somewhere so we know what the cache directory is, so extra complexity.)

Ok that's true. I would prefer a little more complexity over making the happy path slower. If I were to implement this, this is how I would do it.

It should be about the same scenarios as for ccache, and I've been getting good mileage out of it.

Can you elaborate a bit? How often do you think a file's timestamp would be updated without it's contents in a real world project? Since other tools like Make don't support this, I know developers imlpement functions that will pre-generate contents and only write them to a file if they detect they are different so as not to update the timestamp if the contents haven't changed (see the updateIfChanged function at https://github.com/dlang/dmd/blob/master/src/build.d#L1088 for one example)

Anyway, the bigger problem for why this should probably be opt-in is that this will cause the cache directory to grow much much faster, i.e. every time the program is edited and built will create a new entry.

Oh well if this was opt-in then I wouldn't care about adding a bit of time to the happy path. I would be totally fine with making this an opt-in feature.