owned this note
owned this note
Published
Linked with GitHub
# Mergesort (in array) with Thread Pool
contributed by <`jkrvivian`>, <`vic85821`>
## 預期目標
* 透過 thread pool , 實作 mergesort (array)
* 探討資料量大時,效能的變化
* 研究 thread 數目對效能的影響
## 產生大量的資料
怎麼產生大量的亂數資料？
* 寫了一個小程式可以產生指定大小的亂數檔，直接輸入欲輸出的檔案大小，單位為 MB ，就可以產生一個`input.txt`
* 問題:
* 使用`rand()`產生亂數，範圍為`0~2147483647`
* `RAND_MAX` 定義在 `stdlib.h`
* `0~32767` 家裡的windows 7電腦的範圍只有一點點
* 愈大的檔案，亂數的重複度愈高
* 或許可以嘗試加入負數
* 以下是程式碼:
```clike==
#include <stdio.h>
#include <time.h>
int main()
{
FILE *fp = fopen("input.txt","w");
long long int size, length = 0;
int counter = 0;
srand(time(NULL));
scanf("%lld",&size);
size *= 1048576; //轉換成byte
while(length <= size){
for(counter = 0; counter < 100; ++counter)
fprintf(fp, "%d\n", rand());
fseek(fp, 0 ,SEEK_END); //計算檔案大小
length = ftell(fp);
}
fclose(fp);
printf("over\n");
return 0;
}
```
## 更改mergesort-concurrent
* 原本的版本中,不太懂`max_cut`的作用 ... 拿掉
* `cut_func` 與 `merge_sort` 作用相同 ... 擇一
* 更改為用 array 存取資料
### linked list 改成 array (沿用上週的mergesort-concurrent)
---
:::warning
使用 phonebook 讀字串的方式實做,而不是integer排序
:::
* val_t
* 從本來的`intptr_t`改成字串
```clike==
#define MAX_LAST_NAME_LEN 20
typedef char val_t[MAX_LAST_NAME_LEN];
```
* node
* 刪除 next pointer
* 新增 index (該節點在 array 的index)
```c==
typedef struct node {
val_t data;
int index;
} node_t;
```
---
* llist
* 現今資料存放的大小(size)
* 指向 array 起始位置的指標
```c==
typedef struct llist {
node_t *head;
uint32_t size;
} llist_t;
```
---
* list_new
* 新增 array 以存放資料
```c==
llist_t *list_new(int size)
{
/*allocate list */
llist_t *list = malloc(sizeof(llist_t));
list->head = malloc(sizeof(node_t) * size);
list->size = 0;
return list;
}
```
---
* list_add
* 新增資料(如果 array 滿了,則 return -1)
```c==
int list_add(llist_t *list, val_t val)
{
node_t e;
strcpy(e.data,val);
e.index = list->size;
list->head[list->size] = e;
list->size++;
return 0;
}
```
---
>透過 array 實作 merge_sort ,再 merge 的時候會需要一個額外的空間去暫存排序完的資料,造成多餘的記憶體消耗,還在思考要怎麼省去額外的暫存空間就能夠 merge[name=vic85821]
>> 不然先實做一般的,若有想到解決辦法還能夠相互比較[color=red][name=Vivian]
>> 其實重寫程式碼比較快，畢竟原本的思維以 singly-linked list 為主 [name=jserv]
>> 網路上有看到利用 swap 交換的作法,但耗時增加[color=blue][name=vic85821] [reference](http://stackoverflow.com/questions/2571049/how-to-sort-in-place-using-the-merge-sort-algorithm)
### 問題
* merge 的部份,不能保證兩個 merge 的 list 位於相鄰的記憶體,只能透過 busy waiting 來確保正確性,造成程式**效率低**
```c==
if( !(_list->head[0].index + _list->size == tmp_list->head[0].index ||
_list->head[0].index == tmp_list->head[0].index + tmp_list->size)) {
task_t *_task = (task_t *) malloc(sizeof(task_t));
_task->func = merge;
_task->arg = _list;
tqueue_push(pool->queue, _task);
pthread_mutex_unlock(&(data_context.mutex));
}
```
> 還在思考能不能不管記憶體是否連續而直接merge[color=blue][name=vic85821]
>>有個想法!!把 task queue 改成 **priority queue**
>>priority: **cut_func > merge(head[0].index small) > merge(head[0].index large)**
>>這樣可以確保 merge 的 list 是連續的 [color=yellow][name=vic85821]
>>>可以試試！[color=red][name=Vivian]
* 原本的步驟為 讀取資料到 array -> divide -> merge
* 是否能在剛開始便建立為各個單獨的 list ,就能省去 divide 的時間
* memory overhead
* merge sort的意義
* data > memory malloc avaliale
* it is a reason why link list is better than array
* 但這部份跟印象中的 supermalloc 有所抵觸,還在查資料
* supermalloc 是直接 malloc一大塊記憶體,減少後續 malloc 的 system call
> 這樣一來,supermalloc 不就降低了 malloc 彈性高的優點嗎?或許是對於 supermalloc 的理解錯誤!!待查證 [color=#009393] [name=vic85821]
>> 這完全是不同的事情，一個是 virtual address 定址的範圍 (SuperMalloc 的技巧)，另一個是你能否做有效的 random access (sorting on array)。可透過 mmap 搭配之前的 align 技巧，預先映射大量資料到連續的虛擬記憶體區段，再行處理 merge sort [name=jserv]
>>> 好的!! 我再試試看 謝謝老師!! [name=vic85821][color= #009393]
### 分析
**測試100次, sort 2000筆資料所需時間**
* thread 愈多, random access 可能成功率愈低
* 導致 task queue 一直把錯誤的 access 再放回去,直到取得連續的 array 片段
* single thread 效能反而最高,因為不會擾亂 merge 的順序
## 重新設計程式
### 目標
* 透過 array 實作 mergesort
* 利用 mmap 搭配 align 技巧,有效提高 Random access
* Thread pool(Lock & Lock free)
###### tags: `system embedded` `Team9`
Sign in with Wallet
