Fast undo facility for bitmap editor application

Checkpoint each bitmap with memory mappingThe flash memory on iOS devices is fast enough to support undo/redo operations on large bitmaps. Using the mmap system call, I memory mapped 1024x768 ABGR bitmaps with ease, saving my program from using precious DRAM. I don't know how you would like to abstract the undo/redo patterns but the way to avoid any high-overhead copy operations is to have the pointers for undo and redo bitmaps swap each undo/redo. You have specified more than one undo level, but I bet you can get away with some pointer swapping (I am suffering from some insomnia right now and trying to demonstrate the pointer swapping proved too much--it was some pretty garbage psuedocode).

Also, I would not recommend marking your mmap'd pages as F_NOCACHE. It is preferable to have iOS cache writes to the bitmap in DRAM because:

• It's faster if you don't flush to flash
• Flash memory is designed for a fixed number of writes--it's not nice to burn out users' flash (I think it takes somewhere on the order of 5 million writes with the quality flash in iOS devices)
• I believe iOS is aggressive enough in memory management that it will unmap your cached writes and flush them during a memory crisis (I never cared enough to check, though)

Shout out to John Carmack for the tip-off that the iDevice Flash memory is quite fast (He uses F_NOCACHE, though, to get predictable read performance).

Note that I had to make the file be the size of the actual bitmap before calling mmap on the fd. Don't go nuts memory mapping 100 bitmaps, though (just kidding--DO IT!) I mean, how many undos can a user perform? They are weak and their fingers get tired after mere seconds of button-mashing.

There's a third option that comes to mind: each action gets executed on its own layer and undo deletes that layer. It needs a fast rendering mechanism and a smart representation of 'action layers' where you don't store 'transparent' (untouched) pixels.

If you assume u levels of undo, you can merge action layers older than u steps into the background.

You could also have a hybrid approach. If the action is 'small', represent it as a layer. If it's big, as a recorded action, that needs to be replayed. As you say, you need a heuristic to decide between the two cases. You could test rendering/saving performance on the first run af the app after setup and decide some parameter values for the heuristic.

To me, the momento pattern looks the best. Which means that I would probably try to think of ways to optimally store that information. You mention that it can be a 1000x1000 bitmap potentially for one action -- could you, for example, represent the bitmap as a 1-bit bitmap with a separate color field stored elsewhere? Now instead of 2MB you have 125KB to store.

Another thing that I would probably look into is building the information while the user is performing the action -- i.e, while they are scribbling, you can be writing those bits into your data structure as it happens. And then when they are done, you can commit the action to your undo history.

You should be able to apply some algorithmic logic to these undo data structures to reduce their memory impact while hiding the CPU usage during times while waiting for the user.