[MUD-Dev] Re: TECH: Distributed Muds

Jon Lambert tychomud at ix.netcom.com
Wed May 2 20:12:03 New Zealand Standard Time 2001

Caliban Tiresias Darklock wrote:
> On Sun, 29 Apr 2001 13:47:06 -0400, "Derek Snider" <derek at idirect.com>
> wrote:

>> The fd_sets are bitstrings.  With 1024 file descriptors (for
>> example) that is 128 bytes per set.  To clear 384 bytes, and to
>> check the bits on 384 bytes is hardly CPU intensive.

> True, but not under Windows. The Winsock concern is that an FD_SET
> is actually an array of structures, which is a GREAT deal larger
> than a bit vector.

No it's an array of unsigned ints.  There are other differences.
Under Unix the subscript into the fdset is the socket id, and the
value is a bit flag.  Under Windows the value is the socket id and the
subcript is dependent on the number of sockets you are checking.  That
single fdcount is stored with the fdset.  Don't underestimate the
flexibility of that.  That means FD_ZERO does not iterate through the
array, it sets fdcount to zero.  It also means there is no subscript
bit calculation when one does iterate through the array.  It also
means one can short circuit the array traversal using fdcount as the
upper bounds.  Which in turn means one can easily partition fdsets of
any arbitrary size for use in multi-threading.

Damn you got me defending windows select() as a better implementation.

But let me requote from that article by Gooch...

  "Another solution (which would also benefit from the kernel
  optimisation discussed above) is for the application to divide the
  FD array into a number of smaller FD arrays, say 10. You then create
  10 threads, each of which has a polling loop using its smaller FD
  array. So each FD array is now 100 entries long. While this doesn't
  change the total number of FDs that must be scanned, it does change
  when they have to be scanned. Since most FDs are inactive, not all
  the threads will be woken up.  Too see how this works, consider the
  example where, at any time (say during a single timeslice of 10 ms),
  only 5 FDs are active. Assuming these FDs are randomly, uniformly
  distributed, at most 5 threads will need to be woken up. These
  threads then process the activity and go back to the start of their
  polling loops. Where we win is that only 5 threads had to go back
  and call select(2) or poll(2).  Since they each have 100 entry FD
  arrays, the kernel only has to scan 500 FDs. This has halved the
  amount of scanning required. The scanning load has gone from 30% to
  15% by this simple change.  If you were to instead use 100 threads,
  you would still only have at most 5 threads woken up for activity,
  and hence the total number of FDs scanned this timeslice would be
  50. This takes down the scanning load to 0.15%, which is

  "There is one thing to watch out for here: if you use select(2) in
  your polling loop, be aware that the size of your FD array is equal
  to the value of your largest FD. This is because select(2) uses a
  bitmask for its FD array. This means one of your threads will want
  to poll FDs 991 to 1000.  Unfortunately, your FD array is still 1000
  long. What's worse, the kernel still has to do a minimal scan for
  all those 1000 FDs. The solution to this is to use poll(2) instead,
  where you only have to pass as many FDs as you want to poll, and the
  kernel scans only those."

Note because the windows select() allows you to really partition
fdsets into smaller arrays, the 2nd paragraph above is _not_ a gotcha.

Nevertheless the I/O completion ports is still a better alternative.

  "Unfortunately, I/O readiness queues are not POSIX. They're not even

ObOfftopic: Gee why not call it FOOSIX and make it an optional kernel

> An excellent example of where Winsock programming has a concern that
> just plain isn't a problem under UNIX.

No the _traditional_ single-threaded select() design on Windows
performs as well as that on Unix.  The problem is neither are scalable
and since there are at least 2 very good alternatives there's no
reason to use it unless you are porting Unix code or writing a server
to support a small number of users.  Yes it is considered lame on
Windows just for that reason.

> generally assume you will never have more than 64 sockets in an
> FD_SET. ;)

What do BSD and Linux assume to be the FDSETSIZE to be?  Both require
you to #define FDSETSIZE should you want something else.

--* Jon A. Lambert - TychoMUD        Email:jlsysinc at ix.netcom.com *--
--* Mud Server Developer's Page <http://tychomud.home.netcom.com> *--
--* If I had known it was harmless, I would have killed it myself.*--

MUD-Dev mailing list
MUD-Dev at kanga.nu

More information about the MUD-Dev mailing list