# Java 虛擬機器（閱讀筆記）
影片閱讀 [Learn about JVM internals - what does the JVM do?](https://www.youtube.com/watch?v=UwB0OSmkOtQ&feature=youtu.be&ab_channel=InfoQ)
---
### JVM
- the same execution environment to all Java applications
- translation to the underlying layers
- resources management
---
### interpreter overhead
- branch
- 每個對應的 operation 需要執行對應的指令，使得每次讀取指令後皆存在 branch，造成 branch miss 的可能上升。
- solution: threaded interpreter，不需要再每次執行完一個指令後都回到 `switch` 的開頭，而是在執行指令後直接讀取下個指令並使用 `goto` 前往。可使用 `compute goto` 將要執行的指令位置替換成 Label 的 address 實現。
- decoding
- 對 bytecode 的解讀需要逐個 byte 去讀取，且 bytecode 內每個區塊的組成通常會由前兩個 bytes 來決定此區塊的長度，接著才是以此長度儲存的資料，所以很難一次解讀全部的 bytecode。
- solution: pre-decode the bytecodes，使用 pipeline 將 decode 與 executre 同時執行：
- manipulating locals and stack
- JVM 為 stack-based machine，而 stack 操作不能直接以 register 做運算，效率較差。
:::info
JVM 為 stack-based virtual machine 的原因為 stack-based 對硬體的要求較少，在 target hardware 變化很多時較方便實作
:::
- solution: 將部分資料放入 register 中
---
### JIT compiler
以下的 graph 指的是 [Control-flow graph](https://en.wikipedia.org/wiki/Control-flow_graph)，是以圖 (graph) 來表示程式執行過程中**所有**能到達的路徑。
1. turn bytecodes into a graph
- 將 bytecode 轉換成 CFG 的形式，其中每個 block 內有一到數個 instruction，每個 block 為 CFG 內的 vertex，每個 block 是由 branch 來決定，而 branch 間的關係則以 CFG 內 edge 表示。詳細規則可參考 [Analyzing Control Flow in Java Bytecode](https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.35.7827&rep=rep1&type=pdf)。
3. turn graph into a linear sequence of operations (infinite virtual register)
- 將每個 block 內的指令轉為一系列的~~線性指令~~，並以無限大的記憶體表示內部指令的運算
5. allocate physical registers
- 將 virtual register 對應到 architecture 定義的 register
7. generate code
- 把 CFG 轉換成 machine code
* SSA
---
### Code Optimization
搭配閱讀 [你所不知道的 C 語言：編譯器和最佳化原理篇](https://hackmd.io/@sysprog/c-compiler-optimization?type=view)
1. [Dead Code Elimination](https://en.wikipedia.org/wiki/Dead_code_elimination)
- 將執行路徑無法觸及的程式碼刪除
2. [Function Inlining](https://en.wikipedia.org/wiki/Inline_expansion)
- 將函式展開，減少 call 所造成的效能影響
3. Low-Level Tree Rewrite
- 將 instruction 在要運行的目標架構指令上加速
```java
class Foo {
int x;
void increment() {x++}
}
```
轉換 bytecode 為
```java
Load R1, field
Add R1, 1
Store field, R1
```
而大部分架構 (Intel, Arm) 都有提供對 register 加法的指令，所以可以轉換成
```
Add field, 1
```
4. High-Level Tree Rewrite
- 在還未轉換成中階語言或低階語言時所做的優化，如欲先分配好足夠的空間來串接字串
5. more and more...
---
### Challenges
#### Object-orientation
Java 預設所有的 method 都為 virtual (除了被設置為 final 的 method)，而 virtual method 的處理方式為 virtual method dispatch，透過 JVM 指令 `invokevirtual` 來實現。
而 JVM 內部實作 virtual method dispatch 的方式會依據製造商的不同而有差異，但大致的流程如下：
1. 每個使用到 virtual method 的 class 皆保存一個 virtual method table (vtable, VMT)，此 table 為一個 array of pointer 指向 method 的實作，array 內部則儲存此 class 的所有 method 名稱或類型資訊。
2. 由這些 class 產生的物件會存有一個 pointer 稱為 virtual table pointer (vpointer, VPTR) 用來指向這個 class 保存的 table。
3. 當 derived class 有實作 base class 的 virtual method 時，會在 derived class 的 virtual table 中把這個 method 的 pointer 指向此 method；反之，base class 沒有被實作的 method 則會在 derived class 的 table 中指向 base class 的 method。
4. 當呼叫 virtual method 時，會先取得 compile-time 的 class，再依據此 class 找到對應的 method，接著從 stack 中取出 run-time type 的 class 並透過其 virtual table 找到對應 index，再藉由此 index 的 pointer 找到 method 的程式碼並執行。
>參考 [Understandig Virtual Tables in C++](https://pabloariasal.github.io/2017/06/10/understanding-virtual-tables/)
要注意在 Java 中每個 method 預設為 virtual，考慮以下程式：
```java
class Base
{
void bar();
void foo();
}
class Derived extends Base
{
void bar();
}
class DDerived extends Derived
{
void bar();
void foo();
}
```
程式會產生對應的 virtual method table 及 virtaul table pointer：
```graphviz
digraph G {
rankdir = LR;
node [shape=record];
node1 [shape = none;
label = <
<table style="width:0px" border="0" cellspacing="0">
<tr>
<td WIDTH="110" port="f0" border="1" bgcolor="gray">Object of Base</td>
</tr>
<tr>
<td port="f1" border="1">vpointer</td>
</tr>
</table>
>];
node2 [shape = none;
label = <
<table style="width:0px" border="0" cellspacing="0">
<tr>
<td WIDTH="120" port="f0" border="1" bgcolor="gray">Object of Derived</td>
</tr>
<tr>
<td port="f1" border="1">vpointer</td>
</tr>
</table>
>];
node3 [shape = none;
label = <
<table style="width:0px" border="0" cellspacing="0">
<tr>
<td WIDTH="160" port="f0" border="1" bgcolor="gray">Vtable of class Base</td>
</tr>
<tr>
<td port="f1" border="1">bar</td>
</tr>
<tr>
<td port="f2" border="1">foo</td>
</tr>
</table>
>];
node4 [shape = none;
label = <
<table border="0" cellspacing="0">
<tr>
<td WIDTH="160" port="f0" border="1" bgcolor="gray">Vtable of class Derived</td>
</tr>
<tr>
<td port="f1" border="1">bar</td>
</tr>
<tr>
<td port="f2" border="1">foo</td>
</tr>
</table>
>];
node7 [shape = none;
label = <
<table style="width:0px" border="0" cellspacing="0">
<tr>
<td WIDTH="120" port="f0" border="1" bgcolor="gray">Object of DDerived</td>
</tr>
<tr>
<td port="f1" border="1">vpointer</td>
</tr>
</table>
>];
node9 [shape = none;
label = <
<table border="0" cellspacing="0">
<tr>
<td WIDTH="160" port="f0" border="1" bgcolor="gray">Vtable of class DDerived</td>
</tr>
<tr>
<td port="f1" border="1">bar</td>
</tr>
<tr>
<td port="f2" border="1">foo</td>
</tr>
</table>
>];
node [shape=box]
node6 [label="Base::bar()" width = 1.4 height=0.4]
node5 [label="Base::foo()" width = 1.4 height=0.4]
node8 [label="Derived::bar()" width = 1.4 height=0.4]
node10 [label="DDerived::foo()" width = 1.4 height=0.4]
node1:f1 -> node3:f0
node2:f1 -> node4:f0
node7:f1 -> node9:f0
node3:f1 -> node6
node3:f2 -> node5
node4:f2 -> node5
node4:f1 -> node8
node9:f1 -> node8
node9:f2 -> node10
node6->node5->node8->node10 [style=invis]
{ rank=same; node5; node6; node8; node10}
}
```
許多支援 OOP 的程式語言都以上面為基礎實現 dynamic binding，但 Java 還有一個特性為不支援多重繼承，亦即每個 class 只能繼承一個 class，所以可以運用這項特性，把每個 method 與其 parent class 相同的 method 之 index 定為相同，就能快速的在找到 parent class 的 virtual method table 上的 index 後用此 index 找到此 child class 的 method。
要先知道 Java 為[靜態型別的程式語言](https://en.wikipedia.org/wiki/Type_system#Static_type_checking)，亦即所有的程式碼在編譯成 `.class` 檔後，compiler 會先假設內部的所有型態都已經確定。而像以下程式 `Line 7` 這種 upcasting 的行為，在 compile 階段會將其 type 視為宣告的 `Object` type：
```java
public class Program {
static class Person {
}
public static void main(String[] params) throws Exception {
Object one = new Object();
Object two = new Person();
Person three = new Person();
System.out.println("One compile-type : " + getStaticType(one));
System.out.println("Two compile-type : " + getStaticType(two));
System.out.println("Three compile-type : " + getStaticType(three));
}
public static Class getStaticType(Person p) {
return Person.class;
}
public static Class getStaticType(Object o) {
return Object.class;
}
}
```
預期程式輸出為：
```java
One compile-type : class java.lang.Object
Two compile-type : class java.lang.Object
Three compile-type : class Program$Person
```
> [source](https://stackoverflow.com/a/22919120)
接著分析 JVM 在執行 `invokevirtual` 指令時會做的事情，以 [Hotspot VM](https://en.wikipedia.org/wiki/HotSpot_(virtual_machine)) 為例，考慮以下程式碼：
```java
class Base {
void m1()
{
System.out.println("Inside Base's m1 method");
}
void m2()
{
System.out.println("Inside Base's m2 method");
}
}
class Derived extends Base {
void m1()
{
System.out.println("Inside Derived's m1 method");
}
}
class DemoClass {
public static void main(String args[]) {
Base a = new Derived();
a.m1();
}
}
```
在 `a.m1()` 時會執行 `invokevirtual` 指令，在該指令後方需要兩個 bytes 用來找到 method `m1` 在 constant pool 中的 index。
:::info
先前提到 Java 在編譯時就已經決定好型別，所以此處 `a.m1()` 會先被解析為呼叫 `Base.m1`，透過 `javap` 可以更清楚的看到 `Line 11` 後方註解標示 constant pool 中第 10 個位置的 `Base.m1`。
```=
public static void main(java.lang.String[]);
descriptor: ([Ljava/lang/String;)V
flags: (0x0009) ACC_PUBLIC, ACC_STATIC
Code:
stack=2, locals=2, args_size=1
0: new #7 // class Derived
3: dup
4: invokespecial #9 // Method Derived."<init>":()V
7: astore_1
8: aload_1
9: invokevirtual #10 // Method Base.m1:()V
12: return
LineNumberTable:
line 22: 0
line 23: 8
line 24: 12
```
:::
接著 JVM 會從 `Base` class 的 virtual method table 中尋找 `m1` 這個 method 的位置，並把 stack 中的資料 pop 出來，從 [instruction set](https://docs.oracle.com/javase/specs/jvms/se7/html/jvms-6.html#jvms-6.5.invokevirtual) 中可得知此指令會 pop 出一個 objectref 及所有需要的參數，此 objectref 為 run-time type，在此例為 `Derived` class。
上面有提到在 Java 中，相同繼承關係內的 class，其 override 的 method 在 virtual method table 中的 index 都一樣，所以此時可以運用剛剛計算的 index 來取得 run-time class 對應的 method，就能執行此 override 後的 method。
>參考資料
>[1] [How Does JVM Handle Polymorphism (Method Overloading and Method Overriding) Internally](https://www.programmingmitra.com/2017/05/how-does-jvm-handle-method-overriding-internally.html)
>[2] [How exactly does JVM implement virtual method invocation?](https://www.quora.com/How-exactly-does-JVM-implement-virtual-method-invocation)
>[3] [How is the virtual method table implemented in Java?](https://www.quora.com/How-is-the-virtual-method-table-implemented-in-Java)
上述過程可以用 [Inline caching](https://en.wikipedia.org/wiki/Inline_caching) 來優化，概念為將紀錄較常綁定的 class，並編譯成以此 class 為參數的 method，直到發生綁定不同 class 時，再透過 [deoptimization](https://wiki.openjdk.java.net/display/HotSpot/PerformanceTechniques) 將程式碼還原成原本狀態，重新尋找要綁定的 class。
>參考資料
>[1] [An introduction to JVM performance](https://www.slideshare.net/RafaelWinterhalter/an-introduction-to-jvm-performance)
#### Class Loading
- ==Class loading means that assumptions for inling, etc. may change over time.==
- JVM 會記錄 Class 間的依賴關係，當 JVM 發現目前 optimize 後的程式不合法時，會經過 deoptimization 並重新編譯。
---
### Adaptive optimization
- [Adaptive optimization](https://en.wikipedia.org/wiki/Adaptive_optimization) 會在執行時期收集程式運行的資料，並對程式運行時間長的部分進行優化，因為 bytecode 通常為 [Reversible computing](https://en.wikipedia.org/wiki/Reversible_computing)，所以當發現優化後造成程式錯誤時，可以透過 deoptimization 將程式 "fall-back"。
- JIT 對不同行為的程式碼提供不同的編譯級別，分別有 C1 for Client VM， C2 for Server VM。C1 用來執行 client 端的應用，為了要執行快速，所做的優化較少；而 C2 用來執行 server 端的應用，通常會長時間運行，所以其會在運行時收集資料，並在之後進行編譯。
- [Tiered compilation](https://docs.oracle.com/javase/8/docs/technotes/guides/vm/performance-enhancements-7.html) 就是將 C1 與 C2 整合，在程式開始時使用 Client Compiler 加速，接著使用 Server Compiler 收集資料後重新編譯。
---
### Garbage Collection
- GC 的[三種算法](https://plumbr.io/handbook/garbage-collection-algorithms#removing-unused-objects)
- [Mark-Sweep](https://www.geeksforgeeks.org/mark-and-sweep-garbage-collection-algorithm/)
將用不到的物件標記並存入到 free list 中，最後在全部移除，缺點是容易造成[碎片化](https://en.wikipedia.org/wiki/Fragmentation_(computing))。
- [Mark-Compact](https://en.wikipedia.org/wiki/Mark-compact_algorithm)
做完 Mark-sweep 後，再將所有物件 compact 到一起，可以解決碎片化的問題，在清空的物件數量較少時較有效率。
- Mark-Copy
在 mark 階段後，將未標記的物件移動到另一個記憶體空間，在剩餘物件較少時較有效率。
- JVM 是基於 [Generational garbage collection](https://docs.oracle.com/en/java/javase/15/gctuning/garbage-collector-implementation.html#GUID-71D796B3-CBAB-4D80-B5C3-2620E45F6E5D) 來分配物件空間，將空間分成以下：
- Young Generation
- Eden
- Survivor0
- Survivor1
- Old Generation
- Permanent Generation
- HotSpot VM 目前提供三種類型的 [Garbage Collector](https://docs.oracle.com/en/java/javase/15/gctuning/available-collectors.html#GUID-45794DA6-AB96-4856-A96D-FDE5F7DEE498)，用來指示當要執行 GC 時，對應的行為：
- Serial Collector
- Parallel Collector
- Garbage-First (G1) Garbage Collector
- [Zing JVM](https://www.azul.com/products/zing/) 使用的 C4 Garbage Collector 支援 Concurrent Compaction
>參考資料
>[1] [Java Garbage Collection Basics](https://www.oracle.com/webfolder/technetwork/tutorials/obe/java/gc01/index.html)
>[2] [每個程序員都該瞭解的JVM - 垃圾收集器](https://www.jyt0532.com/2020/03/12/garbage-collector/)
>[3] [Java 分代收集算法](https://blog.csdn.net/mccand1234/article/details/52078645)
>[4] [喝杯咖啡，聊點 GC（一） – 基礎概念](https://www.alexleo.click/java-%E5%96%9D%E6%9D%AF%E5%92%96%E5%95%A1%EF%BC%8C%E8%81%8A%E9%BB%9E-gc%EF%BC%88%E4%B8%80%EF%BC%89-%E5%9F%BA%E7%A4%8E%E6%A6%82%E5%BF%B5/)
---
### 評估 Dhrystone 所需特徵
- OOP
- inheritance
- polymorphism
- class
- interface
- constructor
- Exception handler
- throw exception
- Exception table
- multithread (applet only)
- Class Loader
- import (find class path)
- JNI
- data type
- int
- long
- char
- boolean
- String
- array
---
### 其他 JVM 實作
- https://github.com/kifferltd/open-mika
- https://github.com/ReadyTalk/avian/tree/master/classpath
- https://github.com/harbaum/NanoVM
- https://github.com/davidgiven/luje
---
```c=
if (0) {
message:
printf("Hello\n");
}
if (x > 0) goto message;
```
unreachable
###### tags: `linux2020`
Sign in with Wallet
Connect another wallet