skip to main content
10.1145/2429069.2429077acmconferencesArticle/Chapter ViewAbstractPublication PagespoplConference Proceedingsconference-collections
research-article

Cache and I/O efficent functional algorithms

Published: 23 January 2013 Publication History

Abstract

The widely studied I/O and ideal-cache models were developed to account for the large difference in costs to access memory at different levels of the memory hierarchy. Both models are based on a two level memory hierarchy with a fixed size primary memory(cache) of size M, an unbounded secondary memory organized in blocks of size B. The cost measure is based purely on the number of block transfers between the primary and secondary memory. All other operations are free. Many algorithms have been analyzed in these models and indeed these models predict the relative performance of algorithms much more accurately than the standard RAM model. The models, however, require specifying algorithms at a very low level requiring the user to carefully lay out their data in arrays in memory and manage their own memory allocation.
In this paper we present a cost model for analyzing the memory efficiency of algorithms expressed in a simple functional language. We show how some algorithms written in standard forms using just lists and trees (no arrays) and requiring no explicit memory layout or memory management are efficient in the model. We then describe an implementation of the language and show provable bounds for mapping the cost in our model to the cost in the ideal-cache model. These bound imply that purely functional programs based on lists and trees with no special attention to any details of memory layout can be as asymptotically as efficient as the carefully designed imperative I/O efficient algorithms. For example we describe an O(n_B logM/Bn_B)cost sorting algorithm, which is optimal in the ideal cache and I/O models.

Supplementary Material

JPG File (r2d1_talk1.jpg)
MP4 File (r2d1_talk1.mp4)

References

[1]
J. Abello, A. L. Buchsbaum, and J. Westbrook. A functional approach to external graph algorithms. Algorithmica, 32 (3): 437--458, 2002.
[2]
A. Aggarwal and J. S. Vitter. The input/output complexity of sorting and related problems. Commun. ACM, 31 (9): 1116--1127, 1988.
[3]
A. W. Appel. Garbage collection can be faster than stack allocation. Inf. Process. Lett., 25 (4): 275--279, 1987.
[4]
L. Arge, M. A. Bender, E. D. Demaine, C. E. Leiserson, and K. Mehlhorn, editors. Cache-Oblivious and Cache-Aware Algorithms, 18.07. - 23.07.2004, volume 04301 of Dagstuhl Seminar Proceedings, 2005. IBFI, Schloss Dagstuhl, Germany.
[5]
G. E. Blelloch and J. Greiner. Parallelism in sequential functional languages. In FPCA, pages 226--237, 1995.
[6]
Y.-J. Chiang, M. T. Goodrich, E. F. Grove, R. Tamassia, D. E. Vengroff, and J. S. Vitter. External-memory graph algorithms. In K. L. Clarkson, editor, SODA, pages 139--149. ACM/SIAM, 1995. ISBN 0--89871--349--8.
[7]
T. M. Chilimbi and J. R. Larus. Using generational garbage collection to implement cache-conscious data placement. In S. L. P. Jones and R. E. Jones, editors, ISMM, pages 37--48. ACM, 1998. ISBN 1--58113--114--3.
[8]
R. Courts. Improving locality of reference in a garbage-collecting memory management system. Commun. ACM, 31 (9): 1128--1138, 1988.
[9]
M. Frigo, C. E. Leiserson, H. Prokop, and S. Ramachandran. Cache-oblivious algorithms. In FOCS, pages 285--298. IEEE Computer Society, 1999.
[10]
M. T. Goodrich, J.-J. Tsay, D. E. Vengroff, and J. S. Vitter. External-memory computational geometry (preliminary version). In FOCS, pages 714--723. IEEE Computer Society, 1993.
[11]
J. Greiner and G. E. Blelloch. A provably time-efficient parallel implementation of full speculation. ACM Trans. Program. Lang. Syst., 21 (2): 240--285, 1999.
[12]
D. Grunwald, B. G. Zorn, and R. Henderson. Improving the cache locality of memory allocation. In R. Cartwright, editor, PLDI, pages 177--186. ACM, 1993. ISBN 0--89791--598--4.
[13]
R. Harper. Practical Foundations for Programming Languages. Cambridge University Press, 2013. (Draft available at http://www.cs.cmu.edu/ rwh/plbook/book.pdf.).
[14]
R. Jones and R. Lins. Garbage Collection: Algorithms for Automatic Dynamic Memory Management. Wiley, 1996.
[15]
U. Meyer, P. Sanders, and J. F. Sibeyn, editors. Algorithms for Memory Hierarchies, Advanced Lectures {Dagstuhl Research Seminar, March 10--14, 2002}, volume 2625 of Lecture Notes in Computer Science, 2003. Springer. ISBN 3--540-00883--7.
[16]
J. G. Morrisett, M. Felleisen, and R. Harper. Abstract models of memory management. In FPCA, pages 66--77, 1995.
[17]
K. Munagala and A. G. Ranade. I/o-complexity of graph algorithms. In R. E. Tarjan and T. Warnow, editors, SODA, pages 687--694. ACM/SIAM, 1999. ISBN 0--89871--434--6.
[18]
G. D. Plotkin. LCF considered as a programming language. Theor. Comput. Sci., 5 (3): 223--255, 1977.
[19]
M. Rahn, P. Sanders, and J. Singler. Scalable distributed-memory external sorting. In F. Li, M. M. Moro, S. Ghandeharizadeh, J. R. Haritsa, G. Weikum, M. J. Carey, F. Casati, E. Y. Chang, I. Manolescu, S. Mehrotra, U. Dayal, and V. J. Tsotras, editors, ICDE, pages 685--688. IEEE, 2010. ISBN 978--1--4244--5444-0.
[20]
D. D. Sleator and R. E. Tarjan. Amortized efficiency of list update and paging rules. Commun. ACM, 28 (2): 202--208, 1985.
[21]
D. Spoonhower, G. E. Blelloch, R. Harper, and P. B. Gibbons. Space profiling for parallel functional programs. In J. Hook and P. Thiemann, editors, ICFP, pages 253--264. ACM, 2008. ISBN 978--1--59593--919--7.
[22]
J. S. Vitter. Algorithms and data structures for external memory. Foundations and Trends in Theoretical Computer Science, 2 (4): 305--474, 2006.
[23]
P. R. Wilson, M. S. Lam, and T. G. Moher. Caching considerations for generational garbage collection. In LISP and Functional Programming, pages 32--42, 1992.

Cited By

View all
  • (2017)A Compositional Type Systems for Finding Log Memory Bounds of Transactional ProgramsProceedings of the 8th International Symposium on Information and Communication Technology10.1145/3155133.3155183(409-416)Online publication date: 7-Dec-2017
  • (2017)Polymorphism, subtyping, and type inference in MLsubACM SIGPLAN Notices10.1145/3093333.300988252:1(60-72)Online publication date: 1-Jan-2017
  • (2017)Semantic-directed clumping of disjunctive abstract statesACM SIGPLAN Notices10.1145/3093333.300988152:1(32-45)Online publication date: 1-Jan-2017
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
POPL '13: Proceedings of the 40th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages
January 2013
586 pages
ISBN:9781450318327
DOI:10.1145/2429069
  • cover image ACM SIGPLAN Notices
    ACM SIGPLAN Notices  Volume 48, Issue 1
    POPL '13
    January 2013
    561 pages
    ISSN:0362-1340
    EISSN:1558-1160
    DOI:10.1145/2480359
    Issue’s Table of Contents
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]

