Memory leak

[stanmoon]

Hi!

I'm experiencing a memory leak when interacting with a factory.

The factory is created many times and after using it I call the following method:

/**
 * Signals factory destruction
 */
public void doneWithFactory() {
    for (BDD bdd : bddlist) {
        bdd.free();
    }
    factory.gc();
    factory.done();

}

After several thousand creation and destruction of the factories, my system runs out of memory (16GB RAM).

The creation is as follows:

    factory = Factory.mkResizingAndGarbageCollected(INIT_SIZE, BUFFER_SIZE);

The loop that creates and destroys the objects containing the factories is the following:

    while (parser.hasNext()) {
        parser.readNextNetwork();

        log.info("initializing bdd module");
        analyzer = new SynchronousSteadyStateAnalyzer(parser.getCurrentNetwork());
        module = analyzer.getBDDModule();

        log.debug("writing basins for model: " + parser.getCurrentId());
        writeBasins(writer, analyzer, parser.getCurrentId(), analyzer.getBasins());

        module.doneWithFactory();

        if (n % reset == 0) {
            System.gc();
        }

        n++;
    }

I have tried several approaches but it always consumes all the memory. Despite the fact that the reference to the object containing the factories is lost. I guess is some kind of thread issue.

Thanks in advance,

[albertolovato]

I'm not able to reproduce the memory leak you experience, after creating and destroying the factory 5000 times, and performing BDD operations in between. Could you please be more precise about the size of the factory, and the operations you are performing? And also, what version of the library are you using? Thank you

[stanmoon]

@albertolovato, thank you very much for your prompt reply.

I'm using a jar file I downloaded from juliasoft website

http://www.juliasoft.com/beedeedeeDownload (Java BeeDeeDee Library 1.0.7)

However the link is broken now.

I have tried creating the factory with different parameters, but does not seem to matter much. Currently I'm trying with these

    private int INIT_SIZE = 1000;

    private int BUFFER_SIZE = 1000;

    ...

    private ResizingAndGarbageCollectedFactory factory;

Below I include some code samples to illustrate the kind of operations performed with BeeDeeDee library.

I have Boolean formulas that are translated into BDDs:

    /**
     * Transform the provided formula sentence tree in a BDD representation
     * 
     * @param formula
     *            the formula to transform
     * @return the binary decision diagram
     */
    private BDD transform(Formula formula) {
        BDD result;
        if (formula instanceof BooleanConstant) {
            result = getBooleanConstant((BooleanConstant) formula);
        } else if (formula instanceof Variable) {
            result = asBDD((Variable) formula);
        } else if (formula instanceof Not) {
            result = transform(((Not) formula).getSubformula()).not();
        } else if (formula instanceof And) {
            result = transform(((And) formula).getLeftSubformula())
                    .and(transform(((And) formula).getRightSubformula()));
        } else if (formula instanceof Or) {
            result = transform(((Or) formula).getLeftSubformula()).or(transform(((Or) formula).getRightSubformula()));
        } else if (formula instanceof Equality) {
            result = transform(((Equality) formula).getLeftSubformula())
                    .biimp(transform(((Equality) formula).getRightSubformula()));
        } else if (formula instanceof Implication) {
            result = transform(((Implication) formula).getLeftSubformula())
                    .imp(transform(((Implication) formula).getRightSubformula()));
        } else {
            throw new UnsupportedOperationException("Unknown operation: " + formula.getClass().getName());
        }
        bddlist.add(result);
        return result;
    }

    /**
     * Transforms the provided variable returning the corresponding BDD
     * 
     * @param variable
     *            the variable to set
     * @return the corresponding Binary Decision Diagram
     */
    public BDD asBDD(Variable variable) {
        BDD result;
        String name = variable.getName();
        int identifier;
        if (names.containsKey(name)) {
            result = bdds.get(names.get(name));
        } else {
            identifier = nextIdentifier();
            log.debug("identifier for creating variable: " + identifier);
            result = factory.makeVar(identifier);
            // variables always have names
            names.put(name, identifier);
            ids.put(identifier, name);
            bdds.put(identifier, result);
            bddlist.add(result);
        }
        return result;
    }

    /**
     * Obtains the BDD representing the Boolean constant
     * 
     * @param constant
     *            the constant
     * @return the bdd
     */
    public BDD getBooleanConstant(BooleanConstant constant) {
        BDD result;
        int identifier;
        String name = ((BooleanConstant) constant).getValue() ? TRUE_NAME : FALSE_NAME;
        if (names.containsKey(name)) {
            result = bdds.get(names.get(name));
        } else {
            result = ((BooleanConstant) constant).getValue() ? factory.makeOne() : factory.makeZero();
            // Constants have names

            identifier = result.isOne() ? TRUE_ID : FALSE_ID;
            names.put(name, identifier);
            ids.put(identifier, name);
            bdds.put(identifier, result);
            bddlist.add(result);
        }
        return result;
    }

