|
From: Joris K. <de...@gm...> - 2016-04-09 19:08:56
|
Based on all the suggestions in this thread, I've started a first round of code optimization. See my pull request: https://github.com/jgrapht/jgrapht/pull/188 Since this really touches the internals of JGraphT, please perform a thorough code review. @Ernst. Interesting idea to create an VertexPair object once and then modify it for various lookups. I haven't tried it yet though. br, Joris Kinable On Sat, Apr 9, 2016 at 2:14 PM, 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 > |
