1# Interface Inline Cache 2## Overview 3 4`Interface Inline Cache` is an optimization for speeding up find method in interface method call. 5Ark Runtime allows multiple interfaces to be inherited, and uses the itable table to dynamically query the address of the target method. 6`Interface Inline Cache` will stores the parsing result of the previous method address as the cache and directly uses the cache in subsequent call. 7 8## Rationality 9 10`Interface Inline Cache`'s reason for optimization: 11* There is a 90% - 95% chance that the same method will be used in real-world application test. 12* The speed of querying the itable table is very slow. 13 14`Interface Inline Cache` include `Fast Path` and `Slow Path` 15* `Slow path`: Call runtime RESOLVE_VIRTUAL_CALL_AOT to get method address and save method addr and class to cache 16* `Fast Path`: Check whether the class is the same as the last cached class,if equal: use cache; if no equal: goto `Slow Path` 17 18## Dependence 19 20* must be 64bit system 21 22## Algorithm 23 24### Schematic Drawing 25 26``` 27 Cache structure:（offset addr)/(class addr) 32bit/32bit 28 ----------------------------------------------- 29 (.aot_got) 30 ... 31 cache:offset/class ---------->| <-| 32 ... | | 33 (.text) | | 34 interface call start | | 35 --> call runtime irtoc function | | 36 read cache <-----------------------| | 37 if call class == cache.class | 38 use cache.offset(method) | 39 else | 40 call RESOLVE_VIRTUAL_CALL_AOT | 41 save method‘s offset to cache >------| 42 <-- return to (.text) 43 call method 44 ----------------------------------------------- 45``` 46`cache` 471. one cache is 64bit 482. cache's high 32 save the `offset addr`,cache's low 32 save the `class addr` 493. cache's address is in an file's aot_got section 504. number of cache equal "interface call" number in this an file 515. why use 64bit? 52because read and write 64bit is atomic, same `cache` maybe use at same time 53 54`class addr` 551. `class addr` is just the point to a class, in ark runtime, class point is 32bit 562. because `class address` is no move in ark, so we do not need to worry that the saved class will become invalid addresses. 573. if class address is move, it is still save, but maybe the hit rate will be lower. 58 59`offset addr` 601. The purpose of `offset addr` is to obtain the `method addr` through calculation. 612. `offset addr` = ((`method addr`) - ([`class addr`].`methods_` addr)) / 2 ^ 3 623. why can not save `method addr` directly? 63 because method* is 64bit, it must be indirectly stored,cache only have 32bit to use 64``` 65if we want to save ClassA.method_n* 66----------- 67| Class A | 68| ... | Array of Method* 69| ... | -------------- 70| methods_*| -->| method_1* | 71| ... | | ... | 72----------- | ->method_n* | 73 | ... | 74we just need to save method_1* - method_n* 75 76Note: Class A records only its own methods, if the implementation of the target method is in the parent class B of Class A. 77 78----------- 79| Class A | 80| ... | Array of Method* 81| ... | -------------- 82| methods_*| -->| method_1* | 83| ... | | ... | 84----------- 85 86----------- 87| Class B | 88| ... | Array of Method* 89| ... | -------------- 90| methods_*| -->| method_1* | 91| ... | | ... | 92----------- | ->method_n* | 93 | ... | 94 95we still save ClassA.method_1* - ClassB.method_n*, so if 96(ClassA.method_1* - ClassB.method_n*) > 2 ^ 32 97this optimization will be abandoned.This condition is quite rare. 98``` 994. why `offset addr` divided by 2 ^ 3 at the end of the formula？ 100because Method* is 8bit align, so Method* can be compressed. So the actual range we can store is: 101((ClassA.method_1* - ClassB.method_n*) / 2 ^ 3) < 2 ^ 32 102 103## Expected effect 1041. `Interface Inline Cache` will reduce `RESOLVE_VIRTUAL_CALL_AOT` calls by more than 90% 1052. benchmark test case: ImtConflicts100 -- runing time will accelerate by more than 300% 1063. Application startup: 10ms - 100ms. The value depends on the number of interfaces call. 107 108## Cost 1091. an file bloat < 1% 1102. Rss：No significant impact