Use GProf to create call graph information for an application. Take the functions which use the most processing time and start optimizing those. The tool writes profiling output to a file. The application needs to be compiled with special profiling options.
Nicer GUI for GProf output.
Generates profiling information but needs an extra library.
Also a profiler. Writes results right into source code of program.