---
# System prepended metadata

title: 2019q1 Homework7 (skiplist)

---

# 2019q1 Homework7 (skiplist)
contributed by < `LiunuXXX` >
## 預期目標
1. 思考 Linux 核心內部的資料結構，特別是 cache-oblivious data structures 的考量
2. 實作 Skip list，設計對應的效能分析框架
3. 開發適用於使用者層級和核心層級的程式碼

## 開發環境

```
$ lscpu
架構：               x86_64
CPU 作業模式：       32-bit, 64-bit
Byte Order:          Little Endian
Address sizes:       39 bits physical, 48 bits virtual
CPU(s):              4
On-line CPU(s) list: 0-3
每核心執行緒數：     2
每通訊端核心數：     2
Socket(s):           1
NUMA 節點：          1
供應商識別號：       GenuineIntel
CPU 家族：           6
型號：               60
Model name:          Intel(R) Core(TM) i5-4210M CPU @ 2.60GHz
製程：               3
CPU MHz：            859.812
CPU max MHz:         3200.0000
CPU min MHz:         800.0000
BogoMIPS:            5190.32
虛擬：               VT-x
L1d 快取：           32K
L1i 快取：           32K
L2 快取：            256K
L3 快取：            3072K
NUMA node0 CPU(s)：  0-3
```

```
$ uname -r
4.19.45-1-MANJARO

```

