The Quest for Performance: tuple and match representation, memories

[eclipse-viatra-bot]

| --- | --- | | Bugzilla Link | 398765 | | Status | NEW | | Importance | P3 normal | | Reported | Jan 22, 2013 11:06 EDT | | Modified | Jan 19, 2018 14:55 EDT | | Version | oldinquery | | Depends on | 502099, 530057, 502098, 506354, 518791, 521816, 526797, 526799 | | Reporter | Gabor Bergmann |

Description

Cloned from: 327: The Quest for Performance: tuple and match representation, memories\ http://github.com/ujhelyiz/EMF-IncQuery/issues/issue/327

Experiment with:

• left/right/dual inheritance of tuples
• tuple ordering to enhance indexer sharing
• smart adaptation of these strategies
• tuple-backed match, hash code storage, etc.
• Collection implementations: \
  • Use MultiMap (from Guava or other libraries) to back MaskedTupleMemories in indexers\
  • Use MultiSet (from Guava or other libraries) to back TupleMemories in production nodes\
  • Use Set (from JRE, Guava or other libraries) to back TupleMemories in input UniquenessEnforcers \
  • experiment with collection frameworks\ \ From earlier notes:
• PatternMemory.toArray <- called by DualInputNode.retrieveOpposites and MatchFetcher.run... is size() dominant?
• retrieveOpposites -> deduplicate!
• more clever Receiver interface (e.g. unify with indexer? two-phase update with message creation?)
• more lightweight message passing (old experimental patch still available in Viatra code, see also code snippet below)

    public void sendUpdate(Receiver receiver, Direction direction, Tuple updateElement) \
    {\
        if (org.eclipse.viatra2.gtasm.patternmatcher.incremental.rete.util.Options.synchronous) receiver.update(direction, updateElement);\
        else {\
            messageQueue.addLast(new UpdateMessage(receiver, direction, updateElement));\
        }\
    }\

[eclipse-viatra-bot]

By Gabor Bergmann on Mar 13, 2013 10:21

• make pullInto() cheaper for memoryless nodes: if at least one projection indexer already exists, just re-enumerate it

[eclipse-viatra-bot]

By Gabor Bergmann on Mar 14, 2013 06:48

• special identity masks and null masks to increase speed and reuse heap objects

[eclipse-viatra-bot]

By Gabor Bergmann on May 12, 2013 17:49

BasePatternMatch.get(int index) should be overridden in generated match implementations. (this change is not breaking the API)

[eclipse-viatra-bot]

By Istvan Rath on May 20, 2013 04:35

I'm setting version to "unspecified" as we currently do not (firmly) know when these future ideas will be addressed.

[eclipse-viatra-bot]

By Gabor Bergmann on Aug 26, 2013 11:54

Further idea: experiment with various levels of caching at evaluator nodes.

• exploit determinism: reuse result for different tuples if the variables used in expression take the same value
• memoing: use some kind of weakmap to retain evaluation results even the tuple is (temporarily) revoked

[eclipse-viatra-bot]

By Gabor Bergmann on Oct 13, 2014 08:22

Further idea: rethink indexers.

• Avoid having multiple projection indexers of the same node that are merely permutations of each other (in order to maximize indexer reuse and reduce memory footprint). Solution: construct projection indexers always in the ascending order of indices, and equip join node with cleverly constructed masks to translate from tuples of one parent to the projection of the other parent.

• Eliminate those variables from tuples that can always be reproduced via simple lookups (e.g. targets of to-noe edges, where the source is also in the tuple). If their value is necessary for indexing or term evaluation or whatever, do a "remote lookup" on the spot (as part of the new kind of joining, see above) based on the original input node. Make sure the result remains consistent when the input node is updated. (Note: might cause trouble in a distributed scenario.)

[eclipse-viatra-bot]

By Abel Hegedus on Apr 19, 2016 05:24

Updating to correct milestone.

[eclipse-viatra-bot]

By Gabor Bergmann on Jun 28, 2017 05:46

•  special tuple implementations for arity 0,1,2,... up to a point