libev觀察者的數據結構

Question

Libev使用三種數據結構來存儲不同的觀察者。

堆：爲觀察員按時間排序，如ev_timer和ev_periodic。

鏈表：如ev_io，ev_signal，ev_child等

陣列：如ev_prepare，ev_check，ev_async等

有毫無疑問使用堆存儲定時器觀察者。但是選擇鏈表和數組的標準是什麼？

存儲ev_io觀察者的數據結構看起來有點複雜。它首先是一個以fd作爲其索引並且數組中的元素是ev_io watcher的鏈接列表的數組。如果使用鏈表作爲元素，爲數組分配空間更方便。這是原因嗎？

或者僅僅因爲插入或刪除操作ev_io更頻繁而且ev_prepare看起來更穩定？

還是其他原因？

Answer 1

期望的是，對於相同的fd（類似於信號），只有少數（通常是一個，並且幾乎總是至多兩個）io觀察者。將列表鏈接放入觀察程序意味着不需要額外的分配，如果每個觀察程序使用一個數組，則需要這樣做。如果很多I/O監視器在同一個fd上處於活動狀態，那麼這種鏈表方式會比較慢。

使用數組是因爲插入和移除非常快（觀察者存儲數組索引）。使用4字節索引還可以減少64位計算機上的內存需求（每個觀察者12個字節，而對於雙向鏈表，例如16個），並且使用指針數組意味着所有指針在內存中彼此靠近掃描時提高緩存效率，這對於一些觀察者來說是頻繁的操作。

緩存效率也是爲什麼4堆用於2堆的原因，也是爲什麼時間值被複制到堆數據結構的原因，以避免必須在堆操作上訪問觀察者內存。

子觀察者實際上使用固定大小的哈希表，並且期望每個哈希桶的子觀察者數量很少，因此列表指針成爲觀察者數據結構的一部分。

Answer 2

可能原因是在典型的情況下ev_io需要由fd查找。底層庫（epoll，select或其他）會提供fd，它有一些事件。然後，Libev就可以簡單地將它用作索引，並且只需遍歷需要調用的事件觀察者的鏈表。所以它在射擊事件中可以很快。