의 데이터 구조

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

기대는 몇 있다는 것입니다 (일반적으로 하나, 그리고 거의 항상 최대 2 개) (유사 신호) 같은 FD에 대한 IO 전문가. 감시자에 목록 링크를 두는 것은 감시자 당 배열이 사용 된 경우에 요구되는 것처럼 여분의 할당이 필요 없다는 것을 의미합니다. 많은 I/O 관찰자가 동일한 fd에서 활성화 된 경우이 연결된 목록 접근 방식은 느려질 것입니다. 삽입 및 제거가 매우 빠르고 때문에

어레이 (워처는 어레이 인덱스를 저장한다)이 사용된다. 4 바이트 인덱스를 사용하면 64 비트 시스템의 메모리 요구 사항이 줄어 듭니다 (이중 연결 목록의 경우 예를 들어 16 개가 아닌 관찰자 당 12 바이트). 포인터 배열을 사용하면 모든 포인터가 서로 가까이 메모리에 있음을 의미합니다. 스캐닝 할 때 캐시 효율성을 향상시킵니다. 이는 일부 전문가의 경우 자주 수행됩니다.

캐시 효율성은 또한 2 힙보다 4 힙이 사용되는 이유와 힙 데이터 구조에 시간 값이 복사되는 이유 때문에 힙 작업시 감시자 메모리에 액세스하지 않아도됩니다.

자식 관찰자는 실제로 고정 크기 해시 테이블을 사용하며, 해시 버킷 당 자식 관찰자의 수가 작기 때문에 목록 포인터가 관찰자 데이터 구조의 일부가됩니다.

Answer 2

아마도 일반적인 시나리오에서는 ev_io가 fd로 조회해야 할 필요가있을 것입니다. 기본 라이브러리 (epoll, select 또는 기타)는 fd를 제공하고 이벤트는 발생합니다. Libev는이를 단순히 인덱스로 사용하고 호출해야하는 이벤트 감시자의 링크 된 목록을 반복합니다. 따라서 발사 이벤트가 빠를 수 있습니다.