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)

• 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 的時候會需要一個額外的空間去暫存排序完的資料,造成多餘的記憶體消耗,還在思考要怎麼省去額外的暫存空間就能夠 mergevic85821

不然先實做一般的,若有想到解決辦法還能夠相互比較Vivian
其實重寫程式碼比較快，畢竟原本的思維以 singly-linked list 為主 jserv

網路上有看到利用 swap 交換的作法,但耗時增加vic85821 reference

問題

• 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));
}

還在思考能不能不管記憶體是否連續而直接mergevic85821

有個想法!!把 task queue 改成 priority queue
priority: cut_func > merge(head[0].index small) > merge(head[0].index large)
這樣可以確保 merge 的 list 是連續的 vic85821

可以試試！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 的理解錯誤!!待查證 vic85821

這完全是不同的事情，一個是 virtual address 定址的範圍 (SuperMalloc 的技巧)，另一個是你能否做有效的 random access (sorting on array)。可透過 mmap 搭配之前的 align 技巧，預先映射大量資料到連續的虛擬記憶體區段，再行處理 merge sort jserv

好的!! 我再試試看 謝謝老師!! 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