在Julia中使用匿名函数的性能下降

问题描述：

我注意到在Julia中使用匿名函数会导致性能下降.为了说明这一点，我有两种quicksort的实现(取自Julia发行版中的微型性能基准).第一个按升序排序

I have noticed that there is a performance penalty associated with using anonymous functions in Julia. To illustrate I have two implementations of quicksort (taken from the micro performance benchmarks in the Julia distribution). The first sorts in ascending order

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

第二个参数带有一个附加参数:匿名函数，可用于指定升序或降序排序，或用于比较其他奇特类型

The second takes an additional parameter: an anonymous function that can be used to specify ascending or descending sort, or comparison for more exotic types

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的数组(以秒为单位)进行排序的时间:

There is a significant performance penalty when sorting Arrays of Int64, with the default version an order of magnitude faster. Here are times for sorting arrays of length N in seconds:

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: Is this due to limitations in the compiler that will be ironed out in time, or is there an idiomatic way to pass functors/anonymous functions that should be used in cases like this?

更新从答案来看，这似乎将在编译器中得到解决.

update From the answers it looks like this is something that will be fixed up in the compiler.

同时，有两个建议的解决方法.两种方法都相当简单，尽管它们确实开始感觉像您在C ++中必须使用的那种琐的扑克游戏(尽管程度不那么尴尬).

In the mean time, there were two suggested work arounds. Both approaches are fairly straightforward, though they do start to feel like the sort of jiggery-pokery that you have to use in C++ (though not on the same scale of awkward).

第一个是@Toivo Henningsson建议的FastAnon软件包.我没有尝试这种方法，但是看起来不错.

The first is the FastAnon package suggested by @Toivo Henningsson. I didn't try this approach, but it looks good.

我尝试了@simonstar建议的第二种方法，它给我的性能与非泛型qsort相当！实施:

I tried out the second method suggested by @simonstar, which gave me equivalent performance to the non-generic qsort! implementation:

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

感谢大家的帮助.

答

正如其他人所指出的那样，您编写的代码是惯用的Julia，有一天会很快，但是编译器还没有.除了使用FastAnonymous，另一个选择是传递类型而不是匿名函数.对于此模式，您将定义一个不带字段的不可变对象和一个接受类型实例和一些参数的方法(我们称其为evaluate).然后，您的排序函数将接受op对象而不是函数，然后调用evaluate(op, x, y)而不是op(x, y).因为函数专用于其输入类型，所以抽象没有运行时开销.这是减少和数字扩展.

As others have noted, the code you've written is idiomatic Julia and will someday be fast, but the compiler isn't quite there yet. Besides using FastAnonymous, another option is to pass types instead of anonymous functions. For this pattern, you define an immutable with no fields and a method (let's call it evaluate) that accepts an instance of the type and some arguments. Your sorting function would then accept an op object instead of a function and call evaluate(op, x, y) instead of op(x, y). Because functions are specialized on their input types, there is no runtime overhead to the abstraction. This is the basis for reductions and specification of sort order in the standard library, as well as 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

在Julia中使用匿名函数的性能下降

相关推荐