cpp: Slow reference resolution

[marxin]

Describe the bug

We've just ported GCC documentation to Sphinx (thank you guys for the tool). However, I noticed one manual build 45s (90s with cProfile enabled) on my machine and I create an upstream bug:
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=107613

We've got about 1000 cpp:function definitions. Is it an expected build time or a bug in Sphinx?
@jakobandersen

How to Reproduce

$ git clone --depth 1 git://gcc.gnu.org/git/gcc.git
$ cd gcc
$ time sphinx-build -b texinfo -d doctrees /home/marxin/Programming/gcc/gcc/doc/gccint output -j auto
Running Sphinx v5.3.0
making output directory... done
loading intersphinx inventory from https://gcc.gnu.org/onlinedocs/install/objects.inv...
loading intersphinx inventory from https://gcc.gnu.org/onlinedocs/gcc/objects.inv...
...
real	0m44.343s
user	1m4.218s
sys	0m1.587s

cProfile report:

         191708444 function calls (167501490 primitive calls) in 79.083 seconds

   Ordered by: cumulative time
   List reduced from 5238 to 60 due to restriction <60>

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
    576/1    0.001    0.000   79.084   79.084 {built-in method builtins.exec}
        1    0.000    0.000   79.084   79.084 /usr/bin/sphinx-build:1(<module>)
        1    0.000    0.000   78.869   78.869 /usr/lib/python3.10/site-packages/sphinx/cmd/build.py:306(main)
        1    0.000    0.000   78.869   78.869 /usr/lib/python3.10/site-packages/sphinx/cmd/build.py:268(build_main)
        1    0.000    0.000   78.315   78.315 /usr/lib/python3.10/site-packages/sphinx/application.py:339(build)
        1    0.000    0.000   78.315   78.315 /usr/lib/python3.10/site-packages/sphinx/builders/__init__.py:301(build_update)
        1    0.000    0.000   78.315   78.315 /usr/lib/python3.10/site-packages/sphinx/builders/__init__.py:314(build)
        1    0.000    0.000   78.301   78.301 /usr/lib/python3.10/site-packages/sphinx/builders/texinfo.py:84(write)
        1    0.000    0.000   75.902   75.902 /usr/lib/python3.10/site-packages/sphinx/builders/texinfo.py:125(assemble_doctree)
        1    0.000    0.000   69.619   69.619 /usr/lib/python3.10/site-packages/sphinx/environment/__init__.py:623(resolve_references)
        1    0.000    0.000   69.619   69.619 /usr/lib/python3.10/site-packages/sphinx/environment/__init__.py:627(apply_post_transforms)
        1    0.000    0.000   69.471   69.471 /usr/lib/python3.10/site-packages/sphinx/transforms/__init__.py:75(apply_transforms)
        1    0.000    0.000   69.471   69.471 /usr/lib/python3.10/site-packages/docutils/transforms/__init__.py:159(apply_transforms)
       17    0.000    0.000   67.401    3.965 /usr/lib/python3.10/site-packages/sphinx/transforms/post_transforms/__init__.py:33(apply)
        1    0.032    0.032   64.703   64.703 /usr/lib/python3.10/site-packages/sphinx/transforms/post_transforms/__init__.py:61(run)
     3440    1.049    0.000   55.776    0.016 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:4978(direct_lookup)
  1570402    0.604    0.000   54.727    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:4050(get_newest_id)
1570405/1570402    1.934    0.000   54.122    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:4005(get_id)
4385815/1570402    7.573    0.000   51.863    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:3098(get_id)
     1726    0.004    0.000   36.151    0.021 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:8090(resolve_xref)
     1726    0.016    0.000   36.147    0.021 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:7941(_resolve_xref_inner)
