Hiệu suất của các phương pháp lập chỉ mục numpy ưa thích khác nhau, cũng với numba

Question

Vì lập chỉ mục nhanh của tôi là các mảng Numpy là khá cần thiết và lập chỉ mục ưa thích không có danh tiếng tốt về hiệu suất, tôi quyết định thực hiện một vài thử nghiệm. Đặc biệt là kể từ khi Numba đang phát triển khá nhanh, tôi đã thử phương pháp nào hoạt động tốt với tê tê.

Như đầu vào Tôi đã sử dụng các mảng sau đây cho tôi nhỏ mảng-test:

import numpy as np 
import numba as nb 

x = np.arange(0, 100, dtype=np.float64) # array to be indexed 
idx = np.array((0, 4, 55, -1), dtype=np.int32) # fancy indexing array 
bool_mask = np.zeros(x.shape, dtype=np.bool) # boolean indexing mask 
bool_mask[idx] = True # set same elements as in idx True 
y = np.zeros(idx.shape, dtype=np.float64) # output array 
y_bool = np.zeros(bool_mask[bool_mask == True].shape, dtype=np.float64) #bool output array (only for convenience) 

Và các mảng sau đây cho tôi lớn mảng-test (y_bool cần thiết vào đây để đối phó với những con số dupe từ randint):

x = np.arange(0, 1000000, dtype=np.float64) 
idx = np.random.randint(0, 1000000, size=int(1000000/50)) 
bool_mask = np.zeros(x.shape, dtype=np.bool) 
bool_mask[idx] = True 
y = np.zeros(idx.shape, dtype=np.float64) 
y_bool = np.zeros(bool_mask[bool_mask == True].shape, dtype=np.float64) 

Điều này mang lại timings sau mà không sử dụng numba:

%timeit x[idx] 
#1.08 µs ± 21 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each) 
#large arrays: 129 µs ± 3.45 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) 

%timeit x[bool_mask] 
#482 ns ± 18.1 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each) 
#large arrays: 621 µs ± 15.9 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 

%timeit np.take(x, idx) 
#2.27 µs ± 104 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each) 
# large arrays: 112 µs ± 5.76 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) 

%timeit np.take(x, idx, out=y) 
#2.65 µs ± 134 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each) 
# large arrays: 134 µs ± 4.47 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) 

%timeit x.take(idx) 
#919 ns ± 21.3 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each) 
# large arrays: 108 µs ± 1.71 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) 

%timeit x.take(idx, out=y) 
#1.79 µs ± 40.7 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each) 
# larg arrays: 131 µs ± 2.92 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) 

%timeit np.compress(bool_mask, x) 
#1.93 µs ± 95.8 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each) 
# large arrays: 618 µs ± 15.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 

%timeit np.compress(bool_mask, x, out=y_bool) 
#2.58 µs ± 167 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each) 
# large arrays: 637 µs ± 9.88 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 

%timeit x.compress(bool_mask) 
#900 ns ± 82.4 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each) 
# large arrays: 628 µs ± 17.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 

%timeit x.compress(bool_mask, out=y_bool) 
#1.78 µs ± 59.8 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each) 
# large arrays: 628 µs ± 13.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 

%timeit np.extract(bool_mask, x) 
#5.29 µs ± 194 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each) 
# large arrays: 641 µs ± 13 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 

Và với numba, sử dụng jitting trong nopython -mode, cach ing và nogil tôi trang trí đường lối của lập chỉ mục, được hỗ trợ bởi numba:

@nb.jit(nopython=True, cache=True, nogil=True) 
def fancy(x, idx): 
    x[idx] 

@nb.jit(nopython=True, cache=True, nogil=True) 
def fancy_bool(x, bool_mask): 
    x[bool_mask] 

@nb.jit(nopython=True, cache=True, nogil=True) 
def taker(x, idx): 
    np.take(x, idx) 

@nb.jit(nopython=True, cache=True, nogil=True) 
def ndtaker(x, idx): 
    x.take(idx) 

này mang lại kết quả như sau đối với mảng nhỏ và lớn:

