Slow typechecking due to linear search in type context

[michaelballantyne]

Sam Caldwell built a ~1000 line program in Hackett that takes 25 seconds to expand. I spent some time profiling the expansion process and thought I'd share the results, though I'm not familiar enough with Hackett's implementation to suggest a fix.

Code: https://gist.github.com/michaelballantyne/64c18ec55abd7f1acdc4a41655239b54
Profile: https://gist.github.com/michaelballantyne/05488da82d07c5db9d03866b3c024334

It looks like most of the time (~70%) is spent on this line: https://github.com/lexi-lambda/hackett/blob/master/hackett-lib/hackett/private/typecheck.rkt#L222
when called by apply-subst.

The size of the type context for this program reaches about 2500 entries, so the linear search by findf gets pricey, especially with free-identifier=? involved in the predicate. Perhaps the context could use a free identifier table instead?

I also noticed that τ<:/full! appliesapply-current-subst at every type it examines, and that it will then reapply the same substitution when it recurs, resulting in a quadratic number of apply-subst operations being applied to leaves.

[michaelballantyne]

Note that I had disabled contract checking before profiling to try and rule out contract overhead.

[lexi-lambda]

Yeah, the Hackett typechecker is super slow. 🙂

This is a known bug. Performance is generally abysmal, and there are some pretty obvious bottlenecks that would not be difficult to speed up. One of them is definitely the way the type context is represented, another is the way in-scope instance dictionaries are handled (currently, all instances for all typeclasses are stored in a single list, which is, to put it lightly, a horrendously bad idea).

I haven’t spent too much time caring about performance because of the fact that Hackett is still such a toy. There are some pretty sweeping changes I know I need to make to the implementation, I just haven’t had the time. Given that I expect to rewrite large chunks of the code, I haven’t tried very hard (or really tried at all) to make the existing implementation perform acceptably.

Progress lately has been slow-going. The last significant change I made was the type/value namespace split, and since then, I’ve spent a lot of time just trying to figure out what to do next and how to accomplish it. I’ve been more focused on runtime performance than typechecker performance lately, since I know the existing implementation is abysmal. The main reasons for this are an awful, naïve implementation of laziness, a naïve implementation of currying, and no specialization (even in trivial cases) to eliminate runtime dictionary passing. These are the performance-related issues that are currently higher on my list than typechecker performance, but they are not trivial, and I think they involve some significant restructuring to the way Hackett currently works. Strictness analysis also just happens to be a much more complicated topic than I had anticipated, and I’ve struggled to find resources that I understand well enough to come up with a cohesive implementation strategy.

I’ve also spent a bunch of time dabbling with ML modules/functors to try and make sure I’m well enough informed to commit to typeclasses (fortunately, the result of that investigation seems to be “yes, typeclasses are good, and I can deprioritize first-class modules for now”), as well as thinking about type system improvements like anonymous products/sums/records, which seem pretty crucial to making the language truly pleasant to work with. On that note, I’ve also been trying to tackle typeclass deriving for some simple typeclasses, which I started on a separate branch, but while it’s clearly doable, it ended up being a lot less pleasant than I was hoping, so I put it on hold for a moment to try and come up with a better solution (as well as take some time to focus on moving to Chicago).

Anyway, this is clearly way off-topic now, but there’s a mini status update about why I’ve accomplished next to nothing on Hackett for the past three months, as well as which things are currently high on my list of priorities. This bug report and your sample program are both really helpful, so thank you for that… I just might not get to fixing this on my own in the immediate future. Hackett’s still too half-baked in too many places! (So I guess it’s more like eighth-baked.)

[lexi-lambda]

(Oh, and cc @howell on this thread.)