Mức tiêu thụ bộ nhớ không đơn điệu trong từ điển Python2

Question

Ai đó có thể giải thích cách sử dụng bộ nhớ không đơn điệu này của từ điển trong CPython 2.7?

>>> import sys 
>>> sys.getsizeof({}) 
280 
>>> sys.getsizeof({'one': 1, 'two': 2, 'three': 3, 'four': 4, 'five': 5}) 
280 
>>> sys.getsizeof({'one': 1, 'two': 2, 'three': 3, 'four': 4, 'five': 5, 'six': 6}) 
1048 
>>> sys.getsizeof({'one': 1, 'two': 2, 'three': 3, 'four': 4, 'five': 5, 'six': 6, 'seven': 7}) 
1048 
>>> sys.getsizeof({'one': 1, 'two': 2, 'three': 3, 'four': 4, 'five': 5, 'six': 6, 'seven': 7, 'e 
ight': 8}) 
664 
>>> sys.getsizeof({'one': 1, 'two': 2, 'three': 3, 'four': 4, 'five': 5, 'six': 6, 'seven': 7, 'e 
ight': 8, 'nine': 9}) 
664 

Python3 là hợp lý ở đây, nó in kích thước của {'one': 1, 'two': 2, 'three': 3, 'four': 4, 'five': 5, 'six': 6, 'seven': 7} như 480.

Tôi cố gắng này trên Ubuntu 15.10 và OS X 10.11.

Answer 1

TLDR: Chữ cái dict thứ 6 và 7 nhập bảng tính bảng băm nặng và sau đó tăng gấp bốn lần kích thước thay đổi kích thước.

---

Khi CPython 2,7 đánh giá một dict đen, trước khi nó bắt đầu điền vào các mục, các opcode nó sử dụng để tạo dict là BUILD_MAP. Này có một đối số, một gợi ý cho bao nhiêu mục dict sẽ chứa, which it uses to presize the dict:

TARGET(BUILD_MAP) 
    { 
     x = _PyDict_NewPresized((Py_ssize_t)oparg); 
     PUSH(x); 
     if (x != NULL) DISPATCH(); 
     break; 
    } 

này được thiết kế để giảm thiểu số lần dict được thay đổi kích cỡ trong quá trình tạo, nhưng vì họ không chiếm yếu tố tải, nó không hoàn toàn loại bỏ thay đổi kích thước.

Khi số source code comments cho biết, _PyDict_NewPresized được thiết kế để "Tạo từ điển mới có kích thước trước để giữ số lượng phần tử ước tính". Kích thước chính xác của bảng băm trong dict được tạo bị ảnh hưởng bởi một số chi tiết thực hiện, chẳng hạn như kích thước tối thiểu (#define PyDict_MINSIZE 8) và yêu cầu kích thước là sức mạnh của 2 (để tránh phân chia trong quá trình triển khai).

Đối với văn bản dict tối đa 7 mục nhập, _PyDict_NewPresized khởi tạo bảng băm 8 mục; cho 8 mục, nó khởi tạo một bảng băm 16-nhập, kể từ khi thường xuyên thay đổi kích cỡ nó sử dụng luôn luôn chọn một công suất lớn hơn đối số.

---

Dicts resize on insertion when they become at least 2/3 full. Đối với literals dict 6- 7-nhập cảnh, dict bắt đầu với 8 mục, do đó, một thay đổi kích thước xảy ra trên chèn 6. Dict là đủ nhỏ mà thay đổi kích cỡ gấp bốn lần kích thước của bảng băm:

return dictresize(mp, (mp->ma_used > 50000 ? 2 : 4) * mp->ma_used); 

mp->ma_used là số lượng các mục được sử dụng trong bảng băm, 6 vào thời điểm này. 6 nhỏ hơn 50000, vì vậy chúng tôi gọi dictresize(mp, 4 * 6), thay đổi kích thước bảng băm thành 32 mục, công suất nhỏ nhất là 2 lớn hơn 24.

Ngược lại, đối với chữ viết 8 chữ cái, bảng băm bắt đầu với 16 mục nhập. Các dict không trở thành 2/3 đầy đủ trong quá trình tạo, vì vậy bảng băm 16 đầu tiên tồn tại trong quá trình tạo dict, và dict thu được nhỏ hơn với các chữ dict 6 và 7-entry.

---

Python 3 sử dụng một different growth policy, trong số những thay đổi thực hiện dict khác, đó là lý do tại sao bạn thấy kết quả khác nhau bằng Python 3.

Answer 2

Vâng, tôi đã cố gắng một chút và chúng ta hãy xem:

dct = {'four': 3, 'three': 2, 'two': 1, 'one': 0} 
print(sys.getsizeof(dct))        # = 272 
print(sys.getsizeof(dict(dct)))      # = 272 
print(sys.getsizeof({k: v for k, v in dct.items()})) # = 272 

dct = {'four': 3, 'three': 2, 'five': 4, 'two': 1, 'one': 0} 
print(sys.getsizeof(dct))        # = 272 
print(sys.getsizeof(dict(dct)))      # = 272 
print(sys.getsizeof({k: v for k, v in dct.items()})) # = 272 

dct = {'six': 5, 'three': 2, 'two': 1, 'four': 3, 'five': 4, 'one': 0} 
print(sys.getsizeof(dct))        # = 1040 
print(sys.getsizeof(dict(dct)))      # = 656 
print(sys.getsizeof({k: v for k, v in dct.items()})) # = 1040 

dct = {'seven': 6, 'six': 5, 'three': 2, 'two': 1, 'four': 3, 'five': 4, 'one': 0} 
print(sys.getsizeof(dct))        # = 1040 
print(sys.getsizeof(dict(dct)))      # = 656 
print(sys.getsizeof({k: v for k, v in dct.items()})) # = 1040 

dct = {'seven': 6, 'six': 5, 'three': 2, 'two': 1, 'four': 3, 'five': 4, 'eight': 7, 'one': 0} 
print(sys.getsizeof(dct))        # = 656 
print(sys.getsizeof(dict(dct)))      # = 1040 
print(sys.getsizeof({k: v for k, v in dct.items()})) # = 1040 

Tôi không chắc chắn những loại tối ưu hóa đang xảy ra ở đây, nhưng tôi cho rằng đó là bởi vì những cơ cấu sử dụng "thực hành tốt nhất" khác nhau. Tôi có nghĩa là khi nào để phân bổ bao nhiêu bộ nhớ cho bảng băm. Ví dụ, nếu bạn có mười một hoặc nhiều yếu tố bạn sẽ có được một sự khác biệt lạ:

dct = {1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7, 8: 8, 9: 9, 10:10, 11:11} 
print(sys.getsizeof(dct))        # = 1808 
print(sys.getsizeof(dict(dct)))      # = 1040 
print(sys.getsizeof({k: v for k, v in dct.items()})) # = 1040 

Vì vậy, điều này có lẽ chỉ là một số loại tiêu thụ bộ nhớ "tối ưu hóa" khi tạo bộ từ điển theo những cách khác nhau, tại sao có này outlier không đơn điệu đối với cú pháp bằng chữ khi sử dụng 6 hoặc 7 phần tử: Tôi không biết. Có lẽ một số tối ưu hóa bộ nhớ đã đi sai và đó là một lỗi mà nó phân bổ quá nhiều bộ nhớ? Tôi chưa đọc mã nguồn.