This is an example of a Boolean formula that describe an update rule for a Boolean network node: ((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((~AP1&~TFL1)&~AP2)&~EMF1)&~AG)&WUS)&~SEP)&~LFY)|(((((((~AP1&~TFL1)&~AP2)&~EMF1)&~AG)&~WUS)&SEP)&~LFY))|(((((((~AP1&~TFL1)&~AP2)&~EMF1)&~AG)&WUS)&SEP)&~LFY))|(((((((~AP1&~TFL1)&~AP2)&~EMF1)&~AG)&~WUS)&~SEP)&LFY))|(((((((~AP1&~TFL1)&~AP2)&~EMF1)&~AG)&WUS)&~SEP)&LFY))|(((((((~AP1&~TFL1)&~AP2)&~EMF1)&~AG)&~WUS)&SEP)&LFY))|(((((((~AP1&~TFL1)&~AP2)&~EMF1)&~AG)&WUS)&SEP)&LFY))|(((((((~AP1&~TFL1)&~AP2)&EMF1)&~AG)&~WUS)&~SEP)&LFY))|(((((((~AP1&~TFL1)&~AP2)&EMF1)&~AG)&WUS)&~SEP)&LFY))|(((((((~AP1&~TFL1)&~AP2)&EMF1)&~AG)&~WUS)&SEP)&LFY))|(((((((~AP1&~TFL1)&~AP2)&EMF1)&~AG)&WUS)&SEP)&LFY))|(((((((~AP1&~TFL1)&AP2)&~EMF1)&~AG)&WUS)&SEP)&LFY))|(((((((AP1&~TFL1)&~AP2)&~EMF1)&~AG)&WUS)&SEP)&LFY))|(((((((AP1&~TFL1)&AP2)&~EMF1)&~AG)&WUS)&SEP)&LFY))|(((((((~AP1&~TFL1)&~AP2)&~EMF1)&AG)&~WUS)&~SEP)&~LFY))|(((((((~AP1&~TFL1)&~AP2)&~EMF1)&AG)&WUS)&~SEP)&~LFY))|(((((((~AP1&~TFL1)&~AP2)&~EMF1)&AG)&~WUS)&SEP)&~LFY))|(((((((~AP1&~TFL1)&~AP2)&~EMF1)&AG)&WUS)&SEP)&~LFY))|(((((((~AP1&TFL1)&~AP2)&~EMF1)&AG)&~WUS)&SEP)&~LFY))|(((((((~AP1&TFL1)&~AP2)&~EMF1)&AG)&WUS)&SEP)&~LFY))|(((((((~AP1&~TFL1)&~AP2)&~EMF1)&AG)&~WUS)&~SEP)&LFY))|(((((((~AP1&~TFL1)&~AP2)&~EMF1)&AG)&WUS)&~SEP)&LFY))|(((((((~AP1&~TFL1)&~AP2)&~EMF1)&AG)&~WUS)&SEP)&LFY))|(((((((~AP1&~TFL1)&~AP2)&~EMF1)&AG)&WUS)&SEP)&LFY))|(((((((~AP1&TFL1)&~AP2)&~EMF1)&AG)&~WUS)&SEP)&LFY))|(((((((~AP1&TFL1)&~AP2)&~EMF1)&AG)&WUS)&SEP)&LFY))|(((((((~AP1&~TFL1)&~AP2)&EMF1)&AG)&~WUS)&~SEP)&LFY))|(((((((~AP1&~TFL1)&~AP2)&EMF1)&AG)&WUS)&~SEP)&LFY))|(((((((~AP1&~TFL1)&~AP2)&EMF1)&AG)&~WUS)&SEP)&LFY))|(((((((~AP1&~TFL1)&~AP2)&EMF1)&AG)&WUS)&SEP)&LFY))|(((((((~AP1&TFL1)&~AP2)&EMF1)&AG)&WUS)&SEP)&LFY))|(((((((~AP1&~TFL1)&AP2)&~EMF1)&AG)&~WUS)&SEP)&~LFY))|(((((((~AP1&~TFL1)&AP2)&~EMF1)&AG)&WUS)&SEP)&~LFY))|(((((((~AP1&TFL1)&AP2)&~EMF1)&AG)&~WUS)&SEP)&~LFY))|(((((((~AP1&TFL1)&AP2)&~EMF1)&AG)&WUS)&SEP)&~LFY))|(((((((~AP1&~TFL1)&AP2)&~EMF1)&AG)&~WUS)&SEP)&LFY))|(((((((~AP1&~TFL1)&AP2)&~EMF1)&AG)&WUS)&SEP)&LFY))|(((((((~AP1&TFL1)&AP2)&~EMF1)&AG)&~WUS)&SEP)&LFY))|(((((((~AP1&TFL1)&AP2)&~EMF1)&AG)&WUS)&SEP)&LFY))|(((((((~AP1&~TFL1)&AP2)&EMF1)&AG)&WUS)&SEP)&LFY))|(((((((~AP1&TFL1)&AP2)&EMF1)&AG)&WUS)&SEP)&LFY))|(((((((AP1&~TFL1)&~AP2)&~EMF1)&AG)&~WUS)&SEP)&~LFY))|(((((((AP1&~TFL1)&~AP2)&~EMF1)&AG)&WUS)&SEP)&~LFY))|(((((((AP1&TFL1)&~AP2)&~EMF1)&AG)&~WUS)&SEP)&~LFY))|(((((((AP1&TFL1)&~AP2)&~EMF1)&AG)&WUS)&SEP)&~LFY))|(((((((AP1&~TFL1)&~AP2)&~EMF1)&AG)&~WUS)&SEP)&LFY))|(((((((AP1&~TFL1)&~AP2)&~EMF1)&AG)&WUS)&SEP)&LFY))|(((((((AP1&TFL1)&~AP2)&~EMF1)&AG)&~WUS)&SEP)&LFY))|(((((((AP1&TFL1)&~AP2)&~EMF1)&AG)&WUS)&SEP)&LFY))|(((((((AP1&~TFL1)&~AP2)&EMF1)&AG)&WUS)&SEP)&LFY))|(((((((AP1&TFL1)&~AP2)&EMF1)&AG)&WUS)&SEP)&LFY))|(((((((AP1&~TFL1)&AP2)&~EMF1)&AG)&~WUS)&SEP)&~LFY))|(((((((AP1&~TFL1)&AP2)&~EMF1)&AG)&WUS)&SEP)&~LFY))|(((((((AP1&TFL1)&AP2)&~EMF1)&AG)&~WUS)&SEP)&~LFY))|(((((((AP1&TFL1)&AP2)&~EMF1)&AG)&WUS)&SEP)&~LFY))|(((((((AP1&~TFL1)&AP2)&~EMF1)&AG)&~WUS)&SEP)&LFY))|(((((((AP1&~TFL1)&AP2)&~EMF1)&AG)&WUS)&SEP)&LFY))|(((((((AP1&TFL1)&AP2)&~EMF1)&AG)&~WUS)&SEP)&LFY))|(((((((AP1&TFL1)&AP2)&~EMF1)&AG)&WUS)&SEP)&LFY))|(((((((AP1&~TFL1)&AP2)&EMF1)&AG)&WUS)&SEP)&LFY))

