data-structures - libev观察者的数据结构

Question

libev 使用三种数据结构来存储不同的观察者。

堆:对于按时间排序的观察者，例如 ev_timer和 ev_periodic .

链表:如 ev_io , ev_signal , ev_child等等。

数组:如 ev_prepare , ev_check , ev_async等等。

毫无疑问，使用堆来存储计时器观察者。但是选择链表和数组的标准是什么？

存储 ev_io watchers 的数据结构似乎有点复杂。首先是一个带有 fd 的数组作为它的索引，数组中的元素是 ev_io watcher 的链表.如果使用链表作为元素，为数组分配空间更方便。是这个原因吗？

或者仅仅因为ev_io的插入或删除操作更频繁和 ev_prepare似乎更稳定？

还是其他什么原因？

Answer 1

期望是只有少数(通常是一个，几乎总是最多两个)io 观察者用于相同的 fd(信号类似)。将列表链接放入观察者意味着不需要额外的分配，如果每个观察者使用一个数组就会需要。如果许多 I/O 观察者在同一个 fd 上处于事件状态，那么这种链表方法会更慢。

使用数组是因为插入和删除非常快(观察者存储数组索引)。使用 4 字节索引还减少了 64 位机器上的内存需求(每个观察者 12 个字节，而不是例如双向链表的 16 个字节)，并且使用指针数组意味着所有指针在内存中彼此靠近，这提高扫描时的缓存效率，这是一些观察者的频繁操作。

缓存效率也是为什么使用 4 堆而不是 2 堆的原因，也是将时间值复制到堆数据结构的原因，以避免在堆操作中访问观察者内存。

Child watchers 实际上使用了一个固定大小的哈希表，并且再次期望每个哈希桶的 child watchers 数量很少，因此列表指针成为 watcher 数据结构的一部分。