在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包）。