owned this note
owned this note
Published
Linked with GitHub
# 2016q3 Homework4 (Phonebook-Concurrent)
contributed by<`andy19950`>, <`cjTsai3030`>, <`TotallyWrong`>
## 待辦清單
- [ ] 待辦
- [x] Test Integer and String
- [x] Figure out data structure
- [x] Figure out group share github
- [ ] Test Hash Table size
- [x] String Integer Converter
- [ ] Flow chart [see](https://hackmd.io/CwYwhgzAbApgHFAtHAnAIzY4awBNkwCsA7ImFCBCHAIxwBMhhIQA?both)
modification vs integer converter
- [ ] Fake Phone and Detail Data
- [ ] Add and Delete Name
- [ ] Modify Name
- [x] Figure out how to use Atomic Swap
- [ ] Prefetch Hash Table
## 共同 Project:
>>中英文關鍵字間請以空白區隔!
>>已幫忙調整~
>>[color=red][name=課程助教]
### 目標:
我們有再一個禮拜重新做一次 Phonebook-Concurrent,我們想要把這程式重新思考一次,之前花很多時間了解程式和花時間閱讀文件,這次要做到很大的進步。
>> 練習清楚地闡述,重新寫出你們的目標和運用到的背景知識 [name=jserv]
### 事前準備:
1. Github share repository :
* 當分組作業時,可能會遇到要如何統整彼此所負責的工作,這時候除了用先前作業採取 fork 的方式,大家個別編輯自己 fork 完的檔案再統一整理,這一個方式可能會在統整時耗費相當多的時間。
* 目前有找到[資料](http://tech-marsw.logdown.com/blog/2013/08/17/git-notes-github-n-person-cooperation-settings),發現 github 有提供 ==Collaborators==的編輯方式,藉由這一個方法,可以省去統整的時間,在上傳時可能需要事前溝通好要修改的版本,以避免版本不一的狀況。
* 步驟
* 選取要加入 Collaborator 的 repository
* Setting -> Collaborators
* 輸入 github 帳號,並請該 Collaborator 確認邀請。
---
### 新的想法:
1. 在這個 Phonebook-Concurrnet 裡最令人討厭的東西就是 String , 不管是大小還是複製,比較,測長度都要去 Call `<string.h>` 來處理 mmap() 還要補零等複雜操作,只要把 String 轉成 Integer 就好辦多了。
~~2. 採用Double Hash 讓Hash Table不要太大,也方便讓各個Threads各自Append不完需要Mutex~~。
:::warning
:zap: 已經了解使用法還未成功加入Pthread
3. Append 時採用 Atomic Swap 達到 Lock-Free Concurrent
:::
### 想法驗證:
#### String Integer 變換
String 透過 ASCII 轉換 Integer 不難, 所以先寫一個方式驗證,String Operation 和 Intger Operation 的時間差來測試這樣做是否有價值,我們寫了個小程式來測試字串比較和整數比較的時間差:
>>程式碼的排版也要注意喔!
>>[color=red][name=課程助教]
>> 下面的程式碼實在太醜了,拜託請重寫!然後程式縮排非常重要,請依循一致的風格 [name=jserv]
```clike=
int WordCompareString()
{
char name[16] = "Aadfdck", name3[16] = "sasdfck",
name5[16] = "rsdfdfack", name7[16] = "Jsdfdack";
char name2[16] = "Pacgdsk", name4[16] = "dack",
name6[16] = "Bacsdfsdfk", name8[16] = "Oacsdfk";
int i=10000000, sto1;
while (i) {
sto1= strcmp(name,name2)+strcmp(name3,name4)+strcmp(name5,name6)+strcmp(name7,name8)+strcmp(name,name2)+strcmp(name3,name4)+strcmp(name5,name6)+strcmp(name7,name8)+
strcmp(name,name2)+strcmp(name3,name4)+strcmp(name5,name6)+strcmp(name7,name8)+
strcmp(name,name2)+strcmp(name3,name4)+strcmp(name5,name6)+strcmp(name7,name8);
i--;
}
//printf(" %d \n ",sto1);
return sto1;
}
int WordCompareInteger()
{
long long na1=2194081,na3=21940101,na5=291408126,na7=2194812626 ;
long long na2=212294061,na4=512294081,na6=262914081,na8=219481;
int j=10000000, sto2;
while(j)
{
sto2=(na1>na2)+(na3>na4)+(na5>na6)+(na7>na8)+(na1>na2)+(na3>na4)+(na5>na6)+(na7>na8)+
(na1>na2)+(na3>na4)+(na5>na6)+(na7>na8)+(na1>na2)+(na3>na4)+(na5>na6)+(na7>na8);
j--;
}
}
```
在 Makefile 是分成兩個執行檔,各跑21次時間分別為:
* String: 0.51357±0.01224 (95% condifence level)
* Integer: 0.07923±0.00016 (95% condifence level)
執行時間差了快6倍,接下來測試寫,各跑21次時間分別為:
* String:0.79589+-0.00795(95% condifence level)
* Integer:0.07535±0.00085(95% condifence level)
執行時間差了約10倍,可見不管在 Append 或是 Find 採用 Integer 都是比較快的,而且再做 Hash 搜尋時也減少不必要的文字轉換。
#### Atomic Compare and Exchange
為了在 Append 時達到 Lock Free Concurrent 我們會採用 [atomic_compare_exchange](http://en.cppreference.com/w/c/atomic/atomic_compare_exchange)這個Function來達到Lock Free。之前沒有使用過`<stdatomic.h>`中的相關指令,所以就先寫個小程式來測試一些功能。
### Flow Chart:
:::warning
注意 :zap: 還未採用
Double Hash 程式流程圖:
```flow
st=>start: Begin
e=>end: End
op=>operation: 把文字轉換成3個 Integer
io=>inputoutput: 讀入 word.txt
op3=>operation: 用Hash做第一次分類避免碰撞
op4=>operation: 各個執行緒(Threads)再去把各個字串做第二次Hacsh並Append到各自的Hash Table
io4=>inputoutput: Input word.txt
st->io->op->op3->op4->e
```
:::
>> thread 的台灣譯詞為「執行緒」,不是「線程」,請注意 [name=jserv]
### 程式選寫:
數字換算表
>> 這個表格的用意為何? [name=jserv]
|Character| 0 | a | b | c | d | e | f | g | h |
| --|---|---|---|---|---|---|---|---|---|
|**Integer**|0| 1|2 | 3 | 4 | 5 | 6 | 7 | 8|
|**Character**|i|j| k | l | m | n | o | p | q |
|**Integer** |9|10|11|12|13|14|15|16| 17 |
|**Character**|r|s|t|u|v|w|x|y|z|
|**Integer** |18|19|20|21|22|23|24|25|26 |
###### tags: `andy19950` `cjTsai3030` `TotallyWrong` `On going`