http://weblog.savanne.be/153-performance-tip-of-the-day
This is more of a *nix only tip that people can do, but it is a very quick and easy way to speed up Firefox history/awesomebar search, especially after long term usage of Firefox (think months or years). It can also speed up initial loading because it will look through less history. It works because there are holes when an entry is deleted, and it checks every entry.
The requirements of setting this up however require sqlite and the vacuum command, so this is why it remains a *nix/mingw/etc. only option, for now. It would be great if you can also add it to CCleaner.
Google mozilla sqlite vacuum for more details.
Mostly for devs:
http://www.sqlite.org/copyright.html
SQlite is public domain as well, and the source code free to use for any purpose.