I came across Very Sleepy in a blog post by Fabian Giesen on Fixing Cache Issues. It is not nearly as powerful as VTune but it is the best free profiling tool I'm aware of.

If you are aware of other free profiling tools that you like, please add them to the thread.

Very Sleepy is good. I also use gprof on GNU/Linux and Xcode Instruments on OS X.

Visual Studio 2013 has an integrated profiler under the Analyze->Profile menu. It's nowhere near as good as Intel's VTune, but it's free ;)

There is free CodeXL from AMD. It has some advanced profiling stuff for AMD same as VTune has for Intel, but for basic profiling it works fine even on Intel CPU's.

As for using gprof on Linux, there is a tool for more advanced profiling called "perf". It can measure a not only time spent in functions, but also a lot more CPU specific information like cache misses, mispredicted branches, alignment faults and a lot more. Compared to gprof, you don't need to recompile your application with additional arguments except regular debug info.

For CPU cache profiling there's also Cachegrind (part of the Valgrind suite). It's a linux-only open-source tool that maybe doesn't have the friendliest interface, but does some crazy stuff.

The unique thing about Cachegrind is that it simulates the execution of your program on a CPU with instruction and data caches similar to those of the machine you're targeting. It's painfully slow (5-100 times slower, depending on the program), but it provides a line-by-line estimation of were the cache reads, writes and misses happen.