felix-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Jean-Baptiste Onofré ...@nanthrax.net>
Subject Re: [HEADS UP] Resolver optimizations
Date Fri, 26 Jun 2015 13:41:08 GMT
Hi Guillaume,

What a work you did !!

It looks really great !

I cloned your repo to test and take a deeper look.

Thanks !

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é
Talend - http://www.talend.com

View raw message