Valgrind and gprof are two very different tools. Valgrind is an instrumenting profiler. Gprof is a sampling profiler. Gprof spends most of its time doing nothing. Then every 100,000,000 clock cycles or so, it looks at the instruction pointer to see what function your program is in. It collects that data enough times to end up with a good idea of where your program is spending its time. The advantage of this approach is that your program runs almost at full speed. This gives you a better idea of how much time your program spends waiting for things like disk or network I/O.
My typical profiling experience with gprof looks like this:
Some caveats: for gprof to work, you need to add -pg to your CFLAGS. Also, gprof is broken on OS X, so run it on a linux server. If you want a sampling profiler on OS X, I recommend Instruments.app.