Problems right now:

Worst case is currently symbol not existing. We search *everything*.
Search isn't particularly fast. It actually depends on where the
symbol will be found.  We repeatedly search the same blocks.

Read more:  http://sources.redhat.com/ml/gdb/2001-06/msg00077.html