%timeit fancy(x, idx) 
#686 ns ± 25.1 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each) 
# large arrays: 84.7 µs ± 1.82 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) 

%timeit fancy_bool(x, bool_mask) 
#845 ns ± 31 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each) 
# large arrays: 843 µs ± 14.2 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 

%timeit taker(x, idx) 
#814 ns ± 21.1 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each) 
# large arrays: 87 µs ± 1.52 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) 

%timeit ndtaker(x, idx) 
#831 ns ± 24.5 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each) 
# large arrays: 85.4 µs ± 2.69 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) 

---

Tóm tắt

Mặc dù không có numba nhưng rõ ràng là các mảng nhỏ được lập chỉ mục tốt nhất với mặt nạ boolean (khoảng 2 lần so với ndarray.take(idx)), đối với mảng lớn hơn ndarray.take(idx) sẽ hoạt động tốt nhất, trong trường hợp này nhanh hơn 6 lần lập chỉ mục boolean . Điểm hòa vốn có kích thước mảng khoảng 1000 ô có kích thước mảng chỉ số khoảng 20 ô.
Đối với mảng có các yếu tố 1e5 và 5e3 kích thước mảng chỉ mục, ndarray.take(idx) sẽ là khoảng nhanh hơn 10 lần so với lập chỉ mục mặt nạ boolean. Vì vậy, có vẻ như lập chỉ mục boolean dường như làm chậm đáng kể với kích thước mảng, nhưng bắt kịp một chút sau khi đạt đến một số ngưỡng kích thước mảng.

Đối với các chức năng được ghi đè bằng numba, có một tốc độ nhỏ cho tất cả các chức năng lập chỉ mục ngoại trừ việc lập chỉ mục mặt nạ boolean. Việc lập chỉ mục ưa thích đơn giản hoạt động tốt nhất ở đây, nhưng vẫn còn chậm hơn so với mặt nạ boolean mà không có jitting.
Đối với mảng lớn hơn, lập chỉ mục mặt nạ boolean chậm hơn rất nhiều so với các phương thức khác, và thậm chí chậm hơn phiên bản không được ghi. Ba phương pháp khác đều hoạt động khá tốt và nhanh hơn khoảng 15% so với phiên bản không được khai thác.

Đối với trường hợp của tôi với nhiều mảng có kích thước khác nhau, lập chỉ mục ưa thích với tê giác là cách tốt nhất để đi. Có lẽ một số người khác cũng có thể tìm thấy một số thông tin hữu ích trong bài đăng khá dài này.

Chỉnh sửa:
Tôi rất tiếc vì tôi đã quên đặt câu hỏi của mình, điều mà tôi thực tế có. Tôi đã nhanh chóng gõ vào cuối ngày làm việc của tôi và hoàn toàn quên nó ... Vâng, bạn có biết bất kỳ phương pháp tốt hơn và nhanh hơn so với những gì tôi đã kiểm tra? Sử dụng Cython thời gian của tôi là giữa Numba và Python.
Khi mảng chỉ mục được xác định trước một lần và được sử dụng mà không thay đổi trong các lần lặp dài, bất kỳ cách nào để xác định trước quá trình lập chỉ mục sẽ là tuyệt vời. Đối với điều này tôi nghĩ về việc sử dụng các bước tiến. Nhưng tôi đã không thể xác định trước một tập hợp các bước tiến tùy chỉnh. Có thể để có được một cái nhìn được xác định trước vào bộ nhớ bằng cách sử dụng các bước tiến không?

Chỉnh sửa 2:
Tôi đoán tôi sẽ di chuyển câu hỏi của mình về mảng chỉ số liên tục được xác định trước sẽ được sử dụng trên cùng một mảng giá trị (chỉ có giá trị thay đổi chứ không phải hình dạng) cho vài triệu lần lặp lại một câu hỏi mới và cụ thể hơn. Câu hỏi này quá chung chung và có lẽ tôi cũng đã xây dựng câu hỏi một chút sai lầm. Tôi sẽ đăng liên kết tại đây ngay sau khi tôi mở câu hỏi mới!
Here is the link to the followup question.