Sponsors

In-Cooperation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 January 2013

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. I/O efficient algorithms
  2. cost semantics

Qualifiers

  • Research-article

Conference

POPL '13
Sponsor:

Acceptance Rates

Overall Acceptance Rate 860 of 4,328 submissions, 20%

Upcoming Conference

POPL '26

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)8
  • Downloads (Last 6 weeks)0
Reflects downloads up to 19 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2017)A Compositional Type Systems for Finding Log Memory Bounds of Transactional ProgramsProceedings of the 8th International Symposium on Information and Communication Technology10.1145/3155133.3155183(409-416)Online publication date: 7-Dec-2017
  • (2017)Polymorphism, subtyping, and type inference in MLsubACM SIGPLAN Notices10.1145/3093333.300988252:1(60-72)Online publication date: 1-Jan-2017
  • (2017)Semantic-directed clumping of disjunctive abstract statesACM SIGPLAN Notices10.1145/3093333.300988152:1(32-45)Online publication date: 1-Jan-2017
  • (2017)Stream fusion, to completenessACM SIGPLAN Notices10.1145/3093333.300988052:1(285-299)Online publication date: 1-Jan-2017
  • (2017)Parallel functional arraysACM SIGPLAN Notices10.1145/3093333.300986952:1(706-718)Online publication date: 1-Jan-2017
  • (2017)Towards automatic resource bound analysis for OCamlACM SIGPLAN Notices10.1145/3093333.300984252:1(359-373)Online publication date: 1-Jan-2017
  • (2017)Parallel functional arraysProceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages10.1145/3009837.3009869(706-718)Online publication date: 1-Jan-2017
  • (2017)Towards automatic resource bound analysis for OCamlProceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages10.1145/3009837.3009842(359-373)Online publication date: 1-Jan-2017
  • (2017)ML for ML: Learning Cost Semantics by ExperimentTools and Algorithms for the Construction and Analysis of Systems10.1007/978-3-662-54577-5_11(190-207)Online publication date: 31-Mar-2017
  • (2015)Cache efficient functional algorithmsCommunications of the ACM10.1145/277682558:7(101-108)Online publication date: 25-Jun-2015
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media