How to drain your laptop battery using Jigsaw

[David M. Lloyd]

We (with JBoss Modules) also came to this conclusion, though not with a 
formal proof (awesome!)... our solution after analyzing use cases is 
that at run time it makes the most sense to eliminate any resolver 
action at all and just load modules directly as an O(1) operation.  This 
basically implies #2 of your solution though we did not add any run-time 
measures to verify version constraints (we came to the conclusion that 
this was an install-time concern and verifying at run time was probably 
redundant, though we haven't completely closed the book on it either).

Our linking operation basically amounts to iterating the reachable 
dependency graph and building a fresh linkage map for each module, with 
simple cycle elimination via a visited set.  This has proven to be fast 
and effective as a module can be linked on the order of 100s of µsec on 
a commodity 1.8GHz Intel system (and there are likely optimizations we 
haven't yet attempted)... something a resolver-based system can probably 
never hope to approach.

On 12/21/2011 04:23 PM, Jesse Glick wrote:
> My colleague Yarda Tulach had investigated module systems supporting
> version ranges, and wrote up a formal proof [1] that picking one version
> of each of several modules in a repository such that all dependencies
> are satisfied is in general NP-complete. I decided to verify that Jigsaw
> suffers from this problem.
>
> The attached program, run against a recent Jigsaw build (8c6429c279e7),
> starts consuming many seconds of CPU time per round (effectively
> hanging) somewhere around 9 variables (depending on the random seed),
> mostly running in Resolver.resolve according to a profiler. The
> randomized nature of the test and the clause count is designed to stress
> the system, of course.
>
> Possible resolutions to this problem include:
>
> 1. Drop the requirement that module dependencies may include version
> ranges or otherwise permit incompatible changes to be marked, so that a
> dependency is always on some version or later. This seems unsatisfactory.
>
> 2. Drop the requirement that the module system pick a version of each
> module to load such that all dependencies are satisfied. For example:
> just try to load the newest available version of each module, and if any
> dependencies are in fact unsatisfied, report an error and ask the user
> to override one or more module versions manually.
>
> 3. Rewrite Resolver using something like SAT4J, or even leave it as it
> is, and just document that pathological cases can result in unbounded
> execution time.
>
> 4. Require that a new release of any module which uses an incompatible
> version of some dependency (even if used only internally) is itself
> marked incompatible. This seems unsatisfactory since it breaks
> encapsulation - I should not be forced to label my new widely used
> graphics toolkit 2.0 rather than 1.1 merely because I started to use a
> refactored version of some math library after 1.0 was released. Also it
> is unclear how you would enforce this constraint so long as Jigsaw
> assigns no semantics to version numbers except that they are totally
> ordered.
>
> 5. Permit multiple versions of a module to be loaded so long as class
> spaces remain consistent - resolving such configurations when needed -
> and only require that a new release of a module whose public signature
> refers to an incompatible version of some dependency is itself marked
> incompatible. (Whether 'requires public' is used does not matter.) More
> palatable than #4 but still forces a cascade of incompatibility, even
> when the incompatible change in the dependency is unrelated to this
> module's usage of it. Like #4, enforcement would require stronger
> version semantics.
>
> Yarda please step in if I misrepresented any of these options.
>
>
> [1] http://wiki.apidesign.org/wiki/LibraryReExportIsNPComplete


-- 
- DML