cha*_*ang 4 data-structures libev
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看起来更稳定？
还是其他任何原因？
期望是对于相同的fd只有少数(通常是一个,几乎总是最多两个)io观察者(类似于信号).将列表链接放入观察器意味着不需要额外的分配,如果每个观察者使用阵列则需要.如果许多I/O观察者在同一个fd上处于活动状态,那么这种链表方法会更慢.
使用数组是因为插入和删除非常快(观察者存储数组索引).使用4字节索引还可以减少64位计算机上的内存需求(每个观察者12个字节,而不是双链表的16个字节),并且使用指针数组意味着所有指针在内存中彼此靠近,扫描时提高缓存效率,这对一些观察者来说是一种常见的操作.
缓存效率也是为什么在2堆上使用4堆的原因,以及将时间值复制到堆数据结构的原因,以避免必须在堆操作上访问观察程序内存.
儿童观察者实际上使用固定大小的哈希表,并且期望每个哈希桶的子观察者的数量很小,因此列表指针成为观察者数据结构的一部分.