Performance regression in v0.10.0

[davidmezzetti]

Hello - Hope all is well.

I was building a new graph using the latest version the library (v0.10.0) and noticed a performance regression. It appears to be traced to this change: #46 (review).

With large graphs (100K+ nodes 1M+ edges) having to copy the graph takes quiet a while. Additionally, we would have to store a duplicate copy of the graph if we wanted to keep a persistent copy of the GrandCypher instance, which doubles the memory requirements.

Do we perhaps want to require a MultiDiGraph as input? Or only do the conversion if it's not already a MultiDiGraph?

@j6k4m8 @jackboyla

[jackboyla]

Hey @davidmezzetti , thanks for pointing this out. I think a loud warning would suffice here, before converting to MultiDiGraph (if it’s not already a MultiDiGraph).

We might also benefit from adding performance tests to the library so we know when things like this happen again. What do you think @j6k4m8 ?

[davidmezzetti]

I agree that a warning could help.

In my case, queries went from 0.3s to 30-40s. I had thought it had to do with the graph being large but it was eventually traced to that line.

self._target_graph = target_graph
if not isinstance(self._target_graph, nx.MultiDiGraph):
  self._target_graph = nx.MultiDiGraph(target_graph)
  logger.warning("Converting graph to MultiDiGraph")

[davidmezzetti]

Looks great! Thank you!

I now notice in the sample code I put out there that the logging message probably should be before the conversion, otherwise one has to wait to find out why it took so long.

[j6k4m8]

Ah that's a good point @davidmezzetti — want to make that change or want me to?

[davidmezzetti]

Sorry, I lost track of this. I'll see if I can get around to making that change.

[j6k4m8]

I'm wondering if the solution to this problem is to just go in and add an abstraction layer on calls to multidigraph attributes so that we can run safely on non-multigraphs... Definitely bad to require an up-conversion that costs so much time...

[davidmezzetti]

An abstraction layer seems like a good idea. That graph conversion isn't much faster for in-memory graphs.

[j6k4m8]

closed in #55!! :D

[davidmezzetti]

Thanks. I tested this on a large graph I have and it's much closer to the performance in v0.9. There is still a slight performance difference but it's much less noticeable.

[jackboyla]

Glad to hear it’s faster, but I’m curious what exactly is making it slower than 0.9.0.
It may be the logic that filters for multiedges.

[davidmezzetti]

If I can pinpoint anything concrete, I'll be sure to share. Right now it was just anecdotal.