[camperman]

I hadn't heard of perf - very handy indeed. It's in the linux-tools package for distros using apt. You will need to install both the generic package and the one for your kernel version.

[blacksmith_tb]

Installing linux-tools-generic seems to have been enough for me (on Trusty).