在Julia中使用匿名函數的性能損失

Question

我注意到在Julia中使用匿名函數的性能損失。爲了說明我有兩個quicksort的實現（從Julia分佈的微觀性能基準中獲得）。所述第一按升序排序

function qsort!(a,lo,hi) 
    i, j = lo, hi 
    while i < hi 
     pivot = a[(lo+hi)>>>1] 
     while i <= j 
      while a[i] < pivot; i += 1; end 
      while pivot < a[j]; j -= 1; end 
      if i <= j 
       a[i], a[j] = a[j], a[i] 
       i, j = i+1, j-1 
      end 
     end 
     if lo < j; qsort!(a,lo,j); end 
     lo, j = i, hi 
    end 
    return a 
end 

第二需要一個附加的參數：可用於指定升序或降序排序，或比較用於更特殊的類型

function qsort_generic!(a,lo,hi,op=(x,y)->x<y) 
    i, j = lo, hi 
    while i < hi 
     pivot = a[(lo+hi)>>>1] 
     while i <= j 
      while op(a[i], pivot); i += 1; end 
      while op(pivot, a[j]); j -= 1; end 
      if i <= j 
       a[i], a[j] = a[j], a[i] 
       i, j = i+1, j-1 
      end 
     end 
     if lo < j; qsort_generic!(a,lo,j,op); end 
     lo, j = i, hi 
    end 
    return a 
end 

有一個匿名函數當對Int64的數組進行排序時，性能會受到嚴重影響，默認版本的速度要快一個數量級。下面是時間（秒）排序的長度N數組：

N  qsort_generic qsort 
2048 0.00125   0.00018 
4096 0.00278   0.00029 
8192 0.00615   0.00061 
16384 0.01184   0.00119 
32768 0.04482   0.00247 
65536 0.07773   0.00490 

的問題是：這是由於將在時間待熨燙出在編譯器的限制，或是否有傳遞函子的慣用方式/應該在這種情況下使用的匿名函數？

更新從答案看來，這是一種將在編譯器中解決的問題。

與此同時，有兩個建議的解決方法。這兩種方法都相當簡單，儘管它們開始感覺像是你必須在C++中使用的那種jiggery-pokery（儘管它們的規模並不那麼尷尬）。

第一個是由@Toivo Henningsson建議的FastAnon軟件包。我沒有嘗試這種方法，但看起來不錯。

我試用了@simonstar建議的第二種方法，它給了我與非通用qsort相當的性能！執行：

abstract OrderingOp 
immutable AscendingOp<:OrderingOp end 
immutable DescendingOp<:OrderingOp end 
evaluate(::AscendingOp, x, y) = x<y 
evaluate(::DescendingOp, x, y) = x>y 

function qsort_generic!(a,lo,hi,op=AscendingOp()) 
    i, j = lo, hi 
    while i < hi 
     pivot = a[(lo+hi)>>>1] 
     while i <= j 
      while evaluate(op, a[i], pivot); i += 1; end 
      while evaluate(op, pivot, a[j]); j -= 1; end 
      if i <= j 
       a[i], a[j] = a[j], a[i] 
       i, j = i+1, j-1 
      end 
     end 
     if lo < j; qsort_generic!(a,lo,j,op); end 
     lo, j = i, hi 
    end 
    return a 
end 

謝謝大家的幫助。

Answer 1

正如其他人已經指出，你寫的代碼是慣用的Julia，並且有一天會很快，但編譯器還沒有那麼完美。除了使用FastAnonymous之外，另一種選擇是傳遞類型而不是匿名函數。對於這種模式，你定義了一個不可變的字段和一個方法（我們稱之爲evaluate），它接受一個類型的實例和一些參數。然後，您的排序功能將接受op對象而不是函數，並調用evaluate(op, x, y)而不是op(x, y)。因爲函數專門針對它們的輸入類型，所以抽象沒有運行時間開銷。這是標準庫中reductions和specification of sort order以及NumericExtensions的基礎。

例如：

immutable AscendingSort; end 
evaluate(::AscendingSort, x, y) = x < y 

function qsort_generic!(a,lo,hi,op=AscendingSort()) 
    i, j = lo, hi 
    while i < hi 
     pivot = a[(lo+hi)>>>1] 
     while i <= j 
      while evaluate(op, a[i], pivot); i += 1; end 
      while evaluate(op, pivot, a[j]); j -= 1; end 
      if i <= j 
       a[i], a[j] = a[j], a[i] 
       i, j = i+1, j-1 
      end 
     end 
     if lo < j; qsort_generic!(a,lo,j,op); end 
     lo, j = i, hi 
    end 
    return a 
end 

Answer 2

這是一個問題，將在即將到來的類型系統檢修中解決。

更新：這現在已經修復在0.5版本的朱莉婭。

Answer 3

是的，這是由於編譯器的限制，並且有計劃修復它，請參閱。這issue。與此同時，FastAnonymous包可能會提供解決方法。

你完成它的方式看起來非常習慣，不幸的是沒有你錯過的魔術（除了可能的FastAnonymous包）。