如何优化这个毕达哥拉斯三元组的实现

Question

这是haskell代码

import GHC.Int

triples = [(x, y, z) | z <- [(1::Int32)..],
                       x <- [(1::Int32) .. z + 1],
                       y <- [x.. z + 1],
                       x * x + y * y == z * z]

main = mapM_ print (Prelude.take 1000 triples)

其中有以下配置文件

       triples +RTS -p -RTS

    total time  =       47.10 secs   (47103 ticks @ 1000 us, 1 processor)
    total alloc = 62,117,115,176 bytes  (excludes profiling overheads)

COST CENTRE MODULE    SRC                      %time %alloc

triples     Main      triples.hs:(5,1)-(8,46)  100.0  100.0

                                                                              individual      inherited
COST CENTRE  MODULE                SRC                     no.     entries  %time %alloc   %time %alloc

MAIN         MAIN                  <built-in>              118          0    0.0    0.0   100.0  100.0
 CAF         Main                  <entire-module>         235          0    0.0    0.0   100.0  100.0
  main       Main                  triples.hs:10:1-46      236          1    0.0    0.0     0.0    0.0
  triples    Main                  triples.hs:(5,1)-(8,46) 237          1  100.0  100.0   100.0  100.0
 CAF         GHC.Conc.Signal       <entire-module>         227          0    0.0    0.0     0.0    0.0
 CAF         GHC.IO.Encoding       <entire-module>         216          0    0.0    0.0     0.0    0.0
 CAF         GHC.IO.Encoding.Iconv <entire-module>         214          0    0.0    0.0     0.0    0.0
 CAF         GHC.IO.Handle.FD      <entire-module>         206          0    0.0    0.0     0.0    0.0
 CAF         GHC.IO.Handle.Text    <entire-module>         144          0    0.0    0.0     0.0    0.0
 main        Main                  triples.hs:10:1-46      238          0    0.0    0.0     0.0    0.0

而等效的 rust 代码运行速度快一个数量级。这对我来说很奇怪。

fn triples() -> impl Iterator<Item=(i32, i32, i32)> {
    (1..).flat_map(|z| {
        (1..z + 1).flat_map(move |x| {
            (x..z + 1).filter_map(move |y| {
                if x * x + y * y == z * z {
                    Some((x, y, z))
                } else {
                    None
                }
            })
        })
    })
}

fn main() {
    for triple in triples().take(1000) {
        println!("{:?}", triple);
        // unsafe {printf("(%i, %i, %i)\n".as_ptr() as *const i8, x, y, z)};
    }
}

结果是

[I] ~/c/pythagoras (master|✚1…) $ time ./range > /dev/null
0.16user 0.00system 0:00.16elapsed 100%CPU (0avgtext+0avgdata 2248maxresident)k
0inputs+0outputs (0major+124minor)pagefaults 0swaps
[I] ~/c/pythagoras (master|✚1…) $ time ./triples > /dev/null
2.39user 0.00system 0:02.39elapsed 99%CPU (0avgtext+0avgdata 4736maxresident)k
0inputs+0outputs (0major+473minor)pagefaults 0swaps

两个结果都带有 -O3 标志。

是否可以在保存惯用 haskell 代码的同时优化分配？也许一些融合库或其他东西可以做到这一点？

编辑1。好的，使用 Int 而不是 Int32 或 Int64 可以使代码更快，这很好。仍然使用 fflvm 它比 rust 慢两倍并且根据配置文件判断它仍然花费大部分时间在分配上。例如，是什么阻止了 haskell 重用三元组而不是只分配一次？

Answer 1

您的代码有两个问题：

为了性能，您应该编译没有分析，并且进行优化。分析会增加大量开销。在我的系统上 ghc -prof 导致超过 40 秒的运行时间，与您的时间类似。 ghc -O2 没有 -prof 只产生 4.2 秒。
在 64 位系统上使用 Int32。你不应该这样做，因为非本机大小的 Int 操作被编译为减慢 out-of-line primops。当我将 Int32 更改为 Int 时，运行时间变为 0.44 秒。如果我另外使用 -fllvm 作为 LLVM 代码后端，我会得到 0.2 秒。

Answer 2

也许改变你的实现？

triples = [(m^2-n^2,2*m*n,m^2+n^2) | m<-[2..], n<-[1..(m-1)]]

如何优化这个毕达哥拉斯三元组的实现

How to optimize this pythagoras triples implementation

optimization

haskell

allocation