Using fibers to simplify enumerators, part 3: Having it both ways

re: Using fibers to simplify enumerators, part 3: Having it both ways

Anthony Wieser — Fri, 31 Dec 2004 15:47:00 GMT

Thanks for this Raymond.

I've always wanted to see a real use of fibers shown somewhere. Do newer versions of windows make much use of them?

The history of fibers...

Memet — Fri, 31 Dec 2004 16:10:00 GMT

Thanks Raymond,

btw, did the Windows team introduce fibers for any reason? (e.g. MS SQL?) Since from previous conversations, I get the impression that only Win32 has such an explicitly defined Fiber API, and also because Fibers are a relatively obscure thing that most people probably wouldn't ask for, let alone know about.

re: Using fibers to simplify enumerators, part 3: Having it both ways

Grant — Fri, 31 Dec 2004 17:06:00 GMT

Just FYI, C# iterators (new in v2.0) allow this same feat without using fibers. Instead the compiler transforms the producers' preferred code into the consumers' perferred interface.

re: Using fibers to simplify enumerators, part 3: Having it both ways

Joe Game Developer — Fri, 31 Dec 2004 17:11:00 GMT

Very cool example!

As a point of information, some games use fibers. You give each object in the game world its own fiber.

You could use threads (or even processes) instead, but then you have much more overhead because of having to lock to avoid potential race conditions.

Games

Sven G. Ali — Fri, 31 Dec 2004 17:34:00 GMT

Yes, this is incredibly cool.

When I started reading this series I was immediately reminded of my own struggles creating a game engine some time ago.

In a perfect world each game entity would be on its own thread running its own script. The renderer would be on another thread, getting samples of the game world as necessary.

The problem of course is that threads are expensive, locks are required, and the thread scheduler doesn't provide enough control.

The only way to make it work was, as Raymond says, to make life difficult for one side or the other. In my case, and I believe in most game engines, life was made easy for the renderer.

re: Using fibers to simplify enumerators, part 3: Having it both ways

Michael Grier [MSFT] — Fri, 31 Dec 2004 18:39:00 GMT

Fibers are definitely designed to help applications which really understand their data sets, their I/O patterns and don't have a big plug-in/extensibility mechanism. At some point large applications like this become CPU bound since they're actually used by enterprises who do insanely expensive things like buy large storage arrays that let the number of concurrent I/Os scale as far as the CPU and operating system can push them.

So then they need to start optimizing CPU usage and they can't afford the statistical goodness of things like thread scheduling and I/O completion ports.

I bet you can figure out which applications really take advantage of fibers and therefore which bugs around using fibers have gotten fixed. They're enterprise applications which do a lot of I/O but are run by large enough physical systems that the real limiting factor is CPU use.

Caveat emptor. To solve the easy enumerators problem you really want to have smaller things like closures/continuations without having to keep the entire stack around. This is hard without compiler support and even then managing the lifetime of the storage that the closure references is hard without GC. This is effectively how iterators/"yield" works in C#.

re: Using fibers to simplify enumerators, part 3: Having it both ways

RJ — Fri, 31 Dec 2004 19:00:00 GMT

It seems that SwitchToFiber would invalidate all CPU predictions and stall the pipeline. If that is true, another warning for CPU bound apps would be to not call it in a tight loop.

re: Using fibers to simplify enumerators, part 3: Having it both ways

Ben Cooke — Fri, 31 Dec 2004 19:24:00 GMT

I co-wrote a simple game engine some time ago which used coroutines, which fibers seem to be an implementation of, to allow objects to independently operate.

In my case, each "object" in the game was able to register one or more coroutines which would be resumed each frame. Each time the coroutine was resumed the current tick count was passed in so that the coroutine would know how much to adjust its associated object by, depending on what it was supposed to be doing.

This wasn't done with Win32 Fibers, though. Indeed, Raymond's series here was the first I've ever heard of them. My co-author had implemented a simple scripting system, so my coroutine implementation just played with the stack kept inside the script interpreter. The coroutines didn't exist outside the script context.

The nice thing about coroutines vs. threads is that it's up to each routine when it yields, so things like locking become less important. If a coroutine is going to do something unsafe, it must just make sure it leaves everything in a sensible state before yeilding.

In practice, most applications other than "real-time" games are better off with threads, of course.

re: Using fibers to simplify enumerators, part 3: Having it both ways

Rob Earhart — Fri, 31 Dec 2004 21:00:00 GMT

One nitpick: ConvertThreadToFiber() should fail with GetLastError() == ERROR_ALREADY_FIBER if the thread's already a fiber. So try it; if it fails for that reason, keep going, but skip the call to ConvertFiberToThread() at the end, and you can work with components which called yours on a fiber.

