I tried this on the Unix build with the following outcome. (Samples work on CPython 3.7.1).

>>> class MyList(list):
...     def double(self):
...         self += self
...         return self
... 
>>> l = MyList()
>>> l.extend([1,2,3])
>>> l.double()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in double
MemoryError: memory allocation failed, allocating 2097152 bytes
>>> 

It isn't clear (to me) how to create a constructor:

class MyList(list):
    def __init__(self, *args):
        list.__init__(self, *args)
    def double(self):
        self += self
        return self

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in __init__
AttributeError: type object 'list' has no attribute '__init__'
>>> 

This implements simple linear native inheritance (ie doesn't support multiple inherintance at the C level). It does this by just looping over the search through locals_dict, searching all parents of the type.

Yeah, I definitely thought that it needs to be implement finally too, but just thinking about it for a bit, I'm sure how it's implemented in this patch (the most obvious way, which first comes to mind) is the best way.

1. We can't introduce a concept of parent type without thinking of checking for a test of being an instance of a particular type. Do we want to change anything in that regard? Unlikely, how it's done now is clearly well optimized for speed.
2. But then "parent type" is not really a real base type, it's just a container to allow to factor out common set of methods among types. And expensive one in the term of overhead added, as size of type structure is noticeable.
3. But then the problem statement is not "add base types on C side", but "allow chunked tree-like structure to define locals_dict methods of a native type".

That leads to the obvious idea that this extension should be implemented on the level of local_dict's. E.g., the last entry would have a special value for qstr, and a pointer to parent locals_dict.

Anything like that should still be done while thinking for possible optimizations to native types locals_dict entries:

1. Using binary search on method entries.
2. Reorganizing how its stored, e.g. array of qstr's followed by array of pointers.

Actually, looking into that stuff, one immediately starts to wonder why method array is wrapped in into an instance of dict type. Well, by now I don't remember if something directly benefits from that. But it has quite noticeable overhead again, while the purpose of method array should be just to look them up efficiently, with lowest memory overhead.

All these points combined lead to the following idea:

1. .locals_dict for native types should just point to method array.
2. First entry in that array should consist of { num_entries, parent_ptr }.

E.g.

STATIC const mp_rom_map_elem_t deque_locals_dict_table[] = {
    { MP_ROM_QSTR(MP_QSTR_append), MP_ROM_PTR(&deque_append_obj) },
    { MP_ROM_QSTR(MP_QSTR_clear), MP_ROM_PTR(&deque_clear_obj) },
    { MP_ROM_QSTR(MP_QSTR_popleft), MP_ROM_PTR(&deque_popleft_obj) },
};

becomes

STATIC const mp_rom_map_elem_t deque_locals_dict_table[] = {
    { MP_LOCALS_DICT_NUM(3), NULL },
    { MP_ROM_QSTR(MP_QSTR_append), MP_ROM_PTR(&deque_append_obj) },
    { MP_ROM_QSTR(MP_QSTR_clear), MP_ROM_PTR(&deque_clear_obj) },
    { MP_ROM_QSTR(MP_QSTR_popleft), MP_ROM_PTR(&deque_popleft_obj) },
};

I guess I misunderstood the purpose of this PR, and it's not intended to expose native class inheritance at the Python level.

I guess I misunderstood the purpose of this PR, and it's not intended to expose native class inheritance at the Python level.

That is correct, it is purely at the C level.

Anything like that should still be done while thinking for possible optimizations to native types locals_dict entries:

See tools/cc1 which turns native locals_dict into a proper hash table.

Actually, looking into that stuff, one immediately starts to wonder why method array is wrapped in into an instance of dict type. Well, by now I don't remember if something directly benefits from that.

To define a user type, you pass in a dict, and that gets stored directly into locals_dict. That's why it's a full dict object.

2. But then "parent type" is not really a real base type, it's just a container to allow to factor out common set of methods among types.

It could eventually be made into a first-class parent type, with instance checks etc (if it could be done efficiently).

3. But then the problem statement is not "add base types on C side", but "allow chunked tree-like structure to define _locals_dict methods_ of a native type"

But this doesn't attempt to solve the issue of native inheritance, and if that is to be solved eventually it can be built upon the technique proposed here, rather than having a separate technique for extending locals_dict.

Anything like that should still be done while thinking for possible optimizations to native types locals_dict entries:

This might be a nice idea, but would require checking each use of locals_dict to see if it was from a native type, or a user defined type (or convert the dict of a user defined type upon construction).

To define a user type, you pass in a dict, and that gets stored directly into locals_dict. That's why it's a full dict object.

I doubt that what happens there (re: "That's why"). That might be like you describe 5 years ago, but it's no longer the case. uPy type system allows to completely override attribute/method lookup in an object using ->attr vmethod. And that's what instance type enjoy - they implement completely different, and self-contained, algorithm. (The reason of that is of course that such a lookup for instance types is much more complex (==slower) than for native types).

So "why it's a full dict object" is because native and instance type shared the algorithm initially. But now they don't, and as a whole algorithms are self-contained, they each may be optimized to use the data structures the most efficient for each of them.

This might be a nice idea, but would require checking each use of locals_dict to see if it was from a native type, or a user defined type (or convert the dict of a user defined type upon construction).

The operation on the (very) critical path is lookup, and that's why I propose to optimize it. And it's already a virtual method of a type. What other operations we have which operate on method tables? dir() and help()? Sure, those would need to be updated, but they aren't on critical path.

But this doesn't attempt to solve the issue of native inheritance,

But is there an issue there to solve?

and if that is to be solved eventually it can be built upon the technique proposed here, rather than having a separate technique for extending locals_dict.

Sure, both methods could be blended to work nice together, a particular usecase may choose to use either a special "parent" marker in locals_dict, or full-fledged parent type in ->parent. But again, nothing so far calls for the need of such explicit parents.

@dpgeorge -
It would be very helpful if even only the basic parent-looping code is integrated:

Any chance of getting this merged?

It would be very helpful if even only the basic parent-looping code is integrated:

That's now possible since #6253.

Otherwise, I'll close this PR. It's really just a code size optimisation and things have moved on a lot since it was made (how types are defined) so it'd need to be redone anyway.