C++ IOCP server container information

Question

I have been passing a few ideas around in my head about how to actually contain large amounts of connections using an IO type of architecture while maintaining KISS. Through examples on the web, it seems like most use a double/single linked list with CONTAINING_RECORD. And, as a newbie in IO servers ( though, improving every day), I too use a linked-list container for an IO architecture.

My question is, instead of using a single/double linked list for my connections, why cant I just build a large array and use CONTAINING_RECORD? Can I used STL vector? Would that work? Also, what are other type of containers that work best with a massive IO server.

Im in the process of re-writing the server architecture for my game server (after many revisions), and would like to head into the right direction this time around because id rather not have to rewrite it again in the near future.

Thank you for your time, and replies.

Edit: Currently my server architecture is (in a nutshell):

Main thread listening and accepting -> Pass over the socket into a container.
Worker threads(2-3) grab IO events for the container of sockets.
Worker threads Read/Write Data on that container.

Main thread and worker threads all use a linked-list. I want to get away from this.

Answer 1

Your "connection list" will probably have removals from any position, not just the end. For std::vector, removing elements in the middle is an O(N) operation, but for linked lists it can be O(1). (For single-linked lists this isn't trivial and may require an inconvenient API).

std::map may be an interesting choice as it offers both O(log N) finding and removing of elements.

Answer 2

As with all data structures, it depends very much on what you want to do with it.

In a previous job I spent most of my time working on a hugely multithreaded C++ server which, in its Windows incarnation, used IO Completion Ports (the Solaris backend used /dev/poll, which is not that dissimilar in several essentials). That one stored connection-related data structures in a map-like structure dating from before the STL, using the file descriptors as the key values. Thus whenever we got an event on a connection we could look up its related data structures by the descriptor the IO layer handed us. New connections were easy to handle - just add an entry to the dictionary - and closed connections could also be cleaned up quite trivially.

Naturally one has to be careful about cross-thread access to these structures and about operation ordering - since IO is inherently effectful, the ordering of operations is crucial. Fortunately IOCP won't give you another event on another thread for the same socket until you put the socket back into the CP, but the Solaris implementation had to also keep a structure linking file descriptors to worker threads in order to ensure that we only processed one event per socket at a time, and in strict order, and we also tried to inject subsequent events for a socket into the same thread to avoid having to potentially switch the socket's structures onto another processor which is a disaster for cache hit rates.

The basic summary though is that we found an appropriately-designed dictionary class to be incredibly useful for this sort of thing.