1601351/1570402    0.706    0.000   33.534    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:2491(get_param_id)
1601351/1570402    1.342    0.000   32.841    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:2083(get_param_id)
23047127/8166556    3.956    0.000   32.087    0.000 {method 'join' of 'str' objects}
4380613/4318715    1.340    0.000   30.346    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:2092(<genexpr>)
2782980/2752025    1.384    0.000   29.023    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:2003(get_id)
     2140    0.016    0.000   28.288    0.013 /usr/lib/python3.10/site-packages/sphinx/events.py:80(emit)
     2132    0.005    0.000   28.145    0.013 /usr/lib/python3.10/site-packages/sphinx/application.py:460(emit_firstresult)
     2132    0.004    0.000   28.140    0.013 /usr/lib/python3.10/site-packages/sphinx/events.py:109(emit_firstresult)
     2022    0.002    0.000   27.966    0.014 /usr/lib/python3.10/site-packages/sphinx/ext/intersphinx.py:460(missing_reference)
     2022    0.004    0.000   27.965    0.014 /usr/lib/python3.10/site-packages/sphinx/ext/intersphinx.py:431(resolve_reference_detect_inventory)
     2022    0.005    0.000   27.959    0.014 /usr/lib/python3.10/site-packages/sphinx/ext/intersphinx.py:418(resolve_reference_any_inventory)
     2027    0.015    0.000   27.951    0.014 /usr/lib/python3.10/site-packages/sphinx/ext/intersphinx.py:358(_resolve_reference)
     2027    0.012    0.000   27.925    0.014 /usr/lib/python3.10/site-packages/sphinx/ext/intersphinx.py:322(_resolve_reference_in_domain)
     1714    0.007    0.000   27.864    0.016 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:8123(get_full_qualified_name)
2780211/2749262    1.353    0.000   27.654    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:3234(get_id)
3851151/3816887    6.537    0.000   16.358    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:721(get_id)
2815413/2780211    3.378    0.000   15.058    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:2322(get_id)
2280749/2246485    1.041    0.000   10.905    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:1963(get_id)
     1726    0.013    0.000    8.032    0.005 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:5019(find_name)
     3452    1.281    0.000    7.947    0.002 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:4412(_find_named_symbols)
3851151/3816887    1.615    0.000    7.679    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:679(get_id)
2846362/2815413    2.784    0.000    6.799    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:2500(get_type_id)
    294/1    0.005    0.000    6.135    6.135 /usr/lib/python3.10/site-packages/sphinx/util/nodes.py:408(inline_all_toctrees)
  3851151    4.020    0.000    5.731    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:601(get_id)
  1572120    3.127    0.000    5.537    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:4382(get_full_nested_name)
   197118    0.071    0.000    4.911    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:2642(get_param_id)
  3640319    1.312    0.000    4.304    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:4440(matches)
2936/2861    0.002    0.000    3.886    0.001 {built-in method builtins.next}
     1722    0.004    0.000    3.885    0.002 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:4396(_find_first_named_symbol)
      606    0.001    0.000    3.191    0.005 /usr/lib/python3.10/site-packages/sphinx/util/docutils.py:595(findall)
      606    0.006    0.000    3.190    0.005 /usr/lib/python3.10/site-packages/docutils/nodes.py:258(traverse)
41939/40789    0.010    0.000    3.187    0.000 /usr/lib/python3.10/site-packages/docutils/nodes.py:302(_traverse)
4302961/39641    2.762    0.000    3.176    0.000 /usr/lib/python3.10/site-packages/docutils/nodes.py:243(_fast_traverse)
      298    3.001    0.010    3.063    0.010 {built-in method _pickle.load}
  3648373    2.363    0.000    3.003    0.000 /usr/lib/python3.10/site-packages/sphinx/util/cfamily.py:84(__eq__)
100187/2578    0.095    0.000    2.993    0.001 /usr/lib/python3.10/site-packages/docutils/nodes.py:1091(deepcopy)
100187/2578    0.070    0.000    2.932    0.001 /usr/lib/python3.10/site-packages/docutils/nodes.py:1093(<listcomp>)
  2846362    1.485    0.000    2.919    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:2497(get_ptr_suffix_id)
      294    0.002    0.000    2.741    0.009 /usr/lib/python3.10/site-packages/sphinx/environment/__init__.py:567(get_doctree)


========================================================
Thu Nov 10 14:55:03 2022    data.txt

         191708444 function calls (167501490 primitive calls) in 79.083 seconds

   Ordered by: internal time
   List reduced from 5238 to 60 due to restriction <60>

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
4385815/1570402    7.573    0.000   51.863    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:3098(get_id)
3851151/3816887    6.537    0.000   16.358    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:721(get_id)
  3851151    4.020    0.000    5.731    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:601(get_id)
