The ability to save the state of a running virtual machine (VM) for later restoration is an important tool for home, server, and virtual desktop cloud (VDC) environments in order to achieve optimal and balanced hardware utilization. With guest memory sizes of four to eight gigabytes being the norm the time-and space-overhead of storing VM checkpoints still prevents an effective use of the technique. This work presents a method for fast and space-efficient checkpointing of VMs. Based on the observation that operating systems cache disk blocks in memory, the proposed technique transparently intercepts I/O operations and maintains an up-to-date mapping of memory pages and disk blocks containing identical data. At a checkpoint, those memory pages are excluded from the checkpoint image leading to a significant reduction of both the time and space required to take a checkpoint of a running VM. The broad applicability and good performance of the proposed method is demonstrated by an extensive set of experiments. We have implemented the technique for para-virtualized (PV), PVHVM, and fully-virtualized (HVM) guests in the Xen hypervisor. In comparison with an unmodified Xen hypervisor, experiments with Linux and Windows guests, on average, achieve a 86, 76, 53, and 47 percent reduction in the stored data and a 73, 62, 47, and 38 percent shorter time required to take a checkpoint for PV, PVHVM, HVM Linux, and HVM Windows guests, respectively.