[racket] non-terminating type check for typed racket
> 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.