And plocate is yet orders of magnitude faster than GNU grep. :-) And updates its database faster. You don't specify which locate you're using, but mlocate and BSD locate are basically obsolete by now.

(Disclosure: I'm the author of plocate.)