当 Haskell 比 C 快的时候 _Linux伊甸园开源社区-24小时滚动更新开源资讯，全年无休！

传统观点认为没有哪种编程语言能比C语言更快，所有更高级的语言（比如Haskell）注定更慢，因为它们离真实的机器更远。

——传统观点是错误的。没有哪种语言可以打败高度微优化的C语言，但是日常中使用的C代码却不是这样的，而是比微优化的代码慢好几倍。同时高级语言Haskell意味着编译器已经在很多方面做了微优化。结果就是通常情况下日常使用的Haskell代码要比C代码快。当然，并不总是如此，但是已经足够让两者之间的速度差异变得不那么明显，除非你打算自己去做很多微优化。

这一观点似乎已经在计算机语言测试游戏(又名Shootout)中被证实，在游戏中采集了多种用不同语言编写的程序的执行速度和内存占用数据。赢家通常是高度优化的C语言版本。很多程序的Haskell版本通常是轻微落后于C版本。此外如果你阅读Haskell会发现它已经是高度优化，以至于看起来都不像Haskell了。相反它读起来像C语言翻译成的Haskell。在此基础上，你大概会得到结论，日常使用的Haskell（在这些场景中Haskell的优势体现在语言简洁、正确性和可组合性）真是无可救药的慢啊。

但是我后来拜读Tony Albrench的演说后，他讨论有关于通用的C++代码看起来似乎是非常低效的。两件事情极其吸引我的眼球：

1、当存在花费400周期的缓存时，需要从主内存取出。尤其是准备填充缓存行的间接指针，并且强调增加丢失缓存覆盖的数量。

2、一个对分支错误的预测将会浪费20个周期。一个分支逃离简单计算事实上会比计算本身运行更慢。

从另外一个角度说，C语言不再是接近真实机器的一门语言。真实机器有三个CPU等级缓存（其中它们会共享多核），长指令管道行，预测分支，多个ALUs和FPUs，当程序被执行时，为了以这种方式调度使得它看起来像一个简单处理器任一时刻正在执行某个指令，那么硬件数据流需要实时分析。C语言并不会暴露所有代码给程序员，所以在我看来，编写高度优化代码的唯一方法是拥有一个复杂处理器模型和储存架构，取决于你期望机器所做的，然后C语言的逆向工程师将会把它变成现实。结果是难以理解的，所以也就难以把握。看一下C语言安装出现的问题，就像我所表达的一样。

但是大多数代码并不是这样编写的。Tony Albrecht 是一个游戏程序员，一个压缩循环方面的专家。大多数开发者不会生活在那种世界里。对于他们来说，目标就是编写满足需求的代码，越快越好。这不是懒惰或者浪费，而是锻炼。首要设计优化算法，然后实现地道代码。只有运行速度不够快你才会去详细分析和微小优化。不仅仅是微小优化自身过程是昂贵的，而且以后使得代码难以维护。

所以我很好奇：高级的Haskell 给定的编译器比C语言更多机会去进行微小优化。因此，与此相比，当阅读性比原始速度更重要这种可能发生时，它是比较明智且通用的排序。我想比较程序是否足够强大地拥有一个有效的混合工作去解决一个问题，但是足够小地使得我可以快速编写Haskell和C版本。经过打探枪战网站后，我定位在反向互补的问题上。

一个潜在的问题是，我的程序可能会不经意地使用非最佳化方法。所以我决定要分析代码，并且移除拖慢运行速度的部分代码，但是不会改变程序结构或者为了速度而增加复杂性。我记住写的是Haskell和C版本。我也会下载一些枪战得住的作品参考。你可以看到我这篇文章的底部代码。

第一版的Haskell代码需要30秒（相比于0.6秒的启动时间）。正如我所担心的，性能剖析（profilling）确实揭露了代码中一些导致速度慢的点。为了过滤掉输入中的回车，我使用了“isLetter”函数，但是不像C语言中中char类型，Haskell的Char类型覆盖了整个Unicode，所以判断输入字符是否是一个字母的开销就不再是可以忽略不计的。我将过滤操作放在整个输入操作完成之后，比较结果是否为0,，如果输入包含非法字符，这种过滤方式将会使程序更快。我将这个问题修正后，程序耗时迅速下降到可以接受的4.3秒。有趣的是，性能剖析表明有近一半的时间消耗在写出这60行字母；仅输出结果而不换行的话，运行时间将缩短到2秒。

