Re: [Ksummit-discuss] [TECH TOPIC] What kernel documentation could be

[Mauro Carvalho Chehab <mchehab@kernel.org>]

Em Fri, 24 Jun 2022 16:57:56 -0600
Jonathan Corbet <corbet@lwn.net> escreveu:

> Mauro Carvalho Chehab <mchehab@kernel.org> writes:
> 
> > Em Thu, 23 Jun 2022 07:40:45 -0600
> > Jonathan Corbet <corbet@lwn.net> escreveu:  
> >> I've actually, in a spare moment or two, been doing some profiling of
> >> the kernel docs build and trying to track down the sources of the
> >> slowness.  I am thinking that nearly 700 *million* calls to the iterator
> >> for the C-domain symbol list might have something to do with it...  
> >
> > Wow, that's a lot!  
> 
> Just for the curious ...
> 
> The Sphinx C domain code makes this elaborate tree data structure out of
> all the identifier names it has picked up - including the names of
> function parameters when they are provided in prototypes for some
> reason.  This is the structure that is consulted whenever we want to
> resolve a cross-reference, which is fairly often with automarkup
> enabled.
> 
> How does it work?  The algorithm is, as far as I can tell:
> 
>  - Serialize the whole tree in a sort of breadth-first traversal
> 
>  - Make a linear pass through the *entire* list, comparing the
>    identifier name with each entry and accumulating a list of all the
>    matches found.
> 
>  - Return the first match and throw away the rest.
> 
> The result is O(n^2) behavior and, in the kernel docs build, n gets to
> be fairly large.
> 
> I went in with a crowbar and sledgehammer and replaced some of the list
> searches with a dict lookup, resulting in about a 20% speedup in the
> full htmldocs build with Sphinx 5.0.2. 

Great to have a 20% speedup here! Yet, I would expect an even better
performance improvement by replacing 700 million calls from linear search
to dict, as it would change from O(n^2) to O(1) at the average case [1],
but the speedup gain actually depends on the actual number of symbols we
have defined.

[1] According with:
	https://wiki.python.org/moin/TimeComplexity#dict
    Worse case is O(n) - when collisions are common which is unlikely.

> A couple of automarkup
> optimizations result in about a 27% speedup overall.  And I didn't break
> any cross-references.

Great!

> I think it's possible to do better, but this is a start.  I'll post the
> automarkup changes as soon as I can, but I need to verify them across
> the whole range of Sphinx versions. 

> For the Sphinx stuff, I'll need to
> turn my hatchetwork into something presentable and figure out how to
> contribute it upstream, but it seems worth the effort.

Indeed.

Regards,
Mauro