Node.js/coffeescript 在数学密集型算法上的表现 [英] Node.js / coffeescript performance on a math-intensive algorithm

问题描述

我正在尝试使用 node.js 构建一些服务器端逻辑，并实现了描述的菱形正方形算法的一个版本

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

{Float32Array} = 需要'typed-array'genHeightField = (sz) ->时间开始 = 新日期()DATA_SIZE = 大小种子 = 1000.0迭代次数 = 0# 初始化浮点数的二维数组数据 = 新数组(DATA_SIZE)对于 [0...DATA_SIZE] 中的行数据[行] = 新的 Float32Array(DATA_SIZE)对于 [0...DATA_SIZE] 中的列数据[行][列] = 0# 其他的都一样...

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

使用 data[rows] = new Array(DATA_SIZE) 行(基本上等同于原来的)，我得到了基准数字:

<代码>177541713765461

通过 data[rows] = new Float32Array(DATA_SIZE) 行，我得到

19472158553452

这样一个小改动就可以将运行时间缩短约 1/3，即速度提高 50%！

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

警告:必须提到的是，普通的 JS 数字是双精度的，即 64 位浮点数.因此，使用 Float32Array 会降低精度，使这有点像苹果和橘子的比较——我不知道使用 32 位数学能带来多少性能改进，以及有多少是从更快的阵列访问.Float64Array 是 V8 规范的一部分，但尚未在 v8-typed-array 库.)

I am experimenting with node.js to build some server-side logic, and have implemented a version of the diamond-square algorithm described here in coffeescript and Java. Given all the praise I have heard for node.js and V8 performance, I was hoping that node.js would not lag too far behind the java version.

However on a 4096x4096 map, Java finishes in under 1s but node.js/coffeescript takes over 20s on my machine...

These are my full results. x-axis is grid size. Log and linear charts:

Is this because there is something wrong with my coffeescript implementation, or is this just the nature of node.js still?

Coffeescript

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);
    }

}

解决方案

As other answerers have pointed out, JavaScript's arrays are a major performance bottleneck for the type of operations you're doing. Because they're dynamic, it's naturally much slower to access elements than it is with Java's static arrays.

The good news is that there is an emerging standard for statically typed arrays in JavaScript, already supported in some browsers. Though not yet supported in Node proper, you can easily add them with a library: https://github.com/tlrobinson/v8-typed-array

After installing typed-array via npm, here's my modified version of your code:

{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...

The key line in there is the declaration of data[rows].

With the line data[rows] = new Array(DATA_SIZE) (essentially equivalent to the original), I get the benchmark numbers:

17
75
417
1376
5461

And with the line data[rows] = new Float32Array(DATA_SIZE), I get

19
47
215
855
3452

So that one small change cuts the running time down by about 1/3, i.e. a 50% speed increase!

It's still not Java, but it's a pretty substantial improvement. Expect future versions of Node/V8 to narrow the performance gap further.

Caveat: It's got to be mentioned that normal JS numbers are double-precision, i.e. 64-bit floats. Using Float32Array will thus reduce precision, making this a bit of an apples-and-oranges comparison—I don't know how much of the performance improvement is from using 32-bit math, and how much is from faster array access. A Float64Array is part of the V8 spec, but isn't yet implemented in the v8-typed-array library.)

这篇关于Node.js/coffeescript 在数学密集型算法上的表现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！