Node.js / coffeescript在math密集型algorithm上的性能

我正在尝试使用node.js来构build一些服务器端的逻辑,并在coffeescript和Java中实现了这里描述的菱形方法algorithm的一个版本。 考虑到我对node.js和V8性能的所有好评,我希望node.js不会落后于java版本。

但是在4096×4096的地图上,Java在1秒内完成,但是node.js / coffeescript在我的机器上花费了20多秒。

这些是我全部的结果。 x轴是网格大小。 日志和线性图表:

线性

日志

这是因为我的coffeescript实现有什么问题,或者这仅仅是node.js的性质呢?

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

正如其他答复者指出的那样,JavaScript数组是您正在进行的操作types的主要性能瓶颈。 因为它们是dynamic的,访问元素的速度自然慢于Java的静态数组。

好消息是JavaScript中静态types数组有一个新兴标准,在某些浏览器中已经得到支持。 虽然在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[rows]的声明。

使用行data[rows] = new Array(DATA_SIZE) (基本上相当于原始数据),我得到基准数字:

 17 75 417 1376 5461 

和行data[rows] = new Float32Array(DATA_SIZE) ,我得到

 19 47 215 855 3452 

所以,一个小小的改变就会使运行时间减less1/3左右,即速度提高50%!

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

警告:需要提到的是,正常的JS数字是双精度的,即64位浮点数。 因此,使用Float32Array会降低精度,这使得这是一个苹果和橙子的比较 – 我不知道使用32位math有多大的性能改善,以及更快的数组访问。 Float64Array V8规范的一部分,但尚未在v8types数组库中实现。)

如果你正在寻找像这样的algorithm的性能,那么coffee / js和Java都是使用的错误语言。 对于像这样的问题,Javascript尤其糟糕,因为它没有数组types – 数组只是哈希映射,其中键必须是整数,显然不会像真实数组那样快。 你想要的是用C编写这个algorithm,并从节点调用(参见http://nodejs.org/docs/v0.4.10/api/addons.html )。 除非你擅长手工优化机器代码,否则良好的C很容易超越任何其他语言。

忘记咖啡文本一分钟,因为这不是问题的根源。 无论如何,节点运行时,该代码只会被写入常规的旧javascript。

就像任何其他的JavaScript环境一样,节点是单线程的。 V8引擎速度很快,但对于某些types的应用程序,您可能无法超越jvm的速度。

我会首先build议在移动到CS之前,直接在js中使用您的钻石algorithm。 看看你可以做什么样的速度优化。

其实我现在也对这个问题感兴趣,现在就来看看这个。

编辑#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) 

我一直认为,当人们将javascript运行时描述为“快”时,它们相对于其他解释的dynamic语言。 比较ruby,python或smalltalk将是有趣的。 比较JavaScript到Java是不公平的比较。

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