Software Practice and Experience · 1996 · 75 citations · 14 references
ComputingComputer EngineeringComputer ScienceComputer ArchitectureMemoryOperating SystemsMemory HierarchyMemory Hierarchy DesignMemory Hierarchy OptimizationMemory ManagementVirtual MemoryDebuggingHeap OrganizationMemory Access PatternsMemory AllocationMemory Allocation StrategiesRegion-based Memory ManagementVirtual Memory Management
Despite its popularity, malloc's shortcomings frequently cause programmers to code around it. The new library Vmalloc generalizes malloc to give programmers more control over memory allocation. Vmalloc introduces the idea of organizing memory into separate regions, each with a discipline to get raw memory and a method to manage allocation. Applications can write their own disciplines to manipulate arbitrary type of memory or just to better organize memory in a region by creating new regions out of its memory. The provided set of allocation methods include general purpose allocation, fast special cases and aids for memory debugging or profiling. A compatible malloc interface enables current applications to select allocation methods using environment variables so they can tune for performance or perform other tasks such as profiling memory usage, generating traces of allocation calls or debugging memory errors. A performance study comparing Vmalloc and currently popular malloc implementations shows that Vmalloc is competitive to the best of these allocators. Applications can gain further performance improvement by using the right mixture of regions with different Vmalloc methods.
14
The Art of Computer Programming
W.J. Worlton · Nuclear Science and Engineering · 1968 · 2.3K citations
Self-adjusting binary search trees
Daniel D. Sleator, Robert E. Tarjan · Journal of the ACM · 1985 · 1.2K citations · Full text
Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
D. S. Johnson, Alan Demers, Jeffrey D. Ullman et al. · SIAM Journal on Computing · 1974 · 913 citations
A unifying look at data structures
Jean Vuillemin · Communications of the ACM · 1980 · 283 citations · Full text