Several of these formulas are then translated into an even bigger formula describing the transition relation:

Using the following class:

public class SynchronousTransitionRelation extends TransitionRelation {

    /**
     * Obtains the formula representing the synchronous transition relation for
     * the Boolean Network
     * 
     * @param network
     *            the network
     * 
     * @return the boolean formula
     */
    public static Formula obtainSynchronousFormula(BooleanGeneRegulatoryNetwork network) {
        Formula formula = null;
        Formula transitionFormula = null;

        // network dynamics
        for (StateTransitionRule rule : network.getTransitionRules()) {
            transitionFormula = consolidateAnd(transitionFormula, obtainSynchronousRule(rule));
        }

        formula = consolidateAnd(formula, transitionFormula);

        return formula;
    }

    /**
     * obtains the synchronous rule formula
     * 
     * @param rule
     *            the state transition rule
     * @return the asynchronous formula
     */
    private static Formula obtainSynchronousRule(StateTransitionRule rule) {
        Formula formula;
        Variable variable;
        formula = rule.getTransitionFormula();
        variable = new Variable(rule.getGene().getName());
        formula = new Equality(prime(variable), formula);
        return formula;
    }

The transition formula is translated into a BDD and used to compute basins of attraction of steady states:

    /**
     * Obtains the list of Basins of attraction for the Boolean network
     * 
     * Basins of attraction include their attractors
     * 
     * @return the list of basins
     */
    public List<SynchronousAttractorBasin> getBasins() {
        List<SynchronousAttractorBasin> basins = new ArrayList<>();
        Set<BooleanNetworkStateTrajectory> attractors = getAttractors();
        log.debug("[" + attractors.size() + "] attractors found. Attractors: " + attractors);
        for (BooleanNetworkStateTrajectory attractor : attractors) {
            BDD attractorBDD = module.getBooleanConstant(BooleanConstant.FALSE).copy();
            for (InputOutputStatePair pair : attractor.getTrajectory())
                attractorBDD.orWith(toBDD(pair.getInput()));
            log.debug("Attractor:" + attractorBDD);
            basins.add(new SynchronousAttractorBasin(attractor, attractorBDD, backwardReachableSet(attractorBDD)));

        }
        Collections.sort(basins);
        return basins;
    }
    /**
     * Obtains the forward reachable set for the provided BDD
     * 
     * @param set
     *            the initial set of states
     * @return the forward reachable set
     */
    public BDD backwardReachableSet(BDD set) {
        BDD brs = module.getBooleanConstant(BooleanConstant.FALSE);
        BDD frontier = set;
        if (log.isTraceEnabled()) {
            log.trace("frontier: ");
            log.trace(module.toString(frontier));
        }
        while (!frontier.isZero()) {
            frontier = preImageOfSet(frontier).and(brs.not());
            if (log.isTraceEnabled()) {
                log.trace("frontier: ");
                log.trace(module.toString(frontier));
            }
            brs = brs.or(frontier);
            if (log.isTraceEnabled()) {
                log.trace("brs: ");
                log.trace(module.toString(brs));
            }
        }
        return brs;
    }

That means having to use BDD rewritings to compute preimages:

