performance - 当数组大于 800,000,000 时，我的 Fortran 筛选会显着减慢

Question

我是一名物理学家，最近我经常使用 Fortran。最初我广泛使用 Java 来娱乐，因为它是我学习的第一种语言，但我已经放弃了它，转而使用 Fortran 和 C++。我对素数有业余爱好，所以我创建了一个素数筛。我能够在 15 秒内找到最大为 2^31 的所有质数。这是 Java 的最大数组大小，所以到此结束。我小心地移植了代码(我的意思是小心，我很沮丧我的代码很慢而且我找不到错误，我将我的 Fortran 代码移植回 Java 以验证这不是我的错，然后将它移植回来Fortran，删除每次迭代!)。问题是大约 800,000,000 个 Fortran 将停止运行。到目前为止，它击败了 Java，但在那之后它非常慢。我花了几个小时绘制它并拟合曲线。它的速度呈指数级增长，可能需要数百年才能解决到 Java 级别。我问了很多人都没有用。为什么这会发生在我身上？!？!有没有聪明的 Fortran 编码员可以帮助我？我正在运行 2013 年末 i5 的 Macbook Pro。我的代码如下。

program sieve
integer(4),allocatable:: prime(:)
integer(4)::a,max,b,primeCount
write(*,*)"Welcome to the slow prime number sieve!"
write(*,*)"--------------------------------------------"
write(*,*)"Up to what numbers do you need to find primes for?"
write(*,*)"Enter a number below 2^(32-1)"
read*, max

primeCount=0
allocate(prime(max))
prime(1)=1

    do a=2,int(sqrt(real(max))) !the main loop
        if(prime(a)==0)then !if the number is marked as prime procede
            do b=2*a,max,a  !eliminate all the numbers that are multiples of the number
                if(prime(b)==0)then !but only spend time eliminating if the number is still marked prime
                    prime(b)=1
                end if
            end do
        end if
    end do

do a=1,max
    if(prime(a)==0)then
        primeCount=primeCount+1
    end if
end do

print*, primeCount

end program

编辑:我的机器安装了 4 Gigs ram

Answer 1

我可以看到您可以采取一些措施来加速代码，尽管它们似乎都无法解释您遇到的性能急剧下降。最有可能的罪魁祸首似乎是 Alexander Vogt 所建议的 RAM 限制。

你应该做的第一件事是改变prime来自 integer至 logical大批。这减少了内存需求并加快了 if (prime(a)==0) 的评估速度。 .

代码的相关部分将如下所示

logical(1),allocatable:: prime(:)

primeCount=0
allocate(prime(max))
prime = .false.
prime(1)=.true.

    do a=2,int(sqrt(real(max))) !the main loop
        if(.not. prime(a))then !if the number is marked as prime procede
            do b=2*a,max,a  !eliminate all the numbers that are multiples of the number
                if(.not. prime(b))then !but only spend time eliminating if the number is still marked prime
                    prime(b)=.true.
                end if
            end do
        end if
    end do

do a=1,max
    if(.not. prime(a))then
        primeCount=primeCount+1
    end if
end do

如果你声明 prime(1:max)=0，我不会做任何 Java 编程，但会在 Matlab 中进行。然后只在 0 之间切换值和 1我认为 Matlab 将数组视为 logical大批。 Java 可能也在做同样的事情。这可以解释为什么您的 Java 代码不会受到性能下降的影响(假设 RAM 约束确实是问题所在)。

编辑:我做了一些实验。

在我的机器上(Debian Linux 64bit, i3, 16GB RAM, ifort 14 with default flags)， max=800 million (8E8) 用了 22 秒. max=2E9 用了 60 秒.这不是问题中报告的小时数。同样在每种情况下 prime数组恰好被初始化为零。

此外使用 integer(1)使程序运行速度比使用 integer(4) 快 33% .与 logical(1)它的运行速度比 integer(1) 快不到 5% .这种行为可能是由于更好地使用现金作为 prime 的每个元素占用更少的内存空间，因此处理器可以对当前现金数据进行大量迭代，以更快的速度通过循环。

我从中得出的结论是，罪魁祸首是 Alexander Vogt 指出的 RAM 不足，并且作者的体验很可能不会受到忽略初始化 prime 的影响。正如 HighPerformanceMark 指出的那样，数组(尽管这绝对不应该发生)。此外，我怀疑 Java 声明了 prime作为一个逻辑数组，这就是为什么没有出现问题的原因。 (尽管在 Java 中 15 秒内 2^31？这里使用的 Fortran 代码与此相去甚远。真的是比较相同的代码吗？)