On the other hand, niko has described trait resolution as "basically prolog", so that's something you can push to perform as degenerately bad as you want (the recent addition of specialization only making things worse).

The issue is just how degenerately bad "most" code is -- and I think that hinges a lot on how excited the word "higher" gets you vis-a-vis expressing your programs. If you think C# is a pretty cool type system that doesn't afraid of anything you'll probably be fine. If you think scala or haskell with All The GHC Extensions is where it's at... watch out.