The slowness is probably more a factor of the code being fairly old and built up over a long period of time by many contributors rather than something specific to Everything. A rewrite nearly always speeds things up, but it wouldn't matter if it was done with Catalyst or just a modern version of Everything.