An efficient representation for lazy constructors using 64-bit pointers
Pages 23 - 30
Abstract
Pointers in the AMD64 architecture contain unused space, a feature often exploited by modern programming language implementations. We use this property in a defunctionalizing compiler for a subset of Haskell, generating fast programs having a compact memory representation of their runtime structures. We demonstrate that, in most cases, the compact representation is faster, uses less memory and has better cache characteristics. Our prototype shows competitive performance when compared to GHC with full optimizations on.
References
[1]
A.-R. Adl-Tabatabai, J. Bharadwaj, M. Cierniak, M. Eng, J. Fang, B. T. Lewis, B. R. Murphy, and J. M. Stichnoth. Improving 64-bit Java IPF performance by compressing heap references. In Proceedings of the International Symposium on Code Generation and Optimization: Feedback-directed and Runtime Optimization, CGO '04, pages 100--110, Washington, DC, USA, 2004. IEEE Computer Society. ISBN 0-7695-2102-9.
[2]
A. V. Aho, R. Sethi, and J. D. Ullman. Compilers: Principles, Techniques, and Tools. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1986.
[3]
AMD. AMD64 architecture programmer's manual volume 2: 128-bit and 256-bit media instructions, rev. 3.16. http://developer.amd.com/wordpress/media/2012/10/26568_APM_v4.pdf, 2012. Accessed: 31-01-2014.
[4]
AMD. AMD64 architecture programmer's manual volume 2: System programming, rev. 3.23. http://developer.amd.com/wordpress/media/2012/10/24593_APM_v21.pdf, 2012. Accessed: 31-01-2014.
[5]
A. W. Appel. Runtime tags aren't necessary. LISP and Symbolic Computation, 2(2):153--162, 1989.
[6]
G. Argo. Improving the three instruction machine. In Proceedings of the Fourth International Conference on Functional Programming Languages and Computer Architecture, FPCA '89, pages 100--115, New York, NY, USA, 1989. ACM.
[7]
M. Ash. Friday Q&A 2013-09-27: ARM64 and you (blog entry). https://www.mikeash.com/pyblog/friday-qa-2013-09-27-arm64-and-you.html. Accessed: 24-01-2014.
[8]
L.-R. Babé. Firefox 4 performance. https://hacks.mozilla.org/2011/03/firefox4-performance/, 2011. Accessed: 31-01-2014.
[9]
D. G. Bobrow. A note on hash linking. Communications of the ACM, 18(7):413--415, July 1975.
[10]
H. Boehm. A garbage collector for C and C++. http://www.hpl.hp.com/personal/Hans_Boehm/gc/, 2014. Accessed: 01-03-2014.
[11]
S. Y. Borkar, H. Mulder, P. Dubey, S. S. Pawlowski, K. C. Kahn, D. J. Kuck, and J. R. Rattner. Platform 2015: Intel processor and platform evolution for the next decade. Whitepaper, Intel, 2005.
[12]
L. Cardelli. Compiling a functional language. In Proceedings of the 1984 ACM Symposium on LISP and Functional Programming, LFP '84, pages 208--217, New York, NY, USA, 1984. ACM.
[13]
A. Caro. A novel 64 bit data representation for garbage collection and synchronizing memory. Technical Report Computation Structures Group Memo 396, Intel, April 1997. http://csg.csail.mit.edu/pubs/memos/Memo-396/memo-396.pdf.
[14]
A. Caro. Generating Multithreaded Code from Parallel Haskell for Symmetric Multiprocessors. PhD thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, February 1999.
[15]
H. Cejtin, S. Jagannathan, and S. Weeks. Flow-directed closure conversion for typed languages. In G. Smolka, editor, Programming Languages and Systems, volume 1782 of Lecture Notes in Computer Science, pages 56--71. Springer Berlin Heidelberg, 2000.
[16]
D. Chernicoff. The corporate datacenter -- it's ready for Windows Server x64 editions. http://download.microsoft.com/download/4/4/7/44715635--144e-4726--8705-b8ec83c0a34d/The%20Corporate%20Datacenter-It%27s%20Ready%20for%20Windows%20Server%20x64%20Editions.pdf, 2007. Accessed: 31-01-2014.
[17]
T. Chilimbi, M. Hill, and J. Larus. Making pointer-based data structures cache conscious. Computer, 33(12):67--74, Dec 2000.
[18]
O. Danvy and L. R. Nielsen. Defunctionalization at work. In Proceedings of the 3rd ACM SIGPLAN International Conference on Principles and Practice of Declarative Programming, PPDP '01, pages 162--174, New York, NY, USA, 2001. ACM.
[19]
J. Fairbairn and S. Wray. Tim: A simple, lazy abstract machine to execute supercombinators. In G. Kahn, editor, Functional Programming Languages and Computer Architecture, volume 274 of Lecture Notes in Computer Science, pages 34--45. Springer Berlin Heidelberg, 1987.
[20]
G. Fourtounis and N. S. Papaspyrou. Supporting Separate Compilation in a Defunctionalizing Compiler. In J. P. Leal, R. Rocha, and A. Simões, editors, 2nd Symposium on Languages, Applications and Technologies, volume 29 of OpenAccess Series in Informatics (OASIcs), pages 39--49, Dagstuhl, Germany, 2013. Schloss Dagstuhl? Leibniz-Zentrum fuer Informatik. 2013.39.
[21]
G. Fourtounis, N. Papaspyrou, and P. Rondogiannis. The generalized intensional transformation for implementing lazy functional languages. In Proceedings of the 15th International Symposium on Practical Aspects of Declarative Languages (PADL '13), volume 7752 of Lecture Notes in Computer Science, pages 157--172, Rome, Italy, Jan. 2013. Springer.
[22]
E. F. Gehringer and J. L. Keedy. Tagged architecture: How compelling are its advantages? In Proceedings of the 12th Annual International Symposium on Computer Architecture, ISCA '85, pages 162--170, 1985.
[23]
A. Goldberg and D. Robson. Smalltalk-80: The Language and Its Implementation. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1983.
[24]
E. Goto, T. Soma, N. Inada, T. Ida, M. Idesawa, K. Hiraki, M. Suzuki, K. Shimizu, and B. Philipov. Design of a Lisp Machine -- FLATS. In Proceedings of the 1982 ACM Symposium on LISP and Functional Programming, LFP '82, pages 208--215, New York, NY, USA, 1982. ACM.
[25]
D. Gudeman. Representing type information in dynamically typed languages. Technical Report TR 93--27, Department of Computer Science, The University of Arizona, October 1993.
[26]
R. Jones, A. Hosking, and E. Moss. The Garbage Collection Handbook: The Art of Automatic Memory Management. Chapman & Hall/CRC, 1st edition, 2011.
[27]
S. L. P. Jones. Implementing lazy functional languages on stock hardware: the Spineless Tagless G-machine -- version 2.5. Journal of Functional Programming, 2:127--202, 1992.
[28]
S. L. P. Jones, editor. Haskell 98 Language and Libraries: The Revised Report. http://haskell.org/, September 2002.
[29]
K. Langendoen and P. H. Hartel. FCG: A code generator for lazy functional languages. In U. Kastens and P. Pfahler, editors, Compiler Construction, volume 641 of Lecture Notes in Computer Science, pages 278--296. Springer Berlin Heidelberg, 1992.
[30]
C. Lattner and V. S. Adve. Transparent pointer compression for linked data structures. In Proceedings of the 2005 Workshop on Memory System Performance, MSP '05, pages 24--35, New York, NY, USA, 2005. ACM.
[31]
C. Lefurgy, E. Piccininni, and T. Mudge. Evaluation of a high performance code compression method. In Proceedings of the 32nd Annual ACM/IEEE International Symposium on Microarchitecture, MICRO 32, pages 93--102, Washington, DC, USA, 1999. IEEE Computer Society.
[32]
A. Limited. Principles of ARM memory maps. http://infocenter.arm.com/help/topic/com.arm.doc.den0001c/DEN0001C_principles_of_arm_memory_maps.pdf, 2012. Accessed: 29-01-2014.
[33]
H. Liu, N. Glew, L. Petersen, and T. A. Anderson. The Intel Labs Haskell Research Compiler. In Proceedings of the 2013 ACM SIGPLAN Symposium on Haskell, Haskell '13, pages 105--116, New York, NY, USA, 2013. ACM.
[34]
S. Marlow, A. R. Yakushev, and S. L. Peyton Jones. Faster laziness using dynamic pointer tagging. In Proceedings of the 12th ACM SIGPLAN International Conference on Functional Programming, ICFP '07, pages 277--288, New York, NY, USA, 2007. ACM.
[35]
S. Marlow, S. Peyton Jones, and S. Singh. Runtime support for multicore Haskell. In Proceedings of the 14th ACM SIGPLAN International Conference on Functional Programming, ICFP '09, pages 65--78, New York, NY, USA, 2009. ACM.
[36]
M. Matz, J. Hubicka, A. Jaeger, and M. Mitchell. AMD64 ABI draft 0.99.5, September 3, 2010. URL www.x86-64.org/documentation/abi.pdf. Accessed: 31-01-2014.
[37]
Mruby developers. Full-length nan boxing on 64bit platforms, #1441. https://github.com/mruby/mruby/pull/1441, 2013. Accessed: 31-01-2014.
[38]
N. Nethercote and A. Mycroft. The cache behaviour of large lazy functional programs on stock hardware. In Proceedings of the 2002 Workshop on Memory System Performance, MSP '02, pages 44--55, New York, NY, USA, 2002. ACM.
[39]
Oracle. Compressedoops. https://wikis.oracle.com/display/HotSpotInternals/CompressedOops, 2012. Accessed: 14-05-2014.
[40]
Oracle. SPARC Assembly Language Reference Manual, 5.2: Address Sizes. http://docs.oracle.com/cd/E26502_01/html/E28387/glyfs.html. Accessed: 28-01-2014.
[41]
M. Pall. LuaJIT 2.0 intellectual property disclosure and research opportunities. http://lua-users.org/lists/lua-l/2009-11/msg00089.html, 2009. Accessed: 31-01-2014.
[42]
N. Papaspyrou and K. Sagonas. On preserving term sharing in the Erlang virtual machine. In Proceedings of the Eleventh ACM SIGPLAN Workshop on Erlang Workshop, Erlang '12, pages 11--20, New York, NY, USA, 2012. ACM. 2364493.
[43]
F. Pottier and N. Gauthier. Polymorphic typed defunctionalization and concretization. Higher-Order and Symbolic Computation, 19: 125--162, 2006.
[44]
T. Schilling. Challenges for a trace-based just-in-time compiler for Haskell. In A. Gill and J. Hage, editors, Implementation and Application of Functional Languages, volume 7257 of Lecture Notes in Computer Science, pages 51--68. Springer Berlin Heidelberg, 2012.
[45]
The IEEE and The Open Group. The Open Group Base Specifications Issue 6, IEEE Std 1003.1, stdint.h -- integer types. http://pubs.opengroup.org/onlinepubs/000095399/basedefs/stdint.h.html, 2004. Accessed: 28-01-2014.
[46]
K. Venstermans, L. Eeckhout, and K. D. Bosschere. Object-relative addressing: Compressed pointers in 64-bit Java virtual machines. In E. Ernst, editor, ECOOP, volume 4609 of Lecture Notes in Computer Science, pages 79--100. Springer, 2007.
[47]
K. Venstermans, L. Eeckhout, and K. De Bosschere. Java object header elimination for reduced memory consumption in 64-bit virtual machines. ACM Transactions on Architecture and Code Optimization, 4(3), Sept. 2007.
[48]
W. A. Wulf and S. A. McKee. Hitting the memory wall: Implicationsof the obvious. SIGARCH Computer Architecture News, 23(1):20--24, Mar. 1995.
[49]
Y. Zhang and R. Gupta. Data compression transformations for dynamically allocated data structures. In R. N. Horspool, editor, CC, volume 2304 of Lecture Notes in Computer Science, pages 14--28. Springer, 2002.
Index Terms
- An efficient representation for lazy constructors using 64-bit pointers
Recommendations
Introducing the Intel i860 64-Bit Microprocessor
The authors describe the single-chip i860 CPU, a 64-bit, RISC (reduced-instruction-set-computer)-based microprocessor that executes parallel instructions using mainframe and supercomputer architectural concepts. They designed the 1,000,000-transistor, ...
Enhancing the performance of 16-bit code using augmenting instructions
Special Issue: Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool support for embedded systems (San Diego, CA).In the embedded domain, memory usage and energy consumption are critical constraints. Dual width instruction set embedded processors such as the ARM provide a 16-bit instruction set in addition to the 32-bit instruction set to address these concerns. ...
Performance characterization of the 64-bit x86 architecture from compiler optimizations' perspective
CC'06: Proceedings of the 15th international conference on Compiler ConstructionIntel Extended Memory 64 Technology (EM64T) and AMD 64-bit architecture (AMD64) are emerging 64-bit x86 architectures that are fully x86 compatible. Compared with the 32-bit x86 architecture, the 64-bit x86 architectures cater some new features to ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
September 2014
116 pages
ISBN:9781450330404
DOI:10.1145/2636228
- General Chair:
- Jost Berthold,
- Program Chairs:
- Mary Sheeran,
- Ryan Newton
Copyright © 2014 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]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 03 September 2014
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
Conference
ICFP'14
Sponsor:
ICFP'14: ACM SIGPLAN International Conference on Functional Programming
September 4, 2014
Gothenburg, Sweden
Acceptance Rates
FHPC '14 Paper Acceptance Rate 10 of 11 submissions, 91%;
Overall Acceptance Rate 18 of 25 submissions, 72%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 90Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 26 Dec 2024
Other Metrics
Citations
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