In Longhorn, there's also IsThreadAFiber(), which should always work.

GetCurrentFiber() and GetFiberData() don't return garbage; they just don't return what you're expecting (the field in the TEB is overloaded with OS2 information). If you file a bug against me, I'll look into fixing them.

re: Using fibers to simplify enumerators, part 3: Having it both ways

Raymond Chen — Fri, 31 Dec 2004 21:14:00 GMT

ERROR_ALREADY_FIBER is returned only on Windows Server 2003. For Windows 98, 2000, and XP, converting a thread to a fiber twice results in random behavior.

re: Using fibers to simplify enumerators, part 3: Having it both ways

Pavel Lebedinsky — Fri, 31 Dec 2004 21:34:00 GMT

Given all the dire warnings about fibers, has anyone actually measured how much slower the equivalent version using threads would be?

I suspect that switching back and forth between two fiber stacks for each produced element is also not very good for performance.

If threads are used instead then for large collections you could batch the elements by putting a producer-consumer queue between the enumerator thread and the main thread. Then the overhead of thread switching will be amortized over a large number of elements, and you will not have to worry about fiber-safety.

re: Using fibers to simplify enumerators, part 3: Having it both ways

Bug Hunter — Fri, 31 Dec 2004 21:37:00 GMT

"ERROR_ALREADY_FIBER is returned only on Windows Server 2003. For Windows 98, 2000, and XP, converting a thread to a fiber twice results in random behavior."

How did this ever get designed this way?!?

re: Using fibers to simplify enumerators, part 3: Having it both ways

Raymond Chen — Fri, 31 Dec 2004 21:44:00 GMT

Because fibers are a brain-the-size-of-a-planet feature. You are expected to have already worked through all the difficulties yourself - like deciding who will do the thread-to-fiber conversion. In the same way you don't get an error if you free memory twice; you're expected simply not to do that in the first place.

Remember, the ENTIRE PROGRAM must coordinate fiber management - see all the dire warnings - if you're coordinating fibers on a program-wide basis surely you can decide who will be responsible for the thread-to-fiber conversion; that's the least of your problems.

re: Using fibers to simplify enumerators, part 3: Having it both ways

M Knight — Sat, 01 Jan 2005 09:49:00 GMT

Pavel Lebedinsky, switching between fibers is *cheap* compared to switching between threads.

A switch between fibers involves; saving the registers state, and then loading the new register state from the new fiber. This will also switch the stack too. You are looking at a few dozen bytes which need to be moved about.

With a thread; it involves a trip to kernel land, saving the registers state, loading the new registers state, and then a trip back to user-land.

The timesaver is the removal of the trips between user-mode and kernel-mode todo a context switch.

re: Using fibers to simplify enumerators, part 3: Having it both ways

Michael Grier [MSFT] — Sat, 01 Jan 2005 18:11:00 GMT

