>

Cython을 사용하여 여러 배열을 가로로 배열하는 가장 빠른 방법을 찾으려고합니다. 일을 시작하기 위해 10 x 100,000의 임의의 부동 소수점 2D 배열이 있다고 가정 해 봅시다. 나는 object 를 만들 수 있습니다  다음과 같이 각 열을 배열의 값으로 배열합니다.

n = 10 ** 5
a = np.random.rand(10, n)
a_obj = np.empty(n, dtype='O')
for i in range(n):
    a_obj[i] = a[:, i]

각 행의 합계를 찾기 만하면됩니다. 다음과 같이 간단하게 계산할 수 있습니다.

%timeit a.sum(1)
414 µs ± 24.5 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
%timeit a_obj.sum()
113 ms ± 7.01 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

개체 배열이 250 배 느립니다.

물을 정리하기 전에 각 요소에 대한 액세스 권한을 원했습니다. Cython은 각 항목을 직접 반복 할 때 객체 배열의 각 구성원에 대한 액세스 속도를 높일 수 없습니다.

def access_obj(ndarray[object] a):
    cdef int i
    cdef int nc = len(a)
    cdef int nr = len(a[0])
    for i in range(nc):
        for j in range(nr):
            a[i][j]
%timeit access_obj(a_obj)
42.1 ms ± 665 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

그러나 data 를 사용하여 기본 C 배열에 액세스 할 수 있다고 생각합니다.   memoryview 인 속성  개체에 접근하고 훨씬 빠르게 액세스 :

def access_obj_data(ndarray[object] a):
    cdef int i
    cdef int nc = len(a)
    cdef int nr = len(a[0])
    cdef double **data = <double**>a.data
    for i in range(nc):
        for j in range(nr):
            data[i][j]

타이밍 할 때 결과를 캐시하므로 한 번만 수행해야한다고 생각합니다.

%timeit -n 1 -r 1 access_obj_data(a_obj)
8.17 µs ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)

문제는 당신이 a.data 를 던질 수 없다는 것입니다  복식의 C 배열로. 첫 번째 열을 인쇄하면 다음과 같은 결과가 나타납니다.

5e-324
2.1821467023e-314
2.2428810855e-314
2.1219957915e-314
6.94809615162997e-310
6.94809615163037e-310
2.2772194067e-314
2.182150145e-314
2.1219964234e-314
0.0

