len() on mutables vs. immutables

[Daniel Urban]

On Thu, Oct 18, 2012 at 8:42 PM, Demian Brecht <demianbrecht at gmail.com> wrote:
>> str, bytes, bytearrays, arrays, sets, frozensets, dicts, dictviews, and
>> ranges should all return len in O(1) time. That includes the possibility
>> of a subtraction as indicated above.
>
> Awesome. Pretty much what I figured. Of course, I'll have to dig around the
> source just to confirm this with my own eyes (more just curiosity than
> anything), so if you know whereabouts to look, it would be most helpful :)

The source is usually in Objects/*object.c (e.g., the source for list
is in Objects/listobject.c, dict is in dictobject.c and so on). The
implementation of __len__ is usually in a method called
whatever_length (e.g., dict.__len__ is called dict_length). To be
sure, you can check the PyTypeObject declaration for the type.
Probably the tp_as_sequence or tp_as_mapping field contains the
pointer to __len__ (sq_length or mp_length respectively). (You can
also search for "lenfunc", which is the type of such functions.)