3
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ On Chrome v = Math.max(v1,v) is slower than v = 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 loop var iN=i*N; in inner loop var 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\$ – Blindman67 Dec 31 '16 at 20:39
  • \$\begingroup\$ Could you make an running example with maybe around 500 instead of 5000 to test how to optimize it? \$\endgroup\$ – juvian Jan 2 '17 at 21:20
  • \$\begingroup\$ @Blindman67 implemented everything, and the max replacement got me a ~15% speed improvement, but all the other changes were unfortunately negligible. Why do you say that 30x python is about right? Javascript is typically much faster than python, even hitting only 2-3x of C for many tasks. I'm guessing this is just that JS is a bad fit for matrix math? I'm having trouble finding good matrix math benchmarks across language though. Any resources? \$\endgroup\$ – Slater Victoroff Jan 3 '17 at 0:52
  • \$\begingroup\$ @juvian Unfortunately changing the size by an order of magnitude would invalidate any results from optimization since dim and N scale at different rates. If the two are comparable it's almost certain that the limiting areas of code will change. \$\endgroup\$ – Slater Victoroff Jan 3 '17 at 0:54
  • \$\begingroup\$ @SlaterTyranus Been a long time since I used Python, and having quick look around the web seems JS has caught up with it, well at least NodeJs running V8. SO I will retract the last sentence of my previous comment. BTW you could use the GPU via webGL there are a few libs on github that provide interfaces to the GPU for this type of processing using Javascript. \$\endgroup\$ – Blindman67 Jan 3 '17 at 1:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.