GC 1 1 GC GC GC GC DalvikVM GC 12.4% 5.7% 1. Garbage Collection: GC GC Java GC GC GC GC DalvikVM[1] GC 1 Nagoya Institute of Technology GC GC 2. GC GC 2.1 GC 1 c 2016 Information Processing Society of Japan 1
1 GC GC Mark & Sweep[2] GC Copying[3] Reference Counting[4] GC 3 [5] Mark & Sweep 2.2 GC Concurrent GC[6] Concurrent GC GC GC Concurrent GC GC GC SILENT[7] Network Attached Processing NAP [8] Concurrent GC GC 3. GC GC GC 3.1 GC GC GC DalvikVM Mark & Sweep GC gem5 [9] DalvikVM GC DalvikVM GCBench[10] AOBench[11] SPECjvm2008[12] 5 7 GC 80% 46% GC GC 3.2 DalvikVM DalvikVM c 2016 Information Processing Society of Japan 2
1 X 1 10 50 100 200 AOBench 345 151 37 20 11 GCBench 61,717 6,312 1,269 636 319 crypto.rsa 2,789 1,418 344 178 93 crypto.aes 2,804 854 218 115 61 crypto.signverify 2,801 1,412 349 180 94 compress 627 321 84 45 25 serial 4,269 1,156 313 165 87 DalvikVM Mark 3.1 GC 1 X X = 10 10 3.1 crypto.rsa crypto.signverify X = 1 X = 10 2 GC 4. GC 4.1 GC GC GC 2 4 A D c 2016 Information Processing Society of Japan 3
A (i) A A A (a) A D (ii) D C C C C 4.2 DalvikVM LRU LRU LRU 3 GC 3 A D 3 A (i) A A B C (ii) A C B (iii) (a) D (iv) 5. 5.1 5.1.1 4.2 LRU c 2016 Information Processing Society of Japan 4
2 CAM Content Addressable Memory Address LRU prev next prev next Head Tail #Addr 5.1.2 GC CAM RAM RAM 4 Victim Index 5.2 5.2.1 LRU 4 B B B A C (a) B (b) c 2016 Information Processing Society of Japan 5
2 Platform Processor Clock Memory OS ARM-RealView PBX ARMv7 2.0 GHz 256 MB Linux 2.6.38.8-gem5 5 (c) B A C A next C 2 C prev A 0 Head B 5.2.2 5 D D D (a) D D D Victim Index D (b) D (c) D Victim Index Victim Index 6. 6.1 gem5 2 DalvikVM GCBench[10] AOBench[11] SPECjvm2008[12] 5 7 gem5 10 3.2 1 CAM CAM TLB 50 c 2016 Information Processing Society of Japan 6
6 GC 1 X = 100 X = 200 X = 200 X = 100 100 200 100 200 100 200 200 6 200 3 64 192 6.2 GC GC GC GC 6.2.1 GC GC 6 6 2 (MS) (P) Mark & Sweep GC (MS) GC 1 MarkRoot ScanMarked Sweep misc Mark & Sweep (MS) (P) crypto.rsa GC ScanMarked crypto.signverify ScanMarked 12.4% GC 5.7% GC crypto.rsa crypto.signverify compress Mark & Sweep misc GC GC ScanMarked GC 2cycles 1cycle GC (P) 1.8% 5.1.2 6.2.2 GC GC 7 GC GC GC 7 6 c 2016 Information Processing Society of Japan 7
50% 62% 50 7 GC (CO) Concurrent GC (MS) 1 (P) GC Concurrent GC (CO) 2.2 AOBench compress GC 26.0% 7.1% 6.3 5.1.2 LRU LRU GC 6.4 6.1 50 3 64 32bit 8bit 8bit 300Byte CAM 8bit 3 2bit 2bit 3 32 3 = 96bit 784Byte RAM 1KByte 7. GC GC GC Mark & Sweep GC 12.4% Concurrent GC c 2016 Information Processing Society of Japan 8
GC GC GC GC [1] Bornstein, D.: Dalvik Virtual Machine Internals, Google I/O 2008 (2008). [2] McCarthy, J.: Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I, Communications of the ACM, Vol. 3, pp. 184 195 (1960). [3] Minsky, M.: A LISP Garbage Collector Algorithm Using Serial Secondary Storage, Technical report, Massachusetts Institute of Technology (1963). [4] Collins, G. E.: A Method for Overlapping and Erasure of Lists, Communications of the ACM, Vol. 3, pp. 655 657 (1960). [5] (2010). [6] Ossia, Y., Ben-Yitzhak, O., Goft, I., Kolodner, E. K., Leikehman, V. and Owshanko, A.: A Parallel, Incremental and Concurrent GC for Servers, Proc. ACM SIG- PLAN Conf. on Programming Language Design and Implementation (PLDI 02), pp. 129 140 (2002). [7] Takeuchi, I., Yamazaki, K., Amagai, Y. and Yoshida, M.: Lisp can be Hard Real Time, Proc. Japan Lisp User Group Meeting (JLUGM) (2000). [8] Click, C., Tene, G. and Wolf, M.: The Pauseless GC Algorithm, Proc. 1st ACM/USENIX Int l Conf. on Virtual Execution Environments (VEE 05), pp. 46 56 (2005). [9] Binkert, N., Beckmann, B., Black, G., Reinhardt, S. K., Saidi, A., Basu, A., Hestness, J., Hower, D. R., Krishna, T., Sardashti, S., Sen, R., Sewell, K., Shoaib, M., Vaish, N., Hill, M. D. and Wood, D. A.: The gem5 Simulator, ACM SIGARCH Computer Architecture News, Vol. 39, pp. 1 7 (2011). [10] Boehm, H.: An Artificial Garbage Collection Benchmark, http://www.hpl.hp.com/personal/hans Boehm/ gc/gc bench.html. [11] Fujita, S.: Ambient Occlusion Benchmark, http://code.google.com/p/aobench/. [12] SPEC.: SPECjvm2008 benchmarks, http://www.spec.org/jvm2008/ (2008). c 2016 Information Processing Society of Japan 9