Hoard: a scalable memory allocator for multithreaded applications

ABSTRACT

Parallel, multithreaded C and C++ programs such as web servers, database managers, news servers, and scientific applications are becoming increasingly prevalent. For these applications, the memory allocator is often a bottleneck that severely limits program performance and scalability on multiprocessor systems. Previous allocators suffer from problems that include poor performance and scalability, and heap organizations that introduce false sharing. Worse, many allocators exhibit a dramatic increase in memory consumption when confronted with a producer-consumer pattern of object allocation and freeing. This increase in memory consumption can range from a factor of P (the number of processors) to unbounded memory consumption.This paper introduces Hoard, a fast, highly scalable allocator that largely avoids false sharing and is memory efficient. Hoard is the first allocator to simultaneously solve the above problems. Hoard combines one global heap and per-processor heaps with a novel discipline that provably bounds memory consumption and has very low synchronization costs in the common case. Our results on eleven programs demonstrate that Hoard yields low average fragmentation and improves overall program performance over the standard Solaris allocator by up to a factor of 60 on 14 processors, and up to a factor of 18 over the next best allocator we tested.

REFERENCES

• 1: U. Acar, E. Berger, R. Blumofe, and D. Papadopoulos. Hood: A threads library for multiprogrammed multiprocessors. http://www.cs.utexas.edu/users/hood, Sept. 1999.
• 2: J. Barnes and P. Hut. A hierarchical O(N log N) force-calculation algorithm. Nature, 324:446--449, 1986.
• 3: bCandid.com, Inc. http://www.bcandid.com.
• 4: Emery D. Berger , Robert D. Blumofe, Hoard: A Fast, Scalable, and Memory-Efficient Allocator for Shared-MemoryMultiprocessors, University of Texas at Austin, Austin, TX, 1999
• 5: B. Bigler, S. Allan, and R. Oldehoeft. Parallel dynamic storage allocation. International Conference on Parallel Processing, pages 272-275, 1985.
• 6: R. D. Blumofe and C. E. Leiserson. Scheduling multithreaded computations by work stealing. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS), pages 356--368, Santa Fe, New Mexico, Nov. 1994.
• 7: Coyote Systems, Inc. http://www.coyotesystems.com.
• 8: Carla Schlatter Ellis , Thomas J. Olson, Algorithms for parallel memory allocation, International Journal of Parallel Programming, v.17 n.4, p.303-345, Aug. 1988 [doi>10.1007/BF01407909]
• 9: W. Gloger. Dynamic memory allocator implementations in linux system libraries. http:llwww.dent.med.uni-muenehen.del" wmglo/malloc-slides.html.
• 10: A. Gottlieb and J. Wilson. Using the buddy system for concurrent memory allocation. Technical Report System Software Note 6, Courant Institute, 1981.
• 11: A. Gottlieb and J. Wilson. Parallelizing the usual buddy algorithm. Technical Report System Software Note 37, Courant Institute, 1982.
• 12: Dirk Grunwald , Benjamin Zorn , Robert Henderson, Improving the cache locality of memory allocation, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.177-186, June 21-25, 1993, Albuquerque, New Mexico, United States
• 13: Arun K. Iyengar, Dynamic storage allocation on a multiprocessor, Massachusetts Institute of Technology, Cambridge, MA, 1992
• 14: A. K. Iyengar. Parallel dynamic storage allocation algorithms. In Fifth IEEE Symposium on Parallel and Distributed Processing. IEEE Press, 1993.
• 15: Tor E. Jeremiassen , Susan J. Eggers, Reducing false sharing on shared memory multiprocessors through compile time data transformations, Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.179-188, July 19-21, 1995, Santa Barbara, California, United States
• 16: T. Johnson. A concurrent fast-fits memory manager. Technical Report TR91-009, University of Florida, Department of CIS, 1991.
• 17: T. Johnson and T. Davis. Space efficient parallel buddy memory management. Technical Report TR92-008, University of Florida, Department of CIS, 1992.
• 18: Mark Stuart Johnstone , Paul R. Wilson, Non-compacting memory allocation and real-time garbage collection, 1997
• 19: Mark S. Johnstone , Paul R. Wilson, The memory fragmentation problem: solved?, Proceedings of the 1st international symposium on Memory management, p.26-36, October 17-19, 1998, Vancouver, British Columbia, Canada
• 20: Ken Kennedy , Kathryn S. McKinley, Optimizing for parallelism and data locality, Proceedings of the 6th international conference on Supercomputing, p.323-334, July 19-24, 1992, Washington, D. C., United States [doi>10.1145/143369.143427]
• 21: M. R. Krishnan. Heap: Pleasures and pains. Microsoft Developer Newsletter, Feb. 1999.
• 22: Per-Åke Larson , Murali Krishnan, Memory allocation for long-running server applications, Proceedings of the 1st international symposium on Memory management, p.176-185, October 17-19, 1998, Vancouver, British Columbia, Canada
• 23: D. Lea. A memory allocator. http://g.oswego.edu/dl/html/malloe.html.
• 24: B. Lewis. comp. programming, t h r e a d s FAQ. http://www.lambdacs.conffnewsgroup/FAQ.html.
• 25: P. E. McKenney and J. Slingwine. Efficient kernel memory allocation on shared-memory multiprocessor. In USENIX Association, editor, Proceedings of the Winter 1993 USENIX Conference: January 25-29, 1993, San Diego, California, USA, pages 295-305, Berkeley, CA, USA, Winter 1993. USENIX.
• 26: MicroQuill, Inc. http://www.mieroquill.eom.
• 27: MySQL, Inc. The mysql database manager. http://www.mysql.org.
• 28: Girija J. Narlikar , Guy E. Blelloch, Space-efficient scheduling of nested parallelism, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.1, p.138-173, Jan. 1999 [doi>10.1145/314602.314607]
• 29: J. M. Robson. Worst case fragmentation of first fit and best fit storage allocation strategies. ACM Computer Journal, 20(3):242-244, Aug. 1977.
• 30: SGI. The standard template library for c++: Allocators. http :llwww.sg).comlTechno l ogy lS TLI All ocators.html.
• 31: Standard Performance Evaluation Corporation. SPECweb99. http:l/www.spee.orglosglweb99L
• 32: Darko Stefanovic , J. Eliot Moss, Properties of age-based automatic memory reclamation algorithms, 1999
• 33: D. Stein and D. Shah. Implementing lightweight threads. In Proceedings of the 1992 USENIX Summer Conference, pages 1-9, 1992.
• 34: H. Stone. Parallel memory allocation using the FETCH-AND-ADD instruction. Technical Report RC 9674, IBM T. J. Watson Research Center, Nov. 1982.
• 35: Time-Warner/AOL, Inc. AOLserver 3.0. http://www.aolserver.com.
• 36: J. Torrellas , H. S. Lam , J. L. Hennessy, False Sharing and Spatial Locality in Multiprocessor Caches, IEEE Transactions on Computers, v.43 n.6, p.651-663, June 1994 [doi>10.1109/12.286299]
• 37: Voon-Yee Vee , Wen-Jing Hsu, A Scalable and Efficient Storage Allocator on Shared Memory Multiprocessors, Proceedings of the 1999 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '99), p.230, June 23-25, 1999

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Allocation/deallocation strategies