Node.js / Coffeescript 在数学密集型算法上的性能

Question

我正在尝试使用 node.js 来构建一些服务器端逻辑，并实现了描述的钻石方形算法的版本 这里 在coffeescript 和Java 中。鉴于我听到的所有对 Node.js 和 V8 性能的赞扬，我希望 Node.js 不会落后于 java 版本太多。

然而，在 4096x4096 地图上，Java 在 1 秒内完成，但 node.js/coffeescript 在我的机器上花费了 20 秒以上......

这些是我的完整结果。 x 轴是网格大小。对数和线性图表：

这是因为有我的 Coffeescript 实现有问题，或者这仍然是 Node.js 的本质？

脚本

genHeightField = (sz) ->
    timeStart = new Date()

    DATA_SIZE = sz
    SEED = 1000.0
    data = new Array()
    iters = 0

    # warm up the arrays to tell the js engine these are dense arrays
    # seems to have neligible effect when running on node.js though
    for rows in [0...DATA_SIZE]
        data[rows] = new Array();
        for cols in [0...DATA_SIZE]
            data[rows][cols] = 0

    data[0][0] = data[0][DATA_SIZE-1] = data[DATA_SIZE-1][0] = 
      data[DATA_SIZE-1][DATA_SIZE-1] = SEED;

    h = 500.0
    sideLength = DATA_SIZE-1
    while sideLength >= 2
      halfSide = sideLength / 2

      for x in [0...DATA_SIZE-1] by sideLength
          for y in [0...DATA_SIZE-1] by sideLength
              avg = data[x][y] +
                  data[x + sideLength][y] +
                  data[x][y + sideLength] +
                  data[x + sideLength][y + sideLength]
              avg /= 4.0;

              data[x + halfSide][y + halfSide] = 
                  avg + Math.random() * (2 * h) - h;
              iters++
              #console.log "A:" + x + "," + y

      for x in [0...DATA_SIZE-1] by halfSide
        y = (x + halfSide) % sideLength
        while y < DATA_SIZE-1
          avg = 
            data[(x-halfSide+DATA_SIZE-1)%(DATA_SIZE-1)][y]
            data[(x+halfSide)%(DATA_SIZE-1)][y]
            data[x][(y+halfSide)%(DATA_SIZE-1)]
            data[x][(y-halfSide+DATA_SIZE-1)%(DATA_SIZE-1)]
          avg /= 4.0;

          avg = avg + Math.random() * (2 * h) - h;
          data[x][y] = avg;

          if x is 0
            data[DATA_SIZE-1][y] = avg;
          if y is 0  
            data[x][DATA_SIZE-1] = avg;
          #console.log "B: " + x + "," + y
          y += sideLength
          iters++
      sideLength /= 2
      h /= 2.0

    #console.log iters
    console.log (new Date() - timeStart)

genHeightField(256+1)
genHeightField(512+1)
genHeightField(1024+1)
genHeightField(2048+1)
genHeightField(4096+1)

Java

import java.util.Random;

class Gen {

    public static void main(String args[]) {
        genHeight(256+1);
        genHeight(512+1);
        genHeight(1024+1);
        genHeight(2048+1);
        genHeight(4096+1);
    }

    public static void genHeight(int sz) {
        long timeStart = System.currentTimeMillis();
        int iters = 0;

        final int DATA_SIZE = sz;
        final double SEED = 1000.0;
        double[][] data = new double[DATA_SIZE][DATA_SIZE];
        data[0][0] = data[0][DATA_SIZE-1] = data[DATA_SIZE-1][0] = 
                data[DATA_SIZE-1][DATA_SIZE-1] = SEED;

        double h = 500.0;
        Random r = new Random();
        for(int sideLength = DATA_SIZE-1;
            sideLength >= 2;
            sideLength /=2, h/= 2.0){
          int halfSide = sideLength/2;

          for(int x=0;x<DATA_SIZE-1;x+=sideLength){
            for(int y=0;y<DATA_SIZE-1;y+=sideLength){
              double avg = data[x][y] + 
                      data[x+sideLength][y] +
                      data[x][y+sideLength] + 
                      data[x+sideLength][y+sideLength];
              avg /= 4.0;

              data[x+halfSide][y+halfSide] = 
                  avg + (r.nextDouble()*2*h) - h;

              iters++;
              //System.out.println("A:" + x + "," + y);
            }
          }

          for(int x=0;x<DATA_SIZE-1;x+=halfSide){
            for(int y=(x+halfSide)%sideLength;y<DATA_SIZE-1;y+=sideLength){
              double avg = 
                    data[(x-halfSide+DATA_SIZE-1)%(DATA_SIZE-1)][y] + 
                    data[(x+halfSide)%(DATA_SIZE-1)][y] + 
                    data[x][(y+halfSide)%(DATA_SIZE-1)] + 
                    data[x][(y-halfSide+DATA_SIZE-1)%(DATA_SIZE-1)]; 
              avg /= 4.0;

              avg = avg + (r.nextDouble()*2*h) - h;
              data[x][y] = avg;

              if(x == 0)  data[DATA_SIZE-1][y] = avg;
              if(y == 0)  data[x][DATA_SIZE-1] = avg;

              iters++;
              //System.out.println("B:" + x + "," + y);
            }
          }
        }
        //System.out.print(iters +" ");
        System.out.println(System.currentTimeMillis() - timeStart);
    }

}

