Re: [HEADS UP] Resolver optimizations

2015-06-26 Thread Guillaume Nodet
Yeah, I agree this is a valid concern.

From a performance point of view, we'd have to gather a few different big
test cases, but the previous changes lead to a factor 3 improvements. In
this very specific case (the BigResolutionTest), the improvement for
depth-first was an additional factory of 30.
I've done some testing with Karaf and everything seems to work well.  In
particular, installing features really looks much faster.

I think this is a big mitigated by the fact that the resolver does not try
random changes.  Usually, when a permutation is selected, it's because it
causes a conflict, so the permutation is usually a good idea.   DFS could
be a problem if there was no heuristic in place in the resolver, but given
the resolver only selects permutations that will improve the result, I'm
not sure it's really a problem.

Anyway, I've just compute the difference between the new and the old
resolver for the BigResolutionTest.
The wiring contains a few differences (this is the difference between the
new wiring minus the old wiring) :

osgi.identity; {osgi.identity=io.hawt.hawtio-karaf-terminal,
type=osgi.bundle, version=1.4.21}
Removed: osgi.wiring.package;
{filter=((osgi.wiring.package=jline)(version=2.11.0)(!(version=3.0.0)))}
- osgi.wiring.package;
{bundle-symbolic-name=org.apache.karaf.shell.console, bundle-version=2.4.0,
osgi.wiring.package=jline, version=2.12.0} [osgi.identity;
{osgi.identity=org.apache.karaf.shell.console, type=osgi.bundle,
version=2.4.0}]
Removed: osgi.wiring.package;
{filter=((osgi.wiring.package=org.apache.karaf.shell.console.jline)(version=2.2.0)(!(version=4.0.0))),
resolution=optional} - osgi.wiring.package;
{bundle-symbolic-name=org.apache.karaf.shell.console, bundle-version=2.4.0,
osgi.wiring.package=org.apache.karaf.shell.console.jline, version=2.4.0}
[osgi.identity; {osgi.identity=org.apache.karaf.shell.console,
type=osgi.bundle, version=2.4.0}]
Added: osgi.wiring.package;
{filter=((osgi.wiring.package=jline)(version=2.11.0)(!(version=3.0.0)))}
- osgi.wiring.package; {bundle-symbolic-name=jline, bundle-version=2.12.0,
osgi.wiring.package=jline, version=2.12.0} [osgi.identity;
{osgi.identity=jline, type=osgi.bundle, version=2.12.0}]
osgi.identity; {osgi.identity=io.fabric8.fabric-core, type=osgi.bundle,
version=1.2.0.SNAPSHOT}
Added: osgi.service;
{filter=(objectClass=io.fabric8.service.child.ProcessControllerFactory),
effective=active, resolution=optional} - osgi.service;
{objectClass=io.fabric8.service.child.ProcessControllerFactory,
monitorPollTime=1500} [osgi.identity;
{osgi.identity=io.fabric8.fabric-process-container, type=osgi.bundle,
version=1.2.0.SNAPSHOT}]
osgi.identity; {osgi.identity=biz.aQute.bndlib, type=osgi.bundle,
version=2.1.0.20130426-122213}
Added: osgi.wiring.package;
{filter=((osgi.wiring.package=aQute.bnd.annotation.metatype)(version=1.43.0)(!(version=2.0.0)))}
- osgi.wiring.package; {bundle-symbolic-name=biz.aQute.bndlib,
bundle-version=2.2.0.20130927-173417,
osgi.wiring.package=aQute.bnd.annotation.metatype, version=1.44.0}
[osgi.identity; {osgi.identity=biz.aQute.bndlib, type=osgi.bundle,
version=2.2.0.20130927-173417}]
Added: osgi.wiring.package;
{filter=((osgi.wiring.package=org.osgi.resource)(version=1.0.0)(!(version=2.0.0))),
resolution=optional} - osgi.wiring.package;
{bundle-symbolic-name=[Ljava.lang.String;@36f8e32d, bundle-version=4.4.1,
osgi.wiring.package=org.osgi.resource, version=1.0.0} [osgi.identity;
{osgi.identity=org.apache.felix.framework, description=This bundle is
system specific; it implements various system services., type=osgi.bundle,
version=4.4.1}]
osgi.identity; {osgi.identity=io.fabric8.fabric-project-deployer,
type=osgi.bundle, version=1.2.0.SNAPSHOT}
Removed: osgi.wiring.package;
{filter=((osgi.wiring.package=jline)(version=2.12.0)(!(version=3.0.0)))}
- osgi.wiring.package;
{bundle-symbolic-name=org.apache.karaf.shell.console, bundle-version=2.4.0,
osgi.wiring.package=jline, version=2.12.0} [osgi.identity;
{osgi.identity=org.apache.karaf.shell.console, type=osgi.bundle,
version=2.4.0}]
Removed: osgi.wiring.package;
{filter=((osgi.wiring.package=jline.console)(version=2.12.0)(!(version=3.0.0)))}
- osgi.wiring.package;
{bundle-symbolic-name=org.apache.karaf.shell.console, bundle-version=2.4.0,
osgi.wiring.package=jline.console, version=2.12.0} [osgi.identity;
{osgi.identity=org.apache.karaf.shell.console, type=osgi.bundle,
version=2.4.0}]
Added: osgi.wiring.package;
{filter=((osgi.wiring.package=jline.console)(version=2.12.0)(!(version=3.0.0)))}
- osgi.wiring.package; {bundle-symbolic-name=jline, bundle-version=2.12.0,
osgi.wiring.package=jline.console, version=2.12.0} [osgi.identity;
{osgi.identity=jline, type=osgi.bundle, version=2.12.0}]
Added: osgi.wiring.package;
{filter=((osgi.wiring.package=jline)(version=2.12.0)(!(version=3.0.0)))}
- osgi.wiring.package; {bundle-symbolic-name=jline, bundle-version=2.12.0,
osgi.wiring.package=jline, version=2.12.0} [osgi.identity;
{osgi.identity=jline, type=osgi.bundle, 

[jira] [Commented] (FELIX-4938) Throw an exception when service use count overflow

2015-06-26 Thread Alexandre Cartapanis (JIRA)

[ 
https://issues.apache.org/jira/browse/FELIX-4938?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanelfocusedCommentId=14602694#comment-14602694
 ] 

Alexandre Cartapanis commented on FELIX-4938:
-

Great !!

For AtomicLong, i had also thought to this solution, but as equinox also use 
Integer, i was wondering if it was not a kind of OSGi specification 
requirement...

 Throw an exception when service use count overflow
 --

 Key: FELIX-4938
 URL: https://issues.apache.org/jira/browse/FELIX-4938
 Project: Felix
  Issue Type: Improvement
  Components: Framework
Affects Versions: framework-3.0.0, framework-3.0.1, framework-3.0.2, 
 framework-3.0.3, framework-3.0.4, framework-3.0.5, framework-3.0.6, 
 framework-3.0.7, framework-3.0.8, framework-3.0.9, framework-3.2.0, 
 framework-3.2.1, framework-3.2.2, framework-4.0.0, framework-4.0.1, 
 framework-4.0.2, framework-4.0.3, framework-4.2.0, framework-4.2.1, 
 framework-4.4.0, framework-4.4.1, framework-4.6.0, framework-4.6.1, 
 framework-5.0.0, framework-5.0.1, framework-5.1.0
Reporter: Alexandre Cartapanis
Assignee: David Bosschaert
Priority: Minor
  Labels: easyfix
 Fix For: framework-5.1.0

   Original Estimate: 1h
  Remaining Estimate: 1h

 In class org.apache.felix.framework.ServiceRegistry, in the getService 
 method, the service use count is incremented but never checked, so it could 
 overflow if service is not ungeted.
 This is a known bug in equinox 
 (https://bugs.eclipse.org/bugs/show_bug.cgi?id=350719)



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)


Re: [HEADS UP] Resolver optimizations

2015-06-26 Thread Richard S. Hall



On 6/26/15 10:15 , David Bosschaert wrote:

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.


I wouldn't worry too much about producing different results that 
previous versions of the resolver (although admittedly, this would cause 
some pain for some people). The more important issue, from my point of 
view, is that a given version of the resolver should produce a 
consistent result given the same input...


- richard


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é j...@nanthrax.net 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,

[jira] [Created] (FELIX-4942) Optimise the resolver

2015-06-26 Thread Guillaume Nodet (JIRA)
Guillaume Nodet created FELIX-4942:
--

 Summary: Optimise the resolver
 Key: FELIX-4942
 URL: https://issues.apache.org/jira/browse/FELIX-4942
 Project: Felix
  Issue Type: New Feature
Reporter: Guillaume Nodet
Assignee: Guillaume Nodet






--
This message was sent by Atlassian JIRA
(v6.3.4#6332)


[jira] [Closed] (FELIX-4938) Throw an exception when service use count overflow

2015-06-26 Thread Alexandre Cartapanis (JIRA)

 [ 
https://issues.apache.org/jira/browse/FELIX-4938?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
 ]

Alexandre Cartapanis closed FELIX-4938.
---

Good correction

 Throw an exception when service use count overflow
 --

 Key: FELIX-4938
 URL: https://issues.apache.org/jira/browse/FELIX-4938
 Project: Felix
  Issue Type: Improvement
  Components: Framework
Affects Versions: framework-3.0.0, framework-3.0.1, framework-3.0.2, 
 framework-3.0.3, framework-3.0.4, framework-3.0.5, framework-3.0.6, 
 framework-3.0.7, framework-3.0.8, framework-3.0.9, framework-3.2.0, 
 framework-3.2.1, framework-3.2.2, framework-4.0.0, framework-4.0.1, 
 framework-4.0.2, framework-4.0.3, framework-4.2.0, framework-4.2.1, 
 framework-4.4.0, framework-4.4.1, framework-4.6.0, framework-4.6.1, 
 framework-5.0.0, framework-5.0.1, framework-5.1.0
Reporter: Alexandre Cartapanis
Assignee: David Bosschaert
Priority: Minor
  Labels: easyfix
 Fix For: framework-5.1.0

   Original Estimate: 1h
  Remaining Estimate: 1h

 In class org.apache.felix.framework.ServiceRegistry, in the getService 
 method, the service use count is incremented but never checked, so it could 
 overflow if service is not ungeted.
 This is a known bug in equinox 
 (https://bugs.eclipse.org/bugs/show_bug.cgi?id=350719)



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)


Re: [HEADS UP] Resolver optimizations

2015-06-26 Thread Jean-Baptiste Onofré

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é
jbono...@apache.org
http://blog.nanthrax.net
Talend - http://www.talend.com


[jira] [Resolved] (FELIX-4938) Throw an exception when service use count overflow

2015-06-26 Thread David Bosschaert (JIRA)

 [ 
https://issues.apache.org/jira/browse/FELIX-4938?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
 ]

David Bosschaert resolved FELIX-4938.
-
Resolution: Fixed

Thanks! I have applied your patch. I modified it a little bit:
* I also applied the overflow checking to the serviceObjects count.
* I changed the AtomicIntegers to AtomicLongs, which means that the situation 
that will trigger the exception is now extremely unlikely to occur.

You can see the commit here: 
http://svn.apache.org/viewvc?view=revisionrevision=1687743

 Throw an exception when service use count overflow
 --

 Key: FELIX-4938
 URL: https://issues.apache.org/jira/browse/FELIX-4938
 Project: Felix
  Issue Type: Improvement
  Components: Framework
Affects Versions: framework-3.0.0, framework-3.0.1, framework-3.0.2, 
 framework-3.0.3, framework-3.0.4, framework-3.0.5, framework-3.0.6, 
 framework-3.0.7, framework-3.0.8, framework-3.0.9, framework-3.2.0, 
 framework-3.2.1, framework-3.2.2, framework-4.0.0, framework-4.0.1, 
 framework-4.0.2, framework-4.0.3, framework-4.2.0, framework-4.2.1, 
 framework-4.4.0, framework-4.4.1, framework-4.6.0, framework-4.6.1, 
 framework-5.0.0, framework-5.0.1, framework-5.1.0
Reporter: Alexandre Cartapanis
Assignee: David Bosschaert
Priority: Minor
  Labels: easyfix
 Fix For: framework-5.1.0

   Original Estimate: 1h
  Remaining Estimate: 1h

 In class org.apache.felix.framework.ServiceRegistry, in the getService 
 method, the service use count is incremented but never checked, so it could 
 overflow if service is not ungeted.
 This is a known bug in equinox 
 (https://bugs.eclipse.org/bugs/show_bug.cgi?id=350719)



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)


[jira] [Assigned] (FELIX-4926) Investigate rewriting the resolver algorithm to use loops instead of recursion

2015-06-26 Thread Guillaume Nodet (JIRA)

 [ 
https://issues.apache.org/jira/browse/FELIX-4926?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
 ]

Guillaume Nodet reassigned FELIX-4926:
--

Assignee: Guillaume Nodet

 Investigate rewriting the resolver algorithm to use loops instead of 
 recursion 
 ---

 Key: FELIX-4926
 URL: https://issues.apache.org/jira/browse/FELIX-4926
 Project: Felix
  Issue Type: New Feature
  Components: Resolver
Reporter: Guillaume Nodet
Assignee: Guillaume Nodet

 The resolver algorithm for {{Candidates#populate}} currently uses a recursive 
 algorithm.
 At first glance, the number of recursion can amount to the number of 
 resources to resolve.  This limits the size of the resolution.
 I'd like to investigate replacing the recursion with a loop.  
 This may also allow using a fork/join design to leverage multiple cores for 
 the resolution.  The fork/join could also be used for the main resolution 
 loop.
 It may make things slightly harder to keep the reproducibility of the 
 algorithm if things are not always considered in the same order.  Though 
 there may be some way around.



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)


[jira] [Commented] (FELIX-4871) The felix framework logger can't be used with reflection anymore

2015-06-26 Thread Guillaume Nodet (JIRA)

[ 
https://issues.apache.org/jira/browse/FELIX-4871?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanelfocusedCommentId=14602808#comment-14602808
 ] 

Guillaume Nodet commented on FELIX-4871:


The logger needs to inherit the felix logger.  This cause class loader 
constraints.
Specifically, karaf loads the framework in a different class loader, so the 
Main class which creates the framework using the framework launch API can't 
provide a logger if not using reflection.

 The felix framework logger can't be used with reflection anymore
 

 Key: FELIX-4871
 URL: https://issues.apache.org/jira/browse/FELIX-4871
 Project: Felix
  Issue Type: Bug
Affects Versions: framework-5.0.0
Reporter: Guillaume Nodet
Assignee: Guillaume Nodet

 Not being able to use reflection means you need to create a separate jar for 
 the logger so that it can be loaded with the required framework classes.



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)


[jira] [Commented] (FELIX-4942) Optimise the resolver

2015-06-26 Thread Guillaume Nodet (JIRA)

[ 
https://issues.apache.org/jira/browse/FELIX-4942?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanelfocusedCommentId=14602814#comment-14602814
 ] 

Guillaume Nodet commented on FELIX-4942:


See https://github.com/gnodet/felix/commits/FELIX-4942

 Optimise the resolver
 -

 Key: FELIX-4942
 URL: https://issues.apache.org/jira/browse/FELIX-4942
 Project: Felix
  Issue Type: New Feature
Reporter: Guillaume Nodet
Assignee: Guillaume Nodet





--
This message was sent by Atlassian JIRA
(v6.3.4#6332)


[HEADS UP] Resolver optimizations

2015-06-26 Thread Guillaume Nodet
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


[jira] [Commented] (FELIX-4938) Throw an exception when service use count overflow

2015-06-26 Thread ASF GitHub Bot (JIRA)

[ 
https://issues.apache.org/jira/browse/FELIX-4938?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanelfocusedCommentId=14602690#comment-14602690
 ] 

ASF GitHub Bot commented on FELIX-4938:
---

Github user acartapanis closed the pull request at:

https://github.com/apache/felix/pull/24


 Throw an exception when service use count overflow
 --

 Key: FELIX-4938
 URL: https://issues.apache.org/jira/browse/FELIX-4938
 Project: Felix
  Issue Type: Improvement
  Components: Framework
Affects Versions: framework-3.0.0, framework-3.0.1, framework-3.0.2, 
 framework-3.0.3, framework-3.0.4, framework-3.0.5, framework-3.0.6, 
 framework-3.0.7, framework-3.0.8, framework-3.0.9, framework-3.2.0, 
 framework-3.2.1, framework-3.2.2, framework-4.0.0, framework-4.0.1, 
 framework-4.0.2, framework-4.0.3, framework-4.2.0, framework-4.2.1, 
 framework-4.4.0, framework-4.4.1, framework-4.6.0, framework-4.6.1, 
 framework-5.0.0, framework-5.0.1, framework-5.1.0
Reporter: Alexandre Cartapanis
Assignee: David Bosschaert
Priority: Minor
  Labels: easyfix
 Fix For: framework-5.1.0

   Original Estimate: 1h
  Remaining Estimate: 1h

 In class org.apache.felix.framework.ServiceRegistry, in the getService 
 method, the service use count is incremented but never checked, so it could 
 overflow if service is not ungeted.
 This is a known bug in equinox 
 (https://bugs.eclipse.org/bugs/show_bug.cgi?id=350719)



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)


[GitHub] felix pull request: Fix for bug #4938

2015-06-26 Thread acartapanis
Github user acartapanis closed the pull request at:

https://github.com/apache/felix/pull/24


---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastruct...@apache.org or file a JIRA ticket
with INFRA.
---