Consolidation of multiple workloads, encapsulated in virtual machines (VMs), can significantly improve efficiency in cloud infrastructures. But consolidation also introduces contention in shared resources such as the memory hierarchy, leading to degraded VM performance. To avoid such degradation, the current practice is to not pack VMs tightly and leave a large fraction of server resource unused. This is wasteful. We present a performance preserving VM consolidation system that selectively places those VMs together that are likely to have the least contention. This drastically reduces the amount of wasted resources. While the problem of selecting the most suitable VM combinations is NP-Complete, our system employs a practical method that performs provably close to the optimal. In some scenarios resource efficiency may trump performance and our system also implements techniques for this case. Experimental results show that the proposed system realizes over 30% savings in energy costs and up to 52% reduction in performance degradation compared to consolidation algorithms that do not consider degradation.