I've spent the last two weeks working on optimising the resolver. The results are available in the following github fork https://github.com/gnodet/felix/commits/FELIX-4942
The commits are split so that they can be reviewed more easily. Most of them do not really change the algorithm in any way, so I won't comment them, but I want to highlight a bit those that introduce more important changes. * Avoid throwing exceptions during resolution https://github.com/gnodet/felix/commit/fa012fe9d3760f6b80c03eecf0b7f03218ceae6f This commit contains two major ideas: try/catch are slow and the computation of the resolution messages are usually expensive and useless. So instead of exceptions, the resolver creates a small object containing all the information needed to create the exceptions later if needed (this usually happen only once at the end). When the resolver is doing some recursive work, it usually * Compute all package sources for a given resource at the same time https://github.com/gnodet/felix/commit/a602f43ccd76983026d6c0c76958bc3445c0f4c0 Time can be saved by computing all the package sources for a given resource at the same time, especially when a resource exports the same package with multiple versions (the computation is still recursive, but this will be removed in a following commit). * Compute package spaces by stages https://github.com/gnodet/felix/commit/71cd667e89d41d580c8f2b88605694cc361bf134 Instead of doing things lazily, most of the computation can be done by stages. So we first compute the list of wire candidates, then the exported packages, then the imported and required package lists, then the package sources and last, the use constraints. * Parallelism https://github.com/gnodet/felix/commit/b1e88923fb9a2f056f3b6b4bc96682d620652fd5 https://github.com/gnodet/felix/commit/68650153aa6bdde96b4c357ee8faa88fa4e90f6e Following the previous point, things can now be computed in parallel, given they are only using read-only objects from a previous stage and the computation are done for a given resource with no recursion. This allow using multiple threads and start the work for each resource, gather everything at the end of a stage, start the next stage. I haven't really investigated parallelism in checkPackageSpaceConsistency, and this is always done sequentially, however, most of the work is computing the package spaces (and creating Candidates copies). I've also experimented a bit with starting resolving several Candidates in parallel, but with really poor success (usually, I end up with OOM errors). * Remove recursion in Candidates.populate() https://github.com/gnodet/felix/commit/3a82b2342c87450edcd1aa6fa5c514c2b04ae346 The algorithm is exactly the same, but we use a list instead of using recursion. This is faster and do not impose memory constraints (some platforms have a small stack by default). * Use depth-first algorithm for permutations https://github.com/gnodet/felix/commit/e4f479b5ec2bf4351f755909aa33ea5f0c6af2dc When new permutations are computed, they were always added at the end of one of the lists. This lead to a width breadth first algorithm. However, the algorithm is smart enough to find the causes of an error, create a substitution based on this error which should go one step in the right direction. By adding the new substitutions to the beginning of the lists, we always go in the right direction, leading to much fewer iterations. Overall results =========== On my computer, the BigResolutionTest takes roughly 11s (after the removal of GenericCapabiliy#equals method). With the head of this branch, the time is down to 100 ms I'm planning to test the new resolver a bit more in the following days, making sure I don't see any weird behaviour, but the tests looks really good so far. All comments welcome ! Cheers, Guillaume Nodet
