> How do you stop walking your graph if it spans the whole graph of Python objects?

We can stop at specific types of objects (for example types and modules).

> If sys.getsizeof() is only useful for people who know *already* how an
object is implemented internally, then it's actually useless, because
those people can just as well do the calculation themselves.

It's why sys.getsizeof() is a low-level tool. We need high-level tool in the stdlib. Even imperfect recursive counting will be better than confusing for novices sys.getsizeof().

> (By the way, OrderedDict.__sizeof__ already breaks the rule you are trying to impose)

Yes, I know, and I think it is wrong.

Here is improved version of gettotalsizeof():

def gettotalsizeof(*args, exclude_types=(type, type(sys))):
    seen = {}
    stack = []
    for obj in args:
        if id(obj) not in seen:
            seen[id(obj)] = obj
            stack.append(obj)
    sum = 0
    while stack:
        obj = stack.pop()
        sum += sys.getsizeof(obj)
        for obj in gc.get_referents(obj):
            if id(obj) not in seen and not isinstance(obj, exclude_types):
                seen[id(obj)] = obj
                stack.append(obj)
    return sum


>>> gettotalsizeof(sys)
206575
>>> gettotalsizeof(gc)
2341
>>> gettotalsizeof(sys.getsizeof)
60
>>> gettotalsizeof(gettotalsizeof)
60854
>>> class C: pass
... 
>>> gettotalsizeof(C)
805
>>> gettotalsizeof(C())
28