Per-Åke Larson
Murali Krishnan
ABSTRACT
Prior work on dynamic memory allocation has largely neglected long-running server applications, for example, web servers and mail servers. Their requirements differ from those of one-shot applications like compilers or text editors. We investigated how to build an allocator that is not only fast and memory efficient but also scales well on SMP machines. We found that it is not sufficient to focus on reducing lock contention - higher speedups require a reduction in cache misses and bus traffic. We then designed and prototyped a new allocator, called LKmalloc, targeted for both traditional applications and server applications. LKmalloc uses several subheaps, each one with a separate set of free lists and memory arena. A thread always allocates from the same subheap but can free a block belonging to any subheap. A thread is assigned to a subheap by hashing on its thread ID. WC compared its performance with several other allocators on a server-like, simulated workload and found that it indeed scales well and is quite fast hut memory more efficiently.
- 1.Andrew W. Appel, John R. Ellis, and Kai Li, Realtime concurrent collection on stock multi-processors, A CM SIGPLAN Notices, 23(7): 11-20, 1988. Google Scholar
Digital Library
- 2.David Detlefs, AI Dosser, and Benjamin Zorn, Memory Allocation Costs in Large C and C++ Programs, Software Practice and Experience 24(6): 527--542, June 1994. Google ScholarDigital Library
- 3.J. S. Fenton and D. W. Payne. Dynamic storage allocations of arbitrary sized segments. In Proc. IFIPS, pages 344--348, 1974.Google Scholar
- 4.Wolfram Gloger, Dynamic memory allocator implementations in Linux system libraries, http://www.dent.med.uni-muenchen.de/---wmglo/ maltoc-slides.html (site visited May 11, 1998)Google Scholar
- 5.Dirk Grunwald and Benjamin Zorn, CustoMalloc: Efficient Synthesized Memory Allocators, Software: Practice and Experience. 23(8): 851--869, August 1993. Google ScholarDigital Library
- 6.Dirk Grunwald and Benjamin Zorn and Rob Henderson, Improving the Cache Locality of Memory Allocation, A CM SIGPLAN'93 Conference on Programming Language Design and Implementation, pp 177-- 186. Albuquerque, NM. June 1993. Google ScholarDigital Library
- 7.Arun K. Iyengar, Parallel dynamic storage allocation algorithms, In Fifth IEEE Symposium on Parallel and Distributed Processing. IEEE Press, 1993.Google Scholar
- 8.Arun Iyengar, Scalability of Dynamic Storage Allocation Algorithms, In Frontiers '96 - The 6th Symposium on Frontiers of Massively Parallel Computing, IEEE Computer Society Press. Pages: 223-232. Google Scholar
- 9.Donald E. Knuth. Fundamental Algorithms, Vol. 1 of The Art of Computer Programming, chapter 2, pages 435--451. Addison Wesley, Reading, MA, 2nd edition, 1973.Google Scholar
- 10.Doug Lea, A memory allocator, http://~oswego.edu/dl/html/malloc.html (site visited May 11, 1998).Google Scholar
- 11.B. W. Leverett and P. G. Hibbard. An adaptive system for dynamic storage allocation. Software Practice and Experience, 12(6): 543--556, June 1982.Google ScholarCross Ref
- 12.Paul E. McKenney and Jack Slingwine. Efficient kernel memory allocation on shared-memory multiprocessors. In USENIX Conference Proceedings, Berkeley CA, February 1993.Google Scholar
- 13.C. J. Stephenson. Fast fits: New methods for dynamic storage allocation. In Proceedings of the Ninth ACM Symposium on Operating System Principles, pages 30--32, Bretton Woods, NH, October 1983. Google ScholarDigital Library
- 14.Kiem-Phong Vo, Vmalloc: A general and efficient memory allocator. Software Practice and Experience, 26(3), 357-374, 1996.Google ScholarCross Ref
- 15.Paul R. Wilson, Mark S. Johnstone, Michael Neely, and David Boles. Dynamic storage allocation: A survey and critical review. In 1995 International Workshop on Memory Management, Kinross, Scotland, UK, 1995. Springer Verlag LNCS. Google ScholarDigital Library
- 16.Benjamin Zorn, Malloc/free and GC implementations, http://www.cs.colorado.edu/-zorn/Malloc.htn'~l (site visited May 11, 1988).Google Scholar
- 17.Benjamin Zorn and Dirk Grunwald, Evaluating Models of Memory Allocation, A CM Transactions on Modeling and Computer Simulation. 4(I): 107-- 131, January 1994. Google ScholarDigital Library
- 18.Richard Jones, and Rafael Lins, Garbage Collection: Algorithms for automatic dynamic memory management, John Wiley & Sons, 1998 Google ScholarDigital Library
Index Terms
- Memory allocation for long-running server applications
Recommendations
Memory allocation for long-running server applications
Prior work on dynamic memory allocation has largely neglected long-running server applications, for example, web servers and mail servers. Their requirements differ from those of one-shot applications like compilers or text editors. We investigated how ...
Upper Bounds for Dynamic Memory Allocation
In this paper, we study the upper bounds of memory storage for two different allocators. In the first case, we consider a general allocator that can allocate memory blocks anywhere in the available heap space. In the second case, a more economical ...
Efficient dynamic heap allocation of scratch-pad memory
ISMM '08: Proceedings of the 7th international symposium on Memory managementAn increasing number of processor architectures support scratch-pad memory - software managed on-chip memory. Scratch-pad memory provides low latency data storage, like on-chip caches, but under explicit software control. The simple design and ...
Comments