【Python】ListとDequeのパフォーマンスの違い〜CPyhtonの実装を読んで〜

先日以下のブログを読みました。

dev.classmethod.jp

PythonのListとDequeのパフォーマンスを比較しています。しかし、「なぜパフォーマンスに違いが生まれるのか。」記されていないため、この記事ではCPythonの実装を読みながら、違いが生まれる理由を探ってみたいと思います。
※本記事で扱うCPythonのコードは最新版ではありません。 ListはCommit ID3c87a667bb367ace1de6bd1577fdb4f66947da52、DequeはCommit IDd4edfc9abffca965e76ebc5957a92031a4d6c4d4です。

1. List Objectについて

初めに、簡単にデータ構造を整理しておきます。
Listは以下のようになっております。

typedef struct {
    PyObject_VAR_HEAD

    PyObject **ob_item;

    Py_ssize_t allocated;
} PyListObject;

#ifndef PyList_MAXFREELIST
#define PyList_MAXFREELIST 80
#endif
static PyListObject *free_list[PyList_MAXFREELIST];
static int numfree = 0;

ob_itemがvectorへのポインタを指すことで、可変長データ構造を実現しています。 (Listをnew()する場合、free_listからPyListObjectを一つ取り出し、メモリ確保しています。

op->ob_item = (PyObject **) PyMem_Calloc(size, sizeof(PyObject *));

)

https://github.com/python/cpython/blob/3c87a667bb367ace1de6bd1577fdb4f66947da52/Include/listobject.h https://github.com/python/cpython/blob/3c87a667bb367ace1de6bd1577fdb4f66947da52/Objects/listobject.c

2. Deque Objectについて

Dequeは、双方向リンクリストと配列のハイブリッドで実現されています。

#define BLOCKLEN 64
#define CENTER ((BLOCKLEN - 1) / 2)

typedef struct BLOCK {
    struct BLOCK *leftlink;
    PyObject *data[BLOCKLEN];
    struct BLOCK *rightlink;
} block;

typedef struct {
    PyObject_VAR_HEAD
    block *leftblock;
    block *rightblock;
    Py_ssize_t leftindex;       /* 0 <= leftindex < BLOCKLEN */
    Py_ssize_t rightindex;      /* 0 <= rightindex < BLOCKLEN */
    size_t state;               /* incremented whenever the indices move */
    Py_ssize_t maxlen;          /* maxlen is -1 for unbounded deques */
    PyObject *weakreflist;
} dequeobject;

static PyTypeObject deque_type;

#define MAXFREEBLOCKS 16
static Py_ssize_t numfreeblocks = 0;
static block *freeblocks[MAXFREEBLOCKS];

図で整理すると以下の通りです。(一部簡略) f:id:blue_9:20200105195853p:plain

https://github.com/python/cpython/blob/d4edfc9abffca965e76ebc5957a92031a4d6c4d4/Modules/_collectionsmodule.h

https://github.com/python/cpython/blob/d4edfc9abffca965e76ebc5957a92031a4d6c4d4/Modules/_collectionsmodule.c

3. List vs Deque（先頭要素)

参考ブログでは以下のコードで、処理時間を比較しています。

List

list_array = list(range(100000))
for i in range(1000):
    list_array.pop(0)

処理時間は以下の通りです。
1回目　elapsed_time:0.05488991737365723[sec]
2回目　elapsed_time:0.04288434982299805[sec]
3回目　elapsed_time:0.054895877838134766[sec]

Deque

deque_array = deque(range(100000))
for i in range(1000):
    deque_array.popleft()

処理時間は以下の通りです。
1回目　elapsed_time:0.008365631103515625[sec]
2回目　elapsed_time:0.007332801818847656[sec]
3回目　elapsed_time:0.008947134017944336[sec]

3.1. List

List.pop()の実装部はここです。
エラーチェック後、実質的にpop処理をしているのは以下の部分です。

status = list_ass_slice(self, index, index+1, (PyObject *)NULL);

pop(0)の場合、以下のようになります。

ex: a = [1,2,3,4,5,6,7,8,9,10]

list_ass_slice(self, 0, 1, (PyObject *)NULL);

