Article

Recursive data structure profiling

Authors:

Easwaran Raman,

David I. AugustAuthors Info & Claims

MSP '05: Proceedings of the 2005 workshop on Memory system performance

Pages 5 - 14

https://doi.org/10.1145/1111583.1111585

Published: 12 June 2005 Publication History

Abstract

As the processor-memory performance gap increases, so does the need for aggressive data structure optimizations to reduce memory access latencies. Such optimizations require a better understanding of the memory behavior of programs. We propose a profiling technique called Recursive Data Structure Profiling to help better understand the memory access behavior of programs that use recursive data structures (RDS) such as lists, trees, etc. An RDS profile captures the runtime behavior of the individual instances of recursive data structures. RDS profiling differs from other memory profiling techniques in its ability to aggregate information pertaining to an entire data structure instance, rather than merely capturing the behavior of individual loads and stores, thereby giving a more global view of a program's memory accesses.This paper describes a method for collecting RDS profile without requiring any high-level program representation or type information. RDS profiling achieves this with manageable space and time overhead on a mixture of pointer intensive benchmarks from the SPEC, Olden and other benchmark suites. To illustrate the potential of the RDS profile in providing a better understanding of memory accesses, we introduce a metric to quantify the notion of stability of an RDS instance. A stable RDS instance is one that undergoes very few changes to its structure between its initial creation and final destruction, making it an attractive candidate to certain data structure optimizations.

References

[1]

Calder, B., Krintz, C., John, S., and Austin, T. Cache-conscious data placement. In Proceedings of the 8th International Symposium on Architectural Support for Programming Languages and Operating Systems ASPLOS'98 (October 1998).

Digital Library

[2]

Clark, D. W. List structure: measurements, algorithms, and encodings. PhD thesis, Computer Science Department, Carnegie Mellon University, Pittsburgh, PA, 1976.

Digital Library

[3]

Cormen, T. H., Leiserson, C. E., and Rivest, R. L. Introduction to Algorithms. The MIT Press and McGraw-Hill, 1992.

Digital Library

[4]

Ghiya, R., and Hendren, L. J. Is it a tree, dag, or cyclic graph? In Proceedings of the ACM Symposium on Principles of Programming Languages (January 1996).

Digital Library

[5]

Hackett, B., and Rugina, R. Region-based shape analysis with tracked locations. In Proceedings of the 32nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (2005), pp. 310--323.

Digital Library

[6]

Kaplan, H., Shafrir, N., and Tarjan, R. E. Union-find with deletions. In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (2002), pp. 19--28.

Digital Library

[7]

Lattner, C., and Adve, V. Automatic pool allocation for disjoint data structures. In Proceedings of the Workshop on Memory System Performance (2002), ACM Press, pp. 13--24.

Digital Library

[8]

Lattner, C., and Adve, V. Data structure analysis: A fast and scalable context-sensitive heap analysis. Tech. Rep. UIUCDCS-R-2003-2340, University of Illinois, Urbana, Illinois, April 2003.

[9]

Luk, C.-K., Cohn, R., Muth, R., Patil, H., Klauser, A., Lowney, G., Wallace, S., Reddi, V. J., and Hazelwood, K. Pin: Building customized program analysis tools with dynamic instrumentation. In Proceedings of the ACM SIGPLAN 2005 Conference on Programming Language Design and Implementation (June 2005).

Digital Library

[10]

Luk, C.-K., and Mowry, T. C. Memory forwarding: Enabling aggressive layout optimizations by guaranteeing the safety of data relocation. In Proceedings of the 26th International Symposium on Computer Architecture (July 1999).

Digital Library

[11]

Nystrom, E. M., Ju, R. D., and Hwu, W. W. Characterization of repeating data access patterns in integer benchmarks. In Proceedings of the 28th International Symposium on Computer Architecture (September 2001).

[12]

Pearce, D. J., and Kelly, P. H. J. Online algorithms for topological order and strongly connected components. Tech. rep., Imperial College, September 2003.

[13]

Rugina, R. Quantitative shape analysis. In Proceedings of the 11th Static Analysis Symposium (2004).

[14]

Sagiv, M., Reps, T., and R. Wilhelm. Solving shape-analysis problems in languages with destructive updating. In Proceedings of the 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL) (January 1996), pp. 16--31.

Digital Library

[15]

Vachharajani, M., Vachharajani, N., Penry, D. A., Blome, J. A., and August, D. I. Microarchitectural exploration with Liberty. In Proceedings of the 35th International Symposium on Microarchitecture (MICRO) (November 2002), pp. 271--282.

Digital Library

[16]

Wu, Q., Pyatakov, A., Spiridonov, A. N., Raman, E., Clark, D. W., and August, D. I. Exposing memory access regularities using object-relative memory profiling. In Proceedings of the International Symposium on Code Generation and Optimization (2004), IEEE Computer Society.

Digital Library

Cited By

