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

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

  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

  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

 Instead of doing things lazily, most of the computation can be done by
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


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()

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

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 !

Guillaume Nodet

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