[racket-dev] `math' compilation time !!!

On 02/27/2013 09:17 AM, Jens Axel Søgaard wrote:
> 2013/2/27 Eli Barzilay <eli at barzilay.org>:
>> On Sunday, Eli Barzilay wrote:
>>> According to my rough count (and running setup with a "-j 1"),
>>> compiling `math' takes 40% of the whole tree compilation.
>>
>> I'm surprised that nobody finds this disturbing.  Maybe it was the
>> lack of bangs in the subject.
>
> Disturbing, yes.  But besides porting it to non-Typed Racket,
> is there anything that can be done?

Yes. But first, porting to untyped Racket is a nonstarter. Racket's 
numeric tower is nice to work in until you want to make things fast or 
guarantee the data types of results. Typed Racket allows the math 
library to do both and not be crashy.

(An example that came up in the implementation of matrix norms: the type 
of (sqrt (/ 1 x)) isn't Nonnegative-Real if x : Nonnegative-Real, but 
Complex. Consider x = -0.0. Without TR's complaints, `matrix-norm' would 
have contained a time bomb.)

I'm running my own timing tests. So far, I've got 917s (about 15 
minutes) to compile the math library on this machine, single-threaded. I 
need to run a separate test for this, but it looks like the docs took 
more than half that time - which is weird. Stand by on that.

I tried to make the code typecheck quickly, primarily by using fl- and 
fx-prefixed functions, whose applications take less time to check 
because they have fewer cases. We could probably speed up the number 
theory code a little by creating arithmetic functions with similarly 
specialized integer types. Beyond that, I don't know what Jens Axel and 
I could do.

One place I know things are slow is checking functions with `case->' 
types. Such a function is checked once for each case, each time from 
scratch. A lot of the matrix functions have many case types, to ensure, 
for example, that TR can prove the inverse of a (Matrix Real) is a 
(Matrix Real). I have no idea how this could be faster; it just seems 
like a good place to start.

Sam has mentioned that `syntax-parse' is a source of slowness, but he's 
in the same situation we're in: replacing it with something that checks 
fewer properties, like `syntax-case', would introduce a lot of errors. 
Maybe judicious use of cuts would speed some things up? Does 
`syntax-parse' cache the classes and attributes of syntax objects?

Another idea: would it be possible to serialize the results of type 
checking, or serialize a trace that would enable quick re-checking? If 
so, we could distribute results or traces with the Racket code.

I'll reply later with my full timing results.

Neil ⊥