Производительность Node.js / coffeescript по математическому алгоритму
Я экспериментирую с node.js для создания логики на стороне сервера и реализовал версию алгоритма алмазного квадрата, описанного здесь в coffeescript и Java. Учитывая все похвалы, которые я слышал о производительности node.js и V8, я надеялся, что node.js не сильно отстанет от java-версии.
Однако на карте 4096x4096 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)
Джава
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);
}
}
4 ответа
Как отмечали другие авторы, массивы JavaScript являются основным узким местом производительности для операций, которые вы выполняете. Поскольку они динамические, доступ к элементам, естественно, гораздо медленнее, чем со статическими массивами Java.
Хорошей новостью является то, что в JavaScript появился новый стандарт статически типизированных массивов, который уже поддерживается в некоторых браузерах. Хотя они еще не поддерживаются в самом Node, вы можете легко добавить их с помощью библиотеки: https://github.com/tlrobinson/v8-typed-array
После установки typed-array через npm вот моя модифицированная версия вашего кода:
{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
Таким образом, одно небольшое изменение сокращает время работы примерно на 1/3, то есть увеличение скорости на 50%!
Это все еще не Java, но это довольно существенное улучшение. Ожидайте, что будущие версии Node/V8 уменьшат разрыв в производительности.
Предостережение: следует отметить, что обычные числа JS имеют двойную точность, то есть 64-разрядные числа с плавающей запятой. С помощью Float32Array таким образом, это снизит точность, сделав это в некотором смысле сравнением яблок и апельсинов - я не знаю, насколько улучшение производительности связано с использованием 32-битной математики, а сколько - с более быстрым доступом к массиву. Float64Array является частью спецификации V8, но еще не реализована в библиотеке v8-typed-array.)
Если вы ищете производительность в таких алгоритмах, как Coffee / JS, так и Java - неправильные языки для использования. Javascript особенно плох для таких задач, потому что у него нет типа массива - массивы - это просто хэш-карты, где ключи должны быть целыми числами, что, очевидно, не будет таким быстрым, как реальный массив. Вам нужно написать этот алгоритм на C и вызвать его из узла (см. http://nodejs.org/docs/v0.4.10/api/addons.html). Если вы не очень хорошо умеете оптимизировать машинный код, хороший C легко превзойдет любой другой язык.
Забудьте о Coffeescript на минуту, потому что это не корень проблемы. Этот код просто записывается в обычный старый javascript в любом случае, когда его запускает узел.
Как и в любой другой среде javascript, узел является однопоточным. Двигатель V8 чертовски быстр, но для определенных типов приложений вы не сможете превысить скорость jvm.
Сначала я хотел бы попытаться исправить ваш алгоритм алмаза непосредственно в js, прежде чем перейти к CS. Посмотрите, какие виды оптимизации скорости вы можете сделать.
На самом деле, я тоже немного интересуюсь этой проблемой и собираюсь взглянуть на это.
Редактирование #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 как "быструю", они имеют в виду относительно других интерпретируемых, динамических языков. Было бы интересно сравнить ruby, python или smalltalk. Сравнение JavaScript с Java не является честным сравнением.
Чтобы ответить на ваш вопрос, я считаю, что результаты, которые вы видите, указывают на то, что вы можете ожидать, сравнивая эти два совершенно разных языка.