Evaluating models of memory allocation

ABSTRACT

Because dynamic memory management is an important part of a large class of computer programs, high-performance algorithms for dynamic memory management have been and will continue to be of considerable interest. The goal of this research is to explore the size and accuracy of synthetic models of program allocation behavior. These models, if accurate enough, proved an attractive alternative to algorithm evaluation based on trace-driven simulation using actual traces. Based on our analysis, we conclude that even relatively simple synthetic models can effectively emulate the allocation behavior of well-behaved programs. However, even the most complex models we investigate can only roughly approximate the behavior of more complex programs and/or allocation policies. While synthetic models have been used to evaluate the performance of dynamic memory management algorithms, our results show that these models can be inaccurate and must be used with care. Given current trends toward more complex applications and allocation algorithms, the synthetic models we investigate are likely to be even less accurate in the future.

REFERENCES

• 1: Thomas Ball , James R. Larus, Optimally profiling and tracing programs, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.59-70, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143180]
• 2: BELADY, L.A. 1966. A study of replacement algorithms for virtual storage computers. IBM Syst. J. 5, 2, 78-101.
• 3: Gerald Bozman, The software lookaside buffler reduces search overhead with linked lists, Communications of the ACM, v.27 n.3, p.222-227, March 1984 [doi>10.1145/357994.358020]
• 4: BOZMAN, G., BUCO, W., DALY, T. P., AND TETZLAFF, W. H. 1984. Analysis of free-storage algorithms--revisited. IBM Syst. J. 23, 1, 44 64.
• 5: 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]
• 6: Asit Dan , Philip S. Yu , Jen-Yao Chung, Database Access Characterization for Buffer Hit Prediction, Proceedings of the Ninth International Conference on Data Engineering, p.134-143, April 19-23, 1993
• 7: 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
• 8: JAIN, R. 1991. The Art of Computer Systems Performance Evaluation. Wiley, New York.
• 9: Raj Jain , Imrich Chlamtac, The P2 algorithm for dynamic calculation of quantiles and histograms without storing observations, Communications of the ACM, v.28 n.10, p.1076-1085, Oct. 1985 [doi>10.1145/4372.4378]
• 10: KINGSLEY, C. 1982. Description of a very fast storage allocator. Documentation of 4.2 BSD Unix malloc implementation. Univ. of California, Berkeley, Calif.
• 11: Donald Ervin Knuth, The Art of Computer Programming, 2nd Ed. (Addison-Wesley Series in Computer Science and Information, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1978
• 12: KORN, D. G. AND Vo, K.-P. 1985. In search of a better malloc. In Proceedings of the Summer 1985 USENIX Conference. USENIX Association, Berkeley, Calif., 489-506.
• 13: 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]
• 14: MARGOLIN, B. H., PARMELEE, R. P., AND SCHATZOFF, M. 1971. Analysis of free-storage algorithms. IBM Syst. J. 10, 4, 283-304.
• 15: MATTSON, R. L, GECSEI, J., SLUTZ, D. R., AND TRAIGER, I.L. 1970. Evaluation techniques for storage hierarchies. IBM Syst. J. 9, 2, 78-117.
• 16: 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]
• 17: Alan Jay Smith, Cache Memories, ACM Computing Surveys (CSUR), v.14 n.3, p.473-530, Sept. 1982 [doi>10.1145/356887.356892]
• 18: WILSON, P. R., LAl~r, M. S., AND MOHER, T.G. 1990. Caching considerations for generation garbage collection: A case for large and set associative caches. Tech. Rep. UIC-EECS-90-5, Software Systems Lab, Univ. of Illinois at Chicago, Chicago, Ill.
• 19: Benjamin Zorn , Dirk Grunwald, Empirical measurements of six allocation-intensive C programs, ACM SIGPLAN Notices, v.27 n.12, p.71-80, Dec. 1992 [doi>10.1145/142181.142200]
• 20: ZORN, B.G. 1991. The effect of garbage collection on cache performance. Tech. Rep. CU-CS- 528-91, Dept. of Computer Science, Univ. of Colorado, Boulder.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS

General Terms:
Algorithms, Measurement, Performance, Verification

Keywords:
dynamic storage allocation, model evaluation, program behavior modeling, program measurement, trace-driven simulation