There are a bunch of existing tools that use the underlying architecture's performance measuring capabilities to give you things like cache hits/misses and bran

There are a bunch of existing tools that use the underlying architecture's performance measuring capabilities to give you things like cache hits/misses and branch prediction performance; I really like oprofile (but it only runs on linux). If you're using multiple threads, then you might have issues with false sharing, which is a bitch. Valgrind can help you there.