Answer 1

正如其他回答者所指出的，JavaScript 的数组是您正在执行的操作类型的主要性能瓶颈。因为它们是动态的，所以访问元素自然比使用 Java 的静态数组慢得多。

好消息是 JavaScript 中的静态类型数组出现了一个新兴标准，某些浏览器已经支持该标准。虽然 Node 本身尚不支持，但您可以使用库轻松添加它们：https://github。 com/tlrobinson/v8-typed-array

通过 npm 安装 typed-array 后，这是我对代码的修改版本：

{Float32Array} = require 'typed-array'

genHeightField = (sz) ->
    timeStart = new Date()
    DATA_SIZE = sz
    SEED = 1000.0
    iters = 0

    # Initialize 2D array of floats
    data = new Array(DATA_SIZE)
    for rows in [0...DATA_SIZE]
      data[rows] = new Float32Array(DATA_SIZE)
      for cols in [0...DATA_SIZE]
          data[rows][cols] = 0

    # The rest is the same...

其中的关键行是 data[ 的声明行]。

通过行 data[rows] = new Array(DATA_SIZE) （基本上与原始行相同），我得到了基准数字：

17
75
417
1376
5461

并且通过行 data[rows] = new Float32Array(DATA_SIZE) )，我明白了

19
47
215
855
3452

，一个小小的改变就能将运行时间减少大约 1/3，即速度提高 50%！

它仍然不是 Java，但这是一个相当大的改进。预计 Node/V8 的未来版本将进一步缩小性能差距。

警告： 需要注意的是，普通的 JS 数字是双精度的，即 64 位浮点数。因此，使用 Float32Array 会降低精度，这有点像苹果和橘子的比较——我不知道使用 32 位数学有多少性能改进，以及有多少改进。来自更快的数组访问。 Float64Array 是 V8 规范的一部分，但尚未在 v8-typed-array 库。）

Answer 2

如果您正在寻找这样的算法的性能，那么咖啡/js 和 Java 都是错误的语言。 Javascript 对于此类问题尤其糟糕，因为它没有数组类型 - 数组只是哈希映射，其中键必须是整数，这显然不会像真正的数组那么快。您想要的是用 C 语言编写此算法并从节点调用该算法（请参阅 http: //nodejs.org/docs/v0.4.10/api/addons.html）。除非您真的擅长手动优化机器代码，否则优秀的 C 语言将轻松超越任何其他语言。

Answer 3

暂时忘记 Coffeescript，因为那不是问题的根源。无论如何，当节点运行该代码时，该代码都会被写入常规的旧 JavaScript。

就像任何其他 javascript 环境一样，node 是单线程的。 V8 引擎速度非常快，但对于某些类型的应用程序，您可能无法超过 jvm 的速度。

我首先建议在转向 CS 之前尝试直接在 js 中纠正钻石算法。查看您可以进行哪些类型的速度优化。

事实上，我现在也对这个问题感兴趣，并且打算考虑这样做。

编辑 #2 这是我第二次重写，进行了一些优化，例如预填充数据数组。它的速度并没有明显加快，但代码更加简洁。

var makegrid = function(size){
    size++; //increment by 1

    var grid = [];
        grid.length = size,
        gsize = size-1; //frequently used value in later calculations.

    //setup grid array
    var len = size;
    while(len--){
        grid[len] = (new Array(size+1).join(0).split('')); //creates an array of length "size" where each index === 0
    }

    //populate four corners of the grid
    grid[0][0] = grid[gsize][0] = grid[0][gsize] = grid[gsize][gsize] = corner_vals;

    var side_length = gsize;

    while(side_length >= 2){
        var half_side = Math.floor(side_length / 2);

        //generate new square values
        for(var x=0; x<gsize; x += side_length){
            for(var y=0; y<gsize; y += side_length){

                //calculate average of existing corners            
                var avg = ((grid[x][y] + grid[x+side_length][y] + grid[x][y+side_length] + grid[x+side_length][y+side_length]) / 4) + (Math.random() * (2*height_range - height_range));

                //calculate random value for avg for center point
                grid[x+half_side][y+half_side] = Math.floor(avg);

            }
        }

        //generate diamond values
        for(var x=0; x<gsize; x+= half_side){
            for(var y=(x+half_side)%side_length; y<gsize; y+= side_length){

                var avg = Math.floor( ((grid[(x-half_side+gsize)%gsize][y] + grid[(x+half_side)%gsize][y] + grid[x][(y+half_side)%gsize] + grid[x][(y-half_side+gsize)%gsize]) / 4) + (Math.random() * (2*height_range - height_range)) );

                grid[x][y] = avg;

                if( x === 0) grid[gsize][y] = avg;
                if( y === 0) grid[x][gsize] = avg;
            }
        }

        side_length /= 2;
        height_range /= 2;
    }

    return grid;
}

makegrid(256)
makegrid(512)
makegrid(1024)
makegrid(2048)
makegrid(4096)

Answer 4

我一直认为，当人们将 javascript 运行时描述为“快”时，他们的意思是相对于其他解释型动态语言。与 ruby​​、python 或smalltalk 进行比较会很有趣。将 JavaScript 与 Java 进行比较并不是一个公平的比较。

为了回答你的问题，我相信你所看到的结果表明了你可以期望比较这两种截然不同的语言。