Re: [jgrapht-users] some potential speed improvements for containsEdge(u, v) and getEdge(u, v)

[H.N. de R. <hnr...@gr...>]

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