logo标签列表

为什么这个OCaml程序比我的C程序快？

cperformanceocaml
12
我用C、Python和OCaml编写了一个基本的Hippity Hop程序。尽管这可能不是这三种语言的很好的基准，但我得到的结果大致如下：
  • Python：0.350秒
  • C：0.050秒
  • 解释的OCaml：0.040秒
  • 编译后的OCaml：0.010秒
Python的表现并不让我惊讶，但OCaml的速度（特别是解释版本）让我非常震惊。为了比较，我将发布C版本和OCaml版本。

C

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

long get_count(char *name);

int main(int argc, char *argv[])
{
  if (argc != 2){
    printf("Filename must be specified as a positional argument.\n");
    exit(EXIT_FAILURE);
  }

  long count_no = get_count(argv[1]);

  int i;
  for (i = 1; i <= count_no; i++){
    if (((i % 3) == 0) && ((i % 5) == 0)){
      printf("Hop\n");
      continue;
    }
    if ((i % 3) == 0){
      printf("Hoppity\n");
    }
    if ((i % 5) == 0){
      printf("Hophop\n");
    }
  }
  return 0;
}

long get_count(char *name){
  FILE *fileptr = fopen(name, "r");
  if (!fileptr){
    printf("Unable to open file %s.\n", name);
    exit(EXIT_FAILURE);
  }
  size_t text_len = 20;
  char *file_text = calloc(text_len, sizeof(char));
  while (!feof(fileptr)){
    fread(file_text, sizeof(char), text_len, fileptr);
    assert(!ferror(fileptr));
    text_len += 20;
    file_text = realloc(file_text, text_len * sizeof(char));
  }
  long file_as_int = strtol(file_text, NULL, 10);

  free(file_text);
  return file_as_int;
}

OCaml

open String;;

let trim str =
  if str = "" then "" else
  let search_pos init p next =
    let rec search i =
      if p i then raise(Failure "empty") else
      match str.[i] with
      | ' ' | '\n' | '\r' | '\t' -> search (next i)
      | _ -> i
    in
    search init
  in
  let len = String.length str in
  try
    let left = search_pos 0 (fun i -> i >= len) (succ)
    and right = search_pos (len - 1) (fun i -> i < 0) (pred)
    in
    String.sub str left (right - left + 1)
  with
  | Failure "empty" -> ""
;;

let rec iterate_over_numbers curr_num max_num =
  (
   if curr_num <= max_num then (
     if ((curr_num mod 3) == 0) && ((curr_num mod 5) == 0) then 
       print_endline "Hop"
     else if (curr_num mod 3) == 0 then 
       print_endline "Hoppity"
     else if (curr_num mod 5) == 0 then
       print_endline "Hophop";
     iterate_over_numbers (curr_num + 1) max_num
   ))
;;


let fname = Sys.argv.(1);;
let infile = open_in fname;;
let file_text = trim (input_line infile);;
close_in infile;;
let input_number = int_of_string file_text;;
iterate_over_numbers 1 input_number;;

但我很想知道为什么会得到这些结果。是因为我的C程序有问题，还是OCaml更快一些呢？对我来说，一个解释性程序比C版本运行稍快有点奇怪，而编译后的程序运行速度却快了5倍。

