|
From: Joris K. <de...@gm...> - 2016-04-10 19:07:29
|
I've done some testing to measure the impact of frequent object creation. *Algorithm setup:* 1. Implementation where VertexPair objects are frequently created and immediately discarded afterwards (see https://github.com/jgrapht/jgrapht/pull/188). 2. Implementation where I use a ModifiableVertexPair as proposed by Ernst. In this implementation I created a single ModifiableVertexPair indexPair. Each time an edge is queried in the Map<ModifiableVertexPair<V>, ArrayUnenforcedSet<E>> touchingVerticesToEdgeMap, indexPair.updatePair(source, target) gets invoked first. This entirely avoids the creation of new VertexPairs. To ensure that read operations are thread-save, I made the getEdge(u,v) and getAllEdges(u,v) synchronized. Here's the implementation: https://github.com/jkinable/jgrapht/blob/SpecificsOptimization_experimental/jgrapht-core/src/main/java/org/jgrapht/graph/specifics/FastLookupDirectedSpecifics_experimental.java . If you want to try it yourself or see my implementation, download this branch: https://github.com/jkinable/jgrapht/tree/SpecificsOptimization_experimental *Experiment setup:* java version "1.8.0_77" Java(TM) SE Runtime Environment (build 1.8.0_77-b03) Each experiment is repeated 5 times, with 5 warmup iterations each. *Experiments:* 1. ConstructGraph: Build 100 graphs, each consisting of 1000 vertices and 100000 edges 2. UseGraph: Build 100 graphs, run 3 different algorithms on each graph, randomly destroy part of the graph (triggering containsEdge(u,v) and removeEdge(u,v)). Results: Benchmark Mode Cnt Score Error Units ConstructGraph(objectCreation) avgt 5 11313.907 ± 216.430 ms/op UseGraph(objectCreation) avgt 5 33234.987 ± 1009.527 ms/op ConstructGraph(IndexPair) avgt 5 11230.629 ± 146.290 ms/op UseGraph(IndexPair) avgt 5 32295.133 ± 1208.719 ms/op Here objectCreation uses a DirectedSpecifics implementation where short-lived VertexPairs are created. IndexPair uses a DirectedSpecifics implementation where objects are reused. I repeated these experiment several times, never was there a clear winner. Conclusion: I was unable to create a scenario where reusing the objects was significantly more efficient than recreating them. Quite an interesting result if you ask me. Consequently, I would propose to continue with my pull request: https://github.com/jgrapht/jgrapht/pull/188 br, Joris Kinable On Sun, Apr 10, 2016 at 7:24 AM, H.N. de Ridder <hnr...@gr...> wrote: > On Sat, Apr 09, 2016 at 08:25:15PM -0700, John Sichi wrote: > > Yes, that's true. Thread-unsafety is a k.o.-criterium. I tested with 64bit > icedtea 2.6.5. I'm short on time right now, but I'll see in a week or so > whether I can repeat the tests with java8 and also if I can pinpoint when > memory gets tight and what happens then. > > > Hmmm...the problem with the reusable pair object is that it makes even > > reads thread-unsafe (unless it's implemented via a thread-local > variable). > > I'm not 100% sure, but I think the last time we analyzed it, the graph > data > > structures themselves were all OK for concurrent reads (though not of > > course for concurrent reads+writes). > > > > It might be good to repeat the benchmarking with the latest JVM. > > > > On Sat, Apr 9, 2016 at 11:14 AM, H.N. de Ridder < > hnr...@gr...> > > wrote: > > > > > On Fri, Apr 08, 2016 at 02:36:37AM -0700, John Sichi wrote: > > > > Regarding short-lived VertexPairs: long ago I learned to stop > worrying > > > and > > > > love the Eden approach of the garbage collector. Think about how > many > > > > iterators are created and forgotten during a typical algorithm > > > execution... > > > > > > But iterators typically are used more than once, here the new pair is > used > > > only for a single hash lookup. > > > > > > Several years ago I ran into the same performance issue with JgraphT > and > > > as a > > > quick hack created a wrapper class like this (and then forget about it > > > until > > > this discussion): > > > > > > public class CacheGraph<V,E> extends ListenableDirectedGraph<V,E> > > > implements GraphListener<V,E> { > > > private DirectedGraph<V,E> graph; /** The graph we're caching */ > > > private HashMap<V,V> nodeCache; > > > private HashMap<Pair,E> edgeCache; > > > private Pair reusablePair; /** For looking up edges */ > > > > > > The rest of the class is about as you'd expect. Note that Pair, > different > > > from > > > org.jgrapht.util.VertexPair, is modifiable. I used this class to time > the > > > impact of allocating a new Pair() when performing an edge lookup and > in my > > > application it adds about 9% to the running time. And this is when > there > > > is no > > > shortage of memory. When there is, the shit can really hit the fan. So > I > > > suggest using a reusable pair object and not reallocating one for every > > > test. > > > > > > Regards, > > > Ernst > > > > > > > > > > > On Wed, Apr 6, 2016 at 4:18 PM, Joris Kinable <de...@gm...> > wrote: > > > > > > > > > John, > > > > > > > > > > If I understand you correct, you would propose to do the following: > > > > > To the Specifics class, you would add: > > > > > Map<VertexPair<V,V>,Set<E>> vertexPairToEdgeMap=....; > > > > > > > > > > Then in DirectedSpecifics.addEdgeToTouchingVertices(E e) you would > > > *add*: > > > > > VertexPair<V,V> pair=new VertexPair<>(source, target); > > > > > if(!vertexPairToEdgeMap.containsKey(pair)) > > > vertexPairToEdgeMap.put(pair, > > > > > new LinkedHashSet<>()); > > > > > vertexPairToEdgeMap.get(pair).put(e); > > > > > > > > > > And then the current DirectedSpecifics.getEdge(V source, V target) > > > would > > > > > be *replaced* by: > > > > > VertexPair<V,V> pair=new VertexPair<>(source, target); > > > > > if(!vertexPairToEdgeMap.containsKey(pair) || > > > > > vertexPairToEdgeMap.get(pair).isEmpty()) return null; > > > > > else return vertexPairToEdgeMap.get(pair).iterator().next(); > > > > > > > > > > This would be possible, but then the > SimpleIdentityDirectedGraphTest > > > would > > > > > fail. (In this test, the Vertex objects are changed *after* they > are > > > > > created and added to graph, so an IdentityHashMap is required, see > the > > > test > > > > > for details). I'm not sure how to resolve this. An application can > > > indeed > > > > > override createDirectedSpecifics, but both Specifics and > > > > > DirectedSpecifics are resp. private and protected, so you cannot > > > provide a > > > > > custom DirectedSpecifics implementation which avoid this issue. > > > > > > > > > > Also, would the frequent construction of short-lived VertexPair > objects > > > > > not be an issue, i.e. a new VertexPair would be created each time > > > getEdge(V > > > > > source, V target) is invoked. > > > > > > > > > > Joris > > > > > > > > > > On Wed, Apr 6, 2016 at 5:25 PM, John Sichi <js...@gm...> > wrote: > > > > > > > > > >> Per the last option mentioned by Joris, I don't think any > > > equals/hashCode > > > > >> override is required for any object. > > > > >> > > > > >> My preference is a hybrid of his second and third options. > > > > >> > > > > >> We would add an additional graph-level map inside of Specifics > (not > > > > >> vertex-level inside of EdgeContainer), where the key is > VertexPair, > > > and the > > > > >> value is Edge (or Set<Edge> for multigraphs). When adding an > edge, > > > we add > > > > >> a corresponding entry. When removing an edge, we remove the > entry (or > > > > >> remove the edge from the set for multigraphs, deleting the entry > once > > > the > > > > >> set is empty). This allows us to optimize both containsEdge and > > > getEdge > > > > >> (which is slightly different depending on directed vs undirected). > > > > >> > > > > >> The default implementation would be this new indexing. If an > > > application > > > > >> wants to revert to the old approach to save memory, this would be > > > possible > > > > >> by overriding the createDirectedSpecifics and > > > createUndirectedSpecifics > > > > >> methods. > > > > >> > > > > >> > > > > >> On Wed, Apr 6, 2016 at 2:01 PM, Rushang Karia < > > > rus...@ho...> > > > > >> wrote: > > > > >> > > > > >>> > > > > >>> Wouldn't this be solved by checking for references as well in > > > addition > > > > >>> to the equals()? > > > > >>> > > > > >>> ----- Reply message ----- > > > > >>> From: "Aidan Delaney" <ai...@on...> > > > > >>> To: "jgr...@li..." < > > > > >>> jgr...@li...> > > > > >>> Subject: [jgrapht-users] some potential speed improvements for > > > > >>> containsEdge(u, v) and getEdge(u, v) > > > > >>> Date: Wed, Apr 6, 2016 01:33 > > > > >>> > > > > >>> > > > > >>> Dear all, > > > > >>> As far as I recall (and I'm happy to be wrong) overriding hash > code > > > for > > > > >>> Edge leads to Bad Things (tm). JGraphT is a general graph > > > > >>> implementation. As such, it doesn't assume that you're graph is > not > > > a > > > > >>> multigraph. > > > > >>> In the JGraphT implementation, if we add edge e between > > > vertex > > > > >>> v1 and v2 we -- unsurprisingly -- have an edge between v1 and v2. > > > If I > > > > >>> create another edge, e', which is between v1 and v2 and > identical to > > > e > > > > >>> in all other respects, then my graph has two edges, e and e', > between > > > > >>> v1 and v2. By overriding hashCode, e and e' would be equal > edges and > > > > >>> you'd only have one edge between v1 and v2. > > > > >>> I hope the above helps. I'll read it again after my > first > > > > >>> coffee to see if it's actually intelligible. > > > > >>> > > > > >>> -- > > > > >>> Dr Aidan Delaney > > > > >>> Principal Lecturer > > > > >>> Computing, Engineering & Maths > > > > >>> University of Brighton > > > > >>> > > > > >>> @aidandelaney > > > > >>> > > > > > > -- > > > Information System on Graph Classes and their Inclusions (ISGCI) > > > http://www.graphclasses.org > > > > > > > > > > ------------------------------------------------------------------------------ > > > Find and fix application performance issues faster with Applications > > > Manager > > > Applications Manager provides deep performance insights into multiple > > > tiers of > > > your business applications. It resolves application problems quickly > and > > > reduces your MTTR. Get your free trial! > http://pubads.g.doubleclick.net/ > > > gampad/clk?id=1444514301&iu=/ca-pub-7940484522588532 > > > _______________________________________________ > > > jgrapht-users mailing list > > > jgr...@li... > > > https://lists.sourceforge.net/lists/listinfo/jgrapht-users > > > > > -- > Information System on Graph Classes and their Inclusions (ISGCI) > http://www.graphclasses.org > > > ------------------------------------------------------------------------------ > Find and fix application performance issues faster with Applications > Manager > Applications Manager provides deep performance insights into multiple > tiers of > your business applications. It resolves application problems quickly and > reduces your MTTR. Get your free trial! http://pubads.g.doubleclick.net/ > gampad/clk?id=1444514301&iu=/ca-pub-7940484522588532 > _______________________________________________ > jgrapht-users mailing list > jgr...@li... > https://lists.sourceforge.net/lists/listinfo/jgrapht-users > |
