More Web Proxy on the site http://driver.im/

Article

Smaller footprint for java collections

Authors:

Yuval ShimronAuthors Info & Claims

ECOOP'12: Proceedings of the 26th European conference on Object-Oriented Programming

Pages 356 - 382

https://doi.org/10.1007/978-3-642-31057-7_17

Published: 11 June 2012 Publication History

Abstract

In dealing with the container bloat problem, we identify five memory compaction techniques, which can be used to reduce the footprint of the large number of small objects that make these containers. Using these techniques, we describe two alternative methods for more efficient encoding of the JRE's ubiquitous HashMap data structure, and present a mathematical model in which the footprint of this can be analyzed. The fused hashing encoding method reduces memory overhead by 20%---45% on a 32-bit environment and 45%---65% on a 64-bit environment. This encoding guarantees these figures as lower bound regardless of the distribution of keys in hash buckets. The more opportunistic squashed hashing, achieves expected savings of 25%---70% on a 32-bit environment and 30%---75% on a 64-bit environments, but these savings can degrade and are not guaranteed against bad (and unlikely) distribution of keys to buckets. Both techniques are applicable and give merit to an implementation of HashSet which is independent of that of HashMap. Benchmarking using the SPECjvm2008, SPECjbb2005 and DaCapo suites does not demonstrate significant major slowdown or speedup. For TreeMap we show two encodings which reduce the overhead of tree nodes by 43% & 46% on a 32-bit environment and 55% & 73% on a 64-bit environment. These also give to separating the implementation of TreeSet from that of TreeMap, which gives rise to footprint reduction of 59% & 54% on a 32-bit environment and 61% & 77% on a 64-bit environment.

References

[1]

Adl-Tabatabai, A.-R., Cierniak, M., Lueh, G.-Y., Parikh, V. M., Stichnoth, J. M.: Fast, effective code generation in a just-in-time Java compiler. In: Proc. of the Conference on Programming Language Design and Implementation (PLDI 2008), Tucson, Arizona, June 7-13. ACM Press (2008)

Digital Library

[2]

Alon, N., Dietzfelbinger, M., Miltersen, P. B., Petrank, E., Tardos, G.: Linear hash functions. J. ACM 46 (September 1999)

Digital Library

[3]

Arbitman, Y., Naor, M., Segev, G.: Backyard Cuckoo hashing: Constant worstcase operations with a succinct representation. In: Proc. of the 51st IEEE Annual Symp. on Foundation of Comp. Sci. (FOCS 2010), Las Vegas, Navada, October 23-26. IEEE Computer Society Press (2010)

Digital Library

[4]

Bacon, D. F., Fink, S. J., Grove, D.: Space and time efficient implementation of the Java object model. In: Proc. of the 17th Ann. Conf. on OO Prog. Sys., Lang., & Appl. (OOPSLA 2002), Seattle, Washington, November 4-8 (2002); ACM SIGPLAN Notices 37(11)

Digital Library

[5]

Caromel, D., Reynders, J., Philippsen, M.: Benchmarking Java against C and Fortran for scientific applications. In: Thomas, D. (ed.) Proc. of the 20th Euro. Conf. on OO Prog. (ECOOP 2006), Nantes, France, July 3-7. LNCS, vol. 4067. Springer (2006)

[6]

Clarke, D. G., Potter, J. M., Noble, J.: Ownership types for flexible alias protection. In: Proc. of the 13th Ann. Conf. on OO Prog. Sys., Lang., & Appl. (OOPSLA 1998), Vancouver, British Columbia, Canada, October 18-22 (1998); ACM SIGPLAN Notices 33(10)

Digital Library

[7]

Cramer, T., Friedman, R., Miller, T., Seberger, D., Wilson, R., Wolczko, M.: Compiling Java just in time. IEEE Micro 17(3) (May/June 1998)

Digital Library

[8]

Cranor, L. F., Wright, R. N.: Influencing software usage. In: Proc. of the 10th Conference on Computers, Freedom and Privacy (CFP 2000). ACM (2000)

Digital Library

[9]

Dufour, B., Ryder, B. G., Sevitsky, G.: A scalable technique for characterizing the usage of temporaries in framework-intensive Java applications. In: Proc. of the 16th ACM SIGSOFT Symp. on the Foundations of Soft. Eng. (FSE 2008), Atlanta, Georgia, November 9-14. ACM Press (2008)

Digital Library

[10]

Eckel, N., Gil, J.: Empirical Study of Object-Layout Strategies and Optimization Techniques. In: Bertino, E. (ed.) ECOOP 2000. LNCS, vol. 1850, pp. 394-421. Springer, Heidelberg (2000)

Digital Library

[11]

Feller, W.: An Introduction to Probability Theory and Its Applications, vol. I. Wiley (1968)

[12]

Gil, Y., Lenz, K., Shimron, Y.: A microbenchmark case study and lessons learned. In: Proc. of the 5th International Conference Companion on Object Oriented Programming Systems Languages and Applications Companion (VMIL 2011). ACM (2011)

Digital Library

[13]

