On 10/01/2012 02:06 PM, Sam Tobin-Hochstadt wrote:
On Mon, Oct 1, 2012 at 2:26 PM, Neil Toronto <neil.toro...@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 ⊥
_________________________
Racket Developers list:
http://lists.racket-lang.org/dev