23047127/8166556    3.956    0.000   32.087    0.000 {method 'join' of 'str' objects}
2815413/2780211    3.378    0.000   15.058    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:2322(get_id)
  1572120    3.127    0.000    5.537    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:4382(get_full_nested_name)
      298    3.001    0.010    3.063    0.010 {built-in method _pickle.load}
2846362/2815413    2.784    0.000    6.799    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:2500(get_type_id)
4302961/39641    2.762    0.000    3.176    0.000 /usr/lib/python3.10/site-packages/docutils/nodes.py:243(_fast_traverse)
 29973176    2.375    0.000    2.375    0.000 {method 'append' of 'list' objects}
  3648373    2.363    0.000    3.003    0.000 /usr/lib/python3.10/site-packages/sphinx/util/cfamily.py:84(__eq__)
25705524/25702429    2.049    0.000    2.050    0.000 {built-in method builtins.len}
   128714    2.040    0.000    2.168    0.000 /usr/lib/python3.10/site-packages/docutils/nodes.py:544(__init__)
 11344151    1.979    0.000    1.979    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:598(is_anon)
1570405/1570402    1.934    0.000   54.122    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:4005(get_id)
3851151/3816887    1.615    0.000    7.679    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:679(get_id)
  2846362    1.485    0.000    2.919    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:2497(get_ptr_suffix_id)
2782980/2752025    1.384    0.000   29.023    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:2003(get_id)
2780211/2749262    1.353    0.000   27.654    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:3234(get_id)
1601351/1570402    1.342    0.000   32.841    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:2083(get_param_id)
4380613/4318715    1.340    0.000   30.346    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:2092(<genexpr>)
  3640319    1.312    0.000    4.304    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:4440(matches)
     3452    1.281    0.000    7.947    0.002 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:4412(_find_named_symbols)
  3648372    1.185    0.000    1.771    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:4353(children_recurse_anon)
  1575602    1.163    0.000    1.527    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:700(__init__)
     3440    1.049    0.000   55.776    0.016 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:4978(direct_lookup)
2280749/2246485    1.041    0.000   10.905    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:1963(get_id)
  1601351    0.852    0.000    0.997    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:2068(get_modifiers_id)
  1601351    0.792    0.000    1.789    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:2485(get_modifiers_id)
 319619/2    0.784    0.000    2.585    1.293 /usr/lib/python3.10/site-packages/docutils/nodes.py:200(walkabout)
1601351/1570402    0.706    0.000   33.534    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:2491(get_param_id)
  6241842    0.640    0.000    0.641    0.000 {built-in method builtins.isinstance}
656215/647110    0.612    0.000    2.233    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:2663(get_type_id)
  1570402    0.604    0.000   54.727    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:4050(get_newest_id)
  3643767    0.592    0.000    2.359    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:4462(candidates)
1573078/452308    0.583    0.000    0.603    0.000 /usr/lib/python3.10/site-packages/docutils/nodes.py:84(document)
   114955    0.572    0.000    2.667    0.000 /usr/lib/python3.10/site-packages/docutils/nodes.py:1156(__init__)
4311464/4311463    0.482    0.000    0.483    0.000 {built-in method builtins.getattr}
  1575605    0.408    0.000    0.408    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:671(__init__)
  2849881    0.362    0.000    0.364    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:2498(<genexpr>)
  3776630    0.315    0.000    0.315    0.000 {method 'items' of 'dict' objects}
   534664    0.278    0.000    0.363    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:1886(get_id)
   617623    0.238    0.000    0.318    0.000 /usr/lib/python3.10/site-packages/docutils/nodes.py:650(__getitem__)
   182714    0.205    0.000    0.274    0.000 /usr/lib/python3.10/site-packages/docutils/nodes.py:2023(dispatch_departure)
   179719    0.201    0.000    0.274    0.000 /usr/lib/python3.10/site-packages/docutils/nodes.py:2010(dispatch_visit)
   278821    0.175    0.000    0.796    0.000 /usr/lib/python3.10/site-packages/docutils/nodes.py:145(setup_child)
    99893    0.170    0.000    2.303    0.000 /usr/lib/python3.10/site-packages/sphinx/util/nodes.py:630(_new_copy)