유사한 질문이 있지만 작동하는 코드로이 작업을 빠르게 수행 할 수있는 방법에 대한 답변은 없습니다.

  • 답변 # 1

    두 가지 다른 질문이 있다고 생각합니다 :

    <올>

    a_obj.sum() 입니까  너무 느려?

    사이 톤 함수 코드가 왜 느린가요?

    우리는 a_obj.sum() 의 느린 것을 볼 것입니다  Python-dispatch + cache miss의 오버 헤드를 추적 할 수 있습니다. 그러나 이것은 매우 불필요한 분석의 결과이며 더 미묘한 이유가있을 수 있습니다.

    두 번째 질문은 그다지 흥미롭지 않습니다. Cython은 함수를 빠르게 할 수있는 배열의 객체에 대해 충분히 알지 못합니다.

    "가장 빠른 방법은 무엇입니까?"라는 질문도 있습니다. 대답은 거의 항상 이런 종류의 질문에 대한 것이기 때문에 "데이터와 하드웨어에 따라 다릅니다"입니다.

    그러나 우리는 얻은 통찰력을 사용하여 기존 버전을 약간 개선 할 것입니다.

    <시간>

    ' a_obj.sum() 로 시작하자  느립니다 ".

    내 기계의 예에 대한 기준으로 (yep, factor 200 ) :

    >>> %timeit a.sum(1)
    510 µs ± 14.6 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
    >>> %timeit a_obj.sum()
    90.3 ms ± 494 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
    
    

    우즈 위즈에서 먼저 일어나는 일 ? 축소 알고리즘은 다음과 같습니다.

    a_obj.sum()
    
    

    그러나 알고리즘은 result=a_obj[0]+a_obj[1]+a_obj[2]+... 를 알지 못합니다.  numpy-arrays이므로 파이썬 디스패치를 ​​사용하여 알아야합니다.  실제로 두 개의 numpy-array가 추가되었습니다. 이것은 a_obj[i] 를 요약하는 데 상당한 오버 헤드입니다.  우리가 a_obj[i]+a_obj[i+1] 를 지불해야 할 복식  타임스. 좀 더 자세한 내용에 관심이 있다면 얼마 전에 파이썬 배포 비용에 대한 질문에 대답했습니다.

    배열의 모양이 10 라면 , 우리는 오버 헤드 만 10**5 를 지불합니다  시간은 10**5x10 의 작업에 비해 크지 않을 것입니다  추가 사항 :

    10
    
    

    보시다시피, 계수 (약 2)는 현재 훨씬 작습니다. 그러나 Python-dispatch-overhead 이론은 모든 것을 설명 할 수는 없습니다.

    다음 크기의 배열을 살펴 보겠습니다 :

    10**5
    
    

    이번에는 요소가 약 8입니다! 그 이유는 obj-version의 캐시 누락입니다. 이것은 메모리 바운드 작업이므로 기본적으로 메모리 속도는 병목 현상입니다.

    numpy 배열에서 요소는 연속적으로 메모리에 연속적으로 저장됩니다. 메모리에서 더블을 가져올 때마다 7 개의 더블 이웃으로 페치되며이 8 개의 더블이 캐시에 저장됩니다.

    >>> b=np.random.rand(n,10) >>> b_obj=to_obj_array(b) # see listing at the end for code >>> %timeit b.sum(1) 2.43 ms ± 13.4 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) >>> %timeit b_obj.sum() 5.53 ms ± 17.1 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 때  정보는 행 단위로 필요합니다. 메모리에서 캐시로 더블을 가져올 때마다 다음 7 개의 번호가 프리 페치되므로 요약 될 수 있습니다. 가장 효율적인 메모리 액세스 패턴입니다.

    개체 버전에 따라 다릅니다. 정보는 열 단위로 필요합니다. 그래서 우리가 추가 >>> c=np.random.rand(10**4,10**4) >>> c_obj=to_obj_array(c) >>> %timeit c.sum(1) 52.5 ms ± 354 µs per loop (mean ± std. dev. of 7 runs, 10 loops each) >>> %timeit c_obj.sum() 369 ms ± 2.53 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) 를 가져올 때마다캐시에 두 배가 필요합니다. 아직 필요하지 않습니다.이 두 배를 처리 할 수있을 때 캐시에서 이미 제거되었습니다 (캐시가 열의 모든 숫자에 대해 충분히 크지 않기 때문에) 느린에서 가져와야합니다. 다시 기억하십시오.

    즉, 두 번째 접근 방식에서는 모든 더블이 메모리에서 8 번 읽히거나 메모리/캐시 미스에서 8 번 더 읽 힙니다.

    valgrind의 cachegrind를 사용하여 두 변종에 대한 캐시 미스를 측정하는지 쉽게 확인할 수 있습니다 (test_cache.py`의 끝에있는 목록 참조) :

    c.sum(1)
    
    

    즉, 7 -version은 D1 캐시 누락이 약 8 배 더 많습니다.

    <시간>

    그러나 더 재미있는 것은 객체 버전이 더 빠를 수 있다는 것입니다!

    valgrind --tool=cachegrind python test_cache.py array
    ...
    D1  misses:       144,246,083 
    ...
    valgrind --tool=cachegrind python test_cache.py object
    ...
    D1  misses:     1,285,664,578
    ...
    
    

    어떻게 될 수 있을까?

    <올>

    전체 어레이를 캐시에 저장할 수 있으므로 추가 캐시 미스가 없습니다.

    파이썬 디스패치 오버 헤드는 견딜 수 있습니다.

    그러나 느린 버전의 경우 두 배 더 빠릅니까?

    100 % 확신 할 수는 없지만 여기 내 이론이 있습니다 : 배열 버전의 경우, 행 c_obj 의 합을 계산합니다 :

    >>> d=np.random.rand(800,6)
    >>> d_obj=to_obj_array(d)
    >>> %timeit d.sum(1)
    20.2 µs ± 217 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
    >>> %timeit d_obj.sum()
    12.4 µs ± 155 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
    
    

    따라서 이전 작업의 결과가 다음을 계산하기 위해 필요하기 때문에 하드웨어가 명령어를 병렬로 실행할 수 없습니다.

    객체 버전에 대한 계산은 다음과 같습니다.

    i
    
    

    이러한 단계는 CPU간에 종속성이 없기 때문에 CPU와 병렬로 수행 할 수 있습니다.

    <시간>

    그래서 왜 사이 톤이 그렇게 느립니까? cython은 배열의 객체에 대해 아무것도 모르기 때문에 일반적인 Python 코드보다 빠르지 않습니다. 매우 느립니다!

    사이 톤 함수 ... sum_i=sum_i+a[i][j] sum_i=sum_i+a[i][j+1] sum_i=sum_i+a[i][j+2] ... 를 분해하자 :

    <올>

    Cython은 ... sum_i=sum_i+a[i][j] sum_k=sum_k+a[k][j] sum_m=sum_m+a[i][j] ... 에 대해 전혀 모른다  그리고 그것이 일반적인 파이썬 객체라고 가정합니다.

    이것은 access_obj 를 의미합니다  그것은 a[i] 를 호출해야합니다  와이즈 비츠  파이썬 인프라의 도움으로. Btw. 그 a[i][j] 를 위해  본격적인 Python 정수로 변환해야합니다.

    __get_item__  저장된 c-double에서 본격적인 Python-float를 생성하고이를 cython으로 반환합니다.

    cast는 Python-float를 c-float로 반환했습니다.

    결론적으로, 우리는 Python-dispatch를 사용하지 않고 두 개의 임시 Python 객체를 만들었습니다. 필요한 비용을 볼 수 있습니다.

    <시간>

    합산 속도 향상

    우리는 요약이 메모리 바운드 작업 (적어도 내 컴퓨터에서)이라는 것을 알았으므로 가장 중요한 것은 캐시 누락을 피하는 것입니다 (이 파라마운트는 예를 들어 다른 알고리즘이 필요함을 의미 할 수 있음) C-order 및 F-order numpy-array의 경우).

    하지만 우리의 작업이 CPU를 사용하는 작업과 CPU를 공유해야하는 경우 다시 사실상 CPU에 종속 될 수 있으므로 현금 결여 이상에 초점을 두는 것이 장점입니다.

    나중에 소개 될 C 버전에서는 두 가지 접근 방식의 좋은 특성을 결합하고자합니다.

    <올>

    객체 버전과 유사하게 CPU의 고유 병렬 처리를 사용하기 위해 여러 행 합계를 병렬로 계산하려고합니다.

    numpy-array-sum과 유사하게 최소한의 캐시-미스를 원하므로 모든 행을 동시에 계산하는 것이 아니라 작은 블록 (예 : 8) 만 계산합니다. 이 블록 단위 계산은 한 번 캐시 된 데이터가 실제로 필요하기 전에 캐시에서 제거되지 않는다는 이점이 있습니다.

    여기에는 8 개의 묶음으로 행을 처리하는 간단한 버전이 있습니다.

    a[i]
    
    

    이제 Cython을 사용하여이 함수를 래핑 할 수 있습니다 :

    j
    
    

    확장 프로그램을 빌드 한 후 ( __get_item__ 목록 참조) ), 비교를 할 수 있습니다 :

    //fast.c
    #define MAX 8
    void sum_rows_blocks(double *orig, double *out, int n_rows, int n_cols){
       int n_blocks=n_rows/MAX;
       for (int b=0; b<n_blocks; b++){   //for every block
           double res[MAX]={0.0};        //initialize to 0.0
           for(int j=0;j<n_cols;j++){
               for(int i=0;i<MAX;i++){   //calculate sum for MAX-rows simultaniously
                  res[i]+=orig[(b*MAX+i)*n_cols+j];
               }
           }
           for(int i=0;i<MAX;i++){
                 out[b*MAX+i]=res[i];
           }
       }  
       //left_overs:
       int left=n_rows-n_blocks*MAX;
       double res[MAX]={0.0};         //initialize to 0.0
       for(int j=0;j<n_cols;j++){
           for(int i=0;i<left;i++){   //calculate sum for left rows simultaniously
                  res[i]+=orig[(n_blocks*MAX)*n_cols+j];
           }
       }
       for(int i=0;i<left;i++){
             out[n_blocks*MAX+i]=res[i];
       }
    }
    
    

    그것은 //c_sum.pyx cimport numpy as np import numpy as np cdef extern from "fast.c": void sum_rows_blocks(double *orig, double *out, int n_rows, int n_cols) def sum_rows_using_blocks(double[:,:] arr): cdef int n_rows cdef int n_cols cdef np.ndarray[np.double_t] res n_rows=arr.shape[0] n_cols=arr.shape[1] res=np.empty((n_rows, ),'d') sum_rows_blocks(&arr[0,0], &res[0], n_rows, n_cols) return res 를 고려  지금까지 가장 빠른 버전 (12µs)보다 빠릅니다. 큰 배열에 어떻게 작용합니까?

    setup.py
    
    

    좋아요, import c_sum %timeit c_sum.sum_rows_using_blocks(d) #shape=(800,6) 4.26 µs ± 95.8 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each) 보다 약간 빠릅니다  어느 3 걸립니다  ms, 추가 캐시 누락이 없음을 의미합니다.

    개선 될 수 있습니까? 나는 그렇게 생각한다 : 예를 들어 기본 컴파일 플래그 %timeit c_sum.sum_rows_using_blocks(c) #shape=(10**4,10**4) 49.7 ms ± 600 µs per loop (mean ± std. dev. of 7 runs, 10 loops each) 를 사용하지 않는 것  ( c.sum(1) 포함)  설정에서)는 결과 어셈블리를 개선하고 모양 52 의 합계에 대해 10 % 속도 향상으로 이어집니다. .

    <시간>

    목록 :

    -fwrapv
    
    

    extra_compile_args = ["-fno-wrapv"] :

    (800, 6)
    
    

    def to_obj_array(a): n=a.shape[1] obj=np.empty((n,),dtype='O') for i in range(n): obj[i]=a[:,i] return obj :

    check_cache.py
    
    

    import sys import numpy as np def to_obj_array(a): n=a.shape[1] obj=np.empty((n,),dtype='O') for i in range(n): obj[i]=a[:,i] return obj c=np.random.rand(10**4,10**4) c_obj=to_obj_array(c) for i in range(10): if sys.argv[1]=="array": c.sum(1) elif sys.argv[1]=="object": c_obj.sum() else: raise Exception("unknown parameter")

관련 자료

  • 이전 CSS 전환 효과가 작동하지 않습니다
  • 다음 java - Google Maps API에 어떤 문제가 있습니까?