[racket-dev] Math library initial commit almost ready; comments on issues welcome

On 10/01/2012 02:06 PM, Sam Tobin-Hochstadt wrote:
> On Mon, Oct 1, 2012 at 2:26 PM, Neil Toronto <neil.toronto at gmail.com> wrote:
> PR 13098 isn't really fixable, in some sense.  There's just more data
> there with broader types, so it will always take longer than for more
> specific types. All of the things I'd do to fix the problem would
> speed up both the slow and the fast case, without really affecting the
> gap between them.

You're saying it wouldn't hurt to replace functions with more 
specifically typed functions in general, right? Good point.

I think you can speed up the slow cases more than the fast ones, though. 
Huge `case->' types tend to have this structure:

   (case-> (A0 -> B0)
           ((U A0 A1) -> B1)
           ((U A0 A1 A2) -> B2)
           ((U A0 A1 A2 A3) -> B3)
           ...)

The `abs' function, for example, starts this way:

   (case-> (Zero -> Zero)
           (One -> One)
           (Positive-Byte -> Positive-Byte)
           (Byte -> Byte)
           (Positive-Index -> Positive-Index)
           (Index -> Index)
           ...)

I've done some timing tests using generated types like this:

   (case-> (Zero -> Zero)
           ((U Zero One) -> (U Zero One))
           ((U Zero One 2) -> (U Zero One 2))
           ...)

The tests suggest that typechecking application of a function with a 
type like that is quadratic in the size of the function's type, which 
makes sense. Could you get something nearer to linear-time by dividing 
the case types into monotone groups?

My timing tests also show that typechecking is apparently quadratic in 
the depth of expressions, regardless of how simple the types are. Is 
that something you already knew?

(The latter is a medium-ish deal for the math library. Most special 
functions have domains in which they're computed by evaluating a 25- to 
50-degree polynomial. Using Horner's method, that's an expression 50 to 
100 deep; if they're Chebyshev polynomials, it's more like 200-400.)

>>   * `math/base' re-exports `racket/math', but with extra constants (like
>> `phi.0') and functions (like `power-of-two?'). It also exports improved
>> hyperbolic functions, such as a new `sinh' that's much more accurate near
>> zero: in the worst case, 2e-16 relative error (which is great) instead of
>> 0.5 (which is really bad). But its type in `math/base' is
>>
>>    (case-> (Zero -> Zero)
>>            (Flonum -> Flonum)
>>            (Real -> Real)
>>            (Float-Complex -> Float-Complex)
>>            (Complex -> Complex))
>>
>> I haven't been able to give it a type as specific as the type of the `sinh'
>> exported from `racket/math'.
>
> Why aren't you able to do this?

Probably because I haven't tried hard enough. :p Also, every time I read 
its type, I get vertigo.

I know I've been unable to make a case type mirror the runtime branching 
done in a function before, even when the computation only happened in 
the leaves and I used nothing but predicates with filters. I don't 
remember the specifics, though; it was two months ago.

>>   * Another typed/untyped barrier issue: certain functions are actually
>> macros so that TR can optimize around their expansions. (Example: by making
>> `fcvector-ref' a macro, (+ (fcvector-ref xs 0) (fcvector-ref ys 0)) operates
>> entirely on unboxed Float-Complex values.) I really don't want to make an
>> `untyped/math' library to expose the function versions, but I can't think of
>> a way around it.
>
> There's no way around this at the moment.

I've managed to make some headway here in another part of the library, 
by defining macros only in #lang racket. If their expansions contain 
typed identifiers, it seems TR is smart enough to not check their 
contracts when the macros are used in typed code. Also, the optimizer 
can probably remove most of the sanity checks I'd need for things like 
`fcvector-ref'. Further, it looks like I can keep the macros in the 
files they're currently defined in using submodules.

This part could be less painful than I thought. That would be great.

Neil ⊥