2
另外，顺便提一下，在使用“fopen()”的函数中不使用“fclose()”会导致文件泄漏。当然，修复这个问题会减慢速度，但是你打开的东西应该关闭；你分配的东西应该释放。 - Jonathan Leffler
2
这可能与你的问题无关，但是 while (!feof(fileptr)){ 几乎肯定是一个错误。 - Jerry Coffin
2
请注意，这是 FizzBuzz 问题的一个小变体：http://stackoverflow.com/questions/437/what-is-your-solution-to-the-fizzbuzz-problem。但是，它不是重复的 - 这个问题询问的是时间；另一个问题询问的是实现。 - Jonathan Leffler
@Jonathan - 我会尽量回答多少问题。输出只是打印到标准输出流(stdout)。我没有重定向它。当开启优化时，性能大致可与OCaml相比。感谢你指出我忘记fclose打开的文件了。但程序即将结束，这是否有影响呢？ - Jason Baker
@Jerry - 我为那个问题开了一个单独的帖子：https://dev59.com/n0nSa4cB1Zd3GeqPRt2s - Jason Baker
显示剩余3条评论
5个回答
9

时间在0.05以下可能只是简单的噪音。在C语言中，重复主程序足够多次以获得约1秒的执行时间。（我指的是在程序本身的循环中重复它，而不是通过再次运行它来重复）

你是否开启了优化编译？你尝试过减少分支（和比较）的数量吗？

if (i % 3 == 0) {
  if (i % 5 == 0) {
    printf("Hop\n");
    continue;
  }
  printf("Hoppity\n");
} else if (i % 5 == 0){
  printf("Hophop\n");
}

你试过查看汇编输出吗？

另外，printf相当慢。尝试使用puts("Hop")代替，因为你不需要格式化。

这是可能的，但你必须进行测试。你在每15次尝试中节省的时间（只需检查1次）可能无法平衡那些需要3次检查的数字所花费的时间。只有测试才能告诉你 :)（对检查i％15，i％3，i％5的建议进行了评论 - 后来被删除了） - viraptor
是的，我因为代码中有一个打字错误而将其删除，然后意识到它可能不会更有效率，所以我保持了它被删除的状态。 - Chris Lutz
到目前为止，如果我将优化级别提高，似乎速度会快很多。 - Jason Baker
除非使用一个非常基本的printf()子系统从一个精简库中，否则printf()会真正拖慢速度，特别是在glibc creature comforts下。 - Tim Post
如果您使用“else”打印“Hoppity”，则不需要“continue”。 - Jonathan Leffler
@Jonathan - 很难知道哪个更“高效”，但我认为你的版本肯定更易读。 - Chris Lutz
9

你的C代码并不等同于OCaml代码-在OCaml中使用'else if'可以避免重新计算模数。

“读取长整数”中有很多代码。为什么不直接使用fscanf()呢？它可以自动跳过空格等，避免你进行malloc()等操作。我通常不建议使用fscanf()，但这看起来是一个适合使用它的场景——单行代码，可能两边带有空格，没有奇怪的东西。

好奇心害死猫——但在这种情况下，没有害死豹子。

我下载了适用于MacOS X Intel的OCaml 3.11.1，并将问题中的OCaml代码复制到xxx.ml（OCaml）中，然后将其编译成对象文件xxx（使用“ocamlc -o xxx xxx.ml”）；我将C代码原封不动地复制到yyy.c中，并使用fscanf()和fclose()创建了变体zzz.c，然后使用“gcc -O -o yyy yyy.c”和“gcc -O -o zzz zzz.c”进行编译。我创建了一个包含：“987654”加一个换行符的文件“file3”。我创建了一个名为runthem.sh的shell脚本，如下所示。请注意，“time”是一个顽固的命令，它认为其输出必须进入stderr，即使你不想让它这样——你必须很努力才能将输出放到想要的位置。（range命令生成给定范围内的数字，包括每个程序的11个值。）

Osiris JL: cat runthem.sh
for prog in "ocaml xxx.ml" ./xxx ./yyy ./zzz
do
    for iter in $(range 0 10)
    do
        r=$(sh -c "time $prog file3 >/dev/null" 2>&1)
        echo $prog: $r
    done
done
Osiris JL:

我在一台运行Leopard（10.5.8）的现代MacBook Pro（3 GHz Core 2 Duo等，4GB RAM）上运行了所有这些。 我得到的时间如下所示：

