felix-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Guillaume Nodet <gno...@apache.org>
Subject [HEADS UP] Resolver optimizations
Date Fri, 26 Jun 2015 13:06:02 GMT
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

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message