Производительность Node.js / coffeescript по математически интенсивному алгоритму

Question

Я экспериментирую с node.js для создания некоторой серверной логики и реализовал версию алгоритма алмазного квадрата, описанного здесь в coffeescript и Java.Учитывая все похвалы, которые я слышал о производительности node.js и V8, я надеялся, что node.js не сильно отстанет от java-версии.

Однако на карте 4096x4096 Java заканчивается менее чем за 1 с, но файл node.js / coffeescript занимает более 20 с на моей машине ...

Это мои полные результаты.Ось X - это размер сетки.Лог и линейные диаграммы:

Это потому, что что-то не так с моей реализацией coffeescript или это просто природа узла.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);
    }

}

Answer 1

Как отмечали другие авторы, массивы 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 .)

Answer 2

Если вы ищете производительность в таких алгоритмах, как Coffee / JS, так и Java - неправильные языки для использования.Javascript особенно плох для таких задач, потому что у него нет типа массива - массивы - это просто хеш-карты, где ключи должны быть целыми числами, что, очевидно, не будет таким быстрым, как реальный массив.Вам нужно написать этот алгоритм на C и вызвать его из узла (см. http://nodejs.org/docs/v0.4.10/api/addons.html). Если вы не очень хорошо умеете оптимизировать машинный код вручную, хороший C легко превзойдет любой другой язык.

Answer 3

Забудьте о 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)

Answer 4

Я всегда предполагал, что когда люди описывают среду выполнения javascript как «быструю», они имеют в виду относительно других интерпретируемых, динамических языков.Было бы интересно сравнить ruby, python или smalltalk.Сравнение JavaScript с Java не является справедливым сравнением.

Чтобы ответить на ваш вопрос, я считаю, что результаты, которые вы видите, указывают на то, что вы можете ожидать, сравнивая эти два совершенно разных языка.