Clone Tools
  • last updated a few seconds ago
Constraints
Constraints: committers
 
Constraints: files
Constraints: dates
Implement missing optimizations

This commit introduces some missing union optimizations during

exclude rule merging. Those weren't implemented because we didn't

see them in our test cases, but we had customer logs showing such

operations.

It's worth noting this commit adds an utility class which transforms

a JSON dump from a log entry into code which can be used to create

test cases.

  1. … 3 more files in changeset.
Add more missing optimizations

  1. … 2 more files in changeset.
Add ability to trace stack overflows only

Optimize A ∩ (B ∪ C)

-> (A ∩ B) ∪ (A ∩ C)

User data shows this can often be reduced to an empty set because

distribution will compute empty sets on both sides.

  1. … 1 more file in changeset.
Add missing optimization of intersection

when module ids are different

  1. … 1 more file in changeset.
Add missing optimization of intersection

  1. … 1 more file in changeset.
Add a logging exclude factory

This factory is enabled if, and only if, the log level is set to debug (`-d`).

Then it will log all merge operations, and report if there's a stack overflow

in merging exclude specs.

    • -0
    • +96
    ./LoggingExcludeFactory.java
  1. … 13 more files in changeset.
Add test coverage for intersections of 3 elements

and add more test coverage for unions

  1. … 1 more file in changeset.
Add randomization of sets

  1. … 2 more files in changeset.
Fix incorrect reduction of intersections

Simplification of intersections in the normalizing exclude

factory is done by pairs. There was a bug in the reduction

algorithm, that would cause the reduction result to be

wrong because we used the wrong, non simplified, exclude spec

for merging whenever a merge occured, to reduce on the next

item in a list.

  1. … 2 more files in changeset.
Optimize a couple more cases

Optimize intersect(group, module) -> moduleId(group, module)

Optimize intersect(group, module names) -> moduleIdSet(group + name...)

  1. … 1 more file in changeset.
Optimize a couple more cases

Optimize intersect(group, module) -> moduleId(group, module)

Optimize intersect(group, module names) -> moduleIdSet(group + name...)

  1. … 1 more file in changeset.
Fix incorrect simplification of intersection of unions

The result of simplification was only correct if there was one

item not in common on both hands of the intersection.

Fixes #9718

  1. … 1 more file in changeset.
Fix incorrect simplification of intersection of unions

The result of simplification was only correct if there was one

item not in common on both hands of the intersection.

Fixes #9718

  1. … 1 more file in changeset.
Add exclude intersection normalization

This commit introduces exclude intersection normalization.

This is done to avoid the "exclusion explosion" in case:

- we have 2 incoming edges to the same node

- those edges have different excludes

- the different edge excludes cannot be merged (e.g having a `group` and `moduleId` exclude on each)

    • -0
    • +205
    ./Intersections.java
  1. … 2 more files in changeset.
Minor refactoring for readability

Perform simplification only if specs contain expected types

Use hash set estimate size to avoid resizes

  1. … 1 more file in changeset.
Give up a bit on immutability for the sake of performance

Creating an immutable list with Guava has a slight performance

overhead. Given we have to mitigate a performance regression,

choice is to give up here, knowing we have enough guarantees

(the structure is internal).

    • -10
    • +12
    ./NormalizingExcludeFactory.java
Add union/intersection simplification

Use coarce grained locking

Measurements show it's significantly faster than using a read/write lock.

  1. … 1 more file in changeset.
Optimize flattening

This commit optimizes flattening by avoiding the creation of intermediate

data structures. In particular using lists we were converting from and to

sets unnecessarily.

    • -0
    • +61
    ./ExcludeFactory.java
    • -29
    • +64
    ./NormalizingExcludeFactory.java
  1. … 8 more files in changeset.
Reuse caching at lower level

The merge cache can be reused at different stages. In particular, when

the normalizing factory normalizes unions/intersections, it is possible

that the normalized union is found in cache.

  1. … 1 more file in changeset.
Optimize `ExcludePair` for comparisons

Remove indexed exclude factory

It didn't prove as fast as it was intended to be. Instead, we performed

the same optimization for single groups/modules as we did for module sets.

    • -37
    • +91
    ./NormalizingExcludeFactory.java
  1. … 13 more files in changeset.
Rework exclude rule merging

As a follow-up to #9197, this commit properly fixes the

exclude rule merging algorithm, by completely rewriting

it. The new merging algorithm works by implementing the

minimal set of algebra operations that make sense to

minimize computation durations. In order to do this,

this commit introduces a number of exclude specs

(found in their own package) and factories to create

actual implementation of those specs.

Specs represent the different kind of excludes we can

find:

- excluding a group

- excluding a module (no group defined)

- excluding a group+module

- excluding an artifact of a group+module

- pattern-matching excludes

- unions of excludes

- intersections of excludes

With all those minimal bricks, factories are responsible

of generating consistent specs. The dumbest factory

will just generate new instances for everything. This

is the default factory.

Minimally, this factory has to be backed by an optimizing

factory, which will take care of handling special cases:

- union or intersection of a single spec

- union or intersection of 2 specs

- when one of them is null

- when both are equal

Then we have a factory which performs the minimal algebra

to minimize specs:

- unions of unions

- intersections of intersections

- union of a union and individual specs

- insection of an intersection and individual spec

- ...

This factory can be as smart as it can, but one must be

careful that it's worth it: some previously implemented

optimizations (like (A+B).A = A turned out to be costly

to detect, and didn't make it the final cut.

Last but not least, a caching factory is there to avoid

recomputing the same intersections and unions of specs

when we have already done the job. This is efficient if

the underlying (delegate) specs are easily compared,

which is the case thanks to the interning factory.

All in all, the delegation chain allows us to make

the algorithm fast and hopefully reliable, while

making it easier to debug.

    • -0
    • +149
    ./CachingExcludeFactory.java
    • -0
    • +92
    ./DelegatingExcludeFactory.java
    • -0
    • +158
    ./NormalizingExcludeFactory.java
    • -0
    • +89
    ./Optimizations.java
    • -0
    • +61
    ./OptimizingExcludeFactory.java
  1. … 70 more files in changeset.