同时C语言的版本消耗8.2秒。性能剖析并没有直接指出原因所在，但是它似乎暗示着处理器将大部分时间花在其他地方而不是我的代码。我强烈怀疑时间是花在 putc(3)和getc(3)这两个函数调用上。显而易见可以优化成fread(3) 和 fwrite(3)来成块的读和写字符，但是这需要较大幅度的改动代码；还有额外的运算需要用来处理下一个序列的开始（由一个“>”字符标志），当在一个块中发现这个字符，则需要插入相应的换行符。不像在Haskell中对isLetter的替代，这种解决方案需要新增变量和控制逻辑，而不只是切换成一个简单较少消耗的表达式。

没有做出那些改变，我会倾向于支持C，任何一个C程序员在面对运行缓慢的代码时都会这样认为。如果 isLetter非常地慢，跟 putc(3) 和 getc(3) 不一样？那么我认为就是有明显区别的。两个程序都是面向字符的方式写的，因为问题被描述成字符。我用C写了内循环链表的块，因为它看起来像一个更快、更简单的选择，而不是整个字符串被复制到一个新的缓冲区大小，每次都溢出的两倍（该算法平均每个字符复制一次或两次；细节请查看Knuth）。我可能会考虑反转字符串顺序来读写，而不是在一个单独的函数中做内存的逆转，但是性能分析没有显示在时间上有重大变化。总的来说，还是从C中获得了不错的性能，在代码量上也是相当的。

在另一方面，Haskell也是具有良好性能的，且开箱即用，因为编译器自动化了许多微优化，而C会迫使你手动去完成。作为一个人类，我们也可以做得同样地好，但是它能自动化来做，那是相当不错的。

这不是原则上关于代码数量问题，但是对于记录来说，Haskell有42个SLOC，其中21个是可执行的。C语言有115个SLOC，其中有63个可执行的。枪版的C语言冠军有70个SLOC，其中46个是可执行的（计数分隔语句为每行作为单个语句）。

所以这是底行。如果你真的需要你的代码运行速度尽可能地快，并且你计划花费你的开发时间来进行分析和优化，那就行动吧，而且就用C语言来编写，因为没有其他语言（汇编除外）给予你需要的等级控制。但是如果你没有计划做大量优化你并不需要C语言。Haskell将会给你同等的性能，甚至更好，同时削减你的开发和维护成本至75%~90%。

更新：这是编译器和运行指令：

            
                        ghc -main-is HaskellText -O2  -fllvm -funbox-strict-fields HaskellText.hs
gcc -O2 naive-c.c -o naive
time ./HaskellText < big-fasta.txt > /dev/null
time ./naive < big-fasta.txt > /dev/null

这是它的价值所在，下面是两个程序的代码.

第一个Haskell：

            
                
                        
                        module HaskellText (main) where
 
