# 2020_OS_Fall_HW1
學號： F74076027
姓名： 林政傑
系級： 資訊 111
[TOC]
## 開發環境：
- OS: Ubuntu 20.04.1 (Oracle VM Virtual Machine)
- CPU: Intel® Core™ i7-10750H CPU @ 2.60GHz × 4
- Ｍemory: 4GB
- Programming Language: g++ (Ubuntu 9.3.0-10ubuntu2) 9.3.0
## 程式執行時間
- 生成 8GiB 檔案所消耗的時間:
|實驗次數|秒數|
|------|----|
|1 |123 |
|2 |119 |
|3 |122 |
|4 |105 |
|5 |105 |
|平均 |115 |
- 排序 8 GiB 檔案所消耗的時間:
* 2-way merge sort
|實驗次數|8GiB|16GiB |24GiB|
|------|----|------|------|
|1 |515 |1592 |2155 |
|2 |505 |1523 |2183 |
|3 |505 |1547 |2150 |
|4 |517 |1360 |2177 |
|5 |498 |1323 |2170 |
|平均 |508 |1469 |2167 |
* k-way merge sort
|實驗次數|8GiB|16GiB |24GiB|
|------|----|------|-----|
|1 |572 |1368 |1814 |
|2 |584 |1360 |1845 |
|3 |578 |1322 |1887 |
|4 |579 |1349 |1913 |
|5 |595 |1229 |1985 |
|平均 |582 |1326 |1889 |
## 程式開發與使用說明
### 使用說明: 專案目錄
```bash
$ tree
.
├── Makefile
└── source_code
├── benchmark.cpp
├── gen_input.h
├── help.h
└── sort.h
1 directory, 5 files
```
### 使用說明: 編譯
在專案目錄輸入 `make` 即可編譯:
```bash
$ make
g++ source_code/prompt.cpp -o prompt
g++ source_code/gen_input.cpp -o gen
g++ source_code/sort.cpp -o sort
g++ source_code/ksort.cpp -o ksort
```
### 使用說明: 執行
編譯完成之後，會產生三個執行檔: `prompt` 、 `gen` 、 `sort`。
- 在專案目錄輸入 `./gen` 可以在專案目錄生成一個 8GiB 的 input.txt:
```bash
$ ./gen
# generate a 8 GiB input file
```
- 若 input.txt 在專案錄下，在專案目錄輸入 `./sort` 即可執行 **2-way merge sort**
```bash
$ ./sort
# sort input.txt
```
請盡量把 input.txt 放在專案目錄，並且在專案目錄執行`sort` ，如果要在其他目錄執行 `sort`，需要指定 input.txt 的位置:
```bash
somepath$ path_to/sort path_to/input.txt
#example: benchmark1/sort benchmark1/input.txt
```
除了指定 input.txt 外，output.txt 的位置也可以指定:
```bash
somepath$ path_to/sort path_to/input.txt path_to/output.txt
#example: benchmark2/sort benchmark2/input.txt benchmark2/output.txt
```
在 sort 的過程中，當前目錄會產生 tmp 目錄，待 `sort` 結束會將其刪除
- 若 input.txt 在專案錄下，在專案目錄輸入 `./ksort` 即可執行 **k-way merge sort**
```bash
$ ./ksort
# sort input.txt
```
請盡量把 input.txt 放在專案目錄，並且在專案目錄執行 `ksort` ，如果要在其他目錄執行 `ksort`，需要指定 input.txt 的位置:
```bash
somepath$ path_to/ksort path_to/input.txt
#example: benchmark1/ksort benchmark1/input.txt
```
除了指定 input.txt 外，output.txt 的位置也可以指定:
```bash
somepath$ path_to/ksort path_to/input.txt path_to/output.txt
#example: benchmark2/ksort benchmark2/input.txt benchmark2/output.txt
```
在 sort 的過程中，當前目錄會產生 tmp 目錄，待 `ksort` 結束會將其刪除
- 使用 `./prompt` 整合功能:
```bash
$ ./prompt
enter "h" to get help
enter "q" or "ctrl + c" to quit
> h
# show every command's usage
> gen
# generate a 8 GiB input file
> sort
# sort input.txt
> q
# quit prompt
```
**如果要同時執行多個排序，必須多次編譯，把每個執行檔 sort.h 中的 tmp 目錄換成不一樣的名字，否則排序時會互相衝突**
### 程式開發: 產生 input 的方法
使用 `srand(time(NULL))` 初始化亂數表，接下來先用變數 `num` 儲存 `rand()` 的回傳值，然而 ubuntu20 的 `RAND_MAX` 為 2147483647 ，為了產生出負值，若下一個亂數是奇數，則將 `num` 乘上 -1 並且減 1。
每次產生出數字，會去計算這些數字化為字串之後的長度，並根據所有字串的長度來確認 input.txt 的大小，若剛好超過 8 GiB (預設) ，則結束生成亂數。
### 程式開發: 2-way merge sort
第一個排序演算法使用 2-way merge sort ，流程如下圖:
*圖片來源 https://slideplayer.com/slide/5033624/*
在 `sort.h` 裡，`two_way_merge_sort()` 會實作此排序，流程如下:
1. 在 `sort.h` 中定義變數 `chunk_size` ，代表 PASS 0 時單次抓取的數字數量，預設為 200000000 個，換算為 `int` 的大小 (4 byte)，約為 763 MiB 。將這些數字抓進記憶體後，使用 c++ 內建的 `sort()` 排序，並且儲存成拆分過後的 page (如上圖 PASS 0 的橘色方框)。
2. 在接下來的 PASS ，每次都讀取前一個 PASS 產生的兩個 page，從 page[n] 和 page[n+1] 依序抓取最小的數字來比較。如果 page[n] 的數字較小，就將該數字寫入新的 page ，然後再從 page[n] 抓取下個數字；如果 page[n + 1] 的數字較小，就將該數字寫入新的 page ，然後再從 page[n + 1] 抓取下個數字。
3. 假設待排序的數字為 $N$ 個，經過 $log_2 \dfrac{N}{chunk\_size} + 1$ 個 PASS 即完成排序。每個數字在每個 PASS 中需要一次的讀取和一次寫入，總共花費 $2N(log_2 \dfrac{N}{chunk\_size} + 1)$ 次 I/O。
### 程式開發: k-way merge sort
```graphviz
digraph g {
node [shape=record]
in[label="input.txt" fixedsize=true width=4.8]
in->page1
in->page2
in->page3
in->x
in->pageK[label="PASS 0"]
minq[shape=plaintext label="min-priority queue"]
q[label="<front> 1 | 2 | 3 | ... | K"]
page1->q
page2->q
page3->q
x [label = "..."]
x->q
pageK->q[label="PASS 1"]
{rank=same q minq}
out[label="output.txt" fixedsize=true width = 3.4]
q:front->out[label=" pop-front" fontcolor="blue"]
}
```
在 `sort.h` 裡，`k_way_merge_sort()` 會實作此排序，流程如下:
1. 在 `sort.h` 中定義變數 `chunk_size` ，代表 PASS 0 時單次抓取的數字數量，預設為 200000000 個，換算為 `int` 的大小 (4 byte)，約為 763 MiB 。將這些數字抓進記憶體後，使用 c++ 內建的 `sort()` 排序，並且儲存成拆分過後的 page。
2. 接下來，從每個 page 中抓出最小的數字存入 min-priority queue，接下來重複執行 pop-front ，將 front 元素寫入 output.txt 中，然後從原本 front 的數字的 page 再讀取最小數字放入 min-priority queue 。在實作中，我是以 STL list 來當作 min-priority queue ，每當有新元素插入時，會實施 insertion sort 來找出該元素正確的位置。
3. 假設待排序的數字為 $N$ 個，經過 2 個 PASS 即完成排序，每個數字在每個 PASS 中需要一次的讀取和一次寫入，總共花費 $4N$ 次 I/O 。然而更新 min-priority 消耗的時間有可能比 I/O 還要多，所以有些情況 k-way merge sort 效能不如 2-way merge sort，下面的實驗會提到。
## 效能分析報告
### 效能分析方法
- 使用 c++ 內建的 `clock()` 記錄程式執行時間，在執行生成 input.txt 以及 sort 前後測量時間並將其相減。
- 使用 `top` 指令分析 cpu 及記憶體用量，將檔案輸出至文字檔案如下:
`$ top -1 -i -b > perf.txt`
將 `top` 開啟後，開始執行 `sort` 或 `ksort` ，待排序結束，終止 `top` 指令，我們可以得到以下格式的文檔:
```
$ cat perf.txt
. . .
top - 01:29:12 up 10:23, 1 user, load average: 0.35, 0.15, 0.34
Tasks: 216 total, 3 running, 213 sleeping, 0 stopped, 0 zombie
%Cpu0 : 88.9 us, 6.1 sy, 0.0 ni, 5.1 id, 0.0 wa, 0.0 hi, 0.0 si, 0.0 st
%Cpu1 : 1.0 us, 0.0 sy, 0.0 ni, 99.0 id, 0.0 wa, 0.0 hi, 0.0 si, 0.0 st
%Cpu2 : 0.3 us, 0.0 sy, 0.0 ni, 99.3 id, 0.3 wa, 0.0 hi, 0.0 si, 0.0 st
%Cpu3 : 0.7 us, 0.3 sy, 0.0 ni, 98.3 id, 0.3 wa, 0.0 hi, 0.3 si, 0.0 st
MiB Mem : 3935.8 total, 543.0 free, 1319.6 used, 2073.2 buff/cache
MiB Swap: 2048.0 total, 1995.0 free, 53.0 used. 2315.8 avail Mem
PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND
17235 lin 20 0 5884 1672 1520 R 94.3 0.0 0:02.83 gen
1245 lin 20 0 5066132 395596 86624 S 1.7 9.8 12:28.80 gnome-shell
17024 root 20 0 0 0 0 R 0.7 0.0 0:00.04 kworker/u8:1-events_power_efficient
17137 lin 20 0 1127212 68036 45948 S 0.7 1.7 0:01.38 nautilus
950 lin 20 0 901528 80688 42620 S 0.3 2.0 18:23.59 Xorg
. . .
```
文檔中，我所關注的是 4 個核心 `%Cpu0` 、 `%Cpu1` 、 `%Cpu2` 、 `%Cpu3` 在城市執行間的使用率，以及 `gen` 、 `sort` 程序的 `%CPU` 、 `%MEM` 占用率。為了快速抽取這些資訊，我寫了一個 python 腳本去讀取檔案，並且用 pandas 的 dataframe 儲存資訊，萃取後的資料如下:
```
TIME CPU Mem CPU0 CPU1 CPU2 CPU3 Total CPU Usage \
0 0:02.00 66.7 2.6 2.4 6.7 2.7 62.5 96.102429
1 0:05.00 100.0 6.3 3.1 9.7 3.4 92.3 134.027212
.. ... ... ... ... ... ... ... ...
175 8:40.76 98.3 0.1 56.0 0.0 6.0 0.0 81.091417
176 8:43.53 92.0 0.1 52.8 0.0 5.7 0.0 77.599040
Total Mem Usage
0 21.802429
1 25.527212
.. ...
175 19.091417
176 19.099040
[177 rows x 9 columns]
```
:::spoiler **產生以上 dataframe 的 python 原始碼**
```python=
import pandas as pd
def getdf(filepath, target):
file = open(filepath, 'r')
cpu0 = []
cpu1 = []
cpu2 = []
cpu3 = []
totalcpu = []
time = []
cpu = []
mem = []
totalmem = []
tmp = [0,0,0,0,0]
i = -1
while True:
i = i + 1
line = file.readline()
if not line:
break
chunks = line.split(' ')
chunks = list(filter(None, chunks))
if chunks[-1] == 'st\n':
if chunks[2] == 'us,':
tmp[int(chunks[0][4])] = 100.0
else:
tmp[int(chunks[0][4])] = float(chunks[2])
continue
if chunks[0] == 'MiB' and chunks[1] == 'Mem':
tmp[4] = float(chunks[7]) * 100 / float(chunks[3])
continue
if chunks[-1] == target:
cpu.append(float(chunks[8]) / 4)
mem.append(float(chunks[9]))
time.append(chunks[10])
cpu0.append(tmp[0])
cpu1.append(tmp[1])
cpu2.append(tmp[2])
cpu3.append(tmp[3])
totalcpu.append(sum(tmp) / 4)
totalmem.append(tmp[4])
data = {'TIME':time, 'CPU':cpu, 'Mem':mem, 'CPU0':cpu0, 'CPU1':cpu1, 'CPU2':cpu2,
'CPU3':cpu3, 'Total CPU Usage': totalcpu, 'Total Mem Usage': totalmem}
return pd.DataFrame(data)
sort = getdf('perf.txt', 'sort\n')
print(sort)
```
:::
彙整出這些資訊之後，我使用 plotly 將資源占用率的圖畫出來，如以下 3 個範例:
- 第一張圖是總體 CPU 使用率， %Total CPU Usage (藍色) 為整個系統占用的 CPU 百分比，%CPU (紅色) 為 `sort` 占用的百分比，照理來說 %Total CPU Usage 一定要比 %CPU 高，因為它有包含 %CPU 的佔用量，但偶爾會有 %CPU 較高的情況，目前不知道原因，但是大部分時候顯示的數據是合理的。
- 第二張圖是每個虛擬核心的使用率，我的虛擬機配置了 2 核 4 緒，所以有 4 個虛擬核心，也就是 %CPU0 到 %CPU4
- 第三張圖是記憶體使用率，%Total Mem Usage (藍色) 為整個系統占用的 記憶體百分比，%Mem (紅色) 為 `sort` 占用的百分比。我配置給虛擬機的記憶體總共 4 GB 。
:::spoiler **產生以上三張圖的 python 原始碼**
```python=
import plotly.express as px
import plotly.graph_objs as go
def drawpic(data, title, ydata):
fig = go.Figure()
fig.update_layout(
title=title,
xaxis_title="Time (mm:ss)",
yaxis_title="Usage (%)",
template="plotly_dark"
)
color = ['red', 'yellow', 'orange', 'green']
for i in range(len(ydata)):
fig.add_trace(go.Scatter(x=data['TIME'], y=data[ydata[i]], mode='lines',
name='%' + ydata[i]))
fig.show()
drawpic(sort, 'CPU Usage', ['Total CPU Usage', 'CPU'])
drawpic(sort, 'Every Single CPU Usage', ['CPU0', 'CPU1', 'CPU2', 'CPU3'])
drawpic(sort, 'Memory Usage', ['Total Mem Usage', 'Mem'])
```
:::
- 接下來使用 `sudo iotop -o -b > iotop.txt` 來查看硬碟讀寫的狀況，一樣將檔案輸出到一份文字檔，格式如下:
```
...
Total DISK READ: 130.67 M/s | Total DISK WRITE: 7.90 K/s
Current DISK READ: 130.67 M/s | Current DISK WRITE: 3.95 K/s
TID PRIO USER DISK READ DISK WRITE SWAPIN IO COMMAND
7794 be/4 lin 64.16 M/s 0.00 B/s 0.00 % 0.64 % benchmark1/sort1 input.txt benchmark1/output.txt
7795 be/4 lin 66.51 M/s 0.00 B/s 0.00 % 0.57 % benchmark2/sort2 input.txt benchmark2/output.txt
7137 be/4 root 0.00 B/s 0.00 B/s 0.00 % 0.01 % [kworker/u8:0-events_power_efficient]
7763 be/4 lin 0.00 B/s 7.90 K/s 0.00 % 0.00 % top -1 -i -b
...
```
和前面雷同，用 dataframe 紀錄 Total DISK READ 、 Total DISK WRITE 、 DISK READ 、 DISK WRITE，再用 plotly 畫出圖表，這裡就不放 code 跟範例圖表了。
成功計時和畫出圖表後，接下來我開始分析 `sort` 的效能，以及嘗試優化。
### 效能分析: 運行 1 個 2-way merge sort 排序 8 GiB 以及 16 GiB
我總共排序同樣的 8 GiB 以及 16 GiB 資料 5 次，耗費的秒數如下:
|實驗次數|8GiB|16GiB |24GiB|
|------|----|------|------|
|1 |515 |1592 |2155 |
|2 |505 |1523 |2183 |
|3 |505 |1547 |2150 |
|4 |517 |1360 |2177 |
|5 |498 |1323 |2170 |
|平均 |508 |1469 |2167 |
**擷取第一次實驗排序 8 GiB 的數據:**
- 下圖紅色線為 `sort` 占用的 CPU 資源，其一直維持在 25 % 上下，表示 `sort` 程序全程都有吃滿一顆核心，而藍色線則是系統整體占用的 CPU 資源，換句話說，藍色線的值減紅色線的值就是 `sort` 以外其他程序消耗的資源，包括 `gnome-shell` 、 `Xorg` 、 `code` 等等。
- 下圖是每個虛擬核心的使用率，可以發現前期 %CPU3 (紫色)和 %CPU0 (藍色)輪流呈現滿載的狀態，我推測其原因為當時正在執行 2-way merge sort 的 PASS 0 ，該階段需要抓取大量數字進行 C++ 內建的 `sort()` 運算，所以消耗大量運算，讓 %CPU3 和 %CPU0 都呈現 100% 負載。
而接下來進入 merge 階段不需要一次性的排序大量數字，而是需要反覆讀寫 page ，所以對 CPU 的消耗較低，但仍然讓 %CPU3 占用率衝到 80% 以上。
- 下圖藍色為系統整體佔用的記憶體，紅色為 `sort` 佔用的記憶體，很明顯看到紅色線有四塊明顯的凸起，此為 PASS 0 時 `sort()` 處理的資料，總共調用 `sort()` 4 次並產生 4 個 page。
在此程式中每次 `sort()` 處理的資料量為 200000000 個 `int` ，所以記憶體消耗為 $200000000 \times 4 \div 1000000 = 800$ MB 剛好為記憶體 (4GB) 的 20%，符合紅線的高峰值，由此可以知道 `top` 指令的記憶體資訊是足夠準確的。最後一個 page 沒有吃滿 20% 記憶體是因為生成 4 個 page 後， input.txt 剩下的數字不滿 200000000 個。
在 merge 階段只需重複從兩兩 page 讀取最小值，存入 merged page ，所以不需要配置大量記憶體，紅色線在此階段的記憶體消耗趨近於 0% 。
**分析完此實驗的效能後，我產生以下想法:**
>1. 由 CPU Usage 的圖可以發現運行一個 `sort` 下的系統整體佔用(藍色線)為 40% 左右，且 `sort` 佔用(紅色線)為 25% ，由此推測: 如果同時運行 3 個 sort，則系統整體佔用約為 40% + 25% + 25% = 90% ，約可以將這台虛擬機的 CPU 吃滿。
如果同時執行 4 個或以上 `sort` ，則 CPU 運算能力會不夠。也許作業系統會讓其中一個 sort 暫停執行，讓其他三個先執行；抑或是讓 4 個 sort 同時執行?
>2. 由 Memory Usage 的圖可以發現運行一個 `sort` 的 PASS 0 的記憶體佔用 (藍色線) 為 40% 到 50% 不等，且 `sort` 佔用(紅色線)為 20%，由此推測: 如果同時運行 3 個 `sort`，則系統記憶體佔用約為 30% + 3 * 20% = 90% ，快要可以將這台虛擬機的記憶體吃滿。
如果同時執行 4 個或以上 sort ，則記憶體空間不夠。也許作業系統會開始大量使用 swap 機制，將記憶體的資料暫時搬到硬碟?
>3. sort 在 PASS 0 之後便沒有大量利用記憶體，也許可以善用記憶體來改善 `merge` 的效能? 或是利用 multithread 在 PASS 0 的 page 生成後馬上進行 merge?
在之後的實驗我會探討以上議題。
### 效能分析: 同時運行 3 個 2-way merge sort 排序 8 GiB
接下來我嘗試一次執行多個 `sort` ，我將專案目錄複製為 3 份，分別命名為 benchmark1 、 benchmark2 、 benchmark3 。為了方便區隔每個目錄執行的程式，目錄中的 `sort` 也被重新命名為 `sort1` 、 `sort2` 、 `sort3` ，然後使用 shell script 一次執行 3 個 `sort` :
```bash
$ cat many.sh
benchmark1/sort1 input.txt benchmark1/output.txt &
benchmark2/sort2 input.txt benchmark2/output.txt &
benchmark3/sort3 input.txt benchmark3/output.txt
$ chmod 700 many.sh
$ ./many.sh
```
三個同時執行的 `sort` 程式分別花了 553 、 555 、 557 秒 (約莫 9 分鐘，但實際上三個程式跑完需要 9 分半) 完成排序，可以發現較執行單一個程式平均 508 秒慢了 10% 左右，但他們大致上是同步執行的。
**實驗數據:**
- CPU 占用率上 90% 了
- 閒置的核心變少了
- 記憶體占用率變高了，但是還沒吃滿記憶體。這一次實驗中，非 `sort` 的程序佔用的記憶體只有 20% 左右，三個 `sort` 各自佔用的記憶體也都是 20% 左右，所以記憶體的總佔用量約為 20% + 3 * 20% = 80% 左右。我分析了 SWAP 的使用率(紅色折線)，SWAP 的大小為 2GB 。在這次實驗中，有稍微使用 SWAP 。
- 下面這張白底圖是硬碟讀取的速度，單位為 MB/S，其中藍色折線是整個系統的讀取速度，可以看到 PASS 0 時，在調用 c++ 內建的 `sort()` 前，會大量從 input.txt 讀取資料，總共讀取 4 次；後面的 PASS 則是不斷從 page 讀取資料。
- 下面這張白底圖是硬碟寫入的速度，單位為 MB/S，其中藍色折線是整個系統的寫入速度， PASS 0 時，在 c++ 內建的 `sort()` 結束後有大量寫入的工作。
感覺這次實驗還沒辦法讓虛擬機遇到瓶頸，所以我決定再同時執行更多 `sort` ，看作業系統會如何處理這些程式。
### 效能分析: 同時運行 6 個 2-way merge sort 排序 8 GiB
執行 6 個 `sort` ，消耗的時間分別為 617、616、606、608、610、614 秒，然而所有程式跑完卻需要 20 分鐘左右，與 600 多秒相差甚遠，後來發現我所使用的 `clock()` 是用來量測 CPU time，非 wall-clock time。所以我量測到的是程式佔據 cpu 的時間，非程式開始執行到結束的系統時間。
- 同時執行 6 個 `sort` 時，總體 CPU 使用率沒有一直維持在 80% 以上，每次接近 100% 時就迅速掉落，每個 `sort` 也不是全程都佔用滿 1 顆核心，推測其原因為作業系統工作量太大，一直切換執行程序，CPU 佔用高時，正在執行 `sort` ； CPU 佔用低時，執行 gui 、 top 之類的背景程序。
- 每個核心的占用率
- 這次我分析了 SWAP 的使用率(紅色折線)，SWAP 的大小為 2GB 。在這次實驗中， PASS 0 使用的記憶體超過 95% ，記憶體空間已不敷使用，所以大量使用 SWAP 來暫存資料。但是 SWAP 在 PASS 0 時也幾乎都是滿載的狀態，不知道作業系統用甚麼機制去處理記憶體跟 SWAP 都滿載的情況。
**根據這次實驗，我歸納以下結論:**
>1. 從這次實驗可以發現在排序程式超過 CPU 可以負荷的程式的量時，作業系統會想辦法讓每個 `sort` 輪流使用 4 顆核心，並且每個 `sort` 在差不多的時間結束執行 (在此次實驗是約莫 23 分鐘)，代表作業系統分配的資源很平均，沒有發生一個程式執行完，另一個程式才執行到一半的狀況。
>2. 這次實驗可以看到記憶體跟 SWAP 都完全被吃滿，這次實驗過大的記憶體需求也導致這次實驗所花的時間變多，因為 SWAP 的速度跟硬碟一樣慢。
>3. 和前一次實驗 (同時運行 3 個 2-way merge sort) 相比，我發現同時執行 6 個會比較沒效率。假設我需要排序 6 個檔案，同時運行 3 個 2-way merge sort 兩次總共會花 9.5 * 2 = 19 分鐘；同時運行 6 個 2-way merge sort 一次總共會花 19 分 48 秒，慢了 48 秒左右。
>我猜測這些時間應該是耗費在系統排程和 SWAP 上，系統希望平均分配每個程式 (包括背景執行的程式) 佔用 CPU 的時間，雖然可以讓這些程式在差不多的時間結束，但反而降低每個程式的效率。
>但我覺得降低效率不一定是壞的，如果不平均分配資源的話，有些重要的功能會無法正常運行，比如 gui 介面可能會直接卡住不能動，或是想關掉 `sort` 時，會連 `kill` 都無法執行。所以這也許是資源有限的情況下作業系統的取捨吧!
之後的實驗，我將排序程式優化，並觀察效能。
### 效能分析: 運行 1 個 k-way merge sort
我總共排序同樣的 8 GiB 以及 16 GiB 資料 5 次，耗費的秒數如下:
|實驗次數|8GiB|16GiB |24GiB|
|------|----|------|-----|
|1 |572 |1368 |1814 |
|2 |584 |1360 |1845 |
|3 |578 |1322 |1887 |
|4 |579 |1349 |1913 |
|5 |595 |1229 |1985 |
|平均 |582 |1326 |1889 |
**擷取第一次實驗排序 8 GiB 的數據:**
>1. 我起初認為 k-way merge sort 一定會比 2-way merge sort 快，然而在排序 8 GiB 的檔案時， 2-way merge sort 反而會比較快。 2-way merge sort 平均花費 508 秒，而 k-way merge sort 平均花費 582 秒，整整多消耗 14% 的時間。我推測是因為我的機器上的 SSD 速度不算太慢，在 PASS 0 的 page 數量太少的情況下，更新 min-priority queue 的成本反而比 2-way 的比大小還要高，造成了明明 I/O 次數多，但排序速度較快的現象。
>排序 16 GiB 時，k-way merge sort 的速度就比 2-way merge sort 快了，前者平均花費 1326 秒，後者 1469 秒，約為 10% 差距。
>3. 我覺得 k-way merge sort 使用系統資源的模式跟 2-way merge sort 幾乎一模一樣，我無法從中分析有用的資訊。
### 效能分析: 同時運行 6 個 k-way merge sort 排序 8 GiB
這次執行 k-way merge sort ，消耗的時間分別為 802、805、798、792、793、789 秒， 6 個程式跑完總共耗時 26 分鐘。感覺效能優化並沒有成功，尤其是排序 8 GiB 資料時，雖然硬碟重複讀取較少次，但速度就是比 2-way merge sort 慢! 也許是我的 min-priority queue 實作效能太差，拖慢 k-way merge sort 的速度。但是總體上來說，當資料量越來越龐大， k-way merge sort 的優勢會更明顯。
## 結論
1. 作業系統分配的資源很平均，沒有發生一個程式執行完，另一個程式才執行到一半的狀況。系統希望平均分配每個程式 (包括背景執行的程式) 佔用 CPU 的時間，雖然可以讓這些程式在差不多的時間結束，但反而降低每個程式的效率。但若是不平均分配資源的話，有些重要的功能會無法正常運行，如 gui 服務，這算是有限資源下的取捨。
2. 程式執行時，並不是由一顆核心從頭跑到尾，而是系統不定時重新分配每顆核心的工作，所以在 Every Single CPU Usage 圖中可以看到每個核心輪流吃到 100% 然後又降下去。
3. 當記憶體快要滿時，作業系統被迫大量使用 swap，這也許是同時執行多個程式效率差的原因之一。
4. k-way merge sort 並不是所有情況下都比 2-way merge sort 快，因為需要考慮更新 min-priority queue 的成本，以前面實驗的結果來說，用 2-way merge sort 排序 8 GiB 的檔案比較快，但是當資料量更大時， k-way merge sort 的速度會比較快。以下是一張排序 8、16、24 GiB 的比較圖:
Sign in with Wallet
Connect another wallet