If memory serves, SQL Server gets something like a 5-10% boost when running in fiber mode. However I believe that it then can't use XSPs (the DLL-based plug-in mechanism) because, in general, code can't deal with fibers / shifting across threads. (This is why it's not the default; it does break some code that may be running in-process with SQL.)

Maybe they've done the work so that XSP invocations are remoted to run on threads that aren't fibrous; it's been too many years since I've paid deep attention to SQL server, so please research the details here (XSPs) yourself.

Re: cost:

I may be wrong here, but I believe that a context switch forces reloading the PCR (on x86) which is a very expensive operation for the CPU. Fiber switches switch a lot less state, don't go into kernel mode and don't change the PCR.

Mike

re: Using fibers to simplify enumerators, part 3: Having it both ways

Pavel Lebedinsky — Sun, 02 Jan 2005 00:17:00 GMT

> switching between fibers is *cheap* compared to switching between threads.

My point was that any context switching (thread or fiber) has additional costs because of poor locality of reference. These costs may dominate everything else (things like saving the registers, transition to KM and back, running the scheduler code etc). If that's the case then using fibers doesn't really buy you anything, except all the bugs you're going to discover because most code has never been tested with fibers and probably is not fiber-safe.

Now I'm not an expert on this to be able to say one way or another. But when I googled for ["context switch" "cache miss" cost] the first hit was this article:

The Effect of Context Switches on Cache Performance
http://www.eecs.harvard.edu/cs245/papers/Shieyuan.html

They say that at least in some cases, cache-performance dominates the cost of a context switch. Note that this was back in 1991, and by all accounts the situation has only become worse in recent years because CPU speeds grew much faster than memory speeds.

So it seems to me that unless you've actually *measured* the performance of both solutions and found fibers significantly faster, you're better off staying with threads.

re: Using fibers to simplify enumerators, part 3: Having it both ways

Ryan Myers [MSFT] — Sun, 02 Jan 2005 19:52:00 GMT

Any kind of context switch -- whether an explicit one made in fibers, or a true thread change, is painful in terms of cache swap. It's still true, though, that SwitchToFiber() is cheaper than a normal thread context switch, as fiber switching can be done almost entirely in non-priviledged (usermode) code.

And yes, it is still true today that context switches kill the cache. Those of us in the performance team have been on several crusades to reduce the number of switches needed in an "idle" system over the last few years -- pushing for fewer services, fewer ISRs/DPCs, etc. In my particular case, my rallying cry has been high-definition video playback; we've found that having a high number of ISRs/DPCs per second will absolutely sink decoding, even if every single interrupt executes quickly, because they kill the cache. (This is in addition, of course, to the problem of ISRs/DPCs that take too long and lock up the CPU for extended periods of time, such as long NDIS chains or non-conformant ATAPI drives.)

re: Using fibers to simplify enumerators, part 3: Having it both ways

Frank — Tue, 04 Jan 2005 00:18:00 GMT

Just a thought - couldn't you do something similar with "good-old" POSIX setjmp()/longjmp()? Not sure though, I guess it lacks the 'double stack'.

re: Using fibers to simplify enumerators, part 3: Having it both ways

Michael Grier [MSFT] — Tue, 04 Jan 2005 19:06:00 GMT

Yes, a fiber is very similar to a jmp_buf. The thing is that setjmp/longjmp explicitly only are enabled for jumping up the stack, not across between stacks. There's no defined way to allocate a new stack, get code running on it and save its context into a jmp_buf in standard C etc.

Note also that since a jmp_buf is a struct, its size can't really vary and depends on the version of the C runtime (regardless of platform) that you are built with. Fibers are provided by the OS on windows and therefore if someone discovers that some critical piece of state wasn't captured/switched, it can be added.

Unfortunately those additions do tend to break apps who were depending on that piece of context not being switched. Luckily most people have heeded the warning and aren't using fibers except for people who think they already understand their per-fiber context pretty well.

re: Using fibers to simplify enumerators, part 3: Having it both ways

lukaszg — Wed, 05 Jan 2005 21:48:00 GMT

>>
(It's amazing how many people ask questions without taking even the slightest steps towards figuring out the answer themselves. Try writing a test program.)
<<

Isn't that exactly how people come to rely on undocumented behavior? Just because a test program behaves in a certain way on your machine doesn't mean it will on others. Answers to questions like this should be in the docs (don't know if this one is, just making a general point). Of course, sometimes writing a test program is the only way, but it shouldn't be the first one tried.

re: Using fibers to simplify enumerators, part 3: Having it both ways

Raymond Chen — Wed, 05 Jan 2005 22:03:00 GMT

The test program is *one step* towards figuring out the answer. A test program can't tell you that you're right, but it can tell you that you're wrong.

Why does Win32 even have Fibers?

Larry Osterman's WebLog — Thu, 06 Jan 2005 02:58:00 GMT

Partially Debuggable CoRoutines

Wizzy's World — Fri, 21 Jan 2005 02:33:00 GMT

A while back there was an article in MSDN magazine about wrapping up the unmaged fibers API to implement...

C# iterators are not as powerful

Kannan Goundan — Thu, 27 Jan 2005 23:10:00 GMT

While C# iterators cover a good chunk of what you'd normally want to do, they don't use separate stacks and so you can't do everything fibres can. The main restriction is that all your "yield"s have to be in the top function instance.

IEnumerator<X> InOrder(Tree<X> t) {
if (t != null) {
InOrder(t.left);
yield return t.value;
InOrder(t.right);
}
}

At the least, you'd have to put a for loop around the recursive calls and "re-yield" the values to the top. This is pretty inefficient.

Full continuation support would fix this. Unfortunately (AFAIK), adding continuation support causes a significant performance hit (even if you don't use them).

Coroutines in C# and Delphi: Part 1

Joe White's Blog — Wed, 09 Feb 2005 02:43:00 GMT

Coroutines

Joe White's Blog — Fri, 12 Jan 2007 06:19:55 GMT

Coroutines

Joe White's Blog — Fri, 12 Jan 2007 06:21:27 GMT

When does it make sense to use Win32 Fibers?

Eric Eilebrecht's blog — Sun, 18 May 2008 18:29:49 GMT

This has been discussed fairly frequently on the Web. Chris Brumme discusses this here: http://blogs.msdn.com/cbrumme/archive/2003/04/15/51351.aspx