Hsieh, C. H. A., Conte, M. T., Johnson, T. L., Gyllenhaal, J.C., Hwu, W. M. W.: Compilers for improved Java performance. Computer 30(6) (June 1997)

Digital Library

[14]

Kawachiya, K., Ogata, K., Onodera, T.: Analysis and reduction of memory inefficiencies in Java strings. In: Harris, G. E. (ed.) Proc. of the 23rd Ann. Conf. on OO Prog. Sys., Lang., & Appl. (OOPSLA 2008), Nashville, Tennessee, October 19-23. ACM (2008)

Digital Library

[15]

Kotzmann, T., Wimmer, C., Mossenbock, H., Rodriguez, T., Russell, K., Cox, D.: Design of the Java HotSpot client compiler for Java 6. ACM Trans. Prog. Lang. Syst. 5(1) (May 2008)

Digital Library

[16]

Maxwell, E. K., Back, G., Ramakrishnan, N.: Diagnosing memory leaks using graph mining on heap dumps. In: Proc. of the 16th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD 2010), Washington, DC, July 25-28. ACM Press (2010)

Digital Library

[17]

Mitchell, N., Schonberg, E., Sevitsky, G.: Four trends leading to Java runtime bloat. IEEE Software 27(1) (2010)

Digital Library

[18]

Mitchell, N., Sevitsky, G.: The causes of bloat, the limits of health. In: Gabriel, R. P., Bacon, D. (eds.) Proc. of the 22nd Ann. Conf. on OO Prog. Sys., Lang., & Appl. (OOPSLA 2007), Montreal, Quebec, Canada, October 21-25. ACM Press (2007)

Digital Library

[19]

Moreira, J. E., Midkiff, S. P., Gupta, M.: A comparison of Java, C/C++, and FORTRAN for numerical computing. IEEE Antennas and Propagation Magazine 40(5), 102-105 (1998)

[20]

Novark, G., Berger, E. D., Zorn, B. G.: Efficiently and precisely locating memory leaks and bloat. In: ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI (2009)

Digital Library

[21]

Ogata, K., Mikurube, D., Kawachiya, K., Onodera, T.: A study of Java's non-Java memory. In: Cook, W. R., Clarke, S., Rinard, M.C. (eds.) Proc. of the 25th Ann. Conf. on OO Prog. Sys., Lang., & Appl. (OOPSLA 2010), Reno/Tahoe, Nevada, USA, October 17-21. ACM (2010)

Digital Library

[22]

Paleczny, M., Vick, C., Click, C.: The Java Hotspot server compiler. In: Proc. of the Java Virtual Machine Research and Technology Symposium (JVM 2001), Monterey, California, April 23-24. USENIX C++ Technical Conf. Proc. (2001)

Digital Library

[23]

Reiss, S. P.: Visualizing the Java heap. In: Proc. of the 32nd Int. Conf. on Soft. Eng. (ICSE 2010), Cape Town, South Africa, May 2-8. ACM (2010)

Digital Library

[24]

Shacham, O., Vechev, M., Yahav, E.: Chameleon: Adaptive selection of collections. In: Proc. of the Conference on Programming Language Design and Implementation (PLDI 2009), Dublin, Ireland, June 15-20. ACM Press (2009)

Digital Library

[25]

Venstermans, K., Eeckhout, L., Bosschere, K. D.: Java object header elimination for reduced memory consumption in 64-bit virtual machines. TACO 4(3) (2007)

Digital Library

[26]

Wimmer, C.: Automatic Object Inlining in a Java Virtual Machine. PhD thesis, Institute for System Software, Johannes Kepler University Linz (2008)

[27]

Xu, G., Arnold, M., Mitchell, N., Rountev, A., Sevitsky, G.: Go with the flow: Profiling copies to find runtime bloat. In: ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI (2009)

Digital Library

[28]

Xu, G., Mitchell, N., Arnold, M., Rountev, A., Sevitsky, G.: Software bloat analysis: finding, removing, and preventing performance problems in modern large-scale object-oriented applications. In: Proc. of the 18th ACM SIGSOFT Symp. on the Foundations of Soft. Eng. (FSE 2010), Santa Fe, New Mexico, November 7-11. ACM Press (2010)

Digital Library

[29]

Xu, G., Rountev, A.: Precise memory leak detection for Java software using container profiling. In: Proc. of the 30th Int. Conf. on Soft. Eng. (ICSE 2008), Leipzig, Germany, May 10-18. ACM (2008)

Digital Library

[30]

Xu, G., Rountev, A.: Detecting inefficiently-used containers to avoid bloat. In: Proc. of the Conference on Programming Language Design and Implementation (PLDI 2010), Toronto, Canada, June 5-10. ACM Press (2010)

Digital Library

Cited By