Osiris JL: sh runthem.sh
ocaml xxx.ml: real 0m0.961s user 0m0.524s sys 0m0.432s
ocaml xxx.ml: real 0m0.953s user 0m0.516s sys 0m0.430s
ocaml xxx.ml: real 0m0.959s user 0m0.517s sys 0m0.431s
ocaml xxx.ml: real 0m0.951s user 0m0.517s sys 0m0.430s
ocaml xxx.ml: real 0m0.952s user 0m0.516s sys 0m0.431s
ocaml xxx.ml: real 0m0.952s user 0m0.514s sys 0m0.431s
ocaml xxx.ml: real 0m0.951s user 0m0.515s sys 0m0.431s
ocaml xxx.ml: real 0m0.959s user 0m0.515s sys 0m0.431s
ocaml xxx.ml: real 0m0.950s user 0m0.515s sys 0m0.431s
ocaml xxx.ml: real 0m0.956s user 0m0.516s sys 0m0.431s
ocaml xxx.ml: real 0m0.952s user 0m0.514s sys 0m0.432s
./xxx: real 0m0.928s user 0m0.494s sys 0m0.430s
./xxx: real 0m0.938s user 0m0.494s sys 0m0.430s
./xxx: real 0m0.927s user 0m0.494s sys 0m0.430s
./xxx: real 0m0.928s user 0m0.492s sys 0m0.430s
./xxx: real 0m0.928s user 0m0.493s sys 0m0.430s
./xxx: real 0m0.927s user 0m0.493s sys 0m0.430s
./xxx: real 0m0.928s user 0m0.492s sys 0m0.430s
./xxx: real 0m0.933s user 0m0.497s sys 0m0.428s
./xxx: real 0m0.926s user 0m0.494s sys 0m0.429s
./xxx: real 0m0.921s user 0m0.492s sys 0m0.428s
./xxx: real 0m0.925s user 0m0.494s sys 0m0.428s
./yyy: real 0m0.027s user 0m0.026s sys 0m0.001s
./yyy: real 0m0.031s user 0m0.026s sys 0m0.002s
./yyy: real 0m0.028s user 0m0.026s sys 0m0.001s
./yyy: real 0m0.029s user 0m0.026s sys 0m0.002s
./yyy: real 0m0.028s user 0m0.026s sys 0m0.001s
./yyy: real 0m0.029s user 0m0.026s sys 0m0.002s
./yyy: real 0m0.028s user 0m0.026s sys 0m0.001s
./yyy: real 0m0.031s user 0m0.026s sys 0m0.002s
./yyy: real 0m0.028s user 0m0.026s sys 0m0.001s
./yyy: real 0m0.030s user 0m0.026s sys 0m0.002s
./yyy: real 0m0.028s user 0m0.026s sys 0m0.001s
./zzz: real 0m0.030s user 0m0.027s sys 0m0.002s
./zzz: real 0m0.029s user 0m0.027s sys 0m0.001s
./zzz: real 0m0.030s user 0m0.027s sys 0m0.002s
./zzz: real 0m0.029s user 0m0.027s sys 0m0.001s
./zzz: real 0m0.030s user 0m0.027s sys 0m0.002s
./zzz: real 0m0.029s user 0m0.027s sys 0m0.001s
./zzz: real 0m0.030s user 0m0.027s sys 0m0.002s
./zzz: real 0m0.029s user 0m0.027s sys 0m0.001s
./zzz: real 0m0.030s user 0m0.027s sys 0m0.002s
./zzz: real 0m0.029s user 0m0.027s sys 0m0.001s
./zzz: real 0m0.030s user 0m0.027s sys 0m0.002s
Osiris JL:

我没有看到OCaml代码比C代码运行更快。 我在读取的文件中使用了较小的数字运行测试，并且结果同样有利于C代码:
停止编号：345
ocaml xxx.ml: real 0m0.027s user 0m0.020s sys 0m0.005s
ocaml xxx.ml: real 0m0.021s user 0m0.016s sys 0m0.005s
ocaml xxx.ml: real 0m0.025s user 0m0.016s sys 0m0.004s
ocaml xxx.ml: real 0m0.020s user 0m0.015s sys 0m0.003s
ocaml xxx.ml: real 0m0.022s user 0m0.016s sys 0m0.004s
ocaml xxx.ml: real 0m0.019s user 0m0.015s sys 0m0.003s
ocaml xxx.ml: real 0m0.021s user 0m0.016s sys 0m0.004s
ocaml xxx.ml: real 0m0.020s user 0m0.015s sys 0m0.004s
ocaml xxx.ml: real 0m0.021s user 0m0.016s sys 0m0.004s
ocaml xxx.ml: real 0m0.020s user 0m0.015s sys 0m0.004s
ocaml xxx.ml: real 0m0.021s user 0m0.016s sys 0m0.004s
./xxx: real 0m0.003s user 0m0.001s sys 0m0.002s
./xxx: real 0m0.003s user 0m0.001s sys 0m0.001s
./xxx: real 0m0.003s user 0m0.001s sys 0m0.001s
./xxx: real 0m0.002s user 0m0.001s sys 0m0.001s
./xxx: real 0m0.003s user 0m0.001s sys 0m0.001s
./xxx: real 0m0.005s user 0m0.001s sys 0m0.002s
./xxx: real 0m0.003s user 0m0.001s sys 0m0.002s
./xxx: real 0m0.003s user 0m0.001s sys 0m0.001s
./xxx: real 0m0.003s user 0m0.001s sys 0m0.001s
./xxx: real 0m0.003s user 0m0.001s sys 0m0.001s
./xxx: real 0m0.003s user 0m0.001s sys 0m0.001s
./yyy: real 0m0.002s user 0m0.000s sys 0m0.001s
./yyy: real 0m0.003s user 0m0.000s sys 0m0.001s
./yyy: real 0m0.002s user 0m0.000s sys 0m0.001s
./yyy: real 0m0.002s user 0m0.000s sys 0m0.001s
./yyy: real 0m0.002s user 0m0.000s sys 0m0.001s
./yyy: real 0m0.002s user 0m0.000s sys 0m0.001s
./yyy: real 0m0.002s user 0m0.000s sys 0m0.001s
./yyy: real 0m0.001s user 0m0.000s sys 0m0.001s
./yyy: real 0m0.002s user 0m0.000s sys 0m0.001s
./yyy: real 0m0.002s user 0m0.000s sys 0m0.001s
./yyy: real 0m0.003s user 0m0.000s sys 0m0.002s
./zzz: real 0m0.002s user 0m0.000s sys 0m0.001s
./zzz: real 0m0.002s user 0m0.000s sys 0m0.001s
./zzz: real 0m0.002s user 0m0.000s sys 0m0.001s
./zzz: real 0m0.002s user 0m0.000s sys 0m0.001s
./zzz: real 0m0.002s user 0m0.000s sys 0m0.001s
./zzz: real 0m0.002s user 0m0.000s sys 0m0.001s
./zzz: real 0m0.001s user 0m0.000s sys 0m0.001s
./zzz: real 0m0.002s user 0m0.000s sys 0m0.001s
./zzz: real 0m0.003s user 0m0.000s sys 0m0.002s
./zzz: real 0m0.002s user 0m0.000s sys 0m0.001s
./zzz: real 0m0.002s user 0m0.000s sys 0m0.001s

