Node.js/coffeescript по алгоритму с интенсивным вычислением

Ответ 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-битной математики, и насколько это связано с более быстрым доступом к массиву. A Float64Array является частью спецификации V8, но еще не реализован в библиотеке v8-typed-array.)

Ответ 2

Забудьте о Coffeescript в течение минуты, потому что это не корень проблемы. Этот код просто записывается на обычный старый javascript в любом случае, когда node запускает его.

Как и любая другая среда javascript, node является однопоточным. Двигатель 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)

Ответ 3

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

Ответ 4

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

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