Quantcast

Re: some potential speed improvements for containsEdge(u, v) and getEdge(u, v)

classic Classic list List threaded Threaded
10 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: some potential speed improvements for containsEdge(u, v) and getEdge(u, v)

Rushang Karia

Wouldn't this be solved by checking for references as well in addition to the equals()?

----- Reply message -----
From: "Aidan Delaney" <[hidden email]>
To: "[hidden email]" <[hidden email]>
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

------------------------------------------------------------------------------

_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users

------------------------------------------------------------------------------

_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: some potential speed improvements for containsEdge(u, v) and getEdge(u, v)

John Sichi
Administrator
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 <[hidden email]> wrote:

Wouldn't this be solved by checking for references as well in addition to the equals()?

----- Reply message -----
From: "Aidan Delaney" <[hidden email]>
To: "[hidden email]" <[hidden email]>
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

------------------------------------------------------------------------------

_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users



------------------------------------------------------------------------------

_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: some potential speed improvements for containsEdge(u, v) and getEdge(u, v)

Joris Kinable
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 <[hidden email]> 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 <[hidden email]> wrote:

Wouldn't this be solved by checking for references as well in addition to the equals()?

----- Reply message -----
From: "Aidan Delaney" <[hidden email]>
To: "[hidden email]" <[hidden email]>
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

------------------------------------------------------------------------------

_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users



------------------------------------------------------------------------------

_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users



------------------------------------------------------------------------------

_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: some potential speed improvements for containsEdge(u, v) and getEdge(u, v)

John Sichi
Administrator
I was thinking the existing DirectedSpecifics and UndirectedSpecifics would become "legacy" implementations (preserving the old behavior).  We would add new subclasses, say OptimizedDirectedSpecifics and OptimizedUndirectedSpecifics (better names welcome).  The vertexPairToEdgeMap should exist only at the Optimized level (not at the base level).  The default implementation of createDirectedSpecifics would instantiate OptimizedDirectedSpecifics.  But applications (of which SimpleIdentityDirectedGraphTest is a representative) would be free to override this to instantiate the old DirectedSpecifics (with their own refinements, as in that test).  Does that work?

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...

On Wed, Apr 6, 2016 at 4:18 PM, Joris Kinable <[hidden email]> 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 <[hidden email]> 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 <[hidden email]> wrote:

Wouldn't this be solved by checking for references as well in addition to the equals()?

----- Reply message -----
From: "Aidan Delaney" <[hidden email]>
To: "[hidden email]" <[hidden email]>
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

------------------------------------------------------------------------------

_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users



------------------------------------------------------------------------------

_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users




------------------------------------------------------------------------------

_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: some potential speed improvements for containsEdge(u, v) and getEdge(u, v)

H.N. de Ridder
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 <[hidden email]> 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 <[hidden email]> 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 <[hidden email]>
> >> wrote:
> >>
> >>>
> >>> Wouldn't this be solved by checking for references as well in addition
> >>> to the equals()?
> >>>
> >>> ----- Reply message -----
> >>> From: "Aidan Delaney" <[hidden email]>
> >>> To: "[hidden email]" <
> >>> [hidden email]>
> >>> 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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: some potential speed improvements for containsEdge(u, v) and getEdge(u, v)

Joris Kinable
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 <[hidden email]> 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 <[hidden email]> 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 <[hidden email]> 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 <[hidden email]>
> >> wrote:
> >>
> >>>
> >>> Wouldn't this be solved by checking for references as well in addition
> >>> to the equals()?
> >>>
> >>> ----- Reply message -----
> >>> From: "Aidan Delaney" <[hidden email]>
> >>> To: "[hidden email]" <
> >>> [hidden email]>
> >>> 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! <a href="http://pubads.g.doubleclick.net/ gampad/clk?id=1444514301&amp;iu=/ca-pub-7940484522588532" rel="noreferrer" target="_blank">http://pubads.g.doubleclick.net/
gampad/clk?id=1444514301&iu=/ca-pub-7940484522588532
_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users


