Performance degradation from 1.11 to 2.0

[qtov]

Current Behavior

I have noticed a pretty big performance degradation between 1.11 and 2.0.
Had to upgrade recently and could not use 1.11 anymore.
In one of my benchmarking tools, I could see that 2.0 is ~10x slower than 1.11 when trying to do bipartite matching.

Expected Behavior

Not as much of a slowdown.

Steps to Reproduce

Made a benchmark script.

import json
import cProfile
import networkx as nx
from networkx.readwrite import json_graph

with open('graph_adj.txt', 'r') as fl:
    graph = json_graph.adjacency_graph(json.load(fl))

def hopcroft_nx():
    for _ in range(20):
        matches = {}
        for component in nx.connected_components(graph):
            subgraph = graph.subgraph(component)
            spec_resource_match = nx.bipartite.hopcroft_karp_matching(subgraph)
            matches.update(spec_resource_match)
        # I do nothing with matches, just simulate my current workflow.

# add second argument to .run if you want to save it and view it in SnakeViz
cProfile.run('hopcroft_nx()')

With an 11MB 'graph_adj' file.
graph_adj.txt

Now, the values are as follows:
For networkx 1.11, this is the cProfile output:

129524 function calls (125524 primitive calls) in 1.085 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    1.085    1.085 <string>:1(<module>)
       20    0.001    0.000    0.284    0.014 basic.py:142(sets)
     4020    0.001    0.000    0.001    0.000 basic.py:171(<genexpr>)
     4020    0.001    0.000    0.001    0.000 basic.py:172(<genexpr>)
       20    0.266    0.013    0.281    0.014 basic.py:24(color)
     8020    0.008    0.000    0.075    0.000 connected.py:205(_plain_bfs)
       40    0.002    0.000    0.078    0.002 connected.py:26(connected_components)
       20    0.000    0.000    0.001    0.000 decorator.py:199(fix)
       20    0.000    0.000    0.001    0.000 decorator.py:229(fun)
       20    0.000    0.000    0.000    0.000 decorators.py:50(_not_implemented_for)
     8000    0.004    0.000    0.004    0.000 graph.py:1063(neighbors_iter)
     8020    0.005    0.000    0.006    0.000 graph.py:1354(degree_iter)
       40    0.000    0.000    0.000    0.000 graph.py:1450(is_multigraph)
       60    0.000    0.000    0.000    0.000 graph.py:1454(is_directed)
       20    0.470    0.024    0.474    0.024 graph.py:1548(subgraph)
       20    0.000    0.000    0.000    0.000 graph.py:1858(nbunch_iter)
     8020    0.002    0.000    0.002    0.000 graph.py:1904(bunch_iter)
       20    0.000    0.000    0.000    0.000 graph.py:258(__init__)
       40    0.000    0.000    0.000    0.000 graph.py:330(__iter__)
       20    0.000    0.000    0.000    0.000 graph.py:345(__contains__)
    16020    0.016    0.000    0.016    0.000 graph.py:379(__getitem__)
       40    0.000    0.000    0.000    0.000 inspect.py:2527(name)
      100    0.000    0.000    0.000    0.000 inspect.py:2539(kind)
       20    0.000    0.000    0.000    0.000 inspect.py:2619(__init__)
       20    0.000    0.000    0.000    0.000 inspect.py:2627(args)
       20    0.000    0.000    0.000    0.000 inspect.py:2650(kwargs)
       20    0.000    0.000    0.000    0.000 inspect.py:2680(apply_defaults)
       80    0.000    0.000    0.000    0.000 inspect.py:2845(parameters)
       20    0.000    0.000    0.001    0.000 inspect.py:2889(_bind)
       20    0.000    0.000    0.001    0.000 inspect.py:3020(bind)
       20    0.000    0.000    0.008    0.000 isolate.py:43(isolates)
       20    0.001    0.000    0.007    0.000 isolate.py:77(<listcomp>)
