Libev observer data structure

Question

Libev uses three data structures to store different observers.

Heap: for time ev_timer like ev_timer and ev_periodic .

Linked List: e.g. ev_io , ev_signal , ev_child , etc.

Array: e.g. ev_prepare , ev_check , ev_async , etc.

There is no doubt that heap is used to store the timer. But what are the criteria for choosing a linked list and array?

The data structure in which ev_io watchers are stored seems a bit complicated. First, it is an array that has fd as its index, and the element in the array is a linked ev_io watcher list. It is more convenient to allocate space for an array if you use a linked list as an element. This is the reason?

Or just because of the insert or delete ev_io more often, and ev_prepare looks more stable?

Or any other reasons?

Answer 1

It is expected that there are only a few (usually one and almost always no more than two) io observers for the same fd (similarly for signals). Placing the list links in the observer means that no additional allocation is required, as would be necessary if the array were used for each observer. If many I / O watchers were active on the same fd, this linked list approach would be slower.

Arrays are used because insertion and deletion are very fast (the observer stores the index of the array). Using a 4-byte index also reduces memory requirements on 64-bit machines (12 bytes per observer, unlike, for example, 16 for a doubly linked list), and using an array of pointers means that all pointers are next to each other in memory , which increases the efficiency of caching during scanning, which is a frequent action for some observers.

Cache efficiency is also the reason that the 4-heap is used in the 2-heap and the reason that time values ​​are copied to the heap data structure in order to avoid the need for access to the observer's memory when working with the heap.

Child observers actually use a hash table of a fixed size, and again the expectation is that the number of observers for the hash bucket is small, so list pointers become part of the observer data structure.

Answer 2

Probably the reason is that in a typical ev_io script you need to look for fd. The base library (epoll, select or something else) will provide fd that has some kind of event. Then Libev simply used it as an index and simply iterated over the linked list of observers of events to be called. So it can be fast in shooting events.