Answer 1

Tóm tắt của bạn không hoàn toàn chính xác, bạn đã làm thử nghiệm với các mảng có kích thước khác nhau nhưng một điều bạn không làm là thay đổi số lượng chỉ mục.

Tôi đã hạn chế nó lập chỉ mục thuần túy và bỏ qua take (có hiệu quả là lập chỉ mục mảng số nguyên) và compress và extract (vì đây là cách lập chỉ mục mảng boolean hiệu quả). Sự khác biệt duy nhất cho chúng là những yếu tố không đổi. Hệ số không đổi cho các phương pháp take và compress sẽ nhỏ hơn chi phí cho các chức năng gọn gàng np.take và np.compress nhưng nếu không thì hiệu ứng sẽ không thể bỏ qua cho các mảng có kích thước hợp lý.

Chỉ cần cho tôi trình bày nó với những con số khác nhau:

# ~ every 500th element 
x = np.arange(0, 1000000, dtype=np.float64) 
idx = np.random.randint(0, 1000000, size=int(1000000/500)) # changed the ratio! 
bool_mask = np.zeros(x.shape, dtype=np.bool) 
bool_mask[idx] = True 

%timeit x[idx] 
# 51.6 µs ± 2.02 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) 
%timeit x[bool_mask] 
# 1.03 ms ± 37.1 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 


# ~ every 50th element 
idx = np.random.randint(0, 1000000, size=int(1000000/50)) # changed the ratio! 
bool_mask = np.zeros(x.shape, dtype=np.bool) 
bool_mask[idx] = True 

%timeit x[idx] 
# 1.46 ms ± 55.1 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 
%timeit x[bool_mask] 
# 2.69 ms ± 154 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 


# ~ every 5th element 
idx = np.random.randint(0, 1000000, size=int(1000000/5)) # changed the ratio! 
bool_mask = np.zeros(x.shape, dtype=np.bool) 
bool_mask[idx] = True 

%timeit x[idx] 
# 14.9 ms ± 495 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 
%timeit x[bool_mask] 
# 8.31 ms ± 181 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 

Vì vậy, những gì xảy ra ở đây? Thật đơn giản: Việc lập chỉ mục mảng Integer chỉ cần truy cập vào nhiều phần tử vì có các giá trị trong mảng chỉ mục. Điều đó có nghĩa là nếu có ít trận đấu thì nó sẽ diễn ra khá nhanh nhưng chậm nếu có nhiều chỉ số. Tuy nhiên, việc lập chỉ mục mảng Boolean luôn cần phải đi qua toàn bộ mảng boolean và kiểm tra các giá trị "true". Điều đó có nghĩa là nó phải là "liên tục" cho mảng. Tuy nhiên, chờ đợi, nó không thực sự liên tục cho các mảng boolean và tại sao chỉ số mảng nguyên mất nhiều thời gian hơn (trường hợp cuối cùng) so với việc lập chỉ mục mảng boolean ngay cả khi nó phải xử lý các phần tử ít hơn 5 lần?

Đó là nơi nó trở nên phức tạp hơn. Trong trường hợp này mảng boolean có True ở những vị trí ngẫu nhiên có nghĩa là nó sẽ bị thất bại dự đoán chi nhánh. Đây sẽ là nhiều khả năng nếu True và False sẽ có sự xuất hiện bằng nhau nhưng ở những nơi ngẫu nhiên. Đó là lý do tại sao việc lập chỉ mục mảng boolean trở nên chậm hơn - bởi vì tỷ lệ của True đến False trở nên bình đẳng hơn và do đó có nhiều "ngẫu nhiên" hơn. Ngoài ra mảng kết quả sẽ lớn hơn nếu có nhiều hơn True s cũng tiêu tốn nhiều thời gian hơn.

Như một ví dụ cho điều dự đoán rẽ nhánh này sử dụng như ví dụ (có thể khác với hệ thống khác nhau/biên dịch):

