지수 계산 속도

Question

나는 현재 (내가 matlab에 함께 작업 한) N^3의 계산 속도가 NxNxN보다 느린 MATLAB에서

줄리아 테스트입니다. 이것은 N^2 및 NxN에서는 발생하지 않습니다. 이들은 속도가 아닌 정확도를 선호하기 때문에 고차원 지수를 계산하는 데 다른 알고리즘을 사용합니다.

나는 줄리아가 똑같은 일을한다고 생각한다.

줄리아가 적어도 큐브 지수에 대해 기본 알고리즘 대신 곱셈을 사용하여 N의 지수를 계산하도록하는 방법이 있는지 물어보고 싶습니다.

몇 시간 전 나는 이것을 matlab에 몇 가지 테스트를 수행했다. 줄리아에게 그 코드를 번역했습니다. 코드

링크 : http://pastebin.com/bbeukhTc (나는 :(여기에 모든 링크를 업로드하지 못할) matlab에 2014 스크립트의

결과 :

Exponente1

경과 시간은 68.293793 초 (최소 17.7 배)

Exponente2

경과 시간은 24.236218 초입니다. 합니다 (smallests의 6.3 배)

Exponente3

경과 시간 3.853348 초이다. 줄리아 0.46에 스크립트의

결과 :

Exponente1

18.423204 초 (8.22 K 할당 : 372.563 KB) (최소의 51.6x 회)

Exponente2

13.746904 초 (9.02k 할당 : 407.332KB) (최소 38.5 배)

Exponente3

0.356875 초 (10.01 K 할당 : 450.441 KB) 내 테스트에서

줄리아는 matlab에보다 빠른,하지만 난 상대 이전 버전을 사용하고 있습니다. 나는 다른 버전을 시험 할 수 없다.

julia/base/math.jl :

^(x::Float64, y::Integer) = 
    box(Float64, powi_llvm(unbox(Float64,x), unbox(Int32,Int32(y)))) 
^(x::Float32, y::Integer) = 
    box(Float32, powi_llvm(unbox(Float32,x), unbox(Int32,Int32(y)))) 

julia/base/fastmath.jl : 줄리아의 소스 코드를 확인

Answer 1

pow_fast{T<:FloatTypes}(x::T, y::Integer) = pow_fast(x, Int32(y)) 
pow_fast{T<:FloatTypes}(x::T, y::Int32) = 
    box(T, Base.powi_llvm(unbox(T,x), unbox(Int32,y))) 

우리는 줄리아 llvm's source code 확인 powi_llvm

사용하고 있음을 알 수 있습니다

을

define double @powi(double %F, i32 %power) { 
; CHECK: powi: 
; CHECK: bl __powidf2 
     %result = call double @llvm.powi.f64(double %F, i32 %power) 
    ret double %result 
} 

이제 __powidf2 여기서 흥미있는 기능이다

COMPILER_RT_ABI double 
__powidf2(double a, si_int b) 
{ 
    const int recip = b < 0; 
    double r = 1; 
    while (1) 
    { 
     if (b & 1) 
      r *= a; 
     b /= 2; 
     if (b == 0) 
      break; 
     a *= a; 
    } 
    return recip ? 1/r : r; 
} 

예 1 : 소정가 = 2; b = 7 :

-    r   = 1 
- iteration 1: r = 1 * 2 = 2; b = (int)(7/2) = 3; a = 2 * 2 = 4 
- iteration 2: r = 2 * 4 = 8; b = (int)(3/2) = 1; a = 4 * 4 = 16 
- iteration 3: r = 8 * 16 = 128; 

실시 예 2 : 주어진 a = 2; b = 8 :

-    r   = 1 
- iteration 1: r   = 1; b = (int)(8/2) = 4; a = 2 * 2 = 4 
- iteration 2: r   = 1; b = (int)(4/2) = 2; a = 4 * 4 = 16 
- iteration 3: r   = 1; b = (int)(2/2) = 1; a = 16 * 16 = 256 
- iteration 4: r = 1 * 256 = 256; b = (int)(1/2) = 0; 

정수 전력은 항상 시퀀스 곱셈으로서 구현된다. 그래서 N^3은 N^2보다 느립니다.

jl_powi_llvm (fastmath.jl에서 "jl_"은 매크로 확장으로 연결됨)은 지수를 부동 소수점으로 캐스팅하고 pow()를 호출합니다. C 소스 코드 :

JL_DLLEXPORT jl_value_t *jl_powi_llvm(jl_value_t *a, jl_value_t *b) 
{ 
    jl_value_t *ty = jl_typeof(a); 
    if (!jl_is_bitstype(ty)) 
     jl_error("powi_llvm: a is not a bitstype"); 
    if (!jl_is_bitstype(jl_typeof(b)) || jl_datatype_size(jl_typeof(b)) != 4) 
     jl_error("powi_llvm: b is not a 32-bit bitstype"); 
    jl_value_t *newv = newstruct((jl_datatype_t*)ty); 
    void *pa = jl_data_ptr(a), *pr = jl_data_ptr(newv); 
    int sz = jl_datatype_size(ty); 
    switch (sz) { 
    /* choose the right size c-type operation */ 
    case 4: 
     *(float*)pr = powf(*(float*)pa, (float)jl_unbox_int32(b)); 
     break; 
    case 8: 
     *(double*)pr = pow(*(double*)pa, (double)jl_unbox_int32(b)); 
     break; 
    default: 
     jl_error("powi_llvm: runtime floating point intrinsics are not implemented for bit sizes other than 32 and 64"); 
    } 
    return newv; 
} 

Answer 2

Lior의 답변은 우수합니다. 여기에 문제에 대한 해결책이 있습니다. 예, 정확성을 희생하여 곱셈을 강제로 사용하는 방법이 있습니다. @fastmath로, 성능이 훨씬 낫다는 것을

julia> @benchmark 1.1^3 
BenchmarkTools.Trial: 
    samples:   10000 
    evals/sample:  999 
    time tolerance: 5.00% 
    memory tolerance: 1.00% 
    memory estimate: 16.00 bytes 
    allocs estimate: 1 
    minimum time:  13.00 ns (0.00% GC) 
    median time:  14.00 ns (0.00% GC) 
    mean time:  15.74 ns (6.14% GC) 
    maximum time:  1.85 μs (98.16% GC) 

julia> @benchmark @fastmath 1.1^3 
BenchmarkTools.Trial: 
    samples:   10000 
    evals/sample:  1000 
    time tolerance: 5.00% 
    memory tolerance: 1.00% 
    memory estimate: 0.00 bytes 
    allocs estimate: 0 
    minimum time:  2.00 ns (0.00% GC) 
    median time:  3.00 ns (0.00% GC) 
    mean time:  2.59 ns (0.00% GC) 
    maximum time:  20.00 ns (0.00% GC) 

참고 :이 @fastmath 매크로입니다.