Enabling Behavior-Based Energy Consumption & Memory Footprint Optimizations in Native Contexts

Dynamic storage allocation is indispensable to the development of computer software. Yet under first principles, it remains poorly studied. Despite being known as an idea for decades, memory fragmentation, which is the main problem an allocator faces, has not converged to a universal definition or measurement framework. The most widely used allocators today employ general-purpose policies, meaning that their behavior does not adapt to the behavior of the program they serve. However, program behavior is claimed to affect fragmentation and, to a vague extent, overall performance. This dissertation's thesis is that it is possible and useful to automatically construct application-specific allocators to improve several metrics of interest. To this end, we will first explore and benchmark several definitions of memory fragmentation proposed in the literature. We will also implement a command-line interface tool to be used as a golden standard for the evaluation of arbitrary program-allocator pairs. This is possible because theoretical computer science has provided algorithms to solve the problem almost optimally offline. Then we will uncover the performance costs of fragmentation both in the application and the system level. Armed with this knowledge, we will conclude with an interoperable, intelligent allocator targeting fragmentation for arbitrary programs.