Not to long ago I adopted a method created by Maister into the genplus emulator that allows for real time rewinding (think Prince of Persia or Braid).  The method is somewhat like video compression P-Frames where you store the diff of the last frame.  Emulators like FCEU use state saving to disk to pull this off which is very expensive.  The individual state frames are often large ranging anywhere from 75Kb to 300Kb.   This method of storing the diffs in memory allows us to provide almost 30 seconds of rewind (varies depending on the game).  You can do the math to get a rough estimate how much space 30 seconds at 60fps worth of frames would take in its raw form.  The only real performance hit is the serialization and unserialization of the state itself, this proves fairly negligible.  This is really just a for fun feature it is however neat none the less.

See a video here:

This also marks the release of GENPlusDroid (for free). If you have any problems please visit the forums. Download from the market, leave a comment.
https://market.android.com/details?id=ca.halsafar.genesisdroid

Scan the QR Code for quick access:

Halsafar