HackMD
2024q1 Homework2 (quiz1+2)
contributed by < blue76815 >
測驗 1
延伸問題：
- 解釋上述程式碼的運作原理，提出改進方案並予以實作。
- 使用 Linux 核心風格的 List API 改寫上述程式碼，並針對鏈結串列，提出可避免最差狀況的快速排序實作，應設計效能評比的測試程式。
1. 解釋程式碼運作原理
typedef struct __node {
struct __node *left, *right;
struct __node *next;
long value;
} node_t
疑問：
此 Link list 節點，指向下一個節點位址時，是儲存到 *next 結構成員
問題是 *left, *right 沒指向下一個節點位址，
請問是在程式哪個步驟中有處理下個節點位址，儲存到*left 和 *right;結構成員的？
list_tail()
尋找鏈結串列 ( link list ) 的末端節點位址
node_t *list_tail(node_t **left)
{
/* 當 (*left)->next 還有紀錄節點位址
* 就繼續指向下一個節點
* */
while ((*left) && (*left)->next)
left = &((*left)->next );//AAAA
return *left;
}
list_length()
計次鏈結串列 ( link list ) 的節點個數
int list_length(node_t **left)
{
int n = 0;
while (*left) {
/* 一直指向下一個節點，順便 ++n 計次
* 直到 *left 節點位址為NULL尾端時，才跳出不計次
* */
++n;
left = &((*left)->next);// BBBB
}
return n;
}
list_construct()
建立新節點，並將資料 n，存入指定節點內的 value 成員裡
node_t *list_construct(node_t *list, int n)
{
node_t *node = malloc(sizeof(node_t));//建一個新節點
node->next = list; //
node->value = n;//插入節點資料
return node;//回傳節點位址
}
list_construct() 在測驗1中，是用在將 test_arr[count] 陣列裡的資料一個一個的存放到 list 鍊結串列的節點內
int main(int argc, char **argv)
{
node_t *list = NULL;
size_t count = 100000;
int *test_arr = malloc(sizeof(int) * count);
for (int i = 0; i < count; ++i)
test_arr[i] = i;
shuffle(test_arr, count);/* 對 test_arr[] 陣列內的資料洗牌*/
while (count--)
list = list_construct(list, test_arr[count]);
/*將 test_arr[count] 陣列裡的資料
* 一個一個的存放到 `list` 鍊結串列的節點內
* */
...
}
list_construct()和
list_add()不同
list_add() 是在鏈結串列 (link list)中，插入一個節點 ( list_add()函式內，沒有建立一個新節點的功能)
list_add()
在鏈結串列 ( link list )中，插入一個節點
註明: list_add()函式內，沒有建立一個新節點的功能
void list_add(node_t **list, node_t *node_t)
{
node_t->next = *list;
*list = node_t;
}
list_free()
鏈結串列 ( link list )，釋放節點
void list_free(node_t **list)
{
node_t *node = (*list)->next;
while (*list) {
free(*list);
*list = node;
if (node)
node = node->next;
}
}
quick_sort()
快速演算法（Quick Sort） 又稱為分割交換排序法，
其觀念是先在資料中找到一個中間值，
把小於中間值的資料放在左邊
而大於中間值的資料放在右邊，
再以同樣的方式分別處理左右邊兩邊的資料，直到完成為止
備註：在 Introduction to Algorithms, 4/e CH7 Quicksort 介紹中，不叫中間值，而是稱為 pivot
pivot: 樞紐
void quick_sort(node_t **list)
{
int n = list_length(list);
int value;
int i = 0;
int max_level = 2 * n;
node_t *begin[max_level], *end[max_level];
node_t *result = NULL, *left = NULL, *right = NULL;
begin[0] = *list;
end[0] = list_tail(list);
while (i >= 0) {
node_t *L = begin[i], *R = end[i];
if (L != R) {
node_t *pivot = L;
value = pivot->value;
node_t *p = pivot->next;
pivot->next = NULL;
while (p) {
node_t *n = p;
p = p->next;//CCCC
list_add(n->value > value ? &right : &left, n);
}
begin[i] = left;
end[i] = list_tail(&left) ;//DDDD
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
end[i + 2] =list_tail(&right) ;//EEEE
left = right = NULL;
i += 2;
} else {
if (L)
list_add(&result, L);
i--;
}
}
*list = result;
}
詳細流程介紹參閱
quit sort 非遞迴版 程式步驟詳解
2. 改成 Linux 核心的 List API 撰寫風格
在我們的專案文件夾裡，引入 lab0 的 list.h
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
#include <assert.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include "list.h"
Linux List API 使用方法，參閱
目標把
void list_add(node_t **list, node_t *node_t)
node_t *list_tail(node_t **left)
int list_length(node_t **left)
node_t *list_construct(node_t *list, int n)
void list_free(node_t **list)
static bool list_is_ordered(node_t *list)
替換成 list.h 內的 API
有參考 vax-r 同學的作法，寫成
void quick_sort(struct list_head **head)
{
int n = list_length(*head);
int pivot_value;
int i = 0;
int max_level = 2 * n;
struct list_head *begin[max_level];
begin[0] = *head;
for (int i = 1; i < max_level; i++)
begin[i] = list_new();
struct list_head *result = list_new(), *left = list_new(), *right = list_new();//OK
while (i >= 0) {
struct list_head *L = begin[i]->next, *R=begin[i]->prev;
if (L!=R) {
node_t *pivot = list_remove_head(begin[i]);
pivot_value = pivot->value;
node_t *entry, *safe;
list_for_each_entry_safe(entry, safe, begin[i], list){
list_del(&entry->list);
list_add(&entry->list,entry->value > pivot_value? right:left);
}
list_splice_init(left, begin[i]);
list_add(&pivot->list, begin[i + 1]);
list_splice_init(right, begin[i + 2]);
i += 2;
} else {
if (list_is_singular(begin[i]))
list_splice_init(begin[i], result);
i--;
}
}
for (int i = 0; i < max_level; i++)
list_free(begin[i]);
list_free(left);
list_free(right);
*head = result;
}
詳細變更，請看我的 Github 3723ace 紀錄
3. 提出可避免最差狀況的快速排序實作，設計效能評比
3.1 撰寫 gunplot 繪圖程式
makefile 中
sudo taskset -c 0 ./main 10000 > data.csv
其中 sudo taskset -c 0 就是要將程式綁定在1個cpu上執行
根據 man clock_gettime
使用 clock_gettime()函數，計時 nanosecond
先作到量測 1000筆 資料做 q_sort 計時為例
int main(int argc, char **argv)
{
//for (int i = 10; i <= 100000; i++) {
for (int i = 10; i <= 1000; i++) {
unsigned long long time_non_sort = 0, time_sort= 0;
struct timespec t1, t2;
struct list_head *list = list_new();
size_t count = i, data_number=i;
int *test_arr = malloc(sizeof(int) * count);
for (int i = 0; i < count; ++i)
test_arr[i] = i;
shuffle(test_arr, count);
while (count--)
list = list_construct(list, test_arr[count]);
//list_print(list);
clock_gettime(CLOCK_MONOTONIC, &t1); //撮記時間t1
quick_sort(&list);//真正跑分析的函式
clock_gettime(CLOCK_MONOTONIC, &t2); //撮記時間t2
time_non_sort += (unsigned long long) (t2.tv_sec * 1000000000 + t2.tv_nsec) -
(t1.tv_sec * 1000000000 + t1.tv_nsec);//轉成 nanosecond
assert(list_is_ordered(list));
clock_gettime(CLOCK_MONOTONIC, &t1); //撮記時間t1
quick_sort(&list);//真正跑分析的函式
clock_gettime(CLOCK_MONOTONIC, &t2); //撮記時間t2
time_sort += (unsigned long long) (t2.tv_sec * 1000000000 + t2.tv_nsec) -
(t1.tv_sec * 1000000000 + t1.tv_nsec);//轉成 nanosecond
assert(list_is_ordered(list));
printf("%ld,%llu,%llu\n", data_number, time_non_sort, time_sort);
//list_print(list);
list_free(list);
free(test_arr);
}
return 0;
}
gunplot ：撰寫 plot_qsort.gp
reset
set xlabel 'data number'
set ylabel 'nanosecond'
set title 'perfomance comparison'
set term png enhanced font 'Times_New_Roman, 10'
set output 'qsort.png'
set xtics 0,100 //x軸 每間隔100點，設一個座標
set datafile separator ","
set key left
plot \
"data.csv" using 1:2 with linespoints linewidth 1 title "qsort", \
"data.csv" using 1:3 with linespoints linewidth 1 title "non-qsort"
makefile
SHELL = /bin/bash
CC = gcc
CFLAGS = -g -pthread
SRC = $(wildcard *.c)
EXE = $(patsubst %.c, %, $(SRC))
SRC2 = $(wildcard *.csv)
SRC3 = $(wildcard *.png)
all: ${EXE}
%: %.c
${CC} ${CFLAGS} $@.c -o $@
plot:
sudo taskset -c 0 ./main > data.csv
gnuplot plot_qsort.gp
mv data.csv 1000_data.csv
mv qsort.png 1000_qsort.png
clean:
rm ${EXE}
rm ${SRC2}
rm ${SRC3}
編譯驗證程式
$ make
$ make plot
sudo taskset -c 0 ./main > data.csv
gnuplot plot_qsort.gp
mv data.csv 1000_data.csv
mv qsort.png 1000_qsort.png
$ ls
1000_data.csv 1000_qsort.png cpucycles.h list.h main main.c makefile plot_qsort.gp
可看到生成
1000_data.csv 1000_qsort.png 這兩個檔案
1000_qsort.png
4. 針對鏈結串列，提出可避免最差狀況的快速排序實作，應設計效能評比的測試程式。
4.1 quick_sort worst case
根據這篇 快速排序 (Quick Sort) 提到
quick_sort worst case 是發生在
Pivot 恰好是該資料陣列的最小值或最大值，使得切割無法產生一分為二的效果。
c n 為切割時間
故時間複雜度為
4.2 提昇效能方法：
根據 避免 Quick Sort 的 Worst Case 發生
有鑑於時間複雜度高達
，要怎麼樣才能避免取到最小或最大值的 Worst Case 呢？ 以下提供三種可能解法：
- Middle-of-Three 方法
- Randomized Quick Sort
- 使用 Median-of-Medians 作為基準
4.3 撰寫程式
根據 避免 Quick Sort 的 Worst Case 發生 提到的方法
4.3.1 修改 find_middle
之前的 find_middle() 每次要先做 list_length(head)/2; 時間複雜度太長
struct list_head *find_middle(struct list_head *head)
{
//用 list_length(struct list_head *head) 方法取一半
int n = list_length(head)/2;
struct list_head *middle,*safe;
printf("list_length=%d\r\n",n);
list_for_each_safe (middle, safe,head) {
if (n == 0)
break;
n--;
}
return middle;
}
因次參照 Jserv 老師的
分析「快慢指標」作法
改成
node_t *get_middle_node(struct list_head *head) {
struct list_head *slow = head->next;
struct list_head *fast = head->next;
while (fast != head && fast->next != head) {
slow = slow->next;
fast = fast->next->next;
}
return list_entry(slow, node_t, list);
}
4.3.2 實做 Middle-of-Three
step1.取出 link list 頭 (low_node) 尾(high_node) 中間(middle_node) ，這三個節點
step2.前面三筆資料，找出中間值節點(
middle_value_node)。find_median_of_three()step3.中間值節點 和 頭節點 交換
swap_nodes()step4.讓新的 頭節點 作為 pivot
詳細程式實做，請看
github commit Implement median_of_three qsort.
/* 從三筆資料，找出中間值節點 */
node_t *find_median_of_three(node_t *a, node_t *b, node_t *c) {
if ((a->value > b->value && a->value < c->value) || (a->value > c->value && a->value < b->value)) {
return a;
} else if ((b->value > a->value && b->value < c->value) || (b->value > c->value && b->value < a->value)) {
return b;
} else {
return c;
}
}
/**
* https://github.com/torvalds/linux/blob/master/include/linux/list.h
* list_replace - replace old entry by new one
* @old : the element to be replaced
* @new : the new element to insert
*
* If @old was empty, it will be overwritten.
*/
static inline void list_replace(struct list_head *old, struct list_head *new)
{
new->next = old->next;
new->next->prev = new;
new->prev = old->prev;
new->prev->next = new;
}
/**
* https://github.com/torvalds/linux/blob/master/include/linux/list.h
* list_swap - replace entry1 with entry2 and re-add entry1 at entry2's position
* @entry1: the location to place entry2
* @entry2: the location to place entry1
*/
static inline void list_swap(struct list_head *entry1, struct list_head *entry2)
{
struct list_head *pos = entry2->prev;
list_del(entry2);
list_replace(entry1, entry2);
if (pos == entry1)
pos = entry2;
list_add(entry1, pos);
}
struct list_head* swap_nodes(node_t *node1, node_t *node2, struct list_head *head) {
if (node1 == node2) return head;
list_swap(&node1->list,&node2->list);
// If node1 or node2 was the head, update head
if (&node1->list == head) {
head = &node2->list;
} else if (&node2->list == head) {
head = &node1->list;
}
return head;
}
和 q_sort 差別是，加入 median_of_three（begin[i]）預先處裡 link list
void quick_sort_median_of_three(struct list_head **head)
{
....
while (i >= 0) {
struct list_head *L = begin[i]->next, *R=begin[i]->prev;
if (L!=R) {
begin[i]=median_of_three(begin[i]); // 在這行加入 median_of_three（begin[i]）預先處裡 link list
node_t *pivot = list_remove_head(begin[i]);
pivot_value = pivot->value;
....
}
4.3.3 實做 Randomized Quick Sort
根據文章中 2. Randomized Quick Sort 提到
2. Randomized Quick Sort
用亂數選取的方式，隨機挑一個值作為 pivot。
當然，這還是可能會發生 Worst Case 高達 O(n2) 的問題，只是機率比較低。 Average Case 與 Best Case 同樣是 O(n log n)。
所以我們也可以把以上兩種改進合併──先用亂數任選三個，再用其中的中間值作為 pivot。
詳細程式實做，請看
github commit Implement random_pivot qsort.
和 q_sort 差別是加入，這三行是 做 random pivot
/*
step0. 先準備好 begin[i]的 head 節點，準備之後做交換用==> *head_node
step1. 用亂數任選三個，再用其中的中間值作為 pivot。
step2. 再用其中的中間值作為 pivot。
step1~step2 就是 random_pivot_node=random_pivot(begin[i]); 在處裡
最後產生 random_pivot_node
step4. swap_nodes(begin[i], head_node, random_pivot_node);
代表 begin[i] link list 的 pivot 要改成 random_pivot_node做排序
*/
node_t *head_node = list_first_entry(begin[i], node_t, list);
node_t *random_pivot_node=random_pivot(begin[i]);
begin[i]=swap_nodes(head_node, random_pivot_node,begin[i]);
void quick_sort_random_pivot(struct list_head **head)
{
...
while (i >= 0) {
struct list_head *L = begin[i]->next, *R=begin[i]->prev;
if (L!=R) {
// 這三行是 做 random pivot
/*
step0. 先準備好 begin[i]的 head 節點，準備之後做交換用==> *head_node
step1. 用亂數任選三個，再用其中的中間值作為 pivot。
step2. 再用其中的中間值作為 pivot。
step1~step2 就是 random_pivot_node=random_pivot(begin[i]); 在處裡
最後產生 random_pivot_node
step4. swap_nodes(begin[i], head_node, random_pivot_node);
代表 begin[i] link list 的 pivot 要改成 random_pivot_node做排序
*/
node_t *head_node = list_first_entry(begin[i], node_t, list);
node_t *random_pivot_node=random_pivot(begin[i]);
begin[i]=swap_nodes(head_node, random_pivot_node,begin[i]);
node_t *pivot = list_remove_head(begin[i]);
pivot_value = pivot->value;
...
}
4.4 量測效能
因為我們的 quick_sort 排序完，節點是升冪排序
例如 1–>2–>3–>4–>5–>7
所以 worst case 我們餵降冪排序的節點資料，給 quick_sort 排序
詳細程式實做，請看
github commit Implement plot_qsort.gp to measure 3 ways of qsort performance.
編譯量測效能
以量測2000筆為例
$ make
$ make plot
sudo taskset -c 0 ./main > data.csv
gnuplot plot_qsort.gp
mv data.csv 2000_data.csv
mv qsort.png 2000_qsort.png
加入 median_of_three 和 random_pivot 處理，根本沒有使排序更省時，相反的
因為 quick_sort_median_of_three()內多了 median_of_three(begin[i])交換節點的處理步驟
void quick_sort_median_of_three(struct list_head **head)
{
...
while (i >= 0) {
struct list_head *L = begin[i]->next, *R=begin[i]->prev;
if (L!=R) {
/* type35 median_of_three 解決辦法
當`begin[i]` link list 長度有3個節點以上，
才丟進 `median_of_three(begin[i]);` 處裡，
*/
begin[i]=median_of_three(begin[i]); // 在這行加入 median_of_three（begin[i]）預先處裡 link list
node_t *pivot = list_remove_head(begin[i]);
pivot_value = pivot->value;
}
quick_sort_random_pivot內多了random_pivot(begin[i]);交換節點的處理步驟
void quick_sort_random_pivot(struct list_head **head)
{
...
while (i >= 0) {
struct list_head *L = begin[i]->next, *R=begin[i]->prev;
if (L!=R) {
node_t *head_node = list_first_entry(begin[i], node_t, list);
node_t *random_pivot_node=random_pivot(begin[i]);
begin[i]=swap_nodes(head_node, random_pivot_node,begin[i]);
node_t *pivot = list_remove_head(begin[i]);
pivot_value = pivot->value;
...
}
反而比 q_sort 更耗費處理時間
- 問題：在找 median_of_three，其他步驟更精簡的實做方法，才能降低時間複雜度
測驗 2
延伸問題：
- 解釋上述程式碼的運作原理，提出改進方案並予以實作。
- 將改進過的 Timsort 實作整合進 sysprog21/lab0-c，作為另一個有效的排序命令，應設計效能評比的測試程式，確保測試案例符合 Timsort 設想的資料分布樣式。
1. 解釋上述程式碼的運作原理
1.1 Timsort 演算法介紹
Timsort 混和了合併排序法(Merge Sort)及插入排序法(Insertion Sort)
根據 測驗 2 描述提到
Timsort 致力於從以下三個方面，改進合併排序演算法：
- 加快合併（merge）過程
- 減少進行合併的次數。
- 在某些特定情況下，尋找比合併排序更有效的排序方法
1.2 Timsort 演算法步驟
先歸納成以下3個主要步驟
step1. 將遞增數列分割成一組一組 run
step2. 合併（用 Merge sort 做合併）
step3. Galloping mode
以下詳細介紹步驟細節
step1.分割成 run
分割要領
-
數列中，一路遞增的數組，當成一組run數列
例如 測驗2 中
1,2,3,4,3,2,4,7,8 數列中
可以拆分成3個run- 1,2,3,4==>一路遞增，當成一組run數列
- 3,2==>遇到遞減的數列，會被反轉成遞增的序列，變成2,3
- 4,7,8==>一路遞增,當成一組run數列
-
合併序列時，
- 若 run 的數量等於或小於 2 的冪(
- 若大於 2 的冪(
- 若 run 的數量等於或小於 2 的冪(
-
每個 run 的長度，定義一個 minrun (最小運行長度)
- 若長度太短，就用二分插入排序，將 run 後面的元素插入到前面的 run 裡面。
例如 run 的長度設定 minrun=5，則在分割
1,2,3,4,3,2,4,7,8數列時，
按照一路遞增，當成一組run數列規則
只有1,2,3,4是一組run，但是因為設定 minrun=5（一組run數列最小長度得5個數字），因此得取
1,2,3,4,3 當成一組run數列，還要用二分插入排序整理 run 變成
1,2,3,3,4
- 若長度太短，就用二分插入排序，將 run 後面的元素插入到前面的 run 裡面。
-
minrun要定義多少個，參照 最貼近現實的排序演算法- Timsort
那問題來了，該如何知道這個 minrun 的值是多少呀？這個 minrun 必須滿足三個條件，
- minrun必須小於 64 ，因為大於 64 的 Insertion sort 效率會變差。
- 盡可能的平均分配，不能有全部都剛好是 minrun 而最後一個只剩下很少元素的情況發生
- 盡可能將切割完的 run 的數量控制在二的次方（前面講的 2的冪），方便待會的Merge sort
因此 Tim 想了一個非常聰明的方法，先將序列的總長度表示成二進位，取出前六個數之後如果後面還有值，就+1，舉個例子：如果總長度是197，換成二進位那就是 11000101，取出前六個數 110001 = 49，後面還有 01 所以將49+1=50，那麼在最壞的情況下，會被拆成 50 50 50 47，剛好滿足了上面的那三個條件，這個方法真的相當聰明。以上我們已經將 Timsort 的切割完全介紹完畢。
step2.合併
合併
為了達到高效率且省空間的合併，Tim 精心設計了合併的細節，先聊大方向的合併，我們手上現在有非常多個 run，我們從最右邊抓三個 run 出來，由左到右依次命名為 runX, runY, runZ，只要不滿足以下兩個條件的其中之一，就將 runY 與 ( runX 和 runZ 較小的 )合併：
- runX 長度 > runY + runZ 長度
- runY 長度 > runZ 長度
上面那段合併條件限制，就是對應到 成大 測驗二 描述的
Timsort 採用一組堆疊 (stack) 來暫存 run，此舉是為了避免在一開始就掃描整個資料範圍來產生 run，從而降低記憶體開銷。過程中，Timsort 運用 merge_collapse 函式來確保堆疊上的 run 長度保持平衡。該函式主要檢查堆疊頂端的 3 個 run 是否滿足以下原則：
A 的長度要大於 B 和 C 的長度總和。
B 的長度要大於 C 的長度。
step3.Galloping mode
接下來我們來聊兩個 run 之間的合併，為了解決 Merge sort 在處理空間上的不足(可以往上回去看第一張圖)，Tim 想出了底下的合併方法：
- 將比較小的 run 當成圖中的 X
- 把 runX 複製到一個新的空間 temporary
- 接下來用 Merge sort 合併
上面這個合併的方法可以確保在最壞的情況下，Timsort 使用的空間是 n/2 (Tim真的是個很務實的人)，到這邊其實已經可以算是很圓滿的結束了，但是 Tim 覺得這樣不行，還必須對 Merge sort 做出優化，所以 Tim 提出了 Galloping mode。（本次作業我最想釐清的點）
Galloping
再強調一次!
Tim 認為在現實世界中的序列大多都是已經部分排序的(partial sorted)
所以假設有兩個序列 {1, 2, 3, 4, 5, …,1000} {2001, 2002, 2003, …,3000}做 Merge sort，總共需要比對一千次，這實在是太耗資源了，所以 Tim 想了一個新的做法，就是只比二的次方的數，比完之後再用 binary search(前面已經排序好了) 找到那個對的位子，這樣總共比較的次數可以壓低到 O(logn)， 但是Tim又發現了一個問題：
從上面那張圖可以發現在比較 2, 4 的時候 linear search 的效果是比 galloping 的效果來的好的(分別是左二欄和右一欄)，所以 Tim 決定當兩個序列比較到第七次都是由同一個序列取值時，才啟動 Galloping mode。 以上就是 Timsort 所有合併的細節了。
1.3 對應到程式碼介紹原理
介紹篇幅太長，另開共筆頁面
Tim sort 程式步驟詳解
參考資料：
1.4 提出改進方案並予以實作。
1.4.1 改善記憶體洩漏
用 valgrind 檢查
$ valgrind --leak-check=full --show-leak-kinds=all --track-origins=yes --verbose --log-file=filename ./timtest
這裡的指令選項解釋如下：
--leak-check=full：告訴 Valgrind 執行完整的記憶體泄漏檢查。--show-leak-kinds=all：顯示所有類型的記憶體泄漏。
其他常用選項
--track-origins=yes：這個選項可以幫助追蹤未初始化的記憶體讀取的來源，這對於確定未初始化記憶體使用的位置非常有用。--verbose：提供更多的調試信息。--log-file=filename：將 Valgrind 的輸出導向到一個文件。
範例
假設你的程序叫做 my_program，並且已經編譯成執行檔 my_program，並產生valg_log將 Valgrind 的輸出導向到一個文件，你可以這樣使用 Valgrind：
valgrind --leak-check=full --show-leak-kinds=all --track-origins=yes --verbose --verbose --log-file=valg_log ./my_program
$ valgrind --leak-check=full --show-leak-kinds=all --track-origins=yes --verbose --log-file=valg_log ./timtest
其中顯示出
==127653== Searching for pointers to 3 not-freed blocks
==127653== Checked 109,392 bytes
==127653==
==127653== 24,000 bytes in 1 blocks are definitely lost in loss record 1 of 3
==127653== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==127653== by 0x109673: main (main.c:116)
==127653==
==127653== 24,000 bytes in 1 blocks are definitely lost in loss record 2 of 3
==127653== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==127653== by 0x109681: main (main.c:117)
==127653==
==127653== 24,000 bytes in 1 blocks are definitely lost in loss record 3 of 3
==127653== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==127653== by 0x10968F: main (main.c:118)
==127653==
==127653== LEAK SUMMARY:
==127653== definitely lost: 72,000 bytes in 3 blocks
==127653== indirectly lost: 0 bytes in 0 blocks
==127653== possibly lost: 0 bytes in 0 blocks
==127653== still reachable: 0 bytes in 0 blocks
==127653== suppressed: 0 bytes in 0 blocks
==127653==
==127653== ERROR SUMMARY: 3 errors from 3 contexts (suppressed: 0 from 0)
valgrind 指出，我的 main.c
main (main.c:116)
main (main.c:117)
main (main.c:118)
第 116-118 行顯示錯誤
發現
element_t *samples = malloc(sizeof(*samples) * SAMPLES);
element_t *warmdata = malloc(sizeof(*warmdata) * SAMPLES);
element_t *testdata = malloc(sizeof(*testdata) * SAMPLES);
在Tim sort後沒有釋放動態記憶體
加入
free(samples);
free(warmdata);
free(testdata);
再用 valgrind 檢查，顯示
All heap blocks were freed -- no leaks are possible
ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
==128843== HEAP SUMMARY:
==128843== in use at exit: 0 bytes in 0 blocks
==128843== total heap usage: 4 allocs, 4 frees, 73,024 bytes allocated
==128843==
==128843== All heap blocks were freed -- no leaks are possible
==128843==
==128843== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
