# 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電腦的範圍只有一點點
* 愈大的檔案，亂數的重複度愈高
* 或許可以嘗試加入負數
* 以下是程式碼:

#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`改成字串

#define MAX_LAST_NAME_LEN 20
typedef char val_t[MAX_LAST_NAME_LEN];

* node
* 刪除 next pointer
* 新增 index (該節點在 array 的index)

typedef struct node {
    val_t data;
    int index;
} node_t;

---
* llist
* 現今資料存放的大小(size)
* 指向 array 起始位置的指標

typedef struct llist {
    node_t *head;
    uint32_t size;
} llist_t;

---
* list_new
* 新增 array 以存放資料

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)

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 來確保正確性,造成程式**效率低**

 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`