#define b ((PyListObject *)v)
    if (v == NULL)
        n = 0;

    norig = ihigh - ilow; // 1
    d = n - norig;        // -1
    item = a->ob_item;
    s = norig * sizeof(PyObject *); // sizeof(PyObject *)

    if (s) {
        memcpy(recycle, &item[ilow], s);
    }

    if (d < 0) { /* Delete -d items */
        Py_ssize_t tail;
        tail = (Py_SIZE(a) - ihigh) * sizeof(PyObject *); // 9 * sizeof(PyObject *)
        memmove(&item[ihigh+d], &item[ihigh], tail); // a[1:10] を a[0:9]に移動
        if (list_resize(a, Py_SIZE(a) + d) < 0) { // Py_SIZE(a)の変更
        }
        item = a->ob_item;
    }
    for (k = norig - 1; k >= 0; --k)
        Py_XDECREF(recycle[k]); // ref--
    result = 0;

決めては以下の処理。

memmove(&item[ihigh+d], &item[ihigh], tail); // a[1:10] を a[0:9]に移動

計算量がO(n)であることが分かります。

3.2. Deque

deque.leftpop()の実装部はここです。サイズチェック後、実質的にpop処理をしているのは以下の部分です。

item = deque->leftblock->data[deque->leftindex];
deque->leftindex++;
Py_SIZE(deque)--;

計算量がO(1)であることが分かります。

3.3. まとめ(先頭要素)

先頭要素への処理の計算量は以下の通りです。

処理	計算量
List.pop(0)	O(1)
Deque.leftpop()	O(n)

4. List vs deque（中間の要素）

参考ブログでは以下のコードで、処理時間を比較しています。

List

list_array = list(range(10000))
for i in range(1000000):
    list_array.remove(20)
    list_array.insert(20, 20)

処理時間は以下の通りです。
1回目　elapsed_time:25.979241132736206[sec]
2回目　elapsed_time:26.479660749435425[sec]
3回目　elapsed_time:26.32246232032776[sec]

Deque

deque_array = deque(range(10000))
for i in range(1000000):
    deque_array.remove(20)
    deque_array.insert(20, 20)

処理時間は以下の通りです。
1回目　elapsed_time:21.0693142414093[sec]
2回目　elapsed_time:21.471088647842407[sec]
3回目　elapsed_time:21.121334075927734[sec]

4.1. List

Listのremoveの実装はここです。
中身の肝は以下。

list_ass_slice(self, i, i+1, PyObject *)NULL)

popと同様に計算量がO(n)であることが分かります。

Listのinsertの実装はここです。
中身の肝は以下。

ins1(self, index, object)

insert(20,20)の場合、以下のようになります。

ex: a = [0,...,19,21...,100000]

ins1(self, 20, 20)

Py_ssize_t i, n = Py_SIZE(self); // 99,999
if (list_resize(self, n+1) < 0) // Py_SIZE(self)++

items = self->ob_item;
for (i = n; --i >= where; )
     items[i+1] = items[i];
Py_INCREF(v);
items[where] = v;

計算量がO(n)であることが分かります。

4.2. Deque

dequeのremoveの実装はここです。
中身の肝は以下。

for (i=0 ; i<n ; i++) {
        PyObject *item = deque->leftblock->data[deque->leftindex];
        int cmp = PyObject_RichCompareBool(item, value, Py_EQ);

        if (cmp > 0) {
            PyObject *tgt = deque_popleft(deque, NULL);
            assert (tgt != NULL);
            if (_deque_rotate(deque, i))
                return NULL;
            Py_DECREF(tgt);
            Py_RETURN_NONE;
        }
        _deque_rotate(deque, -1);
}

要素判定は常に左端要素を使用します。要素が見つかるまでrotate(-1)を行います。要素が見つかり次第、popleft()し、rotate(要素index)します。
計算量がO(n)であることが分かります。

この_deque_rotate()の中身はここです。
中身の肝は以下。

Py_ssize_t m = n;

if (m > rightindex + 1)
    m = rightindex + 1;