bool_mask = np.zeros(x.shape, dtype=np.bool) 
bool_mask[:1000000//2] = True # first half True, second half False 
%timeit x[bool_mask] 
# 5.92 ms ± 118 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 

bool_mask = np.zeros(x.shape, dtype=np.bool) 
bool_mask[::2] = True # True and False alternating 
%timeit x[bool_mask] 
# 16.6 ms ± 361 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 

bool_mask = np.zeros(x.shape, dtype=np.bool) 
bool_mask[::2] = True 
np.random.shuffle(bool_mask) # shuffled 
%timeit x[bool_mask] 
# 18.2 ms ± 325 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 

Vì vậy, sự phân bố của True và False sẽ cực kỳ quan ảnh hưởng đến thời gian chạy với mặt nạ boolean ngay cả khi chúng chứa cùng số lượng True s! Hiệu ứng tương tự sẽ hiển thị cho các chức năng compress.

Để lập chỉ mục mảng nguyên (và tương tự như vậy np.take) một hiệu ứng khác sẽ hiển thị: vị trí bộ nhớ cache. Các chỉ số trong trường hợp của bạn được phân phối ngẫu nhiên, vì vậy máy tính của bạn phải thực hiện rất nhiều "RAM" cho bộ nhớ cache "bộ xử lý" vì rất khó có hai chỉ số sẽ ở gần nhau.

Hãy so sánh này:

idx = np.random.randint(0, 1000000, size=int(1000000/5)) 
%timeit x[idx] 
# 15.6 ms ± 703 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 

idx = np.random.randint(0, 1000000, size=int(1000000/5)) 
idx = np.sort(idx) # sort them 
%timeit x[idx] 
# 4.33 ms ± 366 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 

Bằng cách sắp xếp các chỉ số cơ hội vô cùng tăng rằng giá trị tiếp theo đã được sẽ được trong bộ nhớ cache và điều này có thể dẫn đến sự tăng tốc rất lớn. Đó là một yếu tố rất quan trọng nếu bạn biết rằng các chỉ số sẽ được sắp xếp (ví dụ nếu chúng được tạo ra bởi np.where chúng được sắp xếp, mà làm cho kết quả của np.where đặc biệt hiệu quả cho việc lập chỉ mục).

Vì vậy, nó không giống như chỉ số mảng nguyên là chậm hơn cho mảng nhỏ và nhanh hơn cho mảng lớn, nó phụ thuộc vào nhiều yếu tố hơn. Cả hai đều có trường hợp sử dụng của họ và tùy thuộc vào hoàn cảnh mà người ta có thể (đáng kể) nhanh hơn người kia.

---

Hãy để tôi cũng nói một chút về chức năng của tê giác. Đầu tiên một số tuyên bố chung:

• cache sẽ không tạo sự khác biệt, nó chỉ tránh biên dịch lại hàm. Trong môi trường tương tác, điều này là vô dụng. Nó nhanh hơn nếu bạn sẽ gói các chức năng trong một mô-đun mặc dù.
• nogil tự nó sẽ không cung cấp tăng tốc. Nó sẽ nhanh hơn nếu nó được gọi trong các luồng khác nhau bởi vì mỗi thực thi hàm có thể giải phóng GIL và sau đó nhiều cuộc gọi có thể chạy song song.

Nếu không, tôi không biết hiệu quả của các chức năng NumPy trong tê giác có thể chậm hơn hoặc nhanh hơn - nhưng ngay cả khi nó nhanh hơn thì sẽ không nhanh hơn nhiều mảng nhỏ). Bởi vì nếu nó có thể được thực hiện nhanh hơn, các nhà phát triển NumPy cũng sẽ thực hiện nó. Quy tắc ngón tay cái của tôi là: Nếu bạn có thể làm điều đó (vectorized) với NumPy không bận tâm với tê giác. Chỉ khi bạn không thể làm điều đó với các chức năng NumPy được vector hóa hoặc NumPy sẽ sử dụng quá nhiều mảng tạm thời thì numba sẽ tỏa sáng!