논리 변수를 double과 혼합하는 것이 더 느린가요?

Question

나는 매트릭스 연산을 수행하는데 필요한 0-1 벡터를 가지고있다. 그것들은별로 희박하지는 않습니다 (값의 절반 만이 0입니다). 이중 대신에 논리적 변수로 저장하면 논리적 변수에 1 바이트, 이중 부동 소수점에 8 바이트의 메모리가 8 배 절약됩니다.

두 값을 모두 사용하는 것보다 논리 벡터와 이중 행렬의 행렬 곱셈을 더 느리게 수행 할 수 있습니까? 아래에있는 내 예비 결과를 참조하십시오

>> x = [0 1 0 1 0 1 0 1]; A = rand(numel(x)); xl = logical(x); 
>> tic; for k = 1:10000; x * A * x'; end; toc %' 
Elapsed time is 0.017682 seconds. 
>> tic; for k = 1:10000; xl * A * xl'; end; toc %' 
Elapsed time is 0.026810 seconds. 
>> xs = sparse(x); 
>> tic; for k = 1:10000; xs * A * xs'; end; toc %' 
Elapsed time is 0.039566 seconds. 

논리적 인 표현을 사용하는 것이 훨씬 느린 것 같다 (스파 스도 느립니다). 왜 누군가가 설명 할 수 있습니까? 타입 캐스팅 시간인가? CPU/FPU 명령어 세트의 한계입니까?

편집 : 내 시스템은 맥 OS X 10.8.3에 MATLAB R2012b, 인텔 코어 i7 3.4 GHz의

EDIT2입니다 : 몇 가지 의견이 맥 OS X의 만 문제가에 내가하고 싶은 것을 보여주기 위해 가능한 경우 다양한 아키텍처 및 운영 체제의 결과를 컴파일하십시오.

EDIT3 : 실제 문제는 길이가 m 인 가능한 모든 이진 벡터로 계산해야합니다. m은 너무 커서 메모리에 맞출 수 없습니다.

Answer 1

조금 더 나은 벤치 마크를 게시하여 시작하겠습니다. = N = 4000과 희소성으로 여기

function [t,err] = test_mat_mult() 
    %# data 
    N = 4000; sparsity = 0.7; %# adjust size and sparsity of data 
    x = double(rand(1,N) > sparsity); 
    xl = logical(x); 
    xs = sparse(x); 
    A = randn(N); 

    %# functions 
    f = cell(3,1); 
    f{1} = @() mult_func(x,A); 
    f{2} = @() mult_func(xl,A); 
    f{3} = @() mult_func(xs,A); 

    %# timeit 
    t = cellfun(@timeit, f); 

    %# check results 
    v = cellfun(@feval, f, 'UniformOutput',true); 
    err = max(abs(v-mean(v))); %# maximum error 
end 

function v = mult_func(x,A) 
    v = x * A * x'; 
end 

내 컴퓨터에 결과이다 (WINXP 32 비트, R2013a) 0.7 : 좀 더 정확한 타이밍을 얻을 스티브 Eddins에서 TIMEIT 기능을 사용하고

>> [t,err] = test_mat_mult 
t = 
    0.031212 %# double 
    0.031970 %# logical 
    0.071998 %# sparse 
err = 
    7.9581e-13 

당신은 sparse 예상 (초점이기 때문에 효율적인 메모리 사용이 속도를하지 않음) 등 모두보다 느린 반면 double이 약간 더 이상 logical 평균입니다 볼 수 있습니다.

---

지금 플랫폼에 최적화 된 BLAS 구현에 그 MATLAB relies이 (DGEMM 생각) full-matrix multiplication을 수행 할 수 있습니다. 일반적인 경우에는 단일/이중 유형의 루틴이 포함되지만 부울은 포함되지 않으므로 logical의 경우 속도가 느린 이유를 설명하는 변환이 발생합니다.

인텔 프로세서에서 BLAS/LAPACK 루틴은 Intel MKL Library에 의해 제공됩니다. AMD에 대한 확실하지,하지만 난 그것을 동등한 ACML 사용 생각 : 물론

>> internal.matlab.language.versionPlugins.blas 
ans = 
Intel(R) Math Kernel Library Version 10.3.11 Product Build 20120606 for 32-bit applications 

스파 스 경우는 다른 이야기입니다. (나는 MATLAB이 많은 희소 연산을 위해 SuiteSparse 패키지를 사용한다는 것을 알고 있지만 확실하지는 않습니다).

Answer 2

결과가 다른 표현과 합리적으로 관련이 있다고 생각합니다.

비 스파 스 (non-sparse) 이중 배열은 캐시에 매우 쉽게 들어갈 수있는 작은 본문을 표현하기에 간단하고 효율적입니다.

논리적 배열은 8 바이트가 아닌 요소 당 바이트 만 사용하는 것이 더 공간 효율적이지만 8 개의 요소 만 있으면 아무 것도 얻지 못합니다. 다른 한편으로, 그것을 사용하여 double 연산을하기 전에 double로 변환해야합니다.

희소 배열은 배열의 대부분이 0 일 때 공간을 절약하기 위해 설계된보다 복잡한 표현을 사용합니다. 주어진 인덱스에있는 요소가 0인지를 결정하거나 0이 아닌 값을 얻으려면 더 많은 연산이 필요합니다. 가장 작은 캐시에서도 쉽게 사용할 수있는 50 % 0이 아닌 배열을 위해이를 사용하면 오용됩니다. 거의 모든 제로 인 대형 어레이의 메모리 및 데이터 전송 비용을 줄이는 것이 최선의 방법입니다. Sparse vs Normal Array Matlab

실제로 8 요소 배열을 다루는 경우에는 비어 있지 않은 double 배열을 사용해야합니다. 실제 작업에 더 큰 배열이 관련된 경우 비슷한 크기로 벤치마킹해야합니다. 또한 테스트 데이터의 희소가 실제 데이터와 일치하는지 확인해야합니다.

Answer 3

벤치 마크에서와 같이 전체적으로 캐시에 들어 가지 않는 데이터로 작업하는 경우 추가 작업 (논리적 유형과 이중 유형 간의 변환 또는 스파 스 저장 방식 사용)을 시도하면 메모리 사용량을 줄이면 코드를 느려지 게됩니다 (눈치 챘 겠지만).

L1 캐시의 데이터 액세스는로드 된 데이터 요소 당 수행되는 충분한 양의 계산 작업이있을 때 "충분히 자유 롭다"는 속도가 빠릅니다 (예에서와 같이). 이 경우 실행 속도는로드/저장 트래픽이 아닌 계산에 의해 제한됩니다. 논리 변수를 사용하면 계산을 수행하므로 벤치 마크 속도가 느려집니다.

실제로 해결할 문제의 작업 집합의 크기는 어느 정도입니까? 적어도 프로세서의 L2 캐시보다 크지 않은 경우에는 정상적인 double 행렬을 사용해야합니다.논리 변수를 사용하는 정확한 임계 값은 상당히 클 가능성이 있지만 결정할 몇 가지 실험이 필요합니다. (또한 MATLAB이 변환을 처리하는 방법에 따라 다르며, 변환을 위해 타일링의 일부로 변환을 수행합니다. MATLAB이이를 수행하지 않으면 double을 사용하는 것보다 결코 빠를 수는 없습니다 큰 데이터 집합입니다).