95956/574    0.146    0.000    0.349    0.001 /usr/lib/python3.10/site-packages/sphinx/writers/texinfo.py:82(find_subsections)
   995142    0.129    0.000    0.129    0.000 /usr/lib/python3.10/site-packages/docutils/utils/__init__.py:203(debug)
  1573130    0.126    0.000    0.126    0.000 {method 'reverse' of 'list' objects}
95960/297    0.123    0.000    0.163    0.001 /usr/lib/python3.10/site-packages/sphinx/writers/texinfo.py:494(footnotes_under)
   133371    0.115    0.000    0.204    0.000 /usr/lib/python3.10/site-packages/sphinx/util/docutils.py:570(dispatch_departure)
139900/139888    0.114    0.000    0.971    0.000 /usr/lib/python3.10/site-packages/sphinx/util/docutils.py:553(dispatch_visit)
   256205    0.110    0.000    0.535    0.000 /usr/lib/python3.10/site-packages/docutils/nodes.py:752(extend)
   221575    0.107    0.000    0.386    0.000 /usr/lib/python3.10/site-packages/docutils/nodes.py:748(append)
    56924    0.107    0.000    0.261    0.000 /usr/lib/python3.10/site-packages/docutils/nodes.py:778(update_basic_atts)
    84240    0.104    0.000    0.163    0.000 /usr/lib/python3.10/site-packages/docutils/nodes.py:385(unescape)
100187/2578    0.095    0.000    2.993    0.001 /usr/lib/python3.10/site-packages/docutils/nodes.py:1091(deepcopy)
   227696    0.076    0.000    0.123    0.000 /usr/lib/python3.10/site-packages/docutils/nodes.py:788(append_attr_list)
    76182    0.076    0.000    0.152    0.000 /usr/lib/python3.10/site-packages/docutils/nodes.py:451(copy)


========================================================
Thu Nov 10 14:55:03 2022    data.txt

         191708444 function calls (167501490 primitive calls) in 79.083 seconds

   Ordered by: call count
   List reduced from 5238 to 60 due to restriction <60>

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
 29973176    2.375    0.000    2.375    0.000 {method 'append' of 'list' objects}
25705524/25702429    2.049    0.000    2.050    0.000 {built-in method builtins.len}
23047127/8166556    3.956    0.000   32.087    0.000 {method 'join' of 'str' objects}
 11344151    1.979    0.000    1.979    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:598(is_anon)
  6241842    0.640    0.000    0.641    0.000 {built-in method builtins.isinstance}
4385815/1570402    7.573    0.000   51.863    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:3098(get_id)
4380613/4318715    1.340    0.000   30.346    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:2092(<genexpr>)
4311464/4311463    0.482    0.000    0.483    0.000 {built-in method builtins.getattr}
4302961/39641    2.762    0.000    3.176    0.000 /usr/lib/python3.10/site-packages/docutils/nodes.py:243(_fast_traverse)
  3851151    4.020    0.000    5.731    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:601(get_id)
3851151/3816887    1.615    0.000    7.679    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:679(get_id)
3851151/3816887    6.537    0.000   16.358    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:721(get_id)
  3776630    0.315    0.000    0.315    0.000 {method 'items' of 'dict' objects}
  3648373    2.363    0.000    3.003    0.000 /usr/lib/python3.10/site-packages/sphinx/util/cfamily.py:84(__eq__)
  3648372    1.185    0.000    1.771    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:4353(children_recurse_anon)
  3643767    0.592    0.000    2.359    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:4462(candidates)
  3640319    1.312    0.000    4.304    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:4440(matches)
  2849881    0.362    0.000    0.364    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:2498(<genexpr>)
  2846362    1.485    0.000    2.919    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:2497(get_ptr_suffix_id)
2846362/2815413    2.784    0.000    6.799    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:2500(get_type_id)
2815413/2780211    3.378    0.000   15.058    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:2322(get_id)
2782980/2752025    1.384    0.000   29.023    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:2003(get_id)
2780211/2749262    1.353    0.000   27.654    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:3234(get_id)
2280749/2246485    1.041    0.000   10.905    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:1963(get_id)
  1601351    0.852    0.000    0.997    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:2068(get_modifiers_id)
1601351/1570402    1.342    0.000   32.841    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:2083(get_param_id)
  1601351    0.792    0.000    1.789    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:2485(get_modifiers_id)