停止编号：87654

ocaml xxx.ml: real 0m0.102s user 0m0.059s sys 0m0.041s
ocaml xxx.ml: real 0m0.102s user 0m0.059s sys 0m0.040s
ocaml xxx.ml: real 0m0.101s user 0m0.060s sys 0m0.040s
ocaml xxx.ml: real 0m0.103s user 0m0.059s sys 0m0.041s
ocaml xxx.ml: real 0m0.102s user 0m0.059s sys 0m0.041s
ocaml xxx.ml: real 0m0.101s user 0m0.059s sys 0m0.041s
ocaml xxx.ml: real 0m0.102s user 0m0.059s sys 0m0.040s
ocaml xxx.ml: real 0m0.103s user 0m0.059s sys 0m0.040s
ocaml xxx.ml: real 0m0.101s user 0m0.059s sys 0m0.040s
ocaml xxx.ml: real 0m0.102s user 0m0.059s sys 0m0.040s
ocaml xxx.ml: real 0m0.105s user 0m0.059s sys 0m0.041s
./xxx: real 0m0.092s user 0m0.044s sys 0m0.038s
./xxx: real 0m0.087s user 0m0.044s sys 0m0.039s
./xxx: real 0m0.085s user 0m0.044s sys 0m0.038s
./xxx: real 0m0.084s user 0m0.044s sys 0m0.038s
./xxx: real 0m0.085s user 0m0.044s sys 0m0.039s
./xxx: real 0m0.086s user 0m0.045s sys 0m0.039s
./xxx: real 0m0.085s user 0m0.044s sys 0m0.039s
./xxx: real 0m0.085s user 0m0.044s sys 0m0.038s
./xxx: real 0m0.084s user 0m0.044s sys 0m0.038s
./xxx: real 0m0.084s user 0m0.044s sys 0m0.039s
./xxx: real 0m0.083s user 0m0.044s sys 0m0.038s
./yyy: real 0m0.004s user 0m0.003s sys 0m0.001s
./yyy: real 0m0.004s user 0m0.003s sys 0m0.001s
./yyy: real 0m0.004s user 0m0.003s sys 0m0.001s
./yyy: real 0m0.004s user 0m0.003s sys 0m0.001s
./yyy: real 0m0.005s user 0m0.003s sys 0m0.001s
./yyy: real 0m0.005s user 0m0.003s sys 0m0.001s
./yyy: real 0m0.004s user 0m0.003s sys 0m0.001s
./yyy: real 0m0.004s user 0m0.003s sys 0m0.001s
./yyy: real 0m0.004s user 0m0.003s sys 0m0.001s
./yyy: real 0m0.004s user 0m0.003s sys 0m0.001s
./yyy: real 0m0.006s user 0m0.003s sys 0m0.002s
./zzz: real 0m0.004s user 0m0.003s sys 0m0.001s
./zzz: real 0m0.004s user 0m0.003s sys 0m0.001s
./zzz: real 0m0.004s user 0m0.003s sys 0m0.001s
./zzz: real 0m0.004s user 0m0.003s sys 0m0.001s
./zzz: real 0m0.004s user 0m0.003s sys 0m0.001s
./zzz: real 0m0.005s user 0m0.003s sys 0m0.002s
./zzz: real 0m0.004s user 0m0.003s sys 0m0.001s
./zzz: real 0m0.004s user 0m0.003s sys 0m0.001s
./zzz: real 0m0.004s user 0m0.003s sys 0m0.001s
./zzz: real 0m0.004s user 0m0.003s sys 0m0.001s
./zzz: real 0m0.005s user 0m0.003s sys 0m0.001s

