Looks like a great piece of work, Guillaume. I left some minor thoughts in a few places on github.
One potential concern is that the change to depth-first search will produce different results than the previous approach. Does it still aim to minimise the number of class-spaces? This might cause different results for bundles that import packages with underspecified version ranges. On the other hand, that might then be a good reason for people to ensure correct import ranges. Cheers, David On 26 June 2015 at 14:41, Jean-Baptiste Onofré <[email protected]> wrote: > Hi Guillaume, > > What a work you did !! > > It looks really great ! > > I cloned your repo to test and take a deeper look. > > Thanks ! > Regards > JB > > > On 06/26/2015 03:06 PM, Guillaume Nodet wrote: >> >> 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 >> > > -- > Jean-Baptiste Onofré > [email protected] > http://blog.nanthrax.net > Talend - http://www.talend.com
