search

FXTi / iocp-wrapper

0 stars 0 forks source link

Implementation for Selector's internal queue #16

Open FXTi opened 5 years ago

FXTi commented 5 years ago

Basic idea is that Selector needs a efficient queue embedded in to suffice the changes of sock struct. The update of sock struct status is a async process, so after the API of Selector is called to change the sock registered on it, the sock still needs to changes its status. For example, if a sock is re-register with another interests, Selector should stop the polling operation first and then fire a new polling operation with new interests options. That requires tracking for updating sock struct. So queue is essential for this function.

Also, sock will need to be removed from the queue if sock doesn't need to be tracked. This should be efficient, and wepoll employ a linked list for that and achieve O(1) time for insert and remove operation on queue. At first, this project use VecDeque but soon realize to remove an element in any position of queue. But Rust's std implementation of LinkedList don't support remove or erase operation.

Now, I propose two solution:

  1. Use Hashmap to emulate a Linkedmap. If Selector generate a unique key for every sock struct and insert into embedded hashmap, and iterate them with keys(). We would achieve the same effect on theory.

  2. Use a no-std linked list that support cursor api. Cursor: https://github.com/rust-lang/rfcs/blob/master/text/2570-linked-list-cursors.md We can embedded a cursor in sock struct and that's equivalent implementation as wepoll, which is ideal in time complexity of operations. Like this: https://crates.io/crates/linked-list But this lib is written 4 years ago, and also lack concurrency support. Maybe I can fix that, then it's perfect for this project. I' ll give a try.

FXTi commented 5 years ago

Actually, removing an element is the motivation of this issue. This mainly serves epoll_close() function, which handles close jobs of IOCP port. Also, Selector::close for this repo.

piscisaureus commented 5 years ago

I don't rally have much of an opinion here. Let's focus on making something work, we can do optimizations later. So for that reason I would suggest to use HashSet or HashMap.

piscisaureus commented 5 years ago

Also, Hash table is not necessarily less efficient than a linked list; in many cases it could actually be more efficient. The reason wepoll uses a linked list is that it is easy to implement in C without external dependencies. Rust has HashSet/HashMap in its standard library so I see no objection to using them.

FXTi commented 5 years ago

Okay, I' ll use HashMap/HashSet first.