import Control.Applicative
import Control.Monad
import Data.ByteString.Lazy.Char8 (ByteString)
import qualified Data.ByteString.Lazy.Char8 as B
import Data.Char
import Data.Int
import Data.Vector.Unboxed (Vector, (!), (//))
import qualified Data.Vector.Unboxed as V
import Data.Word
import System.IO
 
-- | A block requiring the reverse complement.  The first element is the
-- header string. The second element is the actual data.
data Block = Block ByteString ByteString
 
main :: IO ()
main = getBlocks >>= mapM_ (writeBlock . reverseComplement)
 
-- | Write a block to stdio with line breaks.
writeBlock :: Block -> IO ()
writeBlock (Block name txt) = do
      putChar '>'
      B.putStrLn name
      mapM_ B.putStrLn $ splitEvery 60 txt
 
 
-- | A utility function that ought to be part of the bytestring library.
splitEvery :: Int64 -> ByteString -> [ByteString]
splitEvery n t = go t
  where
    go t = if (not $ B.null t2) then t1 : go t2 else [t1]
      where (t1, t2) = B.splitAt n t
 
 
-- | Read a series of blocks, each of which starts with a '>' character.
getBlocks :: IO [Block]
getBlocks = map mkBlock . drop 1 . B.split '>' <$> B.getContents
   where
      mkBlock bs1 = Block h t
        where (h, t) = B.break (== '\n') bs1
  
 
reverseComplement :: Block -> Block
reverseComplement (Block name codes) =
   Block name
   $ B.filter (/= '\0')
   $ B.map (V.unsafeIndex tbl . ord)
   $ B.reverse codes
   where
      tbl = V.replicate 256 '\0' //
            map (first ord) (pairs ++ map (first toLower) pairs)
      pairs = [('A', 'T'),('C', 'G'),('G', 'C'),('T', 'A'),
               ('M', 'K'),('R', 'Y'),('W', 'W'),('S', 'S'),
               ('Y', 'R'),('K', 'M'),('V', 'B'),('H', 'D'),
               ('D', 'H'),('B', 'V'),('N', 'N')]
      first f (x,y) = (f x, y)

                    

            
            

现在是C的。很抱歉，关于丢失在#包含文件的brokets；这个博主不会对他们做出让步，甚至当我尝试直接编写HTML。

            
                
                        
                        #include stdio.h
#include stdlib.h
#include strings.h
 
 
#define BLOCKLEN 1024
#define TITLELEN 132
#define LINELEN 60
 
typedef struct block_struct {
  int len;
  char text [BLOCKLEN];
  struct block_struct *next;
} Block;
 
/* Here to get them profiled */
int my_getc (FILE *stream) {
  return (getc(stream));
}
 
int my_putc (int c, FILE *stream) {
  return (putc(c,stream));
}
 
 
/* Initialised by calls to setComplement. Holds the complement codes. */
static char complement[256];
 
void setComplement(char c1, char c2) {
  complement [c1] = c2;
  complement [c2] = c1;
  complement [c1 | 0x20] = c2;
  complement [c2 | 0x20] = c1;
}
 
 
 
/* Reverse-complement block in-place */
void reverseComplementBlock (Block *block) {
  char *ptr1;
  char *ptr2;
  char c;
 
  ptr1 = &(block->text[0]);
  ptr2 = &(block->text[block->len - 1]);
  while (ptr1 <= ptr2) {
    c = complement [*ptr1];
    *ptr1 = complement [*ptr2];
    *ptr2 = c;
    ptr1++;
    ptr2--;
  }
}
 
/*
  Read blocks up to either the next ">" or EOF. Create a chain of
  blocks in reverse order of reading.
*/
Block *readBlocks () {
  char c;
  int i;
  Block *result;
  Block *old;
 
  old = NULL;
  result = NULL;
  c = ' ';
  while (c != '>' && !feof (stdin)) {
    result = malloc (sizeof (Block));
    i = 0;
    while (i < BLOCKLEN && !feof (stdin)) {
      c = (char)my_getc(stdin);
      if (c == '>') {
    ungetc (c, stdin);
    break;
      }
      if (c >= ' ') { // Drop line breaks.
    result->text[i++] = c;
      }
    }
    result->len = i;
    result->next = old;
    old = result;
  }
  return result;
}
 
 
int process_sequence () {
 
  char title[TITLELEN];
  Block *ptr;
  Block *old_ptr;
  int i;
  int cpos;
 
  if (!feof(stdin)) {
    fgets (title, TITLELEN, stdin);
  } else {
    return 0;
  }
 
  if (index (title, '\n') == NULL) {
    while (my_getc (stdin) != '\n') {}
  }
 
  ptr = readBlocks ();
 
  printf("%s", title);
 
  cpos = 0;
  while (ptr != NULL) {
    reverseComplementBlock (ptr);
    for (i = 0; i < ptr->len; i++) {
      if (cpos++ == 60) {
    my_putc ('\n',stdout);
    cpos = 1;
      }
      my_putc (ptr->text[i], stdout);
    }
    old_ptr = ptr;
    ptr = ptr->next;
    free (old_ptr);
    /* Beware; the obvious "for" loop would free the block and then
       dereference it to move to the next one. */
  }
 
  my_putc ('\n',stdout);
  return 1;
}
 
void main () {
 
  int i;
  char title[TITLELEN];
 
  for (i = 0; i < 256; i++) {
    complement [i] = 0;
  }
  setComplement ('A', 'T');
  setComplement ('C', 'G');
  setComplement ('M', 'K');
  setComplement ('R', 'Y');
  setComplement ('W', 'W');
  setComplement ('S', 'S');
  setComplement ('V', 'B');
  setComplement ('H', 'D');
  setComplement ('N', 'N');
 
  while (process_sequence ()) {}
}

                    

            
            

新闻

软件

博客

论坛

商城

人才

广告

联系

投稿

3G Eden

RSS

当 Haskell 比 C 快的时候