    protected BooleanGeneRegulatoryNetwork network;

    protected Formula transitionRelationFormula;

    protected BDD transitionRelation;

    protected BDD currentVarsConjuntion;

    protected BDD nextTimeVarsConjuntion;

    protected Map<Integer, Integer> forwardMap;

    protected Map<Integer, Integer> backwardMap;

    protected BDDModule module;

    /**
     * finds the image of a given set of states represented with a Binary
     * Decision Diagram
     * 
     * @param set
     *            the set
     * @return the image of the set
     */
    public BDD imageOfSet(BDD set) {
        return transitionRelation.and(set).exist(currentVarsConjuntion).replace(backwardMap);
    }

    /**
     * finds the pre-image of a given set of states represented with a Binary
     * Decision Diagram
     * 
     * @param set
     *            the set of states
     * @return the binary decision diagram representing the pre-image
     */
    public BDD preImageOfSet(BDD set) {
        return transitionRelation.and(set.replace(forwardMap)).exist(nextTimeVarsConjuntion);
    }

[albertolovato]

Thank you for the feedback. I will try to reproduce the leak. In the meantime, could you please try to run your code against the latest version of the library? The version you have is quite old, and we fixed many bugs in the latest one. I created a new release here on Github, where you can find the latest JAR.

Thank you

[stanmoon]

Hi @albertolovato!

I have updated my old version of the beedeedee.jar and added the new dependencies: mockito-all-1.9.5.jar and julia-annotations-1.9.20.jar. I'm still experiencing memory exhaustion. I have also tried keeping a reference to all intermediate bdd operations and calling the method free() in every one of them just before calling factory.done(). Unfortunately, this doesn't seem to prevent the leak.

Best regards,

[albertolovato]

@stanmoon, there is no need to free the bdds: as long as there are no live references to the factory, it should be collected by the Java's GC, along with all the bdd data inside it (simple integer arrays). Unfortunately I'm still unable to reproduce the leak. Could you please give me an executable version of your software (no source needed), or at least a reduced version exhibiting the leak? This way I could try to profile the memory consumption.

[stanmoon]

Thank you @albertolovato!

I was preparing a simplified program that reproduces the leak and found that the leak most probably occurs not with the beedeedee library but with light instances of the sat4j engine that computes the network attractors. I will investigate this and will post my findings asap.

Thanks again,

[stanmoon]

I can confirm that the leak is related to sat4j solver instances and not java beedeedee.

@albertolovato thanks for all the support!