Optimizing Memory Management with Object-Local Heaps
Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
The large discrepancy between the speed of caches and main memory makes efficient memory management more important than ever. This report gives an overview of the current state of the art in memory management, and how then can be used to make the most of hardware systems like cache hierarchies and hardware prefetchers. Pooled allocation, automatic splitting of objects, pointer compression and copying garbage collection are identified as four promising areas, and it is noted that few if any existing systems offer functionality for all four. Furthermore the report describes the design and implementation of a new software package called Object-Local Heaps (OLH). Object-Local Heaps includes a pooled allocator and a compacting garbage collector to avoid memory fragmentation; as well as structure splitting and pointer compression to conserve memory, better utilize caches and improve the performance of hardware prefechers. The main contribution lies showing how these separate ideas can be combined. The system is tested and evaluated using micro-benchmarks. It is found that Object-Local Heaps can increase the throughput by an order of magnitude when iterating over linked structures, compared to an implementation in pure C that is subject to some fragmentation. The throughput when accessing individual fields in objects of two or more fields can also be more than doubled compared to a program that iterates over a standard C++ vector. Additional overhead renders the system unsuitable for search trees and similar structures however, as they require multiple random accesses throughout pools. A red-black tree from the C++ standard template library is more than twice as fast as an equivalent using Object-Local Heaps. Pooled allocation is identified as the most worthwhile feature to integrate in a production language, structure splitting and pointer compression have to be applied more carefully, and might not be suitable for the general case. Some of the shortcomings of Object-Local Heaps could be overcome by using hierarchical memory layouts for search trees, others by leveraging compiler support to reduce latency in general. In conclusion this work shows that automatic memory management can provide opportunities for significant performance gains as well as safety and convenience.
Place, publisher, year, edition, pages
2015. , 42 p.
UPTEC IT, ISSN 1401-5749 ; 15008
Engineering and Technology
IdentifiersURN: urn:nbn:se:uu:diva-259345OAI: oai:DiVA.org:uu-259345DiVA: diva2:843830
Master of Science Programme in Information Technology Engineering
Jimborean, AlexandraBol, Roland