1601351/1570402    0.706    0.000   33.534    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:2491(get_param_id)
  1575605    0.408    0.000    0.408    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:671(__init__)
  1575602    1.163    0.000    1.527    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:700(__init__)
  1573130    0.126    0.000    0.126    0.000 {method 'reverse' of 'list' objects}
1573078/452308    0.583    0.000    0.603    0.000 /usr/lib/python3.10/site-packages/docutils/nodes.py:84(document)
  1572120    3.127    0.000    5.537    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:4382(get_full_nested_name)
1570405/1570402    1.934    0.000   54.122    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:4005(get_id)
  1570402    0.604    0.000   54.727    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:4050(get_newest_id)
   995142    0.129    0.000    0.129    0.000 /usr/lib/python3.10/site-packages/docutils/utils/__init__.py:203(debug)
656215/647110    0.612    0.000    2.233    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:2663(get_type_id)
   617623    0.238    0.000    0.318    0.000 /usr/lib/python3.10/site-packages/docutils/nodes.py:650(__getitem__)
   573962    0.054    0.000    0.054    0.000 {method 'lower' of 'str' objects}
   534664    0.278    0.000    0.363    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:1886(get_id)
   500756    0.051    0.000    0.051    0.000 {method 'replace' of 'str' objects}
 319619/2    0.784    0.000    2.585    1.293 /usr/lib/python3.10/site-packages/docutils/nodes.py:200(walkabout)
   293227    0.024    0.000    0.024    0.000 /usr/lib/python3.10/site-packages/docutils/nodes.py:98(__bool__)
   283793    0.044    0.000    0.044    0.000 {method 'split' of 'str' objects}
   280333    0.036    0.000    0.036    0.000 {method 'get' of 'dict' objects}
   278821    0.175    0.000    0.796    0.000 /usr/lib/python3.10/site-packages/docutils/nodes.py:145(setup_child)
   256205    0.110    0.000    0.535    0.000 /usr/lib/python3.10/site-packages/docutils/nodes.py:752(extend)
   227696    0.076    0.000    0.123    0.000 /usr/lib/python3.10/site-packages/docutils/nodes.py:788(append_attr_list)
   221575    0.107    0.000    0.386    0.000 /usr/lib/python3.10/site-packages/docutils/nodes.py:748(append)
   197118    0.072    0.000    0.290    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:2639(get_modifiers_id)
   197118    0.071    0.000    4.911    0.000 /usr/lib/python3.10/site-packages/sphinx/domains/cpp.py:2642(get_param_id)
   182714    0.205    0.000    0.274    0.000 /usr/lib/python3.10/site-packages/docutils/nodes.py:2023(dispatch_departure)
   179719    0.201    0.000    0.274    0.000 /usr/lib/python3.10/site-packages/docutils/nodes.py:2010(dispatch_visit)
   179425    0.015    0.000    0.015    0.000 /usr/lib/python3.10/site-packages/sphinx/transforms/post_transforms/code.py:50(unknown_departure)
   178873    0.016    0.000    0.016    0.000 /usr/lib/python3.10/site-packages/sphinx/transforms/post_transforms/code.py:47(unknown_visit)
   168152    0.049    0.000    0.049    0.000 {built-in method __new__ of type object at 0x7ffff7f410a0}
   166620    0.062    0.000    0.127    0.000 /usr/lib/python3.10/site-packages/docutils/nodes.py:413(__new__)
139900/139888    0.114    0.000    0.971    0.000 /usr/lib/python3.10/site-packages/sphinx/util/docutils.py:553(dispatch_visit)
   136520    0.019    0.000    0.019    0.000 /usr/lib/python3.10/site-packages/docutils/nodes.py:1129(is_not_known_attribute)
   133371    0.115    0.000    0.204    0.000 /usr/lib/python3.10/site-packages/sphinx/util/docutils.py:570(dispatch_departure)

Environment Information

5.3

Sphinx extensions

No response

Additional context

No response

[marxin]

Ok, so I think the root cause is that we've got ~1000 functions in top-level namespace and there's O(N^2) complexity when it comes to cpp.py::get_full_qualified_name.

