Improve the performance of includes scanning

[shaoyie]

trafficstars

Please check if the PR fulfills these requirements

• [x] The PR has no duplicates (please search among the Pull Requests before creating one)
• [x] The PR follows our contributing guidelines
• [ ] Tests for the changes have been added (for bug fixes / features)
• [ ] Docs have been added / updated (for bug fixes / features)
• [ ] UPGRADING.md has been updated with a migration guide (for breaking changes)

• What kind of change does this PR introduce? Enhancement

• What is the current behavior? It's very slow to scan the includes for a large project when cache is invalid. And the cache is very easy to be invalidated because it caches the includes by a strict chain. Also because of the chain, the scanning can only be performed by single thread.

• What is the new behavior? By applying the sync.Map instead of the array, we can introduce in the goroutine to improve the performance far more better.

• Does this PR introduce a breaking change, and is titled accordingly? No breaking

• Other information:

---

See how to contribute

[CLAassistant]

Thank you for your submission! We really appreciate it. Like many open source projects, we ask that you sign our Contributor License Agreement before we can accept your contribution.

---

Sawyer seems not to be a GitHub user. You need a GitHub account to be able to sign the CLA. If you have already a GitHub account, please add the email address used for this commit to your account.
_{You have signed the CLA already but the status is still pending? Let us recheck it.}

[facchinm]

I'm testing this PR and the speedup is amazing :star_struck: Still didn't find any corner case where it doesn't correctly resolve the includes

[matthijskooijman]

@shaoyie, can you expand a little bit more on how this changes the include scanning process? The old caching code was intended to ensure that the results are always the same, with or without caching. I haven't dug into your new code deeply yet, but I have the impression that this might end up with different results depending on goroutine timing in some cases (I'm thinking of a case where one library exposes a.h and b.h and another exposes just b.h, inclusion of the latter can depend on whether a.h or b.h is resolved first).

In any case, speeding up this process is much welcomed, since it indeed is quite slow currently.

For a related (but distinctly different) improvement to this process, see https://github.com/arduino/arduino-builder/pull/217, which improves caching when compile errors are present by letting the include caching generate .d files (in addition to the compilation process). I never finished that PR properly, since it probably requires changes to recipes/platform.txt, but I never took the time to figure out what is needed exactly and how to do that in a backward compatible way. As I said, it's distinct from this improvement, but if you're interested in also working on that, feel free to work from my code.

[shaoyie]

@shaoyie, can you expand a little bit more on how this changes the include scanning process? The old caching code was intended to ensure that the results are always the same, with or without caching. I haven't dug into your new code deeply yet, but I have the impression that this might end up with different results depending on goroutine timing in some cases (I'm thinking of a case where one library exposes a.h and b.h and another exposes just b.h, inclusion of the latter can depend on whether a.h or b.h is resolved first).

In any case, speeding up this process is much welcomed, since it indeed is quite slow currently.

For a related (but distinctly different) improvement to this process, see arduino/arduino-builder#217, which improves caching when compile errors are present by letting the include caching generate .d files (in addition to the compilation process). I never finished that PR properly, since it probably requires changes to recipes/platform.txt, but I never took the time to figure out what is needed exactly and how to do that in a backward compatible way. As I said, it's distinct from this improvement, but if you're interested in also working on that, feel free to work from my code.

Your impression is right that in multiple goroutines situation, the scanning result may look different depends on the goroutine execution order. My judgement is if the scanning result won't impact the compile result, then it is acceptable. So the new strategy doesn't care the scanning sequence which limited it to single thread, instead it checks the cache's validation against the timestamp of the target file and source file, in which way we can utilize multiple goroutines. If there's extreme case as you mentioned, I just left it to the ResolveLibrary() method to decide which library will be chosen. Also in such a case, if two files had conflict in the filenames, even in the original behavior, still cannot ensure the right file is happened chosen, still need additional manual work to search out the files with same names handle them very carefully.

[shaoyie]

Just like stable sort and unstable sort, the result may vary but legal, depends on what is your expectation.