8000/4000    0.072    0.000    0.074    0.000 matching.py:114(depth_first_search)
       20    0.000    0.000    0.000    0.000 matching.py:128(<dictcomp>)
       20    0.000    0.000    0.000    0.000 matching.py:129(<dictcomp>)
       20    0.001    0.000    0.001    0.000 matching.py:143(<dictcomp>)
       20    0.001    0.000    0.001    0.000 matching.py:144(<dictcomp>)
       20    0.003    0.000    0.519    0.026 matching.py:55(hopcroft_karp_matching)
       40    0.144    0.004    0.156    0.004 matching.py:97(breadth_first_search)
        1    0.013    0.013    1.085    1.085 test.py:43(hopcroft_nx)
        1    0.000    0.000    1.085    1.085 {built-in method builtins.exec}
     8080    0.001    0.000    0.001    0.000 {built-in method builtins.iter}
     8020    0.001    0.000    0.001    0.000 {built-in method builtins.len}
       80    0.000    0.000    0.000    0.000 {built-in method builtins.next}
       20    0.000    0.000    0.000    0.000 {built-in method fromkeys}
     8000    0.001    0.000    0.001    0.000 {method 'add' of 'set' objects}
     4020    0.000    0.000    0.000    0.000 {method 'append' of 'collections.deque' objects}
     8020    0.001    0.000    0.001    0.000 {method 'append' of 'list' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
     8100    0.001    0.000    0.001    0.000 {method 'items' of 'dict' objects}
       60    0.000    0.000    0.000    0.000 {method 'items' of 'mappingproxy' objects}
     8000    0.001    0.000    0.001    0.000 {method 'pop' of 'list' objects}
     4020    0.001    0.000    0.001    0.000 {method 'popleft' of 'collections.deque' objects}
       60    0.000    0.000    0.000    0.000 {method 'update' of 'dict' objects}
     8020    0.064    0.000    0.064    0.000 {method 'update' of 'set' objects}
       20    0.000    0.000    0.000    0.000 {method 'values' of 'mappingproxy' objects}

And for anything over 2.0 it's:

24523484 function calls (24519384 primitive calls) in 5.618 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    5.618    5.618 <string>:1(<module>)
     8000    0.004    0.000    0.012    0.000 _collections_abc.py:664(__contains__)
       20    0.000    0.000    4.379    0.219 basic.py:142(sets)
       20    0.001    0.000    0.001    0.000 basic.py:205(<setcomp>)
       20    0.000    0.000    0.000    0.000 basic.py:206(<setcomp>)
       20    0.296    0.015    2.926    0.146 basic.py:24(color)
       20    0.002    0.000    1.450    0.073 connected.py:156(is_connected)
    16040    0.016    0.000    1.500    0.000 connected.py:234(_plain_bfs)
       40    0.002    0.000    0.062    0.002 connected.py:26(connected_components)
    32040    0.007    0.000    0.007    0.000 coreviews.py:284(__init__)
     8060    0.004    0.000    1.326    0.000 coreviews.py:288(__len__)
  1628060    0.361    0.000    1.199    0.000 coreviews.py:289(<genexpr>)
    24060    0.008    0.000    0.008    0.000 coreviews.py:291(__iter__)
  4434080    1.017    0.000    3.414    0.000 coreviews.py:292(<genexpr>)
     8000    0.005    0.000    0.008    0.000 coreviews.py:294(__getitem__)
       20    0.000    0.000    0.000    0.000 coreviews.py:312(__init__)
       20    0.000    0.000    0.000    0.000 coreviews.py:320(__iter__)
     8020    0.003    0.000    0.005    0.000 coreviews.py:321(<genexpr>)
    32020    0.033    0.000    0.045    0.000 coreviews.py:323(__getitem__)
  6006000    2.402    0.000    3.233    0.000 coreviews.py:325(new_node_ok)
    32080    0.004    0.000    0.004    0.000 coreviews.py:45(__init__)
       20    0.000    0.000    0.004    0.000 coreviews.py:48(__len__)
    24000    0.005    0.000    0.014    0.000 coreviews.py:51(__iter__)
    24020    0.015    0.000    0.043    0.000 coreviews.py:81(__getitem__)
       40    0.000    0.000    0.002    0.000 decorator.py:199(fix)
       40    0.000    0.000    1.453    0.036 decorator.py:229(fun)
       40    0.000    0.000    1.450    0.036 decorators.py:52(_not_implemented_for)
  6006000    0.275    0.000    0.275    0.000 filters.py:24(no_filter)
       20    0.001    0.000    0.002    0.000 filters.py:55(__init__)
  6070040    0.565    0.000    0.565    0.000 filters.py:58(__call__)
     8000    0.004    0.000    0.020    0.000 graph.py:1086(neighbors)
       20    0.000    0.000    0.000    0.000 graph.py:1254(degree)
       80    0.000    0.000    0.000    0.000 graph.py:1315(is_multigraph)
      120    0.000    0.000    0.000    0.000 graph.py:1319(is_directed)
       20    0.000    0.000    0.002    0.000 graph.py:1533(subgraph)
       20    0.000    0.000    0.000    0.000 graph.py:1712(nbunch_iter)
     8020    0.001    0.000    0.001    0.000 graph.py:1757(bunch_iter)
     8060    0.003    0.000    0.005    0.000 graph.py:316(adj)
       80    0.000    0.000    0.000    0.000 graph.py:365(__iter__)
       20    0.000    0.000    0.000    0.000 graph.py:383(__contains__)
       40    0.000    0.000    0.007    0.000 graph.py:397(__len__)
     8020    0.004    0.000    0.026    0.000 graph.py:414(__getitem__)
       20    0.000    0.000    0.000    0.000 graphviews.py:68(__init__)
       80    0.000    0.000    0.000    0.000 inspect.py:2527(name)
      200    0.000    0.000    0.000    0.000 inspect.py:2539(kind)
       40    0.000    0.000    0.000    0.000 inspect.py:2619(__init__)
       40    0.000    0.000    0.000    0.000 inspect.py:2627(args)
       40    0.000    0.000    0.000    0.000 inspect.py:2650(kwargs)
       40    0.000    0.000    0.000    0.000 inspect.py:2680(apply_defaults)
      160    0.000    0.000    0.000    0.000 inspect.py:2845(parameters)
       40    0.001    0.000    0.001    0.000 inspect.py:2889(_bind)
       40    0.000    0.000    0.001    0.000 inspect.py:3020(bind)
       20    0.000    0.000    0.000    0.000 isolate.py:52(isolates)
       20    0.002    0.000    1.354    0.068 isolate.py:94(<genexpr>)
       40    0.140    0.004    0.763    0.019 matching.py:116(breadth_first_search)
8000/4000    0.086    0.000    0.406    0.000 matching.py:133(depth_first_search)
       20    0.000    0.000    0.000    0.000 matching.py:147(<dictcomp>)
       20    0.000    0.000    0.000    0.000 matching.py:148(<dictcomp>)
       20    0.001    0.000    0.001    0.000 matching.py:162(<dictcomp>)
       20    0.000    0.000    0.000    0.000 matching.py:163(<dictcomp>)
       20    0.003    0.000    5.552    0.278 matching.py:56(hopcroft_karp_matching)
       20    0.000    0.000    0.000    0.000 misc.py:198(is_iterator)
       20    0.000    0.000    0.000    0.000 misc.py:207(arbitrary_element)
       20    0.000    0.000    0.000    0.000 reportviews.py:333(__init__)
       20    0.000    0.000    0.000    0.000 reportviews.py:341(__call__)
     8020    0.009    0.000    1.352    0.000 reportviews.py:440(__iter__)
        1    0.001    0.001    5.618    5.618 test.py:43(hopcroft_nx)
        1    0.000    0.000    5.618    5.618 {built-in method builtins.exec}
      100    0.000    0.000    0.000    0.000 {built-in method builtins.hasattr}
32200/32160    0.007    0.000    0.014    0.000 {built-in method builtins.iter}
8140/8080    0.003    0.000    1.330    0.000 {built-in method builtins.len}
      180    0.000    0.000    0.000    0.000 {built-in method builtins.next}
     8060    0.123    0.000    1.322    0.000 {built-in method builtins.sum}
       20    0.000    0.000    1.354    0.068 {built-in method fromkeys}
    16000    0.003    0.000    0.003    0.000 {method 'add' of 'set' objects}
     4020    0.000    0.000    0.000    0.000 {method 'append' of 'collections.deque' objects}
     8060    0.001    0.000    0.001    0.000 {method 'append' of 'list' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
     8000    0.002    0.000    0.002    0.000 {method 'format' of 'str' objects}
      120    0.000    0.000    0.000    0.000 {method 'items' of 'dict' objects}
      120    0.000    0.000    0.000    0.000 {method 'items' of 'mappingproxy' objects}
     8000    0.001    0.000    0.001    0.000 {method 'pop' of 'list' objects}
     4020    0.000    0.000    0.000    0.000 {method 'popleft' of 'collections.deque' objects}
       40    0.000    0.000    0.000    0.000 {method 'update' of 'dict' objects}
    16020    0.194    0.000    1.456    0.000 {method 'update' of 'set' objects}
       40    0.000    0.000    0.000    0.000 {method 'values' of 'mappingproxy' objects}

Environment

WSL2 venv

Python version: 3.10 (for Networkx >= 2.6), 3.8 (for Networkx <= 2.4)
NetworkX version: 1.11 -> 3.2.1

Additional context

While I know that networkx is not made for speed, I'm just bringing to attention if this degradation in performance is actually intended. I also visually see in SnakeViz when putting this cProfile output that there's more changes like "checking for connected graphs", etc.

Unfortunately also trying to convert this graph to scipy using to_scipy_sparse_array also takes almost the same as the matching, hence making the whole conversion useless most of the times.

[dschult]

Thanks for this report! This is a blast from the past.

I suspect it is the change from subgraph constructing a graph to the "new" view based system. In v2.0+, subgraphs are views rather than newly constructed graphs. This saves memory, but is slower if you examine the edges of the subgraph more than once. In those cases, it is faster to make a copy of the subgraph.

Can you try changing the subgraph creation to
subgraph = graph.subgraph(component).copy()
and report back whether this fixes the slowdown?
Thanks!

[qtov]

The matching speed actually got back to 1.11's performance, though the whole algo is slower using .copy().
Apparently "add_edges_from" is packing a punch.

If the graph is being generated dynamically in the same algorithm (based on certain factors from db), then separated into subgraphs and matched, is there a way to reach 1.11's performance as a whole?

Would you happen to know other workarounds? 😅

Also, thanks for the response!

24322819 function calls (24318650 primitive calls) in 8.983 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
       20    0.000    0.000    0.000    0.000 <class 'networkx.utils.decorators.argmap'> compilation 4:1(argmap_connected_components_1)
        1    0.000    0.000    0.000    0.000 <class 'networkx.utils.decorators.argmap'> compilation 8:1(<module>)
       20    0.000    0.000    0.005    0.000 <class 'networkx.utils.decorators.argmap'> compilation 8:1(argmap_is_connected_5)
        1    0.000    0.000    0.000    0.000 <string>:1(<lambda>)
        1    0.000    0.000    8.983    8.983 <string>:1(<module>)
        1    0.000    0.000    0.000    0.000 _collections_abc.py:283(__subclasshook__)
        1    0.000    0.000    0.000    0.000 _collections_abc.py:362(__subclasshook__)
        2    0.000    0.000    0.000    0.000 _collections_abc.py:78(_check_methods)
     8040    0.004    0.000    0.005    0.000 _collections_abc.py:840(items)
     8040    0.002    0.000    0.002    0.000 _collections_abc.py:862(__init__)
  1624040    0.641    0.000    3.740    0.000 _collections_abc.py:909(__iter__)
       20    0.000    0.000    0.000    0.000 abc.py:117(__instancecheck__)
      2/1    0.000    0.000    0.000    0.000 abc.py:121(__subclasscheck__)
        1    0.000    0.000    0.000    0.000 backends.py:375(__signature__)
        2    0.000    0.000    0.000    0.000 backends.py:381(<genexpr>)
   120/40    0.001    0.000    0.341    0.009 backends.py:409(__call__)
       20    0.000    0.000    0.199    0.010 basic.py:157(sets)
       20    0.181    0.009    0.192    0.010 basic.py:20(color)
       20    0.001    0.000    0.001    0.000 basic.py:219(<setcomp>)
       20    0.000    0.000    0.000    0.000 basic.py:220(<setcomp>)
       20    0.000    0.000    0.005    0.000 connected.py:105(is_connected)
     8020    0.001    0.000    0.001    0.000 connected.py:148(<genexpr>)
       40    0.001    0.000    0.004    0.000 connected.py:15(connected_components)
       40    0.005    0.000    0.007    0.000 connected.py:192(_plain_bfs)
     8020    0.007    0.000    0.007    0.000 coreviews.py:267(__init__)
     8020    0.023    0.000    0.023    0.000 coreviews.py:274(__iter__)
  1616020    0.475    0.000    1.504    0.000 coreviews.py:281(<genexpr>)
  1608000    0.587    0.000    1.544    0.000 coreviews.py:283(__getitem__)
       20    0.000    0.000    0.000    0.000 coreviews.py:296(__init__)
       20    0.000    0.000    0.000    0.000 coreviews.py:304(__iter__)
     8020    0.005    0.000    0.007    0.000 coreviews.py:311(<genexpr>)
     8000    0.014    0.000    0.022    0.000 coreviews.py:313(__getitem__)
  3200000    1.417    0.000    1.983    0.000 coreviews.py:316(new_node_ok)
     8040    0.001    0.000    0.001    0.000 coreviews.py:43(__init__)
       20    0.000    0.000    0.000    0.000 coreviews.py:46(__len__)
     8000    0.001    0.000    0.002    0.000 coreviews.py:49(__iter__)
     8020    0.003    0.000    0.004    0.000 coreviews.py:80(__getitem__)
        2    0.000    0.000    0.000    0.000 decorators.py:1039(<genexpr>)
        1    0.000    0.000    0.000    0.000 decorators.py:1045(signature)
      8/5    0.000    0.000    0.000    0.000 decorators.py:1145(_flatten)
        5    0.000    0.000    0.000    0.000 decorators.py:1175(_indent)
       20    0.000    0.000    0.001    0.000 decorators.py:1242(inner_f)
        1    0.000    0.000    0.000    0.000 decorators.py:701(_lazy_compile)
        1    0.000    0.000    0.001    0.001 decorators.py:769(func)
        4    0.000    0.000    0.000    0.000 decorators.py:812(_count)
        3    0.000    0.000    0.000    0.000 decorators.py:835(_name)
        1    0.000    0.000    0.000    0.000 decorators.py:855(compile)
       40    0.000    0.000    0.000    0.000 decorators.py:86(_not_implemented_for)
        1    0.000    0.000    0.000    0.000 decorators.py:903(assemble)
        1    0.000    0.000    0.000    0.000 decorators.py:994(get_name)
        3    0.000    0.000    0.000    0.000 enum.py:359(__call__)
        3    0.000    0.000    0.000    0.000 enum.py:678(__new__)
  3200000    0.215    0.000    0.215    0.000 filters.py:20(no_filter)
       20    0.001    0.000    0.002    0.000 filters.py:51(__init__)
  3232000    0.356    0.000    0.356    0.000 filters.py:54(__call__)
       20    0.000    0.000    0.000    0.000 function.py:156(freeze)
       40    0.000    0.000    0.001    0.000 functools.py:961(__get__)
     8000    0.003    0.000    0.003    0.000 graph.py:1315(neighbors)
       20    0.000    0.000    0.000    0.000 graph.py:1481(degree)
       20    0.000    0.000    0.000    0.000 graph.py:1553(is_multigraph)
      100    0.000    0.000    0.000    0.000 graph.py:1557(is_directed)
       20    0.000    0.000    8.634    0.432 graph.py:1561(copy)
     8020    0.003    0.000    0.015    0.000 graph.py:1642(<genexpr>)
  1600020    0.624    0.000    4.866    0.000 graph.py:1643(<genexpr>)
       20    0.000    0.000    0.003    0.000 graph.py:1763(subgraph)
       20    0.000    0.000    0.000    0.000 graph.py:1964(nbunch_iter)
     8020    0.001    0.000    0.001    0.000 graph.py:2010(bunch_iter)
       40    0.000    0.000    0.000    0.000 graph.py:332(__init__)
       60    0.000    0.000    0.000    0.000 graph.py:37(__set__)
       20    0.000    0.000    0.000    0.000 graph.py:374(adj)
       60    0.000    0.000    0.000    0.000 graph.py:435(__iter__)
       20    0.000    0.000    0.000    0.000 graph.py:453(__contains__)
       40    0.000    0.000    0.000    0.000 graph.py:467(__len__)
     8020    0.002    0.000    0.007    0.000 graph.py:489(__getitem__)
       20    0.015    0.001    0.032    0.002 graph.py:563(add_nodes_from)
       60    0.000    0.000    0.000    0.000 graph.py:59(__set__)
       20    2.985    0.149    8.601    0.430 graph.py:961(add_edges_from)
       20    0.000    0.000    0.000    0.000 graphviews.py:135(subgraph_view)
        1    0.000    0.000    0.000    0.000 inspect.py:2280(_signature_from_function)
      2/1    0.000    0.000    0.000    0.000 inspect.py:2375(_signature_from_callable)
        3    0.000    0.000    0.000    0.000 inspect.py:2637(__init__)
       12    0.000    0.000    0.000    0.000 inspect.py:2687(name)
        1    0.000    0.000    0.000    0.000 inspect.py:2691(default)
        7    0.000    0.000    0.000    0.000 inspect.py:2699(kind)
        2    0.000    0.000    0.000    0.000 inspect.py:277(isfunction)
        2    0.000    0.000    0.000    0.000 inspect.py:2920(__init__)
        2    0.000    0.000    0.000    0.000 inspect.py:2969(<genexpr>)
      2/1    0.000    0.000    0.000    0.000 inspect.py:2998(from_callable)
        3    0.000    0.000    0.000    0.000 inspect.py:3006(parameters)
        1    0.000    0.000    0.000    0.000 inspect.py:3014(replace)
      2/1    0.000    0.000    0.000    0.000 inspect.py:3252(signature)
        1    0.000    0.000    0.000    0.000 inspect.py:612(unwrap)
        1    0.000    0.000    0.000    0.000 inspect.py:632(_is_wrapper)
        1    0.000    0.000    0.000    0.000 inspect.py:66(get_annotations)
       20    0.000    0.000    0.001    0.000 isolate.py:42(isolates)
       20    0.001    0.000    0.005    0.000 isolate.py:85(<genexpr>)
       40    0.076    0.002    0.080    0.002 matching.py:126(breadth_first_search)
8000/4000    0.054    0.000    0.058    0.000 matching.py:143(depth_first_search)
       20    0.000    0.000    0.000    0.000 matching.py:157(<dictcomp>)
       20    0.000    0.000    0.000    0.000 matching.py:158(<dictcomp>)
       20    0.001    0.000    0.001    0.000 matching.py:172(<dictcomp>)
       20    0.000    0.000    0.000    0.000 matching.py:173(<dictcomp>)
       20    0.002    0.000    0.341    0.017 matching.py:57(hopcroft_karp_matching)
       20    0.000    0.000    0.000    0.000 misc.py:143(arbitrary_element)
        3    0.000    0.000    0.000    0.000 re.py:202(sub)
        3    0.000    0.000    0.000    0.000 re.py:288(_compile)
       20    0.000    0.000    0.000    0.000 reportviews.py:417(__init__)
       20    0.000    0.000    0.000    0.000 reportviews.py:424(__call__)
     8020    0.004    0.000    0.004    0.000 reportviews.py:527(__iter__)
        1    0.001    0.001    8.983    8.983 test.py:43(hopcroft_nx)
        1    0.000    0.000    0.000    0.000 {built-in method __new__ of type object at 0x55fc774399a0}
       20    0.000    0.000    0.000    0.000 {built-in method _abc._abc_instancecheck}
      2/1    0.000    0.000    0.000    0.000 {built-in method _abc._abc_subclasscheck}
        1    0.000    0.000    0.000    0.000 {built-in method builtins.any}
        3    0.000    0.000    0.000    0.000 {built-in method builtins.callable}
        1    0.000    0.000    0.000    0.000 {built-in method builtins.compile}
      2/1    0.000    0.000    8.983    8.983 {built-in method builtins.exec}
        3    0.000    0.000    0.000    0.000 {built-in method builtins.getattr}
       65    0.000    0.000    0.000    0.000 {built-in method builtins.hasattr}
        8    0.000    0.000    0.000    0.000 {built-in method builtins.id}
       45    0.000    0.000    0.000    0.000 {built-in method builtins.isinstance}
16080/16060    0.001    0.000    0.001    0.000 {built-in method builtins.iter}
1608360/1608300    0.104    0.000    0.104    0.000 {built-in method builtins.len}
       20    0.000    0.000    0.000    0.000 {built-in method builtins.next}
       20    0.001    0.000    0.001    0.000 {built-in method builtins.sum}
       20    0.000    0.000    0.005    0.000 {built-in method fromkeys}
        1    0.000    0.000    0.000    0.000 {built-in method sys.getrecursionlimit}
       40    0.000    0.000    0.000    0.000 {method '__exit__' of '_thread.RLock' objects}
    15963    0.001    0.000    0.001    0.000 {method 'add' of 'set' objects}
     4020    0.000    0.000    0.000    0.000 {method 'append' of 'collections.deque' objects}
    23948    0.001    0.000    0.001    0.000 {method 'append' of 'list' objects}
  1616000    0.509    0.000    0.509    0.000 {method 'copy' of 'dict' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        1    0.000    0.000    0.000    0.000 {method 'extend' of 'list' objects}
        1    0.000    0.000    0.000    0.000 {method 'format' of 'str' objects}
  1600082    0.193    0.000    0.193    0.000 {method 'get' of 'dict' objects}
        3    0.000    0.000    0.000    0.000 {method 'isidentifier' of 'str' objects}
      120    0.000    0.000    0.000    0.000 {method 'items' of 'dict' objects}
        3    0.000    0.000    0.000    0.000 {method 'join' of 'str' objects}
     8000    0.001    0.000    0.001    0.000 {method 'pop' of 'list' objects}
     4020    0.000    0.000    0.000    0.000 {method 'popleft' of 'collections.deque' objects}
        3    0.000    0.000    0.000    0.000 {method 'sub' of 're.Pattern' objects}
  3216102    0.456    0.000    0.456    0.000 {method 'update' of 'dict' objects}
       20    0.000    0.000    0.000    0.000 {method 'update' of 'set' objects}
        1    0.000    0.000    0.000    0.000 {method 'values' of 'dict' objects}
        3    0.000    0.000    0.000    0.000 {method 'values' of 'mappingproxy' objects}

[rossbar]

Would you happen to know other workarounds? 😅

IMO it's difficult to get a real handle on performance differences when comparing across years worth of development. Python itself has changed quite a bit from 3.2 -> 3.10. You may see improvements if you're able to switch to 3.11. I don't think there's a whole lot that can be done to reproduce the same performance characteristics of nx v1.11 with the modern machinery. If graph copying is the bottleneck of your analysis pipeline, perhaps you can consider trying to vendor the subgraphing system (or performance-relevant bits) from nx v1.11.

[MridulS]

Maybe we should revisit the implementation and try using G._adj instead of G[...]?

networkx/networkx/algorithms/bipartite/matching.py

Line 145 in 2a03462

for u in G[v]: