Arch Linux

It's not CPU bound, but disk bound. Pacman uses a plain file format for its database searches. When arch was a small project with only a few packages, it was fast. When the amount of packages increased to the amount we have now, pacman became slow. The only things I can do to get pacman fast is putting /var on ext3, or, to make it even more fast: mount /var/lib/pacman/{current,extra,testing} on tmpfs and pacman -Sy everytime after a reboot.

There is a better way.

Use SQLite3. This way these kinds of searches would be done almost instantly. Flat files are a bad idea so no matter if you use ext3 or ext666, in a few years you will still hit the same problem. The idea should be to fix the problem in its root, not to try to extend the life a problematic design.

I agree with you, pacman is slow as hell without ext3 and in a while it become much slower.
We have some options here:
- use sqlite as you suggested, but I'm not familiar with the API of it
- use Berkeley DB instead, I know a little bit of DB programming, documentation is good
- use a flat file and search through it, apt-get does this too

For performance, I would go for 1 or 2. To avoid weird external dependencies, we should go for 3, or do it like the ximian guys do with evolution-data-server: compile it in static. This also solves the DB API change problem whenever we get a new DB and require users to run db_upgrade on their pacman DB.

I would go with SQLite3 because it's far easier to statically link (if needed -- recommended in this case so pacman would never face a bug on a new sqlite release, pacman should always be tested and linked against a very specific version and only upgrade when testing to a new version is done), it's smaller than BDB4 and easier to learn.
In any case, I would avoid flat files or xml...

I'll be looking at a new db structure for pacman3. Since this is a larger design issue, not so much a bug, I'm closing this ticket.

Rest assured, it's a known issue though.