2014/04/07 by Silviu S. Craciunas, Christoph Kirsch, Craciunas, Silviu S. +8
Computer Science · #Distributed systems and fault tolerance #FOS: Computer and information sciences #Parallel Computing and Optimization Techniques #Programming Languages (cs.PL) #Security and Verification in Computing #cs.PL
paper · pdf · doi:10.48550/arxiv.1404.1830
arxiv created 2014/04/07 · openalex publication_date 2014/04/07 · arxiv updated 2014/04/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study, formally and experimentally, the trade-off in temporal and spatial overhead when managing contiguous blocks of memory using the explicit, dynamic and real-time heap management system Compact-fit (CF). The key property of CF is that temporal and spatial overhead can be bounded, related, and predicted in constant time through the notion of partial and incremental compaction. Partial compaction determines the maximally tolerated degree of memory fragmentation. Incremental compaction of objects, introduced here, determines the maximal amount of memory involved in any, logically atomic, portion of a compaction operation. We explore CF's potential application space on (1) multiprocessor and multicore systems as well as on (2) memory-constrained uniprocessor systems. For (1), we argue that little or no compaction is likely to avoid the worst case in temporal as well as spatial overhead but also observe that scalability only improves by a constant factor. Scalability can be further improved significantly by reducing overall data sharing through separate instances of Compact-fit. For (2), we observe that incremental compaction can effectively trade-off throughput and memory fragmentation for lower latency.