比较C#、C++和Java的性能（C#的奇怪行为）

Question

比较C#、C++和Java的性能（C#的奇怪行为）

6

我正在使用C++、C#和Java实现Floyd-Warshall算法。在每种语言中，我都进行了顺序和并行实现。测试结果如下：
（流逝时间仅用于主功能和读取文件，变量初始化等不计入测量范围）
从这里下载源代码SourceCodes

C++

IDE：Netbeans
编译器：MinGW-4.8.1
顺序时间：9.333000
并行时间：2.539000
使用OpenMP实现并行

如果NumOfThreads=1，则为顺序，否则为并行

变量

#define n 1000 /* Then number of nodes */
double dist[n][n];

    void floyd_warshall(int NumOfThreads) {
    int i, j, k;
         omp_set_num_threads(NumOfThreads);
    for (k = 0; k < n; ++k)
       #pragma omp parallel for private(i,j)
        for (i = 0; i < n; ++i)
            for (j = 0; j < n; ++j)
                    if ((dist[i][k] * dist[k][j] != 0) && (i != j))
                     if ((dist[i][k] + dist[k][j] < dist[i][j]) || (dist[i][j] == 0))
                        dist[i][j] = dist[i][k] + dist[k][j];    }

Java

IDE: Netbeans
编译器: Netbeans默认
顺序时间: 11.632
并行时间: 3.089
-Xms512m -Xmx1024m
导入java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Future;

Java变量

 public final int numNodes =1000;

    public final double[][] costs= new double[numNodes][numNodes] ;

我没有在这里放置Java代码，因为它正常工作（我想）

c#

IDE：Visual Studio 2012
编译器：Visual Studio 2012默认
顺序时间：31.312
并行时间：8.920
使用System.Threading.Tasks;

变量

  const int n = 1000;
    static double[,] dist = new double[n, n];

并行代码

   static  void floyd_warshall(ParallelOptions pOp)
    {
        int k;     
        for (k = 0; k < n; ++k)
            Parallel.For<int>(0, n, pOp, () => 0, (i, loop, j) =>
                {
              for (j = 0; j < n; ++j)
               if ((dist[i, k] * dist[k, j] != 0) && (i != j))
                  if ((dist[i, k] + dist[k, j] < dist[i, j]) || (dist[i, j] == 0))
                            dist[i, j] = dist[i, k] + dist[k, j];
                    return 0;
                }, (j) => { });

单引号

 static void floyd_warshallSingle()
  {
      int i, j, k;
      for (k = 0; k < n; ++k)
          for (i = 0; i < n; ++i)
              for (j = 0; j < n; ++j)

                  if ((dist[i,k] * dist[k,j] != 0) && (i != j))

                      if ((dist[i,k] + dist[k,j] < dist[i,j]) || (dist[i,j] == 0))
                          dist[i,j] = dist[i,k] + dist[k,j];
  }

我的 C# 实现有什么问题？
所有使用同一个文件
现在我的问题是，为什么用 C# 解决这个算法需要更长的时间？Java 和 C++ 的运行时间几乎相同，但我认为我的 C# 实现有问题，因为 C# 和 C++ 之间的差异很奇怪！
请帮助我改进我的 C# 实现或指出一些原因。谢谢！

编辑1

我把数组改成了交错数组，结果如下：

顺序时间：19.22
并行时间：4.903

仍然存在 C# 与 C++ 或 Java 之间的巨大差异！有什么想法吗？
新变量

const int n = 1000;
    static double[][] dist = new double[n][];

新代码：

static void floyd_warshallSingle()
  {
      int i, j, k;
      for (k = 0; k < n; ++k)
          for (i = 0; i < n; ++i)
              for (j = 0; j < n; ++j)

                  if ((dist[i][k] * dist[k][j] != 0) && (i != j))

                      if ((dist[i][k] + dist[k][j] < dist[i][j]) || (dist[i][j] == 0))
                          dist[i][j] = dist[i][k] + dist[k][j];
  }



   static  void floyd_warshall(ParallelOptions pOp)
    {
        int k;     
        for (k = 0; k < n; ++k)
            Parallel.For<int>(0, n, pOp, () => 0, (i, loop, j) =>
                {
                    for (j = 0; j < n; ++j)
                        if ((dist[i][k] * dist[k][j] != 0) && (i != j))
                            if ((dist[i][ k] + dist[k][j] < dist[i][ j]) || (dist[i][j] == 0))
                                dist[i][ j] = dist[i][k] + dist[k][j];

                    return 0;
                }, (j) => { });
    }

- user4186207

1

你正在 C++ 和 Java 中使用不规则数组，但在 C# 中使用二维数组。后者在某些情况下被认为速度较慢；尝试将你的 C# 实现转换为不规则数组。 - Douglas

1

为了澄清混淆：在C#中有int[][](一个int[]数组)和int[,](一个平坦的内存分配) - 前者通常被称为不规则数组。 int[][]在C#中显然比int[,]更快只是意味着编译器/CLR在某个地方做得很糟糕。在线性访问的情况下，两者的速度应该大致相同，但如果您在不规则数组上进行随机访问，则会出现第二个缓存未命中，这可以避免。但是，不规则数组永远不可能比平坦数组更快。 - Voo

1

另一个问题可能是操作顺序。C# 有严格的从左到右的规则。因此，在 if ((dist[i,k] * dist[k,j] != 0) && (i != j)) 中，乘法总是会被执行。C++ 编译器（我不知道 Java）可能会生成代码来首先进行 i != j 测试，这将更快。下面的 if 语句也是如此：将 (dist[i,j] == 0) 测试放在第一位。 - Jim Mischel

1

为什么你要用乘法测试!=0？检查两边是否都!=0不是等效的，而且可以节省一个乘法吗？ - Rup

1

你会遇到的一个问题（正如我在博客文章中指出的那样）是数组边界检查。在C#中，每个索引都会被检查是否超出了数组的边界。这将影响运行时间。尽管如此，我并不希望它会增加一倍。 - Jim Mischel

显示剩余23条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jim Mischel · Accepted Answer

判断是否为数组边界检查问题，或者至少确定数组边界检查是问题的一部分的方法之一，是删除一些索引计算。例如:

    static void floyd_warshallSingle()
    {
        int i, j, k;
        for (k = 0; k < n; ++k)
        {
            var distk = dist[k];
            for (i = 0; i < n; ++i)
            {
                var disti = dist[i];
                for (j = 0; j < n; ++j)
                    if ((i != j) && (disti[k] * distk[j] != 0))
                        if ((disti[j] == 0) || disti[k] + distk[j] < disti[j])
                            disti[j] = disti[k] + distk[j];
            }
        }
    }

在这里，我所做的只是使用distk作为对dist[k]的引用。我怀疑编译器已经进行了这种优化，这可能就是当你从矩形数组转换为锯齿数组时实现性能提升的原因。但还是值得检查一下。

另外，你说你没有连接调试器运行。我假设你也在运行发布版本？而且三个程序（C++、Java和C#）都在以相同的位数运行吗？也就是说，它们都是64位可执行文件吗？还是32位可执行文件？要小心C#，因为项目选项中可能打开了“优先使用32位”标志。即使在64位系统上使用“任何CPU”编译，这也可能导致你以32位模式运行。