[racket] non-terminating type check for typed racket

From: Danny Yoo (dyoo at cs.wpi.edu)
Date: Mon Apr 18 12:23:27 EDT 2011

> One hot spot identified: the use of remove-duplicates in the
> definition of -and within typed-scheme/types/filter-ops.rkt is taking
> a significant amount of time.

Ok, code analyzed.

The other part of the -or code that's significantly expensive is the
running optimizations and filtering going on while iterating over the
type list.

I see there are two for/ors in there that (1) checks where the current
type is an opposite of any other in the 'result', and (2) checks the
intermediate 'result' list for filter-equal?/implied-atomic? in the
next clause there.  But since this process occurs as we're building up
the result list, that's ultimately an O(n^2) lurking there due to the
Gauss sum.

When I wipe those two clauses out of the case analysis, the runtime of
typed racket drops from 1 minute 30 seconds down to 30 seconds on my
project.  Of course, my barbarian hack makes the type analysis
absolutely unsound... :)  But at the very least, I think I've my
finger on the pulse of a performance issue here.

I can't make too strong a statement about this, but I think it's
worthwhile to figure out how to do the filtering so that it can
efficiently compute the test without having to run through the
intermediate result list.

Posted on the users mailing list.