Cited By
View all- Sandal SOvatman T(2023)Enhancing Ropes for Collaborative Text Editing2023 Congress in Computer Science, Computer Engineering, & Applied Computing (CSCE)10.1109/CSCE60160.2023.00415(2593-2599)Online publication date: 24-Jul-2023
Quad Ropes: immutable, declarative arrays with parallelizable operations
Pages 1 - 8
Abstract
We describe the quad rope data structure, a representation of immutable two-dimensional arrays that avoids many of the performance pitfalls of plain C-style two-dimensional arrays. Our motivation is that, for end-user development in high-level declarative programming languages, it is impractical to let users choose between different array-like data structures. Instead, one should use the same, somewhat performance-robust, representation for every programming task.
Quad ropes roughly retain array efficiency, as long as programmers express their programs using high-level constructs. Moreover, they allow for fast concatenation and dynamic task-based parallelism and are well suited to represent sparse arrays. We describe their operational semantics and evaluate the performance of individual functions on quad ropes as well as declarative algorithms that use our quad rope implementation.
References
[1]
L. Bergstrom, M. Rainey, J. Reppy, A. Shaw, and M. Fluet. Lazy Tree Splitting. In Proceedings of the 15th ACM SIGPLAN International Conference on Functional Programming, ICFP ’10, pages 93–104, New York, NY, USA, 2010. ACM.
[2]
A. Biboudis, N. Palladinos, and Y. Smaragdakis. Clash of the Lambdas, July 2014.
[3]
G. E. Blelloch. Programming Parallel Algorithms. Commun. ACM, 39(3):85–97, Mar. 1996.
[4]
H.-J. Boehm, R. Atkinson, and M. Plass. Ropes: an Alternative to Strings. Software – Practice & Experience, 25:1315–1330, Dec. 1995.
[5]
D. Chase and Y. Lev. Dynamic circular work-stealing deque. In SPAA ’05: Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, pages 21–28, New York, NY, USA, 2005. ACM.
[6]
P. F. Dietz. Fully persistent arrays. In F. Dehne, J. R. Sack, and N. Santoro, editors, Algorithms and Data Structures, volume 382 of Lecture Notes in Computer Science, pages 67–74. Springer Berlin Heidelberg, 1989.
[7]
R. A. Finkel and J. L. Bentley. Quad Trees A Data Structure for Retrieval on Composite Keys. Acta Informatica, 4(1):1–9, Mar. 1974.
[8]
G. Huet. The Zipper. Journal of Functional Programming, 7(05): 549–554, Sept. 1997.
[9]
H. Kaplan and R. E. Tarjan. Persistent Lists with Catenation via Recursive Slow-down. In Proceedings of the Twenty-seventh Annual ACM Symposium on Theory of Computing, STOC ’95, pages 93–102, New York, NY, USA, 1995. ACM.
[10]
A. Kumar, G. E. Blelloch, and R. Harper. Parallel Functional Arrays. In Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages, POPL 2017, pages 706–718, New York, NY, USA, 2017. ACM.
[11]
D. Leijen, W. Schulte, and S. Burckhardt. The Design of a Task Parallel Library. In Proceedings of the 24th ACM SIGPLAN Conference on Object Oriented Programming Systems Languages and Applications, volume 44 of OOPSLA ’09, pages 227–242, New York, NY, USA, 2009. ACM. ISBN 978-1-60558-766-0.
[12]
P. Sestoft. Microbenchmarks in Java and C#. Lecture Notes, Sept. 2013.
[13]
P. Sestoft. Spreadsheet Implementation Technology: Basics and Extensions. The MIT Press, Sept. 2014. ISBN 0262526646.
[14]
G. L. Steele. Parallel Programming and Parallel Abstractions in Fortress. In Proceedings of the 8th International Conference on Functional and Logic Programming, FLOPS’06, page 1, Berlin, Heidelberg, 2006. Springer-Verlag.
[15]
G. L. Steele. Organizing Functional Code for Parallel Execution or, Foldl and Foldr Considered Slightly Harmful. In Proceedings of the 14th ACM SIGPLAN International Conference on Functional Programming, volume 44 of ICFP ’09, pages 1–2, New York, NY, USA, Aug. 2009. ACM.
[16]
N. Stucki, T. Rompf, V. Ureche, and P. Bagwell. RRB Vector: A Practical General Purpose Immutable Sequence. In Proceedings of the 20th ACM SIGPLAN International Conference on Functional Programming, ICFP 2015, pages 342–354, New York, NY, USA, 2015. ACM.
[17]
D. Syme, A. Granicz, and A. Cisternino. Expert F# 4.0. Apress, Berkely, CA, USA, 4th edition, 2015. ISBN 1484207416, 9781484207413.
[18]
A. Tzannes, G. C. Caragea, R. Barua, and U. Vishkin. Lazy Binary-splitting: A Run-time Adaptive Work-stealing Scheduler. In Proceedings of the 15th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, volume 45 of PPoPP ’10, pages 179–190, New York, NY, USA, Jan. 2010. ACM.
Index Terms
- Quad Ropes: immutable, declarative arrays with parallelizable operations
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 2017
62 pages
ISBN:9781450350693
DOI:10.1145/3091966
- General Chairs:
- Martin Elsman,
- Clemens Grelck,
- Andreas Kloeckner,
- David Padua,
- Edgar Solomonik
Copyright © 2017 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 the author(s) 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
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 18 June 2017
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
PLDI '17
Sponsor:
PLDI '17: ACM SIGPLAN Conference on Programming Language Design and Implementation
June 18, 2017
Barcelona, Spain
Acceptance Rates
Overall Acceptance Rate 17 of 25 submissions, 68%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 167Total Downloads
- Downloads (Last 12 months)7
- Downloads (Last 6 weeks)0
Reflects downloads up to 22 Feb 2025
Other Metrics
Citations
Cited By
View all- Sandal SOvatman T(2023)Enhancing Ropes for Collaborative Text Editing2023 Congress in Computer Science, Computer Engineering, & Applied Computing (CSCE)10.1109/CSCE60160.2023.00415(2593-2599)Online publication date: 24-Jul-2023
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in