在OCaml中,抽象的价格有多大(即多态函数)

Question

我还处于学习OCaml的早期阶段,并且很想知道在OCaml中从通用代码中提取最大性能的最佳方法是什么.

作为一个小实验,我编写了两个多态函数:一个在C++中,另一个在OCaml中,找到给定数组中的最大元素.

我观察到的是,在C++中,你不会为这种抽象付出代价,OCaml中的惩罚是性能下降了一个数量级.另外,我快速炮制的C++解决方案比OCaml更通用,但我主要是因为我对语言缺乏经验.

我的问题如下:如何编写和使用OCaml中的多态函数而不支付我刚刚观察到的巨大性能损失？

我在这个特定问题上观察到的另一件事是我在OCaml中的功能解决方案比命令式解决方案慢,而C++中的"功能"解决方案与模拟命令方法相比没有受到任何惩罚.

g++ -std="c++0x" -O3 -o max_cpp max.cpp使用gcc-4.6.3和OCaml代码编译C++代码:ocamlopt -o max_ml max.mlusing ocamlopt version 3.12.1.两个生成的可执行文件都是32位,并在Ubuntu x64 11.04上运行

我提交了两个程序的代码.

C++代码(当然不完全安全;))

#include <iostream>
#include <vector>
#include <numeric>
template <typename T> T max (T a, T b) {
     return (a>b)? a : b;
}

template <typename I> typename I::value_type find_max (I begin, I end) {
    auto max = *begin;
    for (begin++;begin!=end;begin++)
            if (*begin > max) max = *begin;
    return max;
}

template <typename I> typename I::value_type find_max1(I begin, I end) {
    return std::accumulate(begin, end, *begin, max< typename I::value_type> );
}

int main(int argc, char ** argv) {
    const size_t nElem = atoi(argv[1]);
    const size_t nIter = atoi(argv[2]);
    std::vector<int> intA(nElem);
    std::vector<double> dubA(nElem);
    for (int i=0;i<nIter;i++) {
            auto res1 = find_max(intA.begin(), intA.end());
            auto res2 = find_max(dubA.begin(), dubA.end());
            std::cout << "Max int: " << res1 << " " << "Max dub: " << res2 << std::endl;
    }
}

OCaml代码

let max a b = if a > b then a else b

(* functional version *)
let find_max vector =
    Array.fold_right max vector vector.(0)

(* imperative version *)
let find_max1 vector =
    let length = Array.length vector in
    let max = ref (vector.(0)) in
    for i=1 to length-1 do
            if vector.(i) > !max then max := vector.(i)
    done; max

let nElems = int_of_string Sys.argv.(1)

let nIter  = int_of_string Sys.argv.(2)

let _ = let intA = Array.make nElems 0 in
    let dubA = Array.make nElems 0.0 in
    for i=1 to nIter do
            let res1 = find_max intA in
            let res2 = find_max dubA in
            print_int !res1;
            print_newline ();
            print_float !res2;
    done

但是,如果我"重载"函数来区分整数和浮点数,那么程序的性能甚至超过我的C++代码的50%!我想知道为什么.

let find_max_int (vector : int array) =
    let length = Array.length vector in
    let max = ref (vector.(0)) in
    for i=1 to length-1 do
            if vector.(i) > !max then max := vector.(i)
    done; max

let find_max_float (vector : float array) =
    let length = Array.length vector in
    let max = ref (vector.(0)) in
    for i=1 to length-1 do
            if vector.(i) > !max then max := vector.(i)
    done; max

时间表相当粗暴地执行: time ./max_cpp 1000000 100和 time ./max_ml 1000000 100

Answer 1

在OCaml中,比较运算符(<)是类型的通用函数'a -> 'a -> bool(同样用于相等等).这意味着它由运行时系统中的特殊原语实现,可以有效地对任何类型的数据结构进行临时比较.类型检查器能够优化整数和浮点数的单形比较到专门的比较操作,而不是在多态情况下在运行时进行类型检查.如果仅测试此操作,效率的十倍差异就不足为奇了.

请注意,为了获得最大的灵活性,您应该在比较操作中进行抽象find_max.然而,这将阻止单形化优化,因此内联版本仍将表现得更好.

我认为你的方法(做微观基准并希望学习有关真实程序性能的有趣事情)是有缺陷的.你遇到了一个高度特殊的OCaml性能行为,并从那里错误地得出结论,多态函数的性能"很差".由于过早优化,这显然是一个糟糕的结论.写下您打算运行的计算的实际代表性示例,然后推断这个真实世界的代码片段的性能.你将从这种微基准测试和很多不相关的细节中学到很少的真理.

(然而,C++代码专业化方法通常可以产生比OCaml编译技术更高效的代码,它只为所有类型编译函数的一个版本,但必须使相应的数据表示妥协;在OCaml中可能存在开销但是,只有在相当具体的情况下才能观察到这种情况,你通常可以在代码的小关键部分进行特定的内联传递.你获得的回报是更快的编译(没有重复)和实际可读的错误消息 - 就像在C++中集成概念一样.)

编辑:我实际上错误地说,抽象比较将阻止类型导向优化.以下代码虽然仍然没有内联版本那么快,但仍然明显快于使用多态比较的版本:

let find_max1 comp vector =
    let length = Array.length vector in
    let max = ref (vector.(0)) in
    for i=1 to length-1 do
      if comp !max vector.(i) then max := vector.(i)
    done;
    !max

let find_max_int (vector : int array) = find_max1 (fun x y -> x < y) vector
let find_max_float (vector : float array) = find_max1 (fun x y -> x < y) vector