locate is, for whatever reason, tragically slow. The database format it uses is nonsensical and completely optimized for size on very outdated assumptions.

I use an implementation I have written in the shell itself whose database format is nothing more than every file path on the system separated by null bytes, that is simply grepped to find files; the speed difference is absurd.

  —— — time locate */meme.png
 /storage/home/user/pictures/macro/meme.png

 real  0m0.885s
 user  0m0.806s
 sys 0m0.010s
  —— — time greplocate /meme.png$
 /storage/home/user/pictures/macro/meme.png

 real  0m0.089s
 user  0m0.079s
 sys 0m0.011s

This implementation is highly naïve and simplistic, and offloads all the searching to GNU Grep, yet outperforms the actual `locate` command by an order of magnitude.