在 Julia 中使用匿名函数的性能损失

Question

我注意到在 Julia 中使用匿名函数会导致性能下降。为了说明我有两种快速排序的实现(取自 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++ 中使用的那种拼图游戏(尽管不那么笨拙)。

第一个是@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

这是一个问题，将通过即将进行的类型系统大修来解决。

更新:这已经在 0.5 版本的 Julia 中得到修复。