Pei KGuan JBroughton MChen ZYao SWilliams-King DUmmadisetty VYang JRay BJana SSpinellis DGousios GChechik MDi Penta M(2021)StateFormer: fine-grained type recovery from binaries using generative state modelingProceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3468264.3468607(690-702)Online publication date: 20-Aug-2021
https://dl.acm.org/doi/10.1145/3468264.3468607
Joshi KFernando VMisailovic SAtlee JBultan TWhittle J(2019)Statistical algorithmic profiling for randomized approximate programsProceedings of the 41st International Conference on Software Engineering10.1109/ICSE.2019.00071(608-618)Online publication date: 25-May-2019
https://dl.acm.org/doi/10.1109/ICSE.2019.00071
Jeong JLim JSon Y(2019)A data type inference method based on long short-term memory by improved feature for weakness analysis in binary codeFuture Generation Computer Systems10.1016/j.future.2019.05.013Online publication date: May-2019
https://doi.org/10.1016/j.future.2019.05.013
Show More Cited By

Index Terms

Recursive data structure profiling

Recommendations

PROMPT: A Fast and Extensible Memory Profiling Framework

Memory profiling captures programs’ dynamic memory behavior, assisting programmers in debugging, tuning, and enabling advanced compiler optimizations like speculation-based automatic parallelization. As each use case demands its unique program trace ...
TEMProf: memory profiling via EM-emanation in iot and hand-held devices
MICRO-51: Proceedings of the 51st Annual IEEE/ACM International Symposium on Microarchitecture

This paper presents EMProf, a new method for profiling the performance impact of the memory subsystem without any support on, or interference with, the profiled system. Rather than rely on hardware support and/or software instrumentation on the profiled ...
Understanding object-level memory access patterns across the spectrum
SC '17: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis

Memory accesses limit the performance and scalability of countless applications. Many design and optimization efforts will benefit from an in-depth understanding of memory access behavior, which is not offered by extant access tracing and profiling ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

MSP '05: Proceedings of the 2005 workshop on Memory system performance

June 2005

74 pages

ISBN:1595931473

DOI:10.1145/1111583

General Chair:
Brad Calder
U. C, San Diego
,
Program Chair:
Ben Zorn
Microsoft

Copyright © 2005 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 June 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

MSP05

MSP05: Memory Systems Performance Workshop

June 12, 2005

Illinois, Chicago

Acceptance Rates

Overall Acceptance Rate 6 of 20 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

29
Total Citations
View Citations
396
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Pei KGuan JBroughton MChen ZYao SWilliams-King DUmmadisetty VYang JRay BJana SSpinellis DGousios GChechik MDi Penta M(2021)StateFormer: fine-grained type recovery from binaries using generative state modelingProceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3468264.3468607(690-702)Online publication date: 20-Aug-2021
https://dl.acm.org/doi/10.1145/3468264.3468607
Joshi KFernando VMisailovic SAtlee JBultan TWhittle J(2019)Statistical algorithmic profiling for randomized approximate programsProceedings of the 41st International Conference on Software Engineering10.1109/ICSE.2019.00071(608-618)Online publication date: 25-May-2019
https://dl.acm.org/doi/10.1109/ICSE.2019.00071
Jeong JLim JSon Y(2019)A data type inference method based on long short-term memory by improved feature for weakness analysis in binary codeFuture Generation Computer Systems10.1016/j.future.2019.05.013Online publication date: May-2019
https://doi.org/10.1016/j.future.2019.05.013
Grech NFourtounis GFrancalanza ASmaragdakis YTip FBodden E(2018)Shooting from the heap: ultra-scalable static analysis with heap snapshotsProceedings of the 27th ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3213846.3213860(198-208)Online publication date: 12-Jul-2018
https://dl.acm.org/doi/10.1145/3213846.3213860
Rupprecht TChen XWhite DBoockmann JLüttgen GBos HRosu GDi Penta MNguyen T(2017)DSIbin: identifying dynamic data structures in C/C++ binariesProceedings of the 32nd IEEE/ACM International Conference on Automated Software Engineering10.5555/3155562.3155607(331-341)Online publication date: 30-Oct-2017
https://dl.acm.org/doi/10.5555/3155562.3155607
Ji XWang CEl-Sayed NMa XKim YVazhkudai SXue WSanchez DMohr BRaghavan P(2017)Understanding object-level memory access patterns across the spectrumProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis10.1145/3126908.3126917(1-12)Online publication date: 12-Nov-2017
https://dl.acm.org/doi/10.1145/3126908.3126917
Padhye RSen KUchitel SOrso ARobillard M(2017)TravioliProceedings of the 39th International Conference on Software Engineering10.1109/ICSE.2017.50(473-483)Online publication date: 20-May-2017
https://dl.acm.org/doi/10.1109/ICSE.2017.50
Rupprecht TChen XWhite DBoockmann JLuttgen GBos H(2017)DSIbin: Identifying dynamic data structures in C/C++ binaries2017 32nd IEEE/ACM International Conference on Automated Software Engineering (ASE)10.1109/ASE.2017.8115646(331-341)Online publication date: Oct-2017
https://doi.org/10.1109/ASE.2017.8115646
Rupprecht TChen XWhite DMühlberg JBos HLüttgen GWeippl EKatzenbeisser SKruegel CMyers AHalevi S(2016)POSTERProceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security10.1145/2976749.2989041(1772-1774)Online publication date: 24-Oct-2016
https://dl.acm.org/doi/10.1145/2976749.2989041
White DRupprecht TLüttgen GZeller ARoychoudhury A(2016)DSI: an evidence-based approach to identify dynamic data structures in C programsProceedings of the 25th International Symposium on Software Testing and Analysis10.1145/2931037.2931071(259-269)Online publication date: 18-Jul-2016
https://dl.acm.org/doi/10.1145/2931037.2931071
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents