April 1999
- In-Game Languages Eli Stevens {KiZurich}
- In-Game Languages Per Vognsen
- In-Game Languages Chris Gray
- In-Game Languages Caliban Tiresias Darklock
- In-Game Languages Eli Stevens {KiZurich}
- In-Game Languages Matthew D. Fuller
- In-Game Languages Mik Clarke
- In-Game Languages Michael Hohensee
- In-Game Languages Ben Greear
- In-Game Languages Michael Hohensee
- In-Game Languages Mik Clarke
- In-Game Languages Hans-Henrik Staerfeldt
- In-Game Languages David Bennett
- In-Game Languages Richard Woolcock
- In-Game Languages Hans-Henrik Staerfeldt
- In-Game Languages Caliban Tiresias Darklock
- In-Game Languages Hans-Henrik Staerfeldt
- In-Game Languages Andrew Ritchie
- In-Game Languages Matthew D. Fuller
- In-Game Languages adam@treyarch.com
- forward: consistency Ola Fosheim Grøstad
- Confined Gameworld Ling
- Confined Gameworld Caliban Tiresias Darklock
- Confined Gameworld Richard Woolcock
- Confined Gameworld Eli Stevens {KiZurich}
- Confined Gameworld The Wildman
- Confined Gameworld Koster, Raph
- User centered? Ola Fosheim Grøstad
- User centered? Caliban Tiresias Darklock
- User centered? Marc Bowden
- User centered? Adam Wiggins
- User centered? Richard Woolcock
- User centered? Benjamin D. Wiechel
- User centered? Koster, Raph
- target audience Matthew Mihaly
- target audience Caliban Tiresias Darklock
- target audience Marc Bowden
- Fw: Self-organizing worlds (was: Elder Games) Kylotan
- Fw: Self-organizing worlds (was: Elder Games) Matthew Mihaly
- ScryMUD 1.8.11 released. Ben Greear
- Mud driver architecture info B. Scott Boding
- Blending graphics with text u1391470
- Blending graphics with text Laurel Fan
- Blending graphics with text Kylotan
- Blending graphics with text Chris Gray
- Blending graphics with text J C Lawrence
- Blending graphics with text Caliban Tiresias Darklock
- Blending graphics with text Chris Gray
- Blending graphics with text Ola Fosheim Grøstad
- Blending graphics with text Hans-Henrik Staerfeldt
- Blending graphics with text Mik Clarke
- Blending graphics with text u1391470
- Blending graphics with text claw@kanga.nu
- Blending graphics with text Alex Stewart
- Blending graphics with text J C Lawrence
- Virtual machine design Shane King
- Virtual machine design Alex Stewart
- Virtual machine design Jo Dillon
- Virtual machine design Ben Greear
- Virtual machine design Niklas Elmqvist
- Virtual machine design Shane King
- Virtual machine design Ben Greear
- Virtual machine design claw@kanga.nu
- Virtual machine design Alex Stewart
- Virtual machine design Felix A. Croes
- Virtual machine design Eli Stevens {KiZurich}
- Virtual machine design Mik Clarke
- Virtual machine design Schubert, Damion
- Virtual machine design Ben Greear
- Virtual machine design Ben Greear
- Virtual machine design Felix A. Croes
- Virtual machine design Matthew Mihaly
- Virtual machine design Hans-Henrik Staerfeldt
- Virtual machine design claw@kanga.nu
- Virtual machine design Mik Clarke
- Virtual machine design Oliver Jowett
- Virtual machine design Chris Gray
- Virtual machine design claw@kanga.nu
- Virtual machine design Chris Gray
- Virtual machine design Ola Fosheim Grøstad
- Virtual machine design claw@kanga.nu
- Virtual machine design Petri Virkkula
- Virtual machine design Ben Greear
- Virtual machine design Chris Gray
- Virtual machine design Ola Fosheim Grøstad
- Virtual machine design Nathan F Yospe
- Virtual machine design Ola Fosheim Grøstad
- Virtual machine design Petri Virkkula
- Virtual machine design Jon A. Lambert
- Virtual machine design Koster, Raph
- Virtual machine design Jon A. Lambert
- Virtual machine design Chris Gray
- Rebooting (was: Virtual machine design) Eli Stevens {KiZurich}
- Game design highpoints (was Virtual machine design) claw@kanga.nu
- Sockets Quzah [softhome]
- Sockets Alex Stewart
- Sockets Quzah [softhome]
- Sockets Jo Dillon
- Sockets Jon A. Lambert
- Sockets Jon A. Lambert
- Sockets Chris Gray
- Sockets Jon A. Lambert
- Sockets Mark Gritter
Jon A. Lambert writes:
>
> The common select/poll loop for non-blocking sockets that processes
> incoming, exceptions, reads, writes, and other mud processes is not
> very efficient. Firstly setting up the parameters to select and checking
> the FD_SETs involved alone is probably higher overhead than threading.
> Secondly if the poll time is too short you end up burning processor
> cycles in the poll loop for no good reason. And if the time is to long
> you end up sleeping while your mud could be processing ripe events that
> are issued from other functions in the mud (assuming that not all your
> events are initiated immediately for user input). Yes, some good
> implementations attempt to dynamically adjust the polling time depending
> on how active the server is/was. Still there is enough overhead here
> to more than compensate for the overhead incurred through thread locks.
>
This is beginning to sound like one of those OS qualifying exam questions
I've been studying for... :) (And before I get any further, I feel
obligated to point out that the "right answer" is _highly_ dependent
on what sort of architecture and operating system you're using... and,
of course, on the exact nature of the workload.)
The above analysis of poll time only makes sense if there is always
extra work to be done. If I only have 5ms of "internal" event
processing for every 10ms of clock time, then getting it all done
right away (not waiting in select()) isn't going to buy me anything.
(If I _have_ I/O waiting, then select() will return right away and I'm
not wasting any time. If I _don't_ have I/O waiting, then it doesn't
matter whether I do extra processing at the beginning or end of my
window--- assuming the system's not overloaded, of course.)
The only way threads "win" in efficiency is if the overhead of
handling K threading events (with no "fixed", per-timeslice overhead)
is less than the overhead of handling K I/O events in a polling
mechanism.
(Apologies if the below seems hopelessly academic.)
Here's how I'd model it. There are two options for threading--- I/O
could take precedence over "internal" events (using thread priority),
or we could put them all at the same level.
Let K = average number of I/O events per "time slice" (= whatever
time scale internal events happen at)
N = number of I/O sources
L = number of lock operations in the internal thread
L'= average number of lock operations in an I/O handler
---Threading, equal priorities:--- In the best (for efficiency) case,
I/O is "queued" to run after the the internal thread, something like
this:
AAAAAAAAAABBCCDDIIII
A = internal thread, BCD = even threads, I = idle overhead is K
context switches, L + KL' lock operations
---Threading, unequal priorities:--- I/O events may interrupt the
internal thread at any time, but not each other.
AABBAAAACCAAAAIIDDII (for example) overhead is K to 2K
context switches, L + KL' lock operations
(I'm ignoring the problem of contention... this could add at most
2L extra context switches, I think, since in this simple model, only events
and the internal thread can wait on the same lock.)
---Polling---
I/O events are delayed until the next "select" call. This doesn't affect
average number, though, since essentially we get all event from the last
cycle delayed until the start of the next cycle.
BBCCDDAAAAAAAAAAIIII
1 system call, three loops (though FD_SET) of size N (one in the kernel)
Leaving aside the implementation-specific question of what the fixed
overhead is... polling overhead would seem to scale with the number of
_possible_ I/O events, while threading overhead increases with the
number of _actual_ I/O events. (Mapping an event to an fd is not
significantly easier than mapping an event to an fd and then looking at
which thread is waiting on it, so both types pay the same "per-connection"
overhead, if any, in the kernel. And scheduling typically only needs
consider the _active_ threads.)
For short time scales, I'd certainly prefer the latter--- *IF* the constants
on all the variable terms are small enough. So I guess I talked myself into
agreeing with Jon. :)
The natural question is whether select() could be made more efficient.
I think the answer is yes--- have fd's registered to a particular "ready
queue", have the kernel put them on that queue when they become readable,
and then have system calls to pull fd's off the ready queue one by one.
Mark Gritter
mark@erdos.stanford.edu - Sockets Mark Gritter
- Sockets Chris Gray
- Sockets Ola Fosheim Grøstad
- Sockets Ross Nicoll
- Sockets Mark Gritter
- Sockets Petri Virkkula
- Sockets Caliban Tiresias Darklock
- ScryMUD 1.8.13 snapshot released. Ben Greear
- Interview I did that may interest you Koster, Raph
- Censorship Greg Munt
- Censorship Ben Greear
- Censorship Matthew Mihaly
- Censorship Shawn Halpenny
- Censorship Darren Henderson
- Censorship Quzah [softhome]
- Censorship Hans-Henrik Staerfeldt
- Python B. Scott Boding
- Python Gaffney, Jeremy
- AW: Censorship Hofbauer Heinz
- AW: Censorship Matthew Mihaly
- AW: Censorship Damion Schubert
- Censorship, Virtual v Artificial Worlds, Python Greg Munt
- Censorship, Virtual v Artificial Worlds, Python Matthew Mihaly
- Censorship, Virtual v Artificial Worlds, Python Ben Greear
- Censorship, Virtual v Artificial Worlds, Python Matthew Mihaly
- Censorship, Virtual v Artificial Worlds, Python Matthew Mihaly
- Censorship, Virtual v Artificial Worlds, Python Ben Greear
- Censorship, Virtual v Artificial Worlds, Python Dan
- Censorship, Virtual v Artificial Worlds, Python Matthew Mihaly
- Censorship, Virtual v Artificial Worlds, Python Marian Griffith
- Censorship, Virtual v Artificial Worlds, Python Benjamin D. Wiechel
- Censorship & Its Impact On World Immersion Greg Munt
- Censorship & Its Impact On World Immersion Matthew Mihaly