From e37581c6ee08aeca46e1adff9f637314019ace82 Mon Sep 17 00:00:00 2001 From: Oszkar Semerath Date: Thu, 15 Jul 2021 13:37:53 +0200 Subject: Merging immutable nodes during commits. --- .../solver/data/map/VersionedMapStoreImpl.java | 21 ++++--- .../viatra/solver/data/map/internal/MapCursor.java | 20 +++---- .../solver/data/map/internal/MapEntryIterator.java | 7 ++- .../solver/data/map/internal/VersionedMapImpl.java | 46 ++++++++++---- .../viatra/solver/data/map/SmokeTest1Mutable.java | 2 + .../viatra/solver/data/map/SmokeTest2Commit.java | 70 +++++++++++++++++----- 6 files changed, 114 insertions(+), 52 deletions(-) (limited to 'Solvers') diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/VersionedMapStoreImpl.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/VersionedMapStoreImpl.java index d115833e..0c00108b 100644 --- a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/VersionedMapStoreImpl.java +++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/VersionedMapStoreImpl.java @@ -3,7 +3,6 @@ package org.eclipse.viatra.solver.data.map; import java.util.HashMap; import java.util.Map; import java.util.Set; -import java.util.WeakHashMap; import org.eclipse.viatra.solver.data.map.internal.ImmutableNode; import org.eclipse.viatra.solver.data.map.internal.Node; @@ -13,8 +12,8 @@ public class VersionedMapStoreImpl implements VersionedMapStore hashProvider; protected final VALUE defaultValue; - protected Map> states; - protected WeakHashMap, ImmutableNode> nodeCache; + final protected Map> states; + final protected Map, ImmutableNode> nodeCache; protected long nextID; public VersionedMapStoreImpl(ContinousHashProvider hashProvider, VALUE defaultValue) { @@ -23,6 +22,7 @@ public class VersionedMapStoreImpl implements VersionedMapStore(); nextID = 0; + nodeCache = new HashMap<>(); } Set getStates() { @@ -42,22 +42,21 @@ public class VersionedMapStoreImpl implements VersionedMapStore getStateData(long state) { - return states.get(state); - } private long getNextID() { if(nextID == Long.MAX_VALUE) throw new IllegalStateException("Map store run out of Id-s"); return nextID++; } + + public ImmutableNode getStateData(long state) { + return states.get(state); + } + public Map, ImmutableNode> getStore() { + return this.nodeCache; + } public long addState(ImmutableNode data) { long id = getNextID(); states.put(id,data); return id; } -// public void removeState(long state) { -// if(states.containsKey(state)) { -// this.states.remove(state); -// } -// } } diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MapCursor.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MapCursor.java index d658e9d8..e77d073f 100644 --- a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MapCursor.java +++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MapCursor.java @@ -5,6 +5,7 @@ import java.util.ConcurrentModificationException; import java.util.Deque; import org.eclipse.viatra.solver.data.map.Cursor; +import org.eclipse.viatra.solver.data.map.VersionedMap; public class MapCursor implements Cursor { // Constants @@ -20,13 +21,11 @@ public class MapCursor implements Cursor { KEY key; VALUE value; - // State - /** - * Dirty bit for Conc - */ - boolean dirty; + // Hash code for checking concurrent modifications + final VersionedMap map; + final int creationHash; - public MapCursor(Node root) { + public MapCursor(Node root, VersionedMap map) { // Initializing tree stack super(); this.nodeStack = new ArrayDeque<>(); @@ -42,7 +41,8 @@ public class MapCursor implements Cursor { this.value = null; // Initializing state - this.dirty = false; + this.map=map; + this.creationHash = map.hashCode(); // move to first move(); @@ -61,7 +61,7 @@ public class MapCursor implements Cursor { } public boolean move() { - if(dirty) { + if(isDirty()) { throw new ConcurrentModificationException(); } if(!isTerminated()) { @@ -71,7 +71,7 @@ public class MapCursor implements Cursor { } } - public void setDirty() { - this.dirty = true; + public boolean isDirty() { + return this.map.hashCode() != this.creationHash; } } diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MapEntryIterator.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MapEntryIterator.java index 47976b46..e471af31 100644 --- a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MapEntryIterator.java +++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MapEntryIterator.java @@ -6,6 +6,8 @@ import java.util.Map; import java.util.Map.Entry; import java.util.NoSuchElementException; +import org.eclipse.viatra.solver.data.map.VersionedMap; + /** * Preorder iterator for map {@link #Node}s. * @@ -16,9 +18,8 @@ import java.util.NoSuchElementException; */ public class MapEntryIterator extends MapCursor implements Iterator>{ - - public MapEntryIterator(Node root) { - super(root); + public MapEntryIterator(Node root, VersionedMap map) { + super(root,map); } diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/VersionedMapImpl.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/VersionedMapImpl.java index ad734932..e32fa94b 100644 --- a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/VersionedMapImpl.java +++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/VersionedMapImpl.java @@ -22,7 +22,6 @@ public class VersionedMapImpl implements VersionedMap{ protected final ContinousHashProvider hashProvider; protected final VALUE defaultValue; protected Node root; - WeakHashMap, Boolean> iterators; public VersionedMapImpl( VersionedMapStoreImpl store, @@ -33,7 +32,6 @@ public class VersionedMapImpl implements VersionedMap{ this.hashProvider = hashProvider; this.defaultValue = defaultValue; this.root = null; - iterators = new WeakHashMap<>(); } public VersionedMapImpl( VersionedMapStoreImpl store, @@ -44,7 +42,6 @@ public class VersionedMapImpl implements VersionedMap{ this.hashProvider = hashProvider; this.defaultValue = defaultValue; this.root = data; - iterators = new WeakHashMap<>(); } public VALUE getDefaultValue() { @@ -55,9 +52,6 @@ public class VersionedMapImpl implements VersionedMap{ } @Override public void put(KEY key, VALUE value) { - for(MapCursor iterator : iterators.keySet()) { - iterator.setDirty(); - } if(root!=null) { root = root.putValue(key, value, hashProvider, defaultValue, hashProvider.getHash(key, 0), 0); } else { @@ -83,14 +77,12 @@ public class VersionedMapImpl implements VersionedMap{ @Override public Iterator> getIterator() { - MapEntryIterator iterator = new MapEntryIterator<>(this.root); - iterators.put(iterator, null); + MapEntryIterator iterator = new MapEntryIterator<>(this.root,this); return iterator; } @Override public Cursor getCursor() { - MapEntryIterator cursor = new MapEntryIterator<>(this.root); - iterators.put(cursor, null); + MapEntryIterator cursor = new MapEntryIterator<>(this.root,this); return cursor; } @@ -98,7 +90,13 @@ public class VersionedMapImpl implements VersionedMap{ public long commit() { ImmutableNode immutable; if(this.root != null) { - immutable = root.toImmutable(); + Map, ImmutableNode> cache = this.store.getStore(); + if(cache != null) { + immutable = root.toImmutable(cache); + } else { + immutable = root.toImmutable(); + } + } else { immutable = null; } @@ -108,9 +106,33 @@ public class VersionedMapImpl implements VersionedMap{ @Override public void restore(long state) { - // TODO Auto-generated method stub + root = this.store.getStateData(state); } + @Override + public int hashCode() { + final int prime = 31; + int result = 1; + result = prime * result + ((root == null) ? 0 : root.hashCode()); + return result; + } + + @Override + public boolean equals(Object obj) { + if (this == obj) + return true; + if (obj == null) + return false; + if (getClass() != obj.getClass()) + return false; + VersionedMapImpl other = (VersionedMapImpl) obj; + if (root == null) { + if (other.root != null) + return false; + } else if (!root.equals(other.root)) + return false; + return true; + } public void prettyPrint() { StringBuilder s = new StringBuilder(); if(this.root != null) { diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/tests/org/eclipse/viatra/solver/data/map/SmokeTest1Mutable.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/tests/org/eclipse/viatra/solver/data/map/SmokeTest1Mutable.java index 9b08a7bc..76d40e3c 100644 --- a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/tests/org/eclipse/viatra/solver/data/map/SmokeTest1Mutable.java +++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/tests/org/eclipse/viatra/solver/data/map/SmokeTest1Mutable.java @@ -112,6 +112,8 @@ public class SmokeTest1Mutable { } @Test void SmokeLarge() { + var milis = System.currentTimeMillis(); runSmokeTest("SmokeLarge",0, 32*32*32*32, 32*32-1, 2); + System.out.println(System.currentTimeMillis()-milis); } } diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/tests/org/eclipse/viatra/solver/data/map/SmokeTest2Commit.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/tests/org/eclipse/viatra/solver/data/map/SmokeTest2Commit.java index 8be9adb6..337725a6 100644 --- a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/tests/org/eclipse/viatra/solver/data/map/SmokeTest2Commit.java +++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/tests/org/eclipse/viatra/solver/data/map/SmokeTest2Commit.java @@ -90,30 +90,58 @@ public class SmokeTest2Commit { } } + // Mini smoke frequent commints @Test - void MiniSmokeK3V2v1() { - runSmokeTest("MiniSmokeK3V2v1",0, 1000, 3, 2, 10); + void MiniSmokeFrequentK3V2v1() { + runSmokeTest("MiniSmokeK3V2v1",0, 1000, 3, 2, 1); } @Test - void MiniSmokeK3V2v2() { - runSmokeTest("MiniSmokeK3V2v2",1, 1000, 3, 2, 10); + void MiniSmokeFrequentK3V2v2() { + runSmokeTest("MiniSmokeK3V2v2",1, 1000, 3, 2, 1); } @Test - void MiniSmokeK3V2v3() { - runSmokeTest("MiniSmokeK3V2v3",3, 1000, 3, 2, 10); + void MiniSmokeFrequentK3V2v3() { + runSmokeTest("MiniSmokeK3V2v3",3, 1000, 3, 2, 1); } @Test - void MiniSmokeK3V3v1() { - runSmokeTest("MiniSmokeK3V2v1",0, 1000, 3, 3, 10); + void MiniSmokeFrequentK3V3v1() { + runSmokeTest("MiniSmokeK3V2v1",0, 1000, 3, 3, 1); } @Test - void MiniSmokeK3V3v2() { - runSmokeTest("MiniSmokeK3V2v2",1, 1000, 3, 3, 10); + void MiniSmokeFrequentK3V3v2() { + runSmokeTest("MiniSmokeK3V2v2",1, 1000, 3, 3, 1); } @Test - void MiniSmokeK3V3v3() { - runSmokeTest("MiniSmokeK3V2v3",3, 1000, 3, 3, 10); + void MiniSmokeFrequentK3V3v3() { + runSmokeTest("MiniSmokeK3V2v3",3, 1000, 3, 3, 1); } + // Mini smoke rare commits + @Test + void MiniSmokeRareK3V2v1() { + runSmokeTest("MiniSmokeK3V2v1",0, 1000, 3, 2, 100); + } + @Test + void MiniSmokeRareK3V2v2() { + runSmokeTest("MiniSmokeK3V2v2",1, 1000, 3, 2, 100); + } + @Test + void MiniSmokeKRare3V2v3() { + runSmokeTest("MiniSmokeK3V2v3",3, 1000, 3, 2, 100); + } + @Test + void MiniSmokeRareK3V3v1() { + runSmokeTest("MiniSmokeK3V2v1",0, 1000, 3, 3, 100); + } + @Test + void MiniSmokeRareK3V3v2() { + runSmokeTest("MiniSmokeK3V2v2",1, 1000, 3, 3, 100); + } + @Test + void MiniSmokeRareK3V3v3() { + runSmokeTest("MiniSmokeK3V2v3",3, 1000, 3, 3, 100); + } + + // Medium smoke @Test void MediumSmokeK3V2v1() { runSmokeTest("MediumSmokeK3V2v1",1, 1000, 32, 2, 10); @@ -126,8 +154,18 @@ public class SmokeTest2Commit { void MediumSmokeK3V2v3() { runSmokeTest("MediumSmokeK3V2v3",3, 1000, 32, 2, 10); } -// @Test -// void SmokeLarge() { -// runSmokeTest("SmokeLarge",0, 32*32*32*32, 32*32-1, 2); -// } + + //Large Smoke + @Test + void SmokeLargeRareCommit() { + runSmokeTest("SmokeLarge",0, 32*32*32*32, 32*32-1, 2, 100); + } + @Test + void SmokeLargeNormalCommit() { + runSmokeTest("SmokeLarge",0, 32*32*32*32, 32*32-1, 2, 10); + } + @Test + void SmokeLargeFrequentCommit() { + runSmokeTest("SmokeLarge",0, 32*32*32*32, 32*32-1, 2, 1); + } } -- cgit v1.2.3-54-g00ecf