Performance Ideas

[paf31]

• Type checker doesn't use the backtracking of Either, so it could just use exceptions and Eff.
• Try writing the pretty printers using showsPrec-style pretty printing instead of using pattern-arrows.

We should also try to profile the running Javascript to see where the bottleneck is.

[jdegoes]

I do recommend profiling before optimization. Javascript engines do remarkable transformations that make it even more difficult than usual to identify trouble spots without profiling.

Also to the extent that we can parallelize compilation, we can take advantage of web workers on the front-end (not sure if anything similar is available on the backend). With most computers having 4+ cores these days, you can get an easy 2 - 10x increase in performance just from parallelizing.

[garyb]

You can spawn additional processes in node and communicate with JSON over IPC, but I suspect it's a bit clunkier than web workers.

[paf31]

Well psc-make could be parallelized at a fairly high level, and the module graph gives a natural scheme for data flow parallelism. Definitely worth looking into later I think.

[paf31]

I'm more concerned by the several orders of magnitude difference in single threaded performance right now though :P

[paf31]

Also, the Map implementation used in the typechecker has O(N) lookup due to the order of the insertions. Either we should make Map automatically-balancing (preferred), or we should try a different data structure.

[garyb]

I meant to say, I tried profiling psc-in-ps the other day and got a slightly strange results. As far as I can tell from the output, eqArray and bindStateT seem to be the most expensive operations with a grand total of ~5% of the total JS execution time each. It makes no sense.

This was using nprof. I couldn't get dtrace or look or to work.

[paf31]

bindStateT sounds plausible, because both desugaring and type checking use StateT. We can probably use an IORef and exceptions in place of ErrorT in both cases, which should speed things up significantly.

Edit: Do you have the profiler results?

[garyb]

Oh sure, it makes sense for what is expensive, I just meant it's odd that almost 80% of the time is missing in the profiler result, and that the supposedly two most expensive functions are only responsible for 10% of the total time.

I'll make a gist with the results when I get a minute.

[garyb]

https://gist.github.com/garyb/4888f29a11c09e469a40

Different results on my home machine, the total time % value is even less for bindStateT / eqArray!

[paf31]

Interesting. There are a few modules which show up quite often: Data.Map, the typechecker, Names, and PatternArrows. Maybe we can try optimizing those and see if that helps.

[garyb]

I'm going to see if I can get dtrace working on a SmartOS VM, might get some more sense out of that too.

[garyb]

I hacked some timing into the compiler, here's what I get for just running psc:

read & parse files: 10ms
  sortModules: 18ms
  desugar: 531ms
  typecheck: 6212ms
  binding groups: 96ms
  js codegen: 224ms
compile: 8519ms

So the type checker is by far the main culprit. Parser is amazingly fast considering.

[garyb]

I've put it in a branch c1c7f8f

[paf31]

Great to know :) I'll have a look at the typechecker in the next couple of days. I have a few ideas for how it could be improved.

[garyb]

New branch typecheck time is now ~3926ms down from ~5050ms. Pretty good, but considering the amount of work you did on it shame it's not a bit more!