Explain graphlib's cycle-finding code

[tim-one]

Feature or enhancement

Proposal:

The topsort in graphlib has a novel iterative cycle-finding algorithm that's O() time- and space- optimal. It's not obvious, though, and it's overdue for me to explain it. So add appropriate comments.

Has this already been discussed elsewhere?

This is a minor feature, which does not need previous discussion elsewhere

Links to previous discussion of this feature:

No response

Linked PRs

• GH-143948: Explain graphlib's cycle-finding code #143950

[skirpichev]

@tim-one, per discussion in https://discuss.python.org/t/105683/, what do you think on updating user-visible docs too?

[tim-one]

It's not relevant for this PR: the cycle finder is an internal implementation detail, and users can't access it directly.

For general purposes, documenting this stuff is a mixed bag. Experts can make good use of it, but it's as likely as not to mislead most users. For example, O(log n) doesn't mean "faster than" O(n). Those talk about asymptotic behaviors as n grows without bound. Hidden constant factors may well make the O(n) method faster than the O(log n) method before n gets "sufficiently large". "How large?" is then subject to change by Python release, HW gimmicks,, compiler in use, and compiler optimization flags,.

Experts already understand that. Most users have to learn it the hard way 😉 .

That said, when "good asymptotics" is an important feature driving a thing, documenting it is important and of value to everyone. Like pushing/popping a deque is O(1). That's why deques exist.