contributed by <hugikun999
>
heathcliffYang
對自己的電腦硬體要有一定的認知才可以因為環境的不同而採取對應的策略。
1.Byte Order
之前沒有特別注意到這個項目,這個項目有兩種排序方法Big-Endian和Littel-Endian
,所有的資料都是由位元組成,由小到大或由大到小的位元去儲存資料。網路統一使用 Big-Endian,所以如果要從我的電腦傳封包出去就必須因為這之間的差別而做出調整。
Understanding Big and Little Endian Byte Order
$cat /proc/cpuinfo
這種方法類似第一種,可是會分別印出每個 porcessor 的資訊,這邊只放了一個 porcessor 的資訊。
memory hierarchy
這邊是一個重要的觀念,記憶體存在著這種階層式的概念,由上到下代表著記憶體大小由小到大,下面的圖片可以清楚看到越下層離CPU愈遠,越上層的 access 速度也愈快。增大 Cache 並不和速度成正比,這當中牽涉到很多問題,例如:Cache allocate 、 Cache miss、Cache size,是一個可以伸入探討的議題。
memory
當中有講到 Direct mapped caches 和 Fully Associative caches 的優點和缺點,前者限制較大,每個 block 有相對應的 Cache ,相較起來後者彈性許多,block 可以隨意的放入 cache 中,但是缺點正是因為太過自由而造成檢查的花費過大,為了兼顧兩者所以通常採用 n-way set associative cache的型式,先將 Cache 切成幾個 way 再進行 Cache 實體位置的分配。
這是一個對於排版非常方便的工具,其提供許多的 coding style 可以從其中挑選自己所喜歡的,保持版面的乾淨、統一是一件非常重要的事,這對於日後的維護會有非常大的幫助,可以省下非常多不必要的時間。下面是相關的網站,可以查到一些參數所代表的風格。
Artistic Style 2.06
進度要加快亮谷
收到俊逸
#if defined(__GNUC__)
gcc 所提供的 pre-defined macro,會偵測 compiler 是否為 gcc。
__builtin___clear_cache()
拿來清空處理器的 instruction cache。
Which is fastest: read, fread, ifstream or mmap?
mmap
is heavily than read
.read
,files may have been flushed out memory.mmap
can't work efficiently than other funcion.mmap
directly access memory.read
fetches the data from disk to page cache and then copy them to position you specify.這裡有提供一個可以測試 mmap
和 fread
的程式,我把 word.txt 當成輸入檔並用 $perf sate
重覆測試 100 次,可以發現 mmap
的 cache-missed 低了很大一個幅度,但是總體執行卻沒有比較快。
(1)fread
(2)mmap
都尚未做任何的優化以前所測得的數據。
GCC 提供 __attribute
這個關鍵字去指定一些特別的屬性。
__attribute__ ((aligned))
,compiler 會在編譯時根據你的 struct size 自動設定一個高於 size 的 alignment。一個 short 是2個位元組,這裡 compiler 就會設定大於6的2的最小次方,意即8 bytes,但是這會有浪費 memory 的情況。GCC 網頁中有提到 packed
可以減少 alignment。
結果
結果
由上面的測試可以知道,透過設定屬性可以減少浪費在每個 struct 上的記憶體空間,但是再搜尋上並沒有明顯的加快,因為 entry 的 size 並沒有因為加上__attribute__((packed)) 而減少,故在搜尋時讀入的大小一樣沒有省下時間。
(1)
我剛開始的想法是直接將 hash function 出來的值當作依據,每一個 hash 值都代表一個新的 entry head,只有當出來的 hash 值一樣才會在對應到的那個 entry 往下接,因此每次都必須重頭開始比對 hash 值是否已經出現,造成在 append 上的效率十分低落,搜尋的部份由於 table 十分龐大也花費許多時間在比對 hash 值上。總之,結果十分慘烈。
(2)
這邊我將 hash table 的大小設為 31,中間 append 和 fineName 不用使如上次如此多的判斷條件,整體時間往下非常多,但是相比於用開頭字母做分類的方法速度還是比較慢。
當 hash table size = 997時,可以看到搜尋的時間明顯變得很短,代表 collision 已經很少發生了,但因為 table 變得很大所以所需要的記憶體也變多了。
(3)
對於 table size 的大小要如何取決,通常是選質數當作 table 大小,這邊我從測試了10~1000的 size 大小,比較這之間 append() 和 findname() 的花費時間。可以看出來 append() 並沒有因為 size 變大而有顯著的變慢,花費的時間非常不穩定,在700~850之間有一段上升明顯的區塊,隨後又回到之前的平均;反觀在 findname() 這邊有明顯的因為 size 變大而搜尋時間下降的趨勢,大概是呈現指數下降。
TODO
source
使用 hash function 不可避免的一定會發生 collision 的問題,Open addressing 是利用 probing 來偵測或著是找到在 table 中尚未被使用的位置。目前我在實作上都是使用 link list 的方法,如果發生 collision 則將其鏈結到原有的目標後。但是其實還有許多方法可以解決 collision 問題,如果選用的方法設計妥善可以將搜尋複雜度降到 O(1),但這也是在 table 夠大的情況下。
Linear Probing
如果原本位置已經被佔用,將以線性方式找尋一個空的儲存位址將資料存入,簡單來說就是原值加上某個固定的常數或著乘上某倍率,可是這會造成某些特定地方的 hash value 過於集中,容易造成搜尋時間拉長。
Chaining
即是目前所利用的 link list 的方法,當 collision 發生時會將目前的東西以鏈結的型式接在已經存在的東西後面。
Quadratic Probing
不同於 Linear Probing 以線性處理, Quadratic Probing 是加上或減去某個值的平方,而這個值會隨著 collision 發生的次數而遞增,如此可以避免同樣的 hash value 過於集中的出現再某些特定地方。
Rehash
這個方法理解比較簡單,就是拿第一次的 hash value再做一次 hash function。
除了上面提到的這幾種方法,其實只要能設定規則都能解決 collision ,但若要找出一個能使 hash value 平均分散的方法則是比較困難的。
一次割出一塊記憶體空間,每次需要使用的使用的時候再分配出去。malloc 所配置出來的記憶體是零散的,並非像 memory pool 是連續性的記憶體。一次割出一塊記憶體空間可以省下每次 malloc 尋找空記憶體的時間,另外在 free 時也不用一個一個將記憶體空間釋放,可以一次就完成釋放的動作。
下面是一些我找到有用的參考,有些可以增加工作的效率,值得參考。
打造專屬於你的 Git 工作流程