If I select one symbol (_CPPv422gimple_try_set_cleanupP4gtry10gimple_seq), I see the following traceback 3x1000:

  File "/usr/bin/sphinx-build", line 8, in <module>
    sys.exit(main())
  File "/usr/lib/python3.10/site-packages/sphinx/cmd/build.py", line 315, in main
    return build_main(argv)
  File "/usr/lib/python3.10/site-packages/sphinx/cmd/build.py", line 281, in build_main
    app.build(args.force_all, args.filenames)
  File "/usr/lib/python3.10/site-packages/sphinx/application.py", line 347, in build
    self.builder.build_update()
  File "/usr/lib/python3.10/site-packages/sphinx/builders/__init__.py", line 307, in build_update
    self.build(['__all__'], to_build)
  File "/usr/lib/python3.10/site-packages/sphinx/builders/__init__.py", line 376, in build
    self.write(docnames, list(updated_docnames), method)
  File "/usr/lib/python3.10/site-packages/sphinx/builders/texinfo.py", line 100, in write
    doctree = self.assemble_doctree(docname, toctree_only, appendices=appendices)
  File "/usr/lib/python3.10/site-packages/sphinx/builders/texinfo.py", line 150, in assemble_doctree
    self.env.resolve_references(largetree, indexfile, self)
  File "/usr/lib/python3.10/site-packages/sphinx/environment/__init__.py", line 625, in resolve_references
    self.apply_post_transforms(doctree, fromdocname)
  File "/usr/lib/python3.10/site-packages/sphinx/environment/__init__.py", line 637, in apply_post_transforms
    transformer.apply_transforms()
  File "/usr/lib/python3.10/site-packages/sphinx/transforms/__init__.py", line 80, in apply_transforms
    super().apply_transforms()
  File "/usr/lib/python3.10/site-packages/docutils/transforms/__init__.py", line 171, in apply_transforms
    transform.apply(**kwargs)
  File "/usr/lib/python3.10/site-packages/sphinx/transforms/post_transforms/__init__.py", line 35, in apply
    self.run(**kwargs)
  File "/usr/lib/python3.10/site-packages/sphinx/transforms/post_transforms/__init__.py", line 84, in run
    newnode = domain.resolve_xref(self.env, refdoc, self.app.builder,
  File "/usr/lib/python3.10/site-packages/sphinx/domains/cpp.py", line 8102, in resolve_xref
    return self._resolve_xref_inner(env, fromdocname, builder, typ,
  File "/usr/lib/python3.10/site-packages/sphinx/domains/cpp.py", line 7981, in _resolve_xref_inner
    parentSymbol: Symbol = rootSymbol.direct_lookup(parentKey)
  File "/usr/lib/python3.10/site-packages/sphinx/domains/cpp.py", line 4999, in direct_lookup
    if cand.declaration.get_newest_id() == id_:
  File "/usr/lib/python3.10/site-packages/sphinx/domains/cpp.py", line 4060, in get_newest_id
    return self.get_id(_max_id, True)
  File "/usr/lib/python3.10/site-packages/sphinx/domains/cpp.py", line 4056, in get_id
    traceback.print_stack()

So it's about calling 3000x (3x likely due naming versions?) get_id for a function declaration which tends to be slow (as shown in the original cProfile).

[marxin]

The same problem happens also when intersphinx is disabled.

[marxin]

@jbms

[jakobandersen]

I have an old branch with optimizations that I have rebased: https://github.com/jakobandersen/sphinx/tree/c_cpp_optimizations
It should address a lot of the lookup speed. Can you test how it works with the GCC docs?

[marxin]

Oh, great! I can confirm it helps, now I get to real 0m26.377s !!! (with -j auto).

[jbms]

Memoizing calls to get_newest_id definitely helps. However, it would also be useful to avoid the O(N^2) lookup behavior as well, by using a dict so that it is possible to look up names in O(1) time rather than having to do a linear search over every symbol in the namespace.

[jakobandersen]

@jbms, indeed, and if I remember correctly I also have some code fragments in that direction. Though, it's a bit involved to change, e.g., due to lookup in anon entities. I'll try do dig in my branches and see what comes up.

[marxin]

@jakobandersen: Can you please make a pull request that includes the patches addressing this issue?

[AA-Turner]

Note such a PR wouldn't be included in Sphinx 6.0.0, it would go into 6.1 or later.

A

[marxin]

@jakobandersen: Can you please make a submit request with the changes now?