首页 文章

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

提问于
浏览 次
5

我注意到在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

The question is ：这是由于编译器中的限制会及时解决，还是有一种惯用的方式来传递应该在这种情况下使用的仿函数/匿名函数？

update 从答案中可以看出这是将在编译器中修复的内容 .

与此同时，有两个建议的工作 . 这两种方法都相当简单，尽管它们确实开始感觉像你必须在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

谢谢大家的帮助 .

performance anonymous-function julia-lang

3 回答

  • 5

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

    Update: 这已经在Julia的0.5版本中得到修复 .

    回复于
  • 10

    是的，这是由于编译器的限制，并且有计划修复它，参见例如这个issue . 与此同时，FastAnonymous包可能会提供一种解决方法 .

    你完成它的方式看起来非常惯用，遗憾的是没有你缺少的魔法技巧（除了可能的FastAnonymous包） .

    回复于
  • 5

    正如其他人所指出的那样，你的代码还没有 . 除了使用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
    回复于

相关问题