Improve RemoveDependenciesFromEntryIfMissing() when there is a lot of input files.

[yuehuang010]

Steps to reproduce

Create a C++ Project with 300+ files. For simplicity, each file is a clones, named fromo file1.cpp to file file300.cpp. MSBuild project can use

#include <windows.h>
#include <__msvc_all_public_headers.hpp>
int somefunction() { return 0; }

msbuild.exe /t:ClCompile /p:UseMultiToolTask=true

I added some telemetry:
PostExecuteTool Part 1: 414ms
PostExecuteTool Part 2: 493ms
PostExecuteTool Part 2.1: 531ms
PostExecuteTool Part 2.2: 4800ms<!-- Jump here is only calling RemoveDependenciesFromEntryIfMissing()
PostExecuteTool Part 3: 4967ms
PostExecuteTool Total: 5019ms

Expected behavior

RemoveDependenciesFromEntryIfMissing() should take less time. 100ms or less.

Actual behavior

RemoveDependenciesFromEntryIfMissing() is took 4 seconds.

Notes:

CanonicalTrackedInputFiles.RemoveDependenciesFromEntryIfMissing() has a N^2 loop that is calling FileExists(). Adding a simple cache would speed up this process timing a lot.

OS info:
Windows 10, running under VS developer command prompt.

[benvillalobos]

So current status is that it definitely won't be making it into P2, so apologies for that. But this is now the #1 item on my plate. After getting a more detailed explanation on this area of code and being able to debug it more (thanks Rainer), you'll hopefully be seeing more activity on my end.

[benvillalobos]

Notes as I go: A lot of the dependency files are checked whether or not they exist hundreds of times. Using a simple HashSet to store all of the files that were detected in the file check, I was able to bring down the time in the worst case from 860msec to 28msec (using a stopwatch capturing the outer for-loop and logging that to a file). But as you can see, it's a significant improvement.

Question: Let's say a file was not found in first iteration of this function during a build, is it worth continually checking for that file further along in the build? My current implementation is a straightforward "have we seen that the file exists already? if so, never look for it again", do I need to consider scenarios where perhaps the file no longer exists, or the file didn't exist originally, but shows up at a later point?

//cc: @rainersigwald

[yuehuang010]

It is probably safe to the assume that HashSet is good for the lifetime of the class. A smarter system could share with a global system and only need to check the "write" logs as the write is the only difference.

Could also take a look at the Constructor? I stopwatched it taking 400ms (while not as much as RemoveDependenciesFromEntryIfMissing()), I expected it to take only 40-50ms. I refactored disk access from the timer and it still took the same time, thus issue is somewhere else.

edit I should add when I say Constructor() I really meant the function ConstructDependencyTable(). This inner loop is also a great candidate for parallel foreach.

Thanks.