Looks very interesting. I wonder what tricks it uses compared to gdb's record function? Sounds like it's orders of magnitude faster than gdb's record.

Edit: Sounds like they trap all i/o and other things that cause nondeterminism, and emulate those. Otherwise they just let the code run at native speed.

http://rr-project.org/rr.html has all the gory details.