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

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代码的同时优化分配？也许某些融合库或其他东西可以做到这一点？

EDIT1.好吧,使用Int代替Int32或Int64使代码更快,这是很好的.仍然使用fflvm它比生锈慢两倍并且通过配置文件来判断它仍然在大部分时间用于分配.是什么阻止了haskell重用三元组而不是只分配一次？

Answer 1

您的代码有两个问题:

1. 为了提高性能,您应该在不进行分析和优化的情况下进行编译.分析增加了显着的开销.在我的系统上ghc -prof,运行时间超过40秒,与您的时间相似.ghc -O2没有-prof收益只需4.2秒.

2. 使用Int3264位系统上.您不应该这样做,因为非本机大小的Int操作被编译为减慢了线外的primops.当我改为Int32时Int,运行时变为0.44秒.如果我另外-fllvm用于LLVM代码后端,我得到0.2秒.