Ph.D Thesis

Ph.D StudentCohen Nachshon
SubjectMemory Management: From Theory to Practice
DepartmentDepartment of Computer Science
Supervisor PROF. Erez Petrank
Full Thesis textFull thesis text - English Version


Today, all programming languages provide dynamic memory allocation. The application allocates memory when data arrives; this memory is recycled when the application no longer needs it. While significantly simplifying programming, recycling memory has nontrivial costs. In this dissertation, we study these costs, mainly in the context of today’s multi-core machines. As these machines become ubiquitous, it is important to improve the efficiency of applications running on top of them.

Lock-free data structures serve as an important tool in the design of applications running on multi-core machines. These data structures provide a progress guarantee: eventually at least one thread will make progress. In practice, they provide excellent scalability and performance. But while lock-free data structures are widely accepted, providing memory management support for them (without foiling their progress guarantee) remains difficult. Existing techniques, such as the use of hazard pointers, may impose a high performance overhead. In addition, applying them to a given data structure is difficult. All known lock-free reclamation schemes are “manual” in the sense that the developer has to specify when nodes retire and may be safely reclaimed. Retiring nodes adequately is non-trivial and it sometime requires the modification of the original lock-free algorithm.

We proposed a novel memory management scheme for lock-free data structures called optimistic access. This scheme provides efficient memory management support for lock-free data structures that can be presented in a normalized form. Our novel memory manager breaks the traditional memory management invariant, which never lets a program touch reclaimed memory. This broken invariant provides an opportunity to obtain high parallelism with excellent performance, but also requires careful design. Measurements show that it dramatically outperforms known lock-free memory reclamation methods.

We then extended the optimistic memory management scheme to be automatic in the spirit of mark-sweep garbage collection. The proposed algorithm works with any normalized lock-free algorithm and without requiring the programmer to manually retire nodes. Evaluation shows that this automation comes at a very low cost.

Next, we considered state-of-the-art garbage collectors running on multi-core platforms. Garbage collection may benefit greatly from knowledge about program behavior, but most managed languages do not provide means for the programmer to deliver such knowledge. We proposed a very simple interface that requires minor programmer effort and achieves substantial performance and scalability improvements. Experience shows that this interface requires minor modifications to the application. Measurements show that for some significant benchmarks this interface can dramatically reduce the time spent on garbage collection and also improve the overall program performance.

Finally, we conducted a theoretical study about the limits of compaction. To avoid fragmentation, garbage collectors employ compaction. However, compaction is a costly operation that commercial runtimes attempt to avoid. Instead, partial compaction is often used to defragment parts of the heap. Previous studies on the limitations of compaction have provided some initial asymptotic bounds but no implications for practical systems. We extended the theory to obtain better bounds and made them strong enough to become meaningful for modern systems.