------------------------------------------------------------------------------
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: some potential speed improvements for containsEdge(u, v) and getEdge(u, v)

John Sichi
Administrator
In reply to this post by H.N. de Ridder
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 <[hidden email]> 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 <[hidden email]> 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 <[hidden email]> 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 <[hidden email]>
> >> wrote:
> >>
> >>>
> >>> Wouldn't this be solved by checking for references as well in addition
> >>> to the equals()?
> >>>
> >>> ----- Reply message -----
> >>> From: "Aidan Delaney" <[hidden email]>
> >>> To: "[hidden email]" <
> >>> [hidden email]>
> >>> 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! <a href="http://pubads.g.doubleclick.net/ gampad/clk?id=1444514301&amp;iu=/ca-pub-7940484522588532" rel="noreferrer" target="_blank">http://pubads.g.doubleclick.net/
gampad/clk?id=1444514301&iu=/ca-pub-7940484522588532
_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users


------------------------------------------------------------------------------
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: some potential speed improvements for containsEdge(u, v) and getEdge(u, v)

H.N. de Ridder
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 <[hidden email]>
> 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 <[hidden email]> 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 <[hidden email]> 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 <
> > [hidden email]>
> > > >> wrote:
> > > >>
> > > >>>
> > > >>> Wouldn't this be solved by checking for references as well in
> > addition
> > > >>> to the equals()?
> > > >>>
> > > >>> ----- Reply message -----
> > > >>> From: "Aidan Delaney" <[hidden email]>
> > > >>> To: "[hidden email]" <
> > > >>> [hidden email]>
> > > >>> 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
> > [hidden email]
> > 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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: some potential speed improvements for containsEdge(u, v) and getEdge(u, v)

Joris Kinable
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 <[hidden email]> 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 <[hidden email]>
> 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 <[hidden email]> 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 <[hidden email]> 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 <
> > [hidden email]>
> > > >> wrote:
> > > >>
> > > >>>
> > > >>> Wouldn't this be solved by checking for references as well in
> > addition
> > > >>> to the equals()?
> > > >>>
> > > >>> ----- Reply message -----
> > > >>> From: "Aidan Delaney" <[hidden email]>
> > > >>> To: "[hidden email]" <
> > > >>> [hidden email]>
> > > >>> 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
> > [hidden email]
> > 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! <a href="http://pubads.g.doubleclick.net/ gampad/clk?id=1444514301&amp;iu=/ca-pub-7940484522588532" rel="noreferrer" target="_blank">http://pubads.g.doubleclick.net/
gampad/clk?id=1444514301&iu=/ca-pub-7940484522588532
_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users


------------------------------------------------------------------------------
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: some potential speed improvements for containsEdge(u, v) and getEdge(u, v)

H.N. de Ridder

I agree with Joris. Implement the current setup and solve a performance collapse if and when it causes issues.

--
Information System on Graph Classes and their Inclusions (ISGCI)
http://www.graphclasses.org

On 10 April 2016 9:07:25 pm Joris Kinable <[hidden email]> wrote:

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 <[hidden email]> 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 <[hidden email]>
> 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 <[hidden email]> 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 <[hidden email]> 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 <
> > [hidden email]>
> > > >> wrote:
> > > >>
> > > >>>
> > > >>> Wouldn't this be solved by checking for references as well in
> > addition
> > > >>> to the equals()?
> > > >>>
> > > >>> ----- Reply message -----
> > > >>> From: "Aidan Delaney" <[hidden email]>
> > > >>> To: "[hidden email]" <
> > > >>> [hidden email]>
> > > >>> 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
> > [hidden email]
> > 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! <a href="http://pubads.g.doubleclick.net/ gampad/clk?id=1444514301&amp;iu=/ca-pub-7940484522588532" rel="noreferrer" target="_blank">http://pubads.g.doubleclick.net/
gampad/clk?id=1444514301&iu=/ca-pub-7940484522588532
_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users


------------------------------------------------------------------------------
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!
https://ad.doubleclick.net/ddm/clk/302982198;130105516;z
_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Loading...