リストの後に連続したメモリが不十分な場合、CPythonはリストの拡張をどのように処理しますか？

Question

Python listを拡張すると（例えば、mylist.extend()またはmylist += anotherlist）、リストのIDは変更されません。

私は（少なくともCPythonでは）リストがメモリ内で連続していることを理解しています（そしてIDはリストの先頭のアドレスになります）。リストの後のメモリがすでに断片化されていて、リスト拡張子を割り当てることができない場合（たとえその領域に不連続であっても十分な空き領域があっても）どうすればよいでしょうか？割り当てが失敗しますか？どのように緩和されていますか？

Answer 1

CPythonでは、これはリストとタプルの割り当て方法の違いです。リストの場合、オブジェクトには、〜というポインタの内容が割り当てられています。適切なリストオブジェクトは小さく、移動する必要はありません。 からへのベクトルのアドレスは何度でも変更できます。

タプルオブジェクトの場合、ほとんどの場合、タプルオブジェクトのメモリは実際にはタプルオブジェクトに直接割り当てられます。しかし、タプルのサイズを変更することはできませんので、その場合はシナリオが発生しません。

Answer 2

これは実装固有のものですが、CPythonについて質問していると思います。

あなたが言うように、リストは連続したメモリですが、これはPyObjectsのCポインタ（*PyObject）です。オブジェクトそのものは、自分のクラスの整数やオブジェクトであれ、動的メモリのどこかに（おそらく）連続したメモリには割り当てられません。

リストが最初に割り当てられると、（概念的に）右側に「スラック」エントリを残して、必要以上のメモリが得られます。 list.append()は次のスラックエントリだけを使用します。もちろん、最終的に彼らはすべて満員です。

この時点で、メモリの再割り当てが実行されます。 C言語では、これはrealloc()への呼び出しですが、実際にはこの実装ではCランタイムヒープを使用しないことがあります。基本的には、動的メモリから大きなメモリ割り当てが得られ、リストのすべての要素が新しいリストにコピーされます。ただし、オブジェクト自体ではなく、Pythonオブジェクトへのポインタをコピーしています。

これを実行する際にオーバーヘッドがありますが、スラックエントリを使用するとオーバーヘッドが減ります。これにより、list.append()がリストの「左」にエントリを追加するより効率的であることがわかります。

新しいリストのメモリが不足しているため割り当てに失敗した場合、メモリ不足のエラーが発生します。しかし、メモリが不足していると、新しいPythonオブジェクトがこれを引き起こす可能性があります。

ヒープフラグメンテーションが問題になることがありますが、これを管理するにはPythonが最善です。これが、Pythonが独自のヒープ管理を行う理由の1つです。最近のWindowsの実装では、C RTLの代わりに低レベルの仮想メモリAPIが使用されるため、Pythonは独自のメモリ管理を実行できます。