显然，你的经验可能会有所不同 - 但似乎OCaml比C要慢得多，但如果给定文件中的数字足够小，则启动和文件读取会占据处理时间的主导地位。

C的计时，特别是在较小的数字上，非常快，它们并不是那么可靠。

FYI，这两者似乎都没有产生巨大的性能差异。虽然使用fscanf会使代码更易读！ - Jason Baker
1
有趣的是：正如我在主要问题的评论中所问 - 你得到的数字有多大？如果迭代N次会发生什么（其中N足够大，以使最快的程序需要几秒钟的时间）？不要忘记如果您进行了10,000次迭代，则需要关闭文件。 - Jonathan Leffler
2
在这样一个小程序中，很难猜测事情为什么会发展成这样。如果我在做的话，我会像这样编写代码（暂时忽略错误检查）：
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv) { 
    static char buffer[20];   
    int limit, i;

    freopen(argv[1], "r", stdin);
 fgets(buffer, sizeof(buffer), stdin);
    limit = atoi(buffer);

    for (i=1; i<=limit; i++) {
        int div3=i%3==0;
        int div5=i%5==0;
        if (div3 && div5) 
            puts("Hop");
        else if (div3)
            puts("Hoppity");
        else if (div5)
            puts("HopHop");
    }
    return 0;
}

使用 freopen 可以避免创建另一个文件流，而是将标准输入连接到指定的文件。不能保证它更快，但它很可能不会更慢。

同样，好的编译器可能会注意到在循环体内 i 是常量，并将两个余数操作因式分解，因此只需要执行一次。这里我手动完成了这项工作，这可能不会更快，但几乎肯定不会更慢。

使用 puts 而不是 printf 相当类似 —— 它可能不会更快，但它几乎肯定不会更慢。使用 printf 的方式，它必须扫描整个字符串寻找 '%', 这样才能确定是否有转换，但由于 puts 不进行任何转换，因此不需要这么做。

对于这样一个微小的程序来说，还有一个可能更重要的因素： puts 通常比 printf 要小得多。你没有说明如何计时，但如果包括加载代码的时间，实际上非常小的代码可能比执行时间更有影响力。

1

我很想知道在get_count()函数里花费了多少时间。

我不确定这会有多大的影响，但是您正在将long作为字符串读入，这意味着该字符串不能超过20个字节或10个字节（2 ^ 64 =一些20个字符长的十进制数，或2 ^ 32 =一些10个字符长的十进制数），因此您不需要在get_count中使用while循环。此外，您可以在堆栈上分配file_text，而不是调用calloc-但我想您仍然需要将其清零，或以其他方式找到长度并将最后一个字节设置为null。

file_length = lseek(fileptr, 0, SEEK_END);
有趣的观点。我想一遍又一遍地重新分配内存肯定非常低效。我想我只需要熟悉C语言的性能分析器。 :-) - Jason Baker
使用Jonathan上面提到的fscanf建议来读取本地变量，似乎并没有产生很大的差异。 - Jason Baker
1
任何主要涉及打开文件和读取文件的程序都受到打开文件和读取文件速度的限制。在这里进行的C计算将花费打开文件和读取文件时间的百万分之一到千分之一的时间。
我认为这个网站很有用：http://norvig.com/21-days.html#answers
如果这是真的，那么C和OCaml之间就不会存在这样的差异（因为两者都受到磁盘IO的限制）。OP已经表明，当他将优化级别提高时，C代码运行速度大大加快，因此我怀疑这可能是问题所在。 - Chris Lutz
但是访问文件所需的时间完全是随机的。如果文件仍然被缓存，那么所需的时间将比程序冷启动时要少得多。如果他先运行OCaml，然后再运行C，那么C可能会获胜。如果他连续一百万次运行C程序，平均时间将显著降低。 - user181548
@Kinopiko - 我实际上是在对同一文件的副本运行这些操作。 - Jason Baker
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接