修行の場

知人が言っていました。これは修行だと。

Pythonで書いたプログラムがどの程度Cより遅いか。実行速度の遅さのイメージをするための知識を浅く

Pythonで書いたプログラムがどの程度Cより遅いか。実行速度の遅さのイメージをするための知識を浅く

Pythonの実装は色々とありますが、ここではCPythonの情報を調べていきます。 良さそうなWebサイトは、

です。以下はメモです。

Pythonにおけるメモリ操作

オーダー表記から実行速度を想像する際に意識しなければならないのはどの操作について書かれているか、そしてその操作はどの程度高コストか。ということです。 ここでは、メモリ書き込み、読み込み、確保の速度を考えてみます。 Linux Kernel + CPythonを前提に書きます。

CPUのキャッシュ管理

あとで書く。

Linux Kernelのメモリ管理

やっているのはプロセスごとにvirtual addressによるメモリアクセスを提供することです。 内部的にはページングなどをして、ディスクにデータを追い出したりします。 ユーザ空間はsbrk, brk, mmapなどのシステムコールを通してメモリを確保します。

C言語のメモリ管理

Stackoverflowに軽い説明がありました。実装の一例として、取得サイズに応じてmmapとsbrkを使い分ける方法があるようです。プロセスごとのメモリのsbrkはプログラム領域のボーダーを下げるシステムコールでそれによりメモリ領域を増やせるようです。(おそらく、Kernel側で物理メモリへの変換をうまく活用して、データの実際の移動は起きないようになっている?) ちなみにスタックへの変数配置より、ヒープへの変数配置のほうがメモリ管理が複雑で、ヒープ領域のアクセスやメモリ確保のほうが圧倒的に遅いです。(C/C++でスタックに配置するようにコードを書くことが好まれるのはそれが理由?)

Pythonインタプリタのメモリ管理

Python Doc - Memory Managementによると、Python Memory Managerにより、Cのallocatorとは異なる形でメモリ管理をしているとのことです。また、それぞれのPythonオブジェクトに特化したメモリ管理もされていて、CのExntesionを作る場合でも、Python Memory managerを通してメモリ確保することで、GCやmemory compactionをうまく動作させられるようにすることが求められています。 GCやCompactionの挙動を少し理解して置かなければ予想外の挙動が出そうですが、C言語のプログラムと異なる追加のオーバーヘッドはおそらくPythonの基本オブジェクトの大きさ起因になりそうです。

例えば、Floatの構造はこんな感じで、Pythonインタプリタ内部で最適化などがなければ、非常に単純な計算で100倍近く計算時間がかかってもおかしくありません。 https://github.com/python/cpython/blob/f75d59e1a896115bd52f543a417c665d6edc331f/Include/floatobject.h#L14:L18

実際に計測してみたところ、 Pythonでは、

Python 3.6.8 :: Anaconda, Inc.

In [5]: %%time 
   ...:  
   ...: sum = 0 
   ...: i = 0 
   ...: while i < 100000000: 
   ...:     sum += i 
   ...:     i += 1 
   ...: print(sum)
   ...:  
   ...:                                                                                                                                                                                                     
4999999950000000
CPU times: user 11.1 s, sys: 495 µs, total: 11.1 s
Wall time: 11.1 s

C言語では以下の通りで大体50倍程度のようです。スタック領域の計算との比較なの

#include <stdio.h>で、Pythonインタプリタはかなり頑張っている気がします。

int main() {
  long sum = 0;

  for (int i = 0; i < 100000000; i++) {
    sum += i;
  }
  printf("%ld", sum);
}
4999999950000000
real    0m0.227s
user    0m0.227s
sys 0m0.000s

Pythonメモリ管理について少し真面目に

Docによると、小さいオブジェクトと大きいオブジェクトで割り当ての仕方を変えているようです。 大きいオブジェクトはCのmallocと同じ方法で割り当ているようです。 オブジェクトの破棄は基本的にreference countベースインタプリタやC拡張側で明示的にオブジェクトカウントのdecrementと破棄をすることで、不要なオブジェクト開放を実現している。 gcモジュールを使うことで、gcを使ったり、メモリリークのデバグをしたりできる。reference countでは自動的に破棄できないオブジェクトの破棄に使う。

GCの仕組みはArtem Golubinさんのページにまとまっている。 変数はさん世代に分類されて、それぞれの世代は(10, 10, 700)この新しい変数が増えるたびにガベージコレクションされる。タイミングを制御したい場合は、gc.disable()で無効化して, gc.collect()で任意のタイミングでcollectする。また、できる限りweekrefを使って、オブジェクトが破棄されるようにする。

まとめ

  • C言語Pythonの処理速度は桁一つ2つPythonのほうが遅くなりそう。
  • C言語でざっくりテストした結果だと、ヒープ確保:スタック・ヒープ書き込み:スタックヒープ読み込みが20: 2 : 1くらい。ヒープ確保の3分の1くらいはカーネル側の処理時間となっているようです。
  • Pythonでも工夫すれば、処理時間の想像はできそうです。基本変数はすべてヒープ領域に確保されますが、512バイト以下のオブジェクトはスタック領域に配置される変数に近く、ある程度大きいオブジェクトはコンストラクタを呼ぶたびにnewされる。すべての変数はshared_ptrのような削除のされ方をする。くらいに捉えておけばいいかもしれません。

次回はPythonの基本的なデータ型型について学んでいきます。~~~~