Hiệu suất của bản đồ so với starmap?

Question

Tôi đã cố gắng để làm cho một tinh khiết-python (không có phụ thuộc bên ngoài) so sánh yếu tố khôn ngoan của hai trình tự. giải pháp đầu tiên của tôi là:

list(map(operator.eq, seq1, seq2)) 

Sau đó, tôi tìm thấy starmap chức năng từ itertools, mà dường như khá giống với tôi. Nhưng hóa ra lại nhanh hơn 37% trên máy tính của tôi trong trường hợp xấu nhất. Vì nó là không rõ ràng với tôi, tôi đo thời gian cần thiết để lấy 1 phần tử từ một máy phát điện (không biết nếu theo cách này là chính xác):

from operator import eq 
from itertools import starmap 

seq1 = [1,2,3]*10000 
seq2 = [1,2,3]*10000 
seq2[-1] = 5 

gen1 = map(eq, seq1, seq2)) 
gen2 = starmap(eq, zip(seq1, seq2)) 

%timeit -n1000 -r10 next(gen1) 
%timeit -n1000 -r10 next(gen2) 

271 ns ± 1.26 ns per loop (mean ± std. dev. of 10 runs, 1000 loops each) 
208 ns ± 1.72 ns per loop (mean ± std. dev. of 10 runs, 1000 loops each) 

Trong lấy yếu tố giải pháp thứ hai là performant hơn 24% . Sau đó, cả hai đều tạo ra kết quả tương tự cho list. Nhưng từ một nơi nào đó, chúng tôi nhận được thêm 13% trong thời gian:

%timeit list(map(eq, seq1, seq2)) 
%timeit list(starmap(eq, zip(seq1, seq2))) 

5.24 ms ± 29.4 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 
3.34 ms ± 84.8 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 

Tôi không biết cách tìm hiểu kỹ hơn về định dạng mã lồng nhau? Vì vậy, câu hỏi của tôi là lý do tại sao các máy phát điện đầu tiên nhanh hơn trong việc lấy và từ nơi chúng tôi đạt được thêm 13% trong chức năng list?

EDIT: Ý định đầu tiên của tôi là thực hiện so sánh yếu tố khôn ngoan thay vì all, do đó, chức năng all đã được thay thế bằng list. Sự thay thế này không ảnh hưởng đến tỷ lệ thời gian.

CPython 3.6.2 trên Windows 10 (64bit)

Answer 1

Có một số yếu tố góp phần (kết hợp) với phần chênh lệch hiệu suất quan sát:

• zip tái sử dụng trở tuple nếu nó có một số tài liệu tham khảo trong tổng số 1 khi __next__ cuộc gọi tiếp theo được thực hiện.
• map tạo mớituple được chuyển đến "hàm được ánh xạ" mỗi lần thực hiện cuộc gọi __next__. Trên thực tế nó có thể sẽ không tạo ra một bộ tuple mới từ đầu vì Python duy trì một bộ lưu trữ cho các bộ dữ liệu không sử dụng. Nhưng trong trường hợp đó, map phải tìm một bộ dữ liệu không được sử dụng có kích thước phù hợp.
• starmap kiểm tra xem mục tiếp theo trong có thể lặp lại có thuộc loại tuple và nếu có thì nó sẽ chuyển nó lên.
• Gọi một hàm C từ bên trong mã C với PyObject_Call sẽ không tạo một bộ tuple mới được chuyển tới callee.

Vì vậy starmap với zip sẽ chỉ sử dụng một tuple hơn và hơn nữa đó là thông qua để operator.eq do đó làm giảm chức năng gọi overhead vô cùng. Mặt khác, map sẽ tạo một bộ tuple mới (hoặc điền một mảng C từ CPython 3.6) mỗi khi operator.eq được gọi. Vì vậy, những gì thực sự là sự khác biệt tốc độ chỉ là chi phí tạo tuple.

Thay vì liên kết đến mã nguồn tôi sẽ cung cấp một số mã Cython có thể được sử dụng để xác minh điều này:

In [1]: %load_ext cython 

In [2]: %%cython 
    ...: 
    ...: from cpython.ref cimport Py_DECREF 
    ...: 
    ...: cpdef func(zipper): 
    ...:  a = next(zipper) 
    ...:  print('a', a) 
    ...:  Py_DECREF(a) 
    ...:  b = next(zipper) 
    ...:  print('a', a) 

In [3]: func(zip([1, 2], [1, 2])) 
a (1, 1) 
a (2, 2) 

Vâng, tuple s không thực sự bất biến, một đơn giản Py_DECREF là đủ để " lừa "zip vào tin tưởng không ai khác giữ một tham chiếu đến các tuple trả lại!

Đối với các "tuple-pass-thru":

In [4]: %%cython 
    ...: 
    ...: def func_inner(*args): 
    ...:  print(id(args)) 
    ...: 
    ...: def func(*args): 
    ...:  print(id(args)) 
    ...:  func_inner(*args) 

In [5]: func(1, 2) 
1404350461320 
1404350461320 

Vì vậy, các tuple được chuyển ngay qua (chỉ vì chúng được định nghĩa là chức năng C!) Này không xảy ra cho các chức năng Python tinh khiết:

In [6]: def func_inner(*args): 
    ...:  print(id(args)) 
    ...: 
    ...: def func(*args): 
    ...:  print(id(args)) 
    ...:  func_inner(*args) 
    ...: 

In [7]: func(1, 2) 
1404350436488 
1404352833800 

Lưu ý rằng nó cũng không xảy ra nếu gọi là chức năng không phải là một chức năng C ngay cả khi gọi từ một hàm C:

In [8]: %%cython 
    ...: 
    ...: def func_inner_c(*args): 
    ...:  print(id(args)) 
    ...: 
    ...: def func(inner, *args): 
    ...:  print(id(args)) 
    ...:  inner(*args) 
    ...: 

In [9]: def func_inner_py(*args): 
    ...:  print(id(args)) 
    ...: 
    ...: 

In [10]: func(func_inner_py, 1, 2) 
1404350471944 
1404353010184 

In [11]: func(func_inner_c, 1, 2) 
1404344354824 
1404344354824 

Vì vậy, có rất nhiều "trùng hợp ngẫu nhiên" dẫn đến thời điểm đó starmap với zip là nhanh hơn so với gọi map với nhiều tranh cãi khi gọi chức năng cũng là một chức năng C ...

Answer 2

Một khác biệt mà tôi có thể nhận thấy là cách map lấy các mục từ iterables. Cả hai map và zip tạo một bộ các trình vòng lặp từ mỗi lần lặp được chuyển. Giờ đây, zip duy trì một số nội bộ result tuple được điền vào mỗi lần tiếp theo được gọi và mặt khác, map creates a new array^* với mỗi cuộc gọi tiếp theo và deallocates nó.

---

* _{Như đã chỉ ra bởi MSeifert đến 3.5.4 map_next sử dụng để phân bổ một mọi Python tuple mới. Điều này thay đổi trong 3,6 và cho đến 5 lặp C stack được sử dụng và cho bất cứ điều gì lớn hơn đống đó được sử dụng. Các PR liên quan: Issue #27809: map_next() uses fast call và Add _PY_FASTCALL_SMALL_STACK constant | Vấn đề: https://bugs.python.org/issue27809}