Mengapa dua daftar identik memiliki jejak memori yang berbeda?

155

Saya membuat dua daftar l1dan l2, tetapi masing-masing dengan metode pembuatan yang berbeda:

import sys

l1 = [None] * 10
l2 = [None for _ in range(10)]

print('Size of l1 =', sys.getsizeof(l1))
print('Size of l2 =', sys.getsizeof(l2))

Tapi hasilnya mengejutkan saya:

Size of l1 = 144
Size of l2 = 192

Daftar yang dibuat dengan pemahaman daftar adalah ukuran yang lebih besar dalam memori, tetapi kedua daftar tersebut identik dengan Python.

Mengapa demikian? Apakah ini masalah internal CPython, atau penjelasan lain?

Andrej Kesely
sumber
2
Mungkin, operator pengulangan akan memanggil beberapa fungsi yang persis ukuran array yang mendasarinya. Perhatikan, di 144 == sys.getsizeof([]) + 8*10)mana 8 adalah ukuran pointer.
juanpa.arrivillaga
1
Perhatikan bahwa jika Anda mengubah 10ke 11, [None] * 11daftar memiliki ukuran 152, tetapi pemahaman daftar masih memiliki ukuran 192. Pertanyaan yang ditautkan sebelumnya bukan duplikat yang tepat, tetapi relevan untuk memahami mengapa ini terjadi.
Patrick Haugh

Jawaban:

162

Ketika Anda menulis [None] * 10, Python tahu bahwa ia akan membutuhkan daftar tepat 10 objek, sehingga mengalokasikannya dengan tepat.

Saat Anda menggunakan pemahaman daftar, Python tidak tahu berapa banyak yang dibutuhkan. Jadi secara bertahap tumbuh daftar sebagai elemen ditambahkan. Untuk setiap realokasi, ia mengalokasikan lebih banyak ruang daripada yang dibutuhkan segera, sehingga tidak harus merealokasi untuk setiap elemen. Daftar yang dihasilkan cenderung lebih besar dari yang dibutuhkan.

Anda dapat melihat perilaku ini saat membandingkan daftar yang dibuat dengan ukuran yang serupa:

>>> sys.getsizeof([None]*15)
184
>>> sys.getsizeof([None]*16)
192
>>> sys.getsizeof([None for _ in range(15)])
192
>>> sys.getsizeof([None for _ in range(16)])
192
>>> sys.getsizeof([None for _ in range(17)])
264

Anda dapat melihat bahwa metode pertama mengalokasikan apa yang dibutuhkan, sedangkan metode kedua tumbuh secara berkala. Dalam contoh ini, ia mengalokasikan cukup untuk 16 elemen, dan harus realokasi ketika mencapai tanggal 17.

interjay
sumber
1
Ya, itu masuk akal. Mungkin lebih baik membuat daftar *ketika saya tahu ukuran di depan.
Andrej Kesely
27
@AndrejKesely Hanya digunakan [x] * ndengan tidak berubah xdalam daftar Anda. Daftar yang dihasilkan akan menyimpan referensi ke objek yang identik.
schwobaseggl
5
@schwobaseggl, mungkin itu yang Anda inginkan, tetapi ada baiknya Anda memahaminya.
juanpa.arrivillaga
19
@ juanpa.arrivillaga Benar, mungkin saja. Tapi biasanya tidak dan khususnya SO penuh dengan poster yang bertanya-tanya mengapa semua data mereka berubah secara bersamaan: D
schwobaseggl
50

Seperti dicatat dalam pertanyaan ini , pemahaman daftar menggunakan di list.appendbawah tenda, sehingga akan memanggil metode daftar-ukuran, yang secara keseluruhan dialokasikan.

Untuk menunjukkan hal ini kepada diri sendiri, Anda dapat menggunakan disdissasembler:

>>> code = compile('[x for x in iterable]', '', 'eval')
>>> import dis
>>> dis.dis(code)
  1           0 LOAD_CONST               0 (<code object <listcomp> at 0x10560b810, file "", line 1>)
              2 LOAD_CONST               1 ('<listcomp>')
              4 MAKE_FUNCTION            0
              6 LOAD_NAME                0 (iterable)
              8 GET_ITER
             10 CALL_FUNCTION            1
             12 RETURN_VALUE