Steindorfer MVinju J(2018)To-many or to-one? all-in-one! efficient purely functional multi-maps with type-heterogeneous hash-triesACM SIGPLAN Notices10.1145/3296979.319242053:4(283-295)Online publication date: 11-Jun-2018
https://dl.acm.org/doi/10.1145/3296979.3192420
Steindorfer MVinju JFoster JGrossman D(2018)To-many or to-one? all-in-one! efficient purely functional multi-maps with type-heterogeneous hash-triesProceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3192366.3192420(283-295)Online publication date: 11-Jun-2018
https://dl.acm.org/doi/10.1145/3192366.3192420
Costa DAndrzejak AKnoop JSchordan MJohnson TO'Boyle M(2018)CollectionSwitch: a framework for efficient and dynamic collection selectionProceedings of the 2018 International Symposium on Code Generation and Optimization10.1145/3168825(16-26)Online publication date: 24-Feb-2018
https://dl.acm.org/doi/10.1145/3168825
Show More Cited By

Recommendations

Smaller footprint for Java collections
OOPSLA '11: Proceedings of the ACM international conference companion on Object oriented programming systems languages and applications companion

Bloat, specifically, containers's bloat is a potential Java performance bottleneck. We identify five memory compaction techniques that can be used to reduce the footprint of the small objects that make containers. Using these techniques, we describe ...
Exploiting memory usage patterns to improve garbage collections in Java
PPPJ '10: Proceedings of the 8th International Conference on the Principles and Practice of Programming in Java

Copying-based garbage collectors are currently widely employed in JVM systems, as they provide not only cheap allocations but also fast collections. Comparing to their compacting-based counterparts, copying-based collectors trade space for time: they ...
JBrainy: Micro-benchmarking Java Collections with Interference
ICPE '20: Companion of the ACM/SPEC International Conference on Performance Engineering

Software developers use collection data structures extensively and are often faced with the task of picking which collection to use. Choosing an inappropriate collection can have major negative impact on runtime performance. However, choosing the right ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ECOOP'12: Proceedings of the 26th European conference on Object-Oriented Programming

June 2012

763 pages

ISBN:9783642310560

Editor:
James Noble
School of Engineering and Computer Science, Victoria University of Wellington, Wellington, New Zealand

Sponsors

Adobe
Microsoft Reasearch: Microsoft Reasearch
ORACLE: ORACLE
AITO: Association Internationale pour les Technologies Objets
Purdue University: Purdue University

In-Cooperation

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 11 June 2012

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Steindorfer MVinju J(2018)To-many or to-one? all-in-one! efficient purely functional multi-maps with type-heterogeneous hash-triesACM SIGPLAN Notices10.1145/3296979.319242053:4(283-295)Online publication date: 11-Jun-2018
https://dl.acm.org/doi/10.1145/3296979.3192420
Steindorfer MVinju JFoster JGrossman D(2018)To-many or to-one? all-in-one! efficient purely functional multi-maps with type-heterogeneous hash-triesProceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3192366.3192420(283-295)Online publication date: 11-Jun-2018
https://dl.acm.org/doi/10.1145/3192366.3192420
Costa DAndrzejak AKnoop JSchordan MJohnson TO'Boyle M(2018)CollectionSwitch: a framework for efficient and dynamic collection selectionProceedings of the 2018 International Symposium on Code Generation and Optimization10.1145/3168825(16-26)Online publication date: 24-Feb-2018
https://dl.acm.org/doi/10.1145/3168825
Steindorfer MVinju J(2015)Optimizing hash-array mapped tries for fast and lean immutable JVM collectionsACM SIGPLAN Notices10.1145/2858965.281431250:10(783-800)Online publication date: 23-Oct-2015
https://dl.acm.org/doi/10.1145/2858965.2814312
Steindorfer MVinju JAldrich JEugster P(2015)Optimizing hash-array mapped tries for fast and lean immutable JVM collectionsProceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications10.1145/2814270.2814312(783-800)Online publication date: 23-Oct-2015
https://dl.acm.org/doi/10.1145/2814270.2814312
Sato YHozumi SChiba SYoung MXie T(2015)Calculation coverage testing in scientific applicationsProceedings of the 2015 International Symposium on Software Testing and Analysis10.1145/2771783.2771807(350-360)Online publication date: 13-Jul-2015
https://dl.acm.org/doi/10.1145/2771783.2771807
Steindorfer MVinju J(2014)Code specialization for memory efficient hash tries (short paper)ACM SIGPLAN Notices10.1145/2775053.265876350:3(11-14)Online publication date: 15-Sep-2014
https://dl.acm.org/doi/10.1145/2775053.2658763
Steindorfer MVinju JSchultz UFlatt M(2014)Code specialization for memory efficient hash tries (short paper)Proceedings of the 2014 International Conference on Generative Programming: Concepts and Experiences10.1145/2658761.2658763(11-14)Online publication date: 15-Sep-2014
https://dl.acm.org/doi/10.1145/2658761.2658763
Xu G(2013)ResurrectorACM SIGPLAN Notices10.1145/2544173.250951248:10(111-130)Online publication date: 29-Oct-2013
https://dl.acm.org/doi/10.1145/2544173.2509512
Xu GHosking AEugster PLopes C(2013)ResurrectorProceedings of the 2013 ACM SIGPLAN international conference on Object oriented programming systems languages & applications10.1145/2509136.2509512(111-130)Online publication date: 29-Oct-2013
https://dl.acm.org/doi/10.1145/2509136.2509512
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents