Empirical measurements of six allocation-intensive C programs

ABSTRACT

Dynamic memory management is an important part of a large class of computer programs and high-performance algorithms for dynamic memory management have been, and will continue to be, of considerable interest. This paper presents empirical data from a collection of six allocation-intensive C programs. Extensive statistics about the allocation behavior of the programs measured, including the distributions of object sizes, lifetimes, and interarrival times, are presented. This data is valuable for the following reasons: first, the data from these programs can be used to design high-performance algorithms for dynamic memory management. Second, these programs can be used as a benchmark test suite for evaluating and comparing the performance of different dynamic memory management algorithms. Finally, the data presented gives readers greater insight into the storage allocation patterns of a broad range of programs. The data presented in this paper is an abbreviated version of more extensive statistics that are publically available on the internet.

REFERENCES

• 1: A. P. Batson , R. E. Brundage, Segment sizes and liftetimes in Algol 60 programs, Communications of the ACM, v.20 n.1, p.36-44, Jan. 1977 [doi>10.1145/359367.359422]
• 2: Alan Batson , Shy-Ming Ju , David C. Wood, Measurements of segment size, Communications of the ACM, v.13 n.3, p.155-159, March 1970 [doi>10.1145/362052.362055]
• 3: [3] G. Bozman, W. Buco, T. P. Daly, and W. H. Tetzlaff. Analysis of free-storage algorithms--revisited. IBM Systems Journal, 23(1):44-64, 1984.
• 4: R. P. Brent, Efficient implementation of the first-fit strategy for dynamic storage allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.3, p.388-403, July 1989 [doi>10.1145/65979.65981]
• 5: [5] John DeTreville. Heap usage in the Topaz environment. Technical Report 63, Digital Equipment Corporation System Research Center, Palo Alto, CA, August 1990.
• 6: [6] Dirk Grunwald and Benjamin Zorn. CUSTOMALLOC: Efficient synthesized memory allocators. Technical Report CS-CS-602-92, Department of Computer Science, University of Colorado, Boulder, Boulder, CO, July 1992.
• 7: [7] Raj Jain. The Art of Computer Systems Performance Evaluation. Wiley Professional Computing. John Wiley and Sons, Inc., New York, 1991.
• 8: J. R. Larus, Abstract execution: a technique for efficiently tracing programs, Software—Practice & Experience, v.20 n.12, p.1241-1258, Dec. 1990 [doi>10.1002/spe.4380201205]
• 9: [9] B. H. Margolin, R. P. Parmelee, and M. Schatzoff. Analysis of free-storage algorithms. IBM Systems Journal, 10(4):283-304, 1971.
• 10: Rodney R. Oldehoeft , Stephen J. Allan, Adaptive exact-fit storage management, Communications of the ACM, v.28 n.5, p.506-511, May 1985 [doi>10.1145/3532.3536]
• 11: Thomas A. Standish, Data Structure Techniques, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1980
• 12: Charles Burr Weinstock, Dynamic storage allocation techniques., Carnegie Mellon University, Pittsburgh, PA, 1976
• 13: [13] Benjamin Zorn. The measured cost of conservative garbage collection. Technical Report CU-CS- 573-92, Department of Computer Science, University of Colorado, Boulder, Boulder, CO, February 1992.
• 14: [14] Benjamin Zorn and Dirk Grunwald. Evaluating models of memory allocation. Technical Report CS-CS-603-92, Department of Computer Science, University of Colorado, Boulder, Boulder, CO, July 1992.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: C

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

General Terms:
Algorithms, Design, Languages, Measurement, Performance, Theory