if (m > leftindex)
    m = leftindex;
    assert (m > 0 && m <= len);
    rightindex -= m;
    leftindex -= m;
    src = &rightblock->data[rightindex + 1];
    dest = &leftblock->data[leftindex];
    n -= m;
    do {
        *(dest++) = *(src++);
    } while (--m);

    deque->leftblock = leftblock;
    deque->rightblock = rightblock;
    deque->leftindex = leftindex;
    deque->rightindex = rightindex;

計算量がO(n)であることが分かります。

次にinsertの実装はここです。
中身の肝は以下。

    if (_deque_rotate(deque, -index))
        return NULL;
    if (index < 0)
        rv = deque_append(deque, value);
    else
        rv = deque_appendleft(deque, value);
    if (_deque_rotate(deque, index))
        return NULL;

rotate()して左端か右端にappend()しています。
rotate()の計算量は上記の通り、O(n)であることが分かります。

4.3. まとめ(中間要素)

中間要素への処理の計算量は以下の通りです。

処理	計算量
List.remove()	O(n)
List.insert()	O(n)
Deque.remove()	O(n)
Deque.insert()	O(n)

参照ブログでは、Dequeの方が高速に処理できました。その理由は、以下の通りです。

List: 削除要素以外の全要素でメモリ移動が伴う
Deuqe: 先頭要素から削除要素までのみメモリ移動が伴う

処理時間測定コードでは、先頭から20番目の要素をromove()、insert()しています。よってDequeの方が、メモリ移動の対象になる要素が少なく、処理時間が高速だったと考えられます。

5. List vs deque（末端の要素）

参考ブログでは以下のコードで、処理時間を比較しています。

List

list_array = list(range(1000))
for i in range(100000):
    list_array.append(0)

処理時間は以下の通りです。
1回目　elapsed_time:0.017949581146240234[sec]
2回目　elapsed_time:0.019548416137695312[sec]
3回目　elapsed_time:0.019548416137695312[sec]

Deque

deque_array = deque(range(1000))
for i in range(100000):
    deque_array.append(0)

処理時間は以下の通りです。
1回目　elapsed_time:0.023968935012817383[sec]
2回目　elapsed_time:0.023933887481689453[sec]
3回目　elapsed_time:0.01991128921508789[sec]

5.1. List

Listのappendの実装はここです。中身の肝は以下。

app1(self, object)

append(0)の場合、以下のようになります。

Py_ssize_t n = PyList_GET_SIZE(self);
if (list_resize(self, n+1) < 0) // Py_SIZE(self)++

Py_INCREF(v);
PyList_SET_ITEM(self, n, v); // (((PyListObject *)(op))->ob_item[i] = (v))

計算量がO(1)であることが分かります。

5.2. Deque

dequeのappendの実装はここです。中身の肝は以下。

deque_append_internal(deque, item, deque->maxlen)

deque_append_internal()の実装はここです。中身の肝は以下。

    deque->rightindex++;
    deque->rightblock->data[deque->rightindex] = item;

計算量がO(1)であることが分かります。

5.3. まとめ(末端要素)

末尾要素への処理の計算量は以下の通りです。

処理	計算量
List.append()	O(1)
Deque.append()	O(1)

6. おわりに

本記事では、PythonのListとDequeの処理の違いをCythonのコードから探ってみました。
ListとDequeによって「なぜパフォーマンスに違いが生まれるのか。」理解につながれば幸いです。

7. 参考文献

https://postd.cc/python-internals-pyobject/ https://note.nkmk.me/python-collections-deque/ https://docs.python.org/ja/3/c-api/sequence.html https://docs.python.org/ja/3/c-api/intro.html https://docs.python.org/3/c-api/typeobj.html

cyblue9's blog

【Python】ListとDequeのパフォーマンスの違い〜CPyhtonの実装を読んで〜

目次

1. List Objectについて

2. Deque Objectについて

3. List vs Deque（先頭要素)

3.1. List

3.2. Deque

3.3. まとめ(先頭要素)

4. List vs deque（中間の要素）

4.1. List

4.2. Deque

4.3. まとめ(中間要素)

5. List vs deque（末端の要素）

5.1. List

5.2. Deque

5.3. まとめ(末端要素)

6. おわりに

7. 参考文献