Disassembly of <code object <listcomp> at 0x10560b810, file "", line 1>:
  1           0 BUILD_LIST               0
              2 LOAD_FAST                0 (.0)
        >>    4 FOR_ITER                 8 (to 14)
              6 STORE_FAST               1 (x)
              8 LOAD_FAST                1 (x)
             10 LIST_APPEND              2
             12 JUMP_ABSOLUTE            4
        >>   14 RETURN_VALUE
>>>

Perhatikan LIST_APPENDopcode dalam pembongkaran <listcomp>objek kode. Dari dokumen :

LIST_APPEND (i)

Panggilan list.append(TOS[-i], TOS). Digunakan untuk mengimplementasikan daftar pemahaman.

Sekarang, untuk operasi pengulangan daftar, kami memiliki petunjuk tentang apa yang terjadi jika kita mempertimbangkan:

>>> import sys
>>> sys.getsizeof([])
64
>>> 8*10
80
>>> 64 + 80
144
>>> sys.getsizeof([None]*10)
144

Jadi, tampaknya untuk dapat persis mengalokasikan ukuran. Melihat kode sumber , kami melihat inilah yang terjadi:

static PyObject *
list_repeat(PyListObject *a, Py_ssize_t n)
{
    Py_ssize_t i, j;
    Py_ssize_t size;
    PyListObject *np;
    PyObject **p, **items;
    PyObject *elem;
    if (n < 0)
        n = 0;
    if (n > 0 && Py_SIZE(a) > PY_SSIZE_T_MAX / n)
        return PyErr_NoMemory();
    size = Py_SIZE(a) * n;
    if (size == 0)
        return PyList_New(0);
    np = (PyListObject *) PyList_New(size);

Yaitu, di sini: size = Py_SIZE(a) * n;. Sisa fungsi hanya mengisi array.

juanpa.arrivillaga
sumber
"Seperti dicatat dalam pertanyaan ini, pemahaman daftar menggunakan daftar. Tambahkan di bawah tenda" Saya pikir lebih tepat untuk mengatakan bahwa itu menggunakan .extend().
Akumulasi
@Akumulasi mengapa menurut Anda begitu?
juanpa.arrivillaga
Karena itu tidak menambahkan elemen satu per satu. Saat Anda menambahkan elemen ke daftar, Anda benar-benar membuat daftar baru, dengan alokasi memori baru, dan memasukkan daftar ke dalam alokasi memori baru itu. Daftar pemahaman, di sisi lain, menempatkan sebagian besar elemen baru ke dalam memori yang telah dialokasikan, dan ketika mereka kehabisan memori yang dialokasikan, mereka mengalokasikan potongan memori lain, tidak hanya cukup untuk elemen baru.
Akumulasi
7
@Akumulasi Itu tidak benar. list.appendadalah operasi waktu konstan diamortisasi karena ketika daftar mengubah ukuran, itu secara keseluruhan menempatkan. Tidak setiap operasi penambahan, oleh karena itu, menghasilkan array yang baru dialokasikan. Dalam kasus apa pun pertanyaan yang saya tautkan menunjukkan kepada Anda dalam kode sumber yang pada kenyataannya, pemahaman daftar memang digunakan list.append,. Saya akan kembali ke laptop saya sebentar lagi dan saya dapat menunjukkan kepada Anda bytecode yang dibongkar untuk pemahaman daftar dan LIST_APPENDopcode yang sesuai
juanpa.arrivillaga
3

Tidak ada yang merupakan blok memori, tetapi itu bukan ukuran yang ditentukan sebelumnya. Selain itu, ada beberapa spasi tambahan dalam array antara elemen array. Anda dapat melihatnya sendiri dengan menjalankan:

for ele in l2:
    print(sys.getsizeof(ele))

>>>>16
16
16
16
16
16
16
16
16
16

Yang tidak total ukuran l2, tetapi lebih sedikit.

print(sys.getsizeof([None]))
72

Dan ini jauh lebih besar dari sepersepuluh ukuran l1.

Angka-angka Anda harus bervariasi tergantung pada detail sistem operasi Anda dan detail penggunaan memori saat ini di sistem operasi Anda. Ukuran [Tidak ada] tidak pernah bisa lebih besar dari memori yang berdekatan yang tersedia di mana variabel diatur untuk disimpan, dan variabel mungkin harus dipindahkan jika nanti secara dinamis dialokasikan menjadi lebih besar.

StevenJD
sumber
1
Nonesebenarnya tidak disimpan dalam array yang mendasarinya, satu-satunya hal yang disimpan adalah PyObjectpointer (8 byte). Semua objek Python dialokasikan pada heap. Noneadalah singleton, sehingga memiliki daftar dengan banyak nones hanya akan membuat array pointer PyObject ke Noneobjek yang sama di heap (dan tidak menggunakan memori tambahan dalam proses per tambahan None). Saya tidak yakin apa yang Anda maksud dengan "Tidak ada yang tidak memiliki ukuran yang ditentukan sebelumnya", tetapi itu kedengarannya tidak benar. Akhirnya, perulangan Anda dengan getsizeofsetiap elemen tidak menunjukkan apa yang menurut Anda itu menunjukkan.
juanpa.arrivillaga
Jika seperti yang Anda katakan benar, ukuran [Tidak ada] * 10 harus sama dengan ukuran [Tidak ada]. Tapi jelas ini tidak begitu-- beberapa penyimpanan tambahan telah ditambahkan. Bahkan, ukuran [Tidak ada] yang diulang sepuluh kali (160) juga lebih kecil dari ukuran [Tidak ada] yang dikalikan dengan sepuluh. Seperti yang Anda tunjukkan, jelas ukuran pointer ke [None] lebih kecil daripada ukuran [None] itu sendiri (16 byte daripada 72 byte). Namun, 160 + 32 adalah 192. Saya tidak berpikir jawaban sebelumnya menyelesaikan masalah sepenuhnya. Sudah jelas bahwa sejumlah kecil memori (mungkin bergantung pada kondisi mesin) dialokasikan.
StevenJD
"Jika seperti yang Anda katakan benar, ukuran [Tidak ada] * 10 harus sama dengan ukuran [Tidak ada]" apa yang saya katakan yang mungkin menyiratkan hal itu? Sekali lagi, Anda tampaknya berkonsentrasi pada fakta bahwa buffer yang mendasarinya dialokasikan berlebihan, atau bahwa ukuran daftar mencakup lebih dari ukuran buffer yang mendasarinya (tentu saja memang demikian), tetapi itu bukan poin dari pertanyaan ini. Sekali lagi, penggunaan Anda gestsizeofpada masing ele- masing l2adalah menyesatkan karena getsizeof(l2) tidak memperhitungkan ukuran elemen di dalam wadah .
juanpa.arrivillaga
Untuk membuktikan kepada diri sendiri bahwa klaim terakhir, lakukan l1 = [None]; l2 = [None]*100; l3 = [l2]kemudian print(sys.getsizeof(l1), sys.getsizeof(l2), sys.getsizeof(l3)). Anda akan mendapatkan hasil seperti: 72 864 72. Artinya, masing-masing, 64 + 1*8, 64 + 100*8, dan 64 + 1*8, sekali lagi, dengan asumsi sistem 64bit dengan ukuran pointer 8 byte.
juanpa.arrivillaga
1
Seperti yang telah saya nyatakan, sys.getsizeof* tidak memperhitungkan ukuran barang dalam wadah. Dari dokumen : "Hanya konsumsi memori yang secara langsung dikaitkan dengan objek diperhitungkan, bukan konsumsi memori objek yang dimaksud ... Lihat ukuran rekursif resep untuk contoh menggunakan getsizeof () secara rekursif untuk menemukan ukuran wadah dan semua isinya. "
juanpa.arrivillaga