Haskell与C的linspace函数性能对比及代码问题排查求助

linspace函数需实现以下逻辑：接受起始值Start、结束值End和可选参数Steps，输出首元素为Start、末元素为End的均匀数值列表，结果长度为Steps+1，与MATLAB的linspace行为一致。分别用Haskell和C实现该函数后，C版本性能远超Haskell，现需排查Haskell代码的性能瓶颈。

补充信息 #

• C编译命令：gcc -o linspace linspace.c，gcc版本12.2.0
• Haskell编译命令：ghc -O2 -o linspace linspace.hs，ghc版本9.0.2
• 基准测试命令：time linspace 0 10 100000
• 测试结果：
  C（测试1）：

  real    0m0.187s
  user    0m0.076s
  sys 0m0.012s
  

  C（测试2）：

  real    0m0.132s
  user    0m0.068s
  sys 0m0.010s
  

  Haskell版本运行极慢，耗时远超C版本。

原Haskell代码 #

{-# LANGUAGE BangPatterns #-}

import System.Environment

linspace :: Fractional a => a -> a -> Maybe Int -> [a]
linspace start end maybe = linspace' [] 0
  where
    stepCount =
        case maybe of
            Just i
                | i > 0 -> i
                | otherwise -> errorWithoutStackTrace "Number of steps must be > 0"
            Nothing -> 100
    stepSize = abs $ (end - start) / (fromIntegral stepCount)
    linspace' !acc n
        | n > stepCount = acc
        | otherwise =
            let !el = start + stepSize * (fromIntegral n)
             in linspace' (acc ++ [el]) (n + 1)

main = do
    argv <- getArgs
    let argc = length argv
    if argc /= 2 && argc /= 3
        then errorWithoutStackTrace "linspace <start> <end> [steps]"
        else return ()
    let start = read $ argv !! 0 :: Double
        end = read $ argv !! 1 :: Double
        steps =
            if argc == 3
                then Just $ read (argv !! 2) :: Maybe Int
                else Nothing
    putStrLn . show $ linspace start end steps

原C代码 #

#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <math.h>

int
main (int argc, char **argv) {
    if (argc != 3 && argc != 4) {
        fprintf(stderr, "Usage: linspace <start> <end> [steps]\n");
        return EXIT_FAILURE;
    }
    errno = 0;
    double start, end;
    int steps;
    start = strtod(argv[1], NULL);
    if (errno) {
        perror(argv[1]);
        return EXIT_FAILURE;
    }
    errno = 0;
    end = strtod(argv[2], NULL);
    if (errno) {
        perror(argv[2]);
        return EXIT_FAILURE;
    }
    errno = 0;
    if (argc == 4) {
        steps = (int) strtol(argv[3], NULL, 10);
        if (errno) {
            perror(argv[3]);
            return EXIT_FAILURE;
        } else if (steps <= 0) {
            fprintf(stderr, "Number of steps must be > 0\n");
            return EXIT_FAILURE;
        }
    } else
        steps = 100;
    
    double stepSize;
    stepSize = fabs((start - end) / steps);
    double *vals;
    vals = malloc(sizeof(double) * (steps + 1));
    for (int i = 0; i <= steps; i++) {
        vals[i] = start + stepSize * i;
    }
    printf("[");
    for (int i = 0; i <= steps; i++) {
        if (i == steps)
            printf("%f", vals[i]);
        else
            printf("%f, ", vals[i]);
    }
    printf("]\n");
}

性能瓶颈分析 #

Haskell代码的核心性能问题在于列表构建方式：
原代码使用acc ++ [el]来累加构建列表。Haskell的列表是单链表结构，++操作需要遍历整个左列表（acc）才能将新元素追加到末尾，每次操作的时间复杂度为O(k)（k为当前acc的长度）。当Steps为100000时，总时间复杂度为O(n²)，这会导致运行时间急剧增加。

优化方案 #

方案1：反向构建列表后反转 #

利用(:)操作（常数时间复杂度）反向构建列表，最后通过reverse（线性时间复杂度）转为正确顺序，整体时间复杂度降为O(n)：

{-# LANGUAGE BangPatterns #-}

import System.Environment

linspace :: Fractional a => a -> a -> Maybe Int -> [a]
linspace start end maybe = reverse $ linspace' [] 0
  where
    stepCount =
        case maybe of
            Just i
                | i > 0 -> i
                | otherwise -> errorWithoutStackTrace "Number of steps must be > 0"
            Nothing -> 100
    stepSize = abs $ (end - start) / (fromIntegral stepCount)
    linspace' !acc n
        | n > stepCount = acc
        | otherwise =
            let !el = start + stepSize * (fromIntegral n)
             in linspace' (el : acc) (n + 1)

main = do
    argv <- getArgs
    let argc = length argv
    if argc /= 2 && argc /= 3
        then errorWithoutStackTrace "linspace <start> <end> [steps]"
        else return ()
    let start = read $ argv !! 0 :: Double
        end = read $ argv !! 1 :: Double
        steps =
            if argc == 3
                then Just $ read (argv !! 2) :: Maybe Int
                else Nothing
    putStrLn . show $ linspace start end steps

方案2：使用列表生成式 #

Haskell的列表生成式会被GHC优化为高效的循环实现，代码更简洁且性能优异：

{-# LANGUAGE BangPatterns #-}

import System.Environment

linspace :: Fractional a => a -> a -> Maybe Int -> [a]
linspace start end maybe = [ start + stepSize * fromIntegral n | n <- [0..stepCount] ]
  where
    stepCount =
        case maybe of
            Just i
                | i > 0 -> i
                | otherwise -> errorWithoutStackTrace "Number of steps must be > 0"
            Nothing -> 100
    stepSize = abs $ (end - start) / (fromIntegral stepCount)

main = do
    argv <- getArgs
    let argc = length argv
    if argc /= 2 && argc /= 3
        then errorWithoutStackTrace "linspace <start> <end> [steps]"
        else return ()
    let start = read $ argv !! 0 :: Double
        end = read $ argv !! 1 :: Double
        steps =
            if argc == 3
                then Just $ read (argv !! 2) :: Maybe Int
                else Nothing
    putStrLn . show $ linspace start end steps

额外优化建议 #

如果需要进一步提升输出性能，可以替换show函数为手动格式化输出（类似C版本的printf），避免show生成大量字符串带来的开销。

内容的提问来源于stack exchange，提问作者EmErAJID