Как оптимизировать код на JS для ускорения работы?

Question

[Eldrich]

Доброго дня.

Стоит задача рассчитать значения матрицы 52000 на 52000 на JS.
Значение в каждой ячейке является результатом вычисления Косинусовой близости векторов размерностью 300.

Для ускорения вычислений использую GPUJS:

gpu.addFunction(function mF(a, b) {
            return a * b;
        });
const f3 = gpu.createKernel(function(inp) {

            var a = 0
            var b = 0
            var c = 0
            for (var i = 0; i < 300; i++) {
                a += mF(inp[this.thread.y][i], inp[this.thread.x][i])
                b += mF(inp[this.thread.y][i], inp[this.thread.y][i])
                c += mF(inp[this.thread.x][i], inp[this.thread.x][i])
            }

            return a / (Math.pow(b, 0.5) * Math.pow(c, 0.5));

        }).setOutput([52000, 52000])

Можно ли это оптимизировать?

В среднем на расчет всех косинусовых значений от одного вектора ко всем остальным уходит 7мс (без GPU 36 мс), что составляет почти 6 минут для расчета всей матрицы. Я в JS профан и, скорее всего, не вижу очевидных способов оптимизации кода для ускорения его работы.
Так же скрипт благополучно умирает при расчете всей огромной матрицы, приходится считать кусочками по 1000 векторов.

Спасибо

Comments

[sim3x]

Перенести расчет на бекенд
Использовать numpy

[Eldrich]

Артём Егоров, На вход подается двумерный массив vectorsData, где первый индекс - номер вектора (0-51999), второй индекс - массив со значениями самого вектора (300 штук)
Далее просто вызов: f3(vectorsData)

[Александр Таратин]

Eldrich, Попробуйте не по 1000 а по 2048

[Adamos]

(Math.pow(b, 0.5) * Math.pow(c, 0.5)) === (Math.pow(b * c, 0.5))

Там точно в математической части не считаются одни и те же данные? Может, их можно кэшировать?
inp[this.thread.y][i] используется трижды. Почему не присвоить его значение локальной переменной?
Может быть, конечно, JS сам кеширует такие обращения. Но в С за подобный код избили бы подсвечниками.

[Eldrich]

Adamos, Изменений в производительности нет(

[Adamos]

Eldrich, а я, кстати, погорячился насчет подсвечников. За вызов в цикле функции, единственное назначение которой - перемножение аргументов, вас бы просто выкинули за порог.

Еще раз: не верю, что у вас какие-то уникальные данные считаются для каждой ячейки. Ищите, где считается одно и то же, и сохраняйте результат. Самое лучшее ускорение расчетов - это не считать вообще.
Как минимум, там, где заполняются эти вектора, сразу посчитать произведение x * x, x * y и y * y. Чтобы потом не делать это в каждом цикле.

[Eldrich]

Adamos, Вы правы насчет отсутствия уникальности. Когда рассчитывается косинусовая близость ячейки 1 к ячейке 2, то не обязательно рассчитывать эту близость от ячейки 2 к ячейке 1, что снижает время расчетов в 2 раза.
Но в любом случае я всё еще не могу поставить расчеты всей матрицы на вычисление..

Answer 1

[Eldrich]

Нашел решение, объединив возможности библиотеки и совет @Taraflex

Код выглядит так:

var kernelMatrixSize = 4096

        const gpu = new GPU({
            mode: 'gpu'
        });

        const f3 = gpu.createKernel(function(inp1, inp2) {

                var a = 0
                var b = 0
                var c = 0
                for (var i = 0; i < 300; i++) {
                    a += inp1[this.thread.y][i] * inp2[this.thread.x][i]
                    b += Math.pow(inp1[this.thread.y][i], 2)
                    c += Math.pow(inp2[this.thread.x][i], 2)
                }

                return Math.floor(a / (Math.sqrt(b * c)) * 1000000) / 1000000;

            }).setOutput([kernelMatrixSize, kernelMatrixSize])
            .setOutputToTexture(true);
x = getAllDistanceBetween(vectorsData)
y = x[0].toArray(gpu)

Если стоит метка setOutputToTexture, то вычисление матрицы 4096х4096 длится 224 мс, преобразование текстуры в массив занимает примерно 3 секунды. Высчитываем только половину матрицы, так как расстояние от 0 вектора до 1 = расстоянию от 1 к 0. Итого вычисление всех необходимых ячеек займет чуть меньше 60 секунд, вместо 6 минут ранее.

Всем спасибо за помощь.

Comments

[Adamos]

Для умножения числа само на себя использовать Math.pow?
Снимите мое имя с титров!

[Eldrich]

Adamos, В рамках моей задачи не наблюдаю повышения производительности при отказе от Math.pow

[Александр Таратин]

Eldrich, Вместо Math.floor можно битовый сдвиг попробовать.
Math.floor(5.6) == 5.6 >> 0
либо
Math.floor(5.6) == 5.6 >>> 0 но последнее наверное в шейдер не скомпилится

[Александр Таратин]

Eldrich, 4096 может на старых устройствах или мобилках не заработать.

Answer 2

[Андрей Федосеев]

Так же скрипт благополучно умирает при расчете всей огромной матрицы, приходится считать кусочками по 1000 векторов.

Может имеет смыл отправлять эти куски в SharedWorker

Answer 3

[string15]

Можно попробовать WebAssembly

Answer 4

[dom1n1k]

Никогда не имел дел с GPUJS, но то что бросается в глаза из общих сооражений - кешировать индексы и обязательно заменить pow 0.5 на sqrt (причем на один, а не два!).