```
$ gcc --version
gcc (GCC) 8.3.0


```
## 作業要求
* 完成 [第 11 週測驗題 (中)](https://hackmd.io/s/BkFJPHriE) 和所有延伸題目
* 在 Linux 核心原始程式碼使用 skip list 的案例，介紹其原理，設計 Linux 核心模組的實驗
    * 需要涵蓋 kernel API 同步機制的運用
    * 執行時期的分析 (提示: 可善用 eBPF)

## 作業區
==完成 [第 11 週測驗題 (中)](https://hackmd.io/s/BkFJPHriE) 和所有延伸題目==
### 測驗 `1`

給定一個 circular linked list 實作如下: (檔案 `list.h`)
```cpp
#ifndef INTERNAL_LIST_H
#define INTERNAL_LIST_H

/* circular doubly-linked list */
typedef struct __list_t {
    struct __list_t *prev, *next;
} list_t;

/*
 * Initialize a list to empty. Because these are circular lists, an "empty"
 * list is an entry where both links point to itself. This makes insertion
 * and removal simpler because they do not need any branches.
 */
static inline void list_init(list_t *list) {
    list->prev = list;
    list->next = list;
}

/*
 * Append the provided entry to the end of the list. This assumes the entry
 * is not in a list already because it overwrites the linked list pointers.
 */
static inline void list_push(list_t *list, list_t *entry) {
    list_t *prev = list->prev;
    entry->prev = prev;
    entry->next = list;
    prev->next = entry;
    list->prev = entry;
}

/*
 * Remove the provided entry from whichever list it is currently in. This
 * assumes that the entry is in a list. You do not need to provide the list
 * because the lists are circular, so the list's pointers will automatically
 * be updated if the first or last entries are removed.
 */
static inline void list_remove(list_t *entry) {
    list_t *prev = entry->prev;
    list_t *next = entry->next;
    prev->next = next;
    next->prev = prev;
}

/*
 * Remove and return the first entry in the list or NULL if the list is empty.
 */
static inline list_t *list_pop(list_t *list) {
    list_t *foo = list->prev;
    if (foo == list)
        return NULL;
    LL1
}
#endif
```

請參照上方程式註解，補完對應程式碼。

==作答區==

LL1 = ?
* `(a)` return foo;
* `(b)` return foo->next;
* `(c)` return foo->prev;
* `(d)` list_remove(foo->prev); return foo;
* `(e)` list_remove(foo); return foo;
* `(f)` list_remove(foo->next); return foo->next;
* `(g)` list_remove(foo); return foo->next;
---
首先我們看看`list_pop`的要求
```clike
/*
 * Remove and return the first entry in the list or NULL if the list is empty.
 */
```
可知我們需要用到 `list_remove` 將 list 的 first entry 移除後並且回傳，若 list 為空就回傳 NULL

接著看 `list_remove` 的實作
```clike
/*
 * Remove the provided entry from whichever list it is currently in. This
 * assumes that the entry is in a list. You do not need to provide the list
 * because the lists are circular, so the list's pointers will automatically
 * be updated if the first or last entries are removed.
 */
 static inline void list_remove(list_t *entry) {
    list_t *prev = entry->prev;
    list_t *next = entry->next;
    prev->next = next;
    next->prev = prev;
}
 ```
 * prev 記錄 entry 的前一個 node
 ```clike
    list_t *prev = entry->prev;
 ```
 ![](https://i.imgur.com/IRbbWOR.jpg)
 
 ---
  * next 記錄 entry 的後一個 node
 ```clike
    list_t *next = entry->next;
 ```   
 ![](https://i.imgur.com/SEhNd5t.jpg)

---
* prev 的 next 指標指向 next
```clike
    prev->next = next;
```
![](https://i.imgur.com/peLAuI0.jpg)

---

```clike
    next->prev = prev;
````
* next 的 prev 指標指向 prev
![](https://i.imgur.com/wooGjJR.jpg)

* 最終狀態如下圖
![](https://i.imgur.com/9Me2JPT.jpg)

---
以上完成了 `list_remove` 的一次操作，可以注意到此方法僅改變前後指標， entry 並未被移除，其 prev 及 next 指標並未變動。

接下來回到 `list_pop` 中的第一行

```clike
    list_t *foo = list->prev;
```
* foo 記錄 list 的前一 node ，此 node 即為 list 的 first entry 
![](https://i.imgur.com/wgO8lMA.jpg)

---
因此我們用 `list_remove` 將 foo 移除，再將其回傳即可，如下圖
![](https://i.imgur.com/d0Hi20l.jpg)


故答案選擇 `(e)` list_remove(foo); return foo;

---


## 延伸問題:
### 1. 研讀 2019q3 Week11 的 cache-oblivious data structures 參考資料，記錄所見所聞:
---

[Maximize Cache Performance with this One Weird Trick: An Introduction to Cache-Oblivious Data Structures](https://rcoh.me/posts/cache-oblivious-datastructures/)

文章中提到，Postgres 利用固定大小的 blocks ,又稱為 "pages" 實作 B-Tree，其目的是為了與 OS 中的 page sizes 做對應，而 OS 又對應到硬體。

然而，上述做法實作於不同硬體時，必須針對其挑選一最適合的 page size 以達到較好的效能。

因此本篇的主題便是想設計不被 underlying cache size 影響的資料結構及演算法，如此我們不需自己調整 cache size，程式碼便會最佳化的利用 cache layers，擁有此性質的資料結構及演算法，我們稱之為 "cache-size oblivious"。

首先，我們來看一張 BST 的效能比較圖

![](https://rcoh.me/images/cache-oblivious-graph.png)

上圖中我們可以看到三種不同策略的 BST 走訪:
1. blue line : level by level 的走訪，又稱為 "bread first traversal".
2. orange line : (preorder) "depth first traversal".
3. green line : 利用 "recusive blocking" 法實作上述的 cache obivious 概念.

由上圖我們發現，在 elements in tree 達到 1600 萬的時候，"recursive blocking" 法的效率為另外兩種方法的近兩倍之外。

接下來我們探討如何實作 green line 的方法，以及其如何效能遠高於其他兩種方法的原因。

#### A new scheme for analyzing algorithms

一般分析演算法效能的 Big-$O$ notation，是假設讀取成本與記憶體中的 byte 成正比，然而真實世界的運作方式是以 block 為單位，即便你只想讀少量 bytes 的資料，還是得付出其所在整個 block 的成本，反之，若你想從同一個 block 讀取更多的 bytes，幾乎不用負擔任何額外成本。

因此 cache 利用率較好的演算法應該有以下特質:
When we read a block of data, we make use of every byte in that block.

然而使用一般演算法分析無法看出 "cache-oblivious" 的效益，因此我們介紹一種較接近真實世界運作 (work in blocks) 的演算法分析模型。 

探討這種不受 cache size 影響又能最佳化運作的演算法時，我們假設 memory 有兩個區塊，small fast layer 及 big slow layer，其擁有以下特性:

1. memory 只可以從 slow layer 移動到 fast layer，且單位為固定大小的 block, $B$
2. slow layer 的大小為無限大，而 fast layer 的大小為 $M$
3. 我們分析演算法時以 $M$ 為 cache 的單位，$B$ 為 block 的單位
4. 分析時一單位的工作量為從 slow memory 載入 a block 至 fast memory，其他皆視為極快速的工作，不納入考量

回到前面那張 BST 效能比較圖

![](https://rcoh.me/images/cache-oblivious-graph.png)

我們可以發現，在 Elements in Tree($N$)很小時，效能幾乎沒有差異，那是因為所有樹都在同一 block 內，讀取成本相差無幾，此外，blue and orange lines 中平坦的部分發生在特定的 internal cache sizes，而當$N$越大，cache-oblivious 的優勢就越大。

接著我們看看上圖三種方法的運作方式:

#### Blue line : By Level (Breadth)
![](https://rcoh.me/images/breadthfirst.svg)

* 其在 memory 內的觀點是以上圖的橘框為單位，elements 內的數字即為其在 array 內的位置
* 這種方法有個明顯的缺點，當 level 夠大時，每個 level 就代表一個 block，不但前面低階層的 block 利用率極低，如第一個 block 只存了 1 個 element ，且從樹根走訪至樹葉時，每經過一 level 就相當於讀取不同的 block，導致讀取成本高達 $\log_2N$

#### Orange line : Preorder (Depth First)
![](https://rcoh.me/images/depthfirst.svg)
* 這種方法在讀取至下一個 block 之前，會持續往下走訪，在上圖的橘框內作樹根至樹葉走訪時，都在同一個 block 內讀取，為最佳情況。
* 最靠右下的 block 只存放一個 element，若是做最右邊的走訪，讀取成本也是 $\log_2N$
* 此方法僅比 BFS 好一點

#### Green line : Recursive Block Approach
![](https://rcoh.me/images/van-layout.svg)

* 利用 divide and conquer strategy 實現 cache-oblivious data structures and algorithms
* 從樹高 $(logN)$ 一半處 split ，則上半部有 $2^{\log_2(N)/2}=\sqrt{N}$ 個 nodes，而其 child nodes 也有大約 $\sqrt{N}$ 個 nodes，如此遞迴 split，如上圖
* 每個綠框為一個 block，橘框為 superblock
* blocks 間以及 superblocks 間皆是連續的
* 再讀取下一個 block 前，隨著讀取的 block size 變大，能走訪的 level 也越大
例如 : 
讀取一 block of size $B$，可以走訪             $\log_2B$ 的 levels
樹有 $\log_2N$ 個 levels，則讀出的 blocks 數為
$\frac{\log_2N}{\log_2B}=\log_BN=F(N)$



### 2. 依據之前給定的 Linux 核心 linked list 實作，開發 cache-oblivious 的版本，並證實其效益
---

一般在設計 cache-oblivious 的 data structures and algorithms 時有三個常用策略:

1. van Emde Boas (vEB)
2. Weighted 平衡樹
3. Packed Memory Structure

而前面所利用的 Recursive Block Approach 便是採用 vEM 策略，如下圖

![](https://www.itread01.com/uploads/images/20161007/1475818713-3600.jpg)

而設計 cache-oblivious linked list 常用的策略為 Packed Memory Structure

在 [Cache-Oblivious Algorithms and Data Structures](http://erikdemaine.org/papers/BRICS2002/paper.pdf) 中提到:


The packed-memory structure maintains N elements consecutive
in memory with gaps of size $O(1)$, subject to insertions and deletions in $O(\log2N)$
amortized time and $O((\log_2N)/B)$ amortized

接著我們介紹在 [Data Structures Libraries](http://www.lsi.upc.edu/~lfrias/thesis/thesis-lfrias.pdf?fbclid=IwAR0r3a8tTkC2QDVxR6cyEWN41JhZiQwdnQht8IJBJz3cGjVhfrr2aEYGqT8) 中與  packed-memory structure 相關的三種資料結構，其概念是在 linked list 配置 array 儲存資料，並將整個結構稱為 bucket

![](https://i.imgur.com/HDqAKp6.png)

( a ) Contiguous: 在 linked list 內配置的 array 作連續性配置

* 優點：在同一個 bucket 內的 array 存取資料時，因為容易在同一個 memory block 內，存取速度會相較於原本的 linked list 快
* 缺點：和 array 一樣，插入或刪除資料時必須付出移動資料的成本

( b ) With gaps: bucket 內部 array 的元素間允許存在空隙
* 減少因插入刪除而移動資料的成本，較 Contiguous 好一些
* 每一個 element 必須耗費額外空間記錄此空間是否存資料

( c ) Linked: 內部元素間由 link 連接
* 須耗費額外空間儲存 link
* 插入或刪除時不須負擔額外移動資料的成本
* scalability 較佳







### 3. 實作 Skip list，並且比照之前的 unit test 提供對應的測試、效能分析，還有改善機制
---

==在 Linux 核心原始程式碼使用 skip list 的案例，介紹其原理，設計 Linux 核心模組的實驗==
* 需要涵蓋 kernel API 同步機制的運用
* 執行時期的分析 (提示: 可善用 eBPF)

# References
1. [Maximize Cache Performance with this One Weird Trick: An Introduction to Cache-Oblivious Data Structures](https://rcoh.me/posts/cache-oblivious-datastructures/#fnref:assum)
2. [關於算法，那些你不知道的事](https://www.itread01.com/articles/1475818714.html?fbclid=IwAR39mapd0cR55YSU4rgLAPqOjR0L6gBE9JxbTzdIq2H8sOF44kbiFs3xL9s)
3. [Cache-Oblivious Algorithms
and Data Structures] (http://erikdemaine.org/papers/BRICS2002/paper.pdf)
