I'm working with some math-heavy code in JavaScript. I just realized that there's a render that currently takes about 30 minutes. 95% of that time is spent in a single ~40 line function that I've pasted below. I am not extremely well-versed in JavaScript math optimization, so my first attempts to optimize this code haven't gone wonderfully.
I would love any pointers as to what in here is slowing things down. I have good reason to believe that things are non-optimal because the same code in Python runs about 30x faster and JS is not a slow language.
// return cost and gradient, given an arrangement
costGrad: function(Y) {
var N = this.N; // About 5000 long
var dim = this.dim; // About 300 long
var P = this.P; // About 5000^2 long
var pmul = this.iter < 100 ? 4 : 1; // trick that helps with local optima
// compute current Q distribution, unnormalized first
var Qu = zeros(N * N);
var qsum = 0.0;
for(var i=0;i<N;i++) {
for(var j=i+1;j<N;j++) {
var dsum = 0.0;
for(var d=0;d<dim;d++) {
var dhere = Y[i][d] - Y[j][d];
dsum += dhere * dhere;
}
var qu = 1.0 / (1.0 + dsum); // Student t-distribution
Qu[i*N+j] = qu;
Qu[j*N+i] = qu;
qsum += 2 * qu;
}
}
// normalize Q distribution to sum to 1
var NN = N*N;
var Q = zeros(NN);
for(var q=0;q<NN;q++) { Q[q] = Math.max(Qu[q] / qsum, 1e-100); }
var cost = 0.0;
var grad = [];
for(var i=0;i<N;i++) {
var gsum = new Array(dim); // init grad for point i
for(var d=0;d<dim;d++) { gsum[d] = 0.0; }
for(var j=0;j<N;j++) {
cost += - P[i*N+j] * Math.log(Q[i*N+j]); // accumulate cost (the non-constant portion at least...)
var premult = 4 * (pmul * P[i*N+j] - Q[i*N+j]) * Qu[i*N+j];
for(var d=0;d<dim;d++) {
gsum[d] += premult * (Y[i][d] - Y[j][d]);
}
}
grad.push(gsum);
}
return {cost: cost, grad: grad};
}
For those that are curious to see more, this is from the wonderful tsnejs library from Andrej Karpathy.
v = Math.max(v1,v)
is slower thanv = v1 > v ? v1 : v;
You should use literal array declaration, set length for size, and use fill to init.gsum =[]; gsum.length=dim; gsum.fill(0)
You do i*N+j to index many time inside loop. In outer loopvar iN=i*N;
in inner loopvar iNJ = iN+j
then index using iNJ. Not much else to do maybe typed arrays. Firefox is currently much faster than Chrome, also you can uses webWorkers as it looks like it can be done concurrently.. But javscript is still slow Python 30x is about right \$\endgroup\$