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就可以简单地将它用作索引，并且只需遍历需要调用的事件观察者的链表。所以它在射击事件中可以很快。