int64.org

Microsoft, Page 1

Asynchronous page faults

With I/O, we’ve got some choices:

1. Syn­chro­nous, copy­ing from OS cache ( fread). This is the sim­plest form of I/O, but isn’t very scal­able.
2. Syn­chro­nous, read­ing di­rectly from OS cache (mem­ory map­ping). This is wicked fast and ef­fi­cient once mem­ory is filled, but aside from some cases with read-​ahead, your threads will still block with page faults.
3. Asyn­chro­nous, copy­ing from OS cache ( ReadFile). Much more scal­able than fread, but each read still in­volves du­pli­cat­ing data from the OS cache into your buffer. Fine if you’re read­ing some data only to mod­ify the buffer in place, but still not very great when you’re treat­ing it as read only (such as to send over a socket).
4. Asyn­chro­nous, main­tain­ing your own cache ( FILE_FLAG_NO_BUFFERING). More scal­able still than Read­File, but you need to do your own caching and it’s not shared with other processes.

Note that there’s one im­por­tant choice miss­ing: mem­ory map­ping with asyn­chro­nous page faults. As far as I know there are no op­er­at­ing sys­tems that ac­tu­ally offer this—it’s kind of a dream fea­ture of mine. There are two APIs that will help sup­port this:

HANDLE CreateMemoryManager();
BOOL MakeResident(HANDLE, LPVOID, SIZE_T, LPOVERLAPPED);

CreateMemoryManager opens a han­dle to the Win­dows mem­ory man­ager, and MakeResident will fill the pages you spec­ify (re­turn­ing true for syn­chro­nous com­ple­tion, false for error/async like every­thing else). The best of both worlds: fast, easy ac­cess through mem­ory, a full asyn­chro­nous work­flow, and shared cache usage. This would be es­pe­cially use­ful on mod­ern CPUs that offer gi­gan­tic ad­dress spaces.

The mem­ory man­ager al­ready has sim­i­lar func­tion­al­ity in there some­where, so it might not be dif­fi­cult to pull into user-​mode. Just an ed­u­cated guess. Maybe it’d be ter­ri­bly dif­fi­cult. Dream fea­ture!

Is C# the Boost of C-family languages?

For all the cons of giv­ing a sin­gle en­tity con­trol over C#, one pro is that it gives the lan­guage an un­matched agility to try new things in the C fam­ily of lan­guages. LINQ—both its lan­guage in­te­gra­tion and its back­ing APIs—is an in­cred­i­bly pow­er­ful tool for query­ing and trans­form­ing data with very con­cise code. I re­ally can’t ex­press how much I’ve come to love it.

The new async sup­port an­nounced at PDC10 is ba­si­cally the holy grail of async cod­ing, let­ting you focus on what your task is and not how you’re going to im­ple­ment a com­plex async code path for it. It’s an old idea that many async coders have come up with, but, as far as I know, has never been suc­cess­fully im­ple­mented sim­ply be­cause it re­quired too much lan­guage sup­port.

The lack of peer re­view and stan­dards com­mit­tee for .​NET shows—there’s a pretty high rate of turnover as Mi­crosoft tries to iron down the right way to tackle prob­lems, and it re­sults in a very large li­brary with lots of re­dun­dant func­tion­al­ity. As much as this might hurt .​NET, I’m start­ing to view C# as a sort of Boost for the C lan­guage fam­ily. Some great ideas are get­ting real-​world use, and if other lan­guages even­tu­ally feel the need to get some­thing sim­i­lar, they will have a bounty of ex­pe­ri­ence to pull from.

C++, at least, is a ter­ri­fy­ingly com­plex lan­guage. Get­ting new fea­tures into it is an up­hill bat­tle, even when they ad­dress a prob­lem that every­one is frus­trated with. Get­ting com­plex new fea­tures like these into it would be a very long process, with a lot of ar­gu­ing and years of delay. Any extra in­cu­ba­tion time we can give them is a plus.

Come meet up at The Underground

Live around LA or here for the PDC? Like last year, Mi­crosoft is host­ing a party. This year it's at the Conga Room at LA Live. It's free, so if you're in the area make sure you RSVP and come grab some drinks!

ClearType in Windows 7

One of my big pet peeves with ClearType prior to Win­dows 7 was that it only anti-aliased hor­i­zon­tally with sub-pix­els. This is great for small fonts, be­cause at such a small scale tra­di­tional anti-alias­ing has a smudg­ing ef­fect, re­duc­ing clar­ity and in­creas­ing the font’s weight. For large fonts how­ever, it in­tro­duces some very no­tice­able alias­ing on curves, as best seen in the ‘6′ and ‘g’ here:

You’ve prob­a­bly no­ticed this on web­sites every­where, but have come to ac­cept it. De­pend­ing on your browser and op­er­at­ing sys­tem, you can prob­a­bly see it in the title here. This prob­lem is solved in Win­dows 7 with the in­tro­duc­tion of Di­rectWrite, which com­bines ClearType’s hor­i­zon­tal anti-alias­ing with reg­u­lar ver­ti­cal anti-alias­ing when using large font sizes:

Of course, Di­rectWrite af­fects more than just Latin char­ac­ters. Any glyphs with very slight an­gles will see a huge ben­e­fit, such as hi­ra­gana:

Un­for­tu­nately, this isn’t a free up­grade. For what­ever rea­son, Mi­crosoft didn’t make all the old GDI func­tions use Di­rectWrite’s im­prove­ments so to make use of this, all your old GDI and Draw­Text code will need to be up­graded to use Di­rec­t2D and Di­rectWrite di­rectly, so an old WM_PAINT pro­ce­dure like this:

PAINTSTRUCT ps;
HDC hdc = BeginPaint(hwnd, &ps);

HFONT font = CreateFont(-96, 0, 0, 0, FW_NORMAL,
                        0, 0, 0, 0, 0, 0, 0, 0, L"Calibri");

SelectObject(hdc, (HGDIOBJ)font);

RECT rc;
GetClientRect(hwnd, &rc);

DrawText(hdc, L"Int64.org", 9, &rc,
         DT_SINGLELINE | DT_CENTER | DT_VCENTER);

EndPaint(hwnd, &ps);

Will turn into this:

ID2D1Factory *d2df;

D2D1CreateFactory(D2D1_FACTORY_TYPE_SINGLE_THREADED,
   __uuidof(ID2D1Factory), 0, (void**)&d2df);

IDWriteFactory *dwf;

DWriteCreateFactory(DWRITE_FACTORY_TYPE_SHARED,
   __uuidof(IDWriteFactory), (IUnknown**)&dwf);

IDWriteTextFormat *dwfmt;

dwf->CreateTextFormat(L"Calibri", 0, DWRITE_FONT_WEIGHT_REGULAR,
   DWRITE_FONT_STYLE_NORMAL, DWRITE_FONT_STRETCH_NORMAL,
   96.0f, L"en-us", &dwfmt);

dwfmt->SetTextAlignment(DWRITE_TEXT_ALIGNMENT_CENTER);
dwfmt->SetParagraphAlignment(DWRITE_PARAGRAPH_ALIGNMENT_CENTER);

RECT rc;
GetClientRect(hwnd, &rc);

D2D1_SIZE_U size = D2D1::SizeU(rc.right - rc.left,
                               rc.bottom - rc.top);

ID2D1HwndRenderTarget *d2drt;

d2df->CreateHwndRenderTarget(D2D1::RenderTargetProperties(),
   D2D1::HwndRenderTargetProperties(hwnd, size), &d2drt);

ID2D1SolidColorBrush *d2db;

d2drt->CreateSolidColorBrush(D2D1::ColorF(D2D1::ColorF::Black),
   &d2db);

D2D1_SIZE_F layoutSize = d2drt->GetSize();
D2D1_RECT_F layoutRect = D2D1::RectF(0.0, 0.0,
   layoutSize.width, layoutSize.height);

d2drt->BeginDraw();
d2drt->DrawText(L"Int64.org", 9, dwfmt, layoutRect, d2db);
d2drt->EndDraw();

This is no small change, and con­sid­er­ing this API won’t work on any­thing but Vista and Win­dows 7, you’ll be cut­ting out a lot of users if you spe­cial­ize for it. While you could prob­a­bly make a clever Draw­Text wrap­per, Di­rec­t2D and Di­rectWrite are re­ally set up to get you the most ben­e­fit if you’re all in. Hope­fully gen­eral li­braries like Pango and Cairo will get up­dated back­ends for it.

Di­rectWrite has other ben­e­fits too, like sub-pixel ren­der­ing. When you ren­der text in GDI, glyphs will al­ways get snapped to pix­els. If you have two let­ters side by side, it will choose to al­ways start the next let­ter 1 or 2 pix­els away from the last—but what if the cur­rent font size says it should ac­tu­ally be a 1.5 pixel dis­tance? In GDI, this will be rounded to 1 or 2. This is also no­tice­able with kern­ing, which tries to re­move ex­ces­sive space be­tween spe­cific glyphs such as “Vo”. Be­cause of this, most of the text you see in GDI is very slightly warped. It’s much more ap­par­ent when an­i­mat­ing, where it causes the text to have a wob­bling ef­fect as it con­stantly snaps from one pixel to the next in­stead of smoothly tran­si­tion­ing be­tween the two.

Di­rectWrite’s sub-pixel ren­der­ing helps to al­le­vi­ate this by doing ex­actly that: glyphs can now start ren­der­ing at that 1.5 pixel dis­tance, or any other point in be­tween. Here you can see the dif­fer­ing space be­tween the ‘V’ and ‘o’, as well as a slight dif­fer­ence be­tween the ‘o’s with Di­rectWrite on the right side, be­cause they are being ren­dered on sub-pixel off­sets:

The dif­fer­ence be­tween an­i­mat­ing with sub-pixel ren­der­ing and with­out is stag­ger­ing when we view it in mo­tion:

Prior to Di­rectWrite the nor­mal way to an­i­mate like this was to ren­der to a tex­ture with mono­chrome anti-alias­ing (that is, with­out ClearType), and trans­form the tex­ture while ren­der­ing. The prob­lem with that is the trans­form will in­tro­duce a lot of im­per­fec­tions with­out ex­pen­sive su­per-sam­pling, and of course it won’t be able to use ClearType. With Di­rectWrite you get pixel-per­fect ClearType ren­der­ing every time.

Ap­par­ently WPF 4 is al­ready using Di­rec­t2D and Di­rectWrite to some de­gree, hope­fully there will be high-qual­ity text in­te­grated in Flash’s fu­ture. Fire­fox has also been look­ing at adding Di­rectWrite sup­port, but I haven’t seen any news of We­bkit (Chrome/Sa­fari) or Opera doing the same. It looks like Fire­fox might ac­tu­ally get it in be­fore In­ter­net Ex­plorer. Edit: looks like In­ter­net Ex­plorer 9 will use Di­rectWrite—won­der which will go gold with the fea­ture first?

Di­rec­t2D and Di­rectWrite are in­cluded in Win­dows 7, but Mi­crosoft has back­ported them in the Plat­form Up­date for Win­dows Server 2008 and Win­dows Vista so there’s no rea­son peo­ple who are stick­ing with Vista should be left out. Are there peo­ple stick­ing with Vista?

I/O Improvements in Windows Vista

My tips for ef­fi­cient I/O are rel­e­vant all the way back to cod­ing for Win­dows 2000. A lot of time has passed since then though, and for all the crit­i­cism it got, Win­dows Vista ac­tu­ally brought in a few new ways to make I/O even more per­for­mant than be­fore.

This will prob­a­bly be my last post on user-mode I/O until some­thing new and in­ter­est­ing comes along, com­plet­ing what started a cou­ple weeks ago with High Per­for­mance I/O on Win­dows.

Synchronous completion

In the past, non-block­ing I/O was a great way to re­duce the stress on a com­ple­tion port. An un­for­tu­nate side-ef­fect of this was an in­creased amount of syscalls -- the last non-block­ing call you make will do noth­ing, only re­turn­ing WSAE­WOULD­BLOCK. You would still need to call an asyn­chro­nous ver­sion to wait for more data.

Win­dows Vista solved this el­e­gantly with Set­File­Com­ple­tion­No­ti­fi­ca­tion­Modes. This func­tion lets you tell a file or socket that you don't want a com­ple­tion packet queued up when an op­er­a­tion com­pletes syn­chro­nously (that is, a func­tion re­turned suc­cess im­me­di­ately and not ER­ROR_IO_PEND­ING). Using this, the last I/O call will al­ways be of some use -- ei­ther it com­pletes im­me­di­ately and you can con­tinue pro­cess­ing, or it starts an asyn­chro­nous op­er­a­tion and a com­ple­tion packet will be queued up when it fin­ishes.

Like the non-block­ing I/O trick, con­tin­u­ally call­ing this can starve other op­er­a­tions in a com­ple­tion port if a socket or file feeds data faster than you can process it. Care should be taken to limit the num­ber of times you con­tinue pro­cess­ing syn­chro­nous com­ple­tions.

Reuse memory with file handles

If you want to op­ti­mize even more for through­put, you can as­so­ci­ate a range of mem­ory with an un­buffered file han­dle using Set­FileIoOver­lappe­dRange. This tells the OS that a block of mem­ory will be re-used, and should be kept locked in mem­ory until the file han­dle is closed. Of course if you won't be per­form­ing I/O with a han­dle very often, it might just waste mem­ory.

Dequeue multiple completion packets at once

A new fea­ture to fur­ther re­duce the stress on a com­ple­tion port is GetQueued­Com­ple­tion­Sta­tu­sEx, which lets you de­queue mul­ti­ple com­ple­tion pack­ets in one call.

If you read the docs for it, you'll even­tu­ally re­al­ize it only re­turns error in­for­ma­tion if the func­tion it­self fails—not if an async op­er­a­tion fails. Un­for­tu­nately this im­por­tant in­for­ma­tion is miss­ing from all the of­fi­cial docs I could find, and search­ing gives noth­ing. So how do you get error in­for­ma­tion out of GetQueued­Com­ple­tion­Sta­tu­sEx? Well, after play­ing around a bit I dis­cov­ered that you can call GetOver­lappe­dResult or WSAGe­tOver­lappe­dResult to get it, so not a prob­lem.

This func­tion should only be used if your ap­pli­ca­tion has a sin­gle thread or han­dles a high amount of con­cur­rent I/O op­er­a­tions, or you might end up de­feat­ing the mul­ti­thread­ing baked in to com­ple­tion ports by not let­ting it spread com­ple­tion no­ti­fi­ca­tions around. If you can use it, it's a nice and easy way to boost the per­for­mance of your code by low­er­ing con­tention on a com­ple­tion port.

Bandwidth reservation

One large change in Win­dows Vista was I/O sched­ul­ing and pri­or­i­ti­za­tion. If you have I/O that is de­pen­dant on steady stream­ing like audio or video, you can now use Set­File­Band­widthReser­va­tion to help en­sure it will never be in­ter­rupted by some­thing else hog­ging a disk.

Cancel specific I/O requests

A big pain pre-Vista was the in­abil­ity to can­cel in­di­vid­ual I/O op­er­a­tions. The only op­tion was to can­cel all op­er­a­tions for a han­dle, and only from the thread which ini­ti­ated them.

If it turns out some I/O op­er­a­tion is no longer re­quired, it is now pos­si­ble to can­cel in­di­vid­ual I/Os using Can­ce­lIoEx. This much needed func­tion re­places the al­most use­less Can­ce­lIo, and opens the doors to shar­ing file han­dles be­tween sep­a­rate op­er­a­tions.

Visual C++ 2010 Beta 1

Vi­sual Stu­dio 2010 Beta 1 was re­leased yes­ter­day for MSDN sub­scribers. Prob­a­bly the most an­tic­i­pated re­lease in a while for C++ de­vel­op­ers, 2010 is Mi­crosoft's at­tempt to give C++ first-class sup­port, some­thing which hasn't been seen since Vi­sual Stu­dio 6.0.

Up­date: down­loads are now avail­able for non-MSDN sub­scribers.

On the com­piler side of things, we get par­tial C++0x sup­port in the form of lambda ex­pres­sions, rvalue ref­er­ences, auto, de­cltype, and sta­tic as­sert. The fea­tures are piled on with an im­proved TR1 li­brary—fi­nally in­clud­ing the much re­quested stdint.h and cst­dint head­ers, but still lack­ing int­types.h.

Also in­cluded is the Par­al­lel Pat­terns Li­brary, a new task-based con­cur­rency li­brary that makes heavy use of the C++0x fea­tures for a nice mod­ern de­sign. I men­tioned be­fore that on Win­dows 7 this will make use of a User-mode sched­uled thread pool so it should be re­ally ef­fi­cient. Un­for­tu­nately given its pro­pri­etary na­ture I'm not sure how much use it will get.

The first thing you will no­tice on the IDE side is the in­line error check­ing. Some­thing we've en­joyed while edit­ing C# for some time, we now get the red squig­gly lines when an error is found. It works fairly well, but sup­port for lambda ex­pres­sions has not been writ­ten yet.

In­tel­lisense has markedly im­proved since 2008. Using ad­vanced C++ or a Boost li­brary no longer guar­an­tees it break­ing. It has worked with nearly all the C++ I've thrown at it so far.

You can also see an Ex­ter­nal De­pen­den­cies vir­tual folder added to your pro­ject source, which is dy­nam­i­cally filled with all the files In­tel­lisense will scan. I've found it is not ter­ri­bly use­ful, though, be­cause even with small pro­jects the header count in­creases rapidly enough to make the vir­tual folder be­come an un­in­tel­li­gi­ble mess.

The prob­lem is only ag­gra­vated by li­braries like Boost, which have hun­dreds of head­ers or­ga­nized nicely in fold­ers. Putting them into a sin­gle vir­tual folder just doesn't work.

This re­lease also marks the move to the ex­ten­si­ble MS­Build sys­tem for C++ pro­jects, which aims to pro­vide func­tion­al­ity sim­i­lar to GNU make in an XML for­mat.

Per­haps the most ob­vi­ous change for the over­all IDE is that the main UI is now done en­tirely in WPF. It sounded like a de­cent plan at first but I'm not too happy with it now. Minor dif­fer­ences from the way na­tive con­trols be­have can be pretty an­noy­ing, and the five to twenty sec­ond load time makes it less use­ful for open­ing ran­dom .cpp files when 2008 would load them in one or two sec­onds.

Tips for efficient I/O

There are a few things to keep in mind for I/O that can have pretty in­cred­i­ble ef­fects on per­for­mance and scal­a­bil­ity. It’s not re­ally any new API, but how you use it.

Reduce blocking

The whole point of I/O com­ple­tion ports is to do op­er­a­tions asyn­chro­nously, to keep the CPU busy doing work while wait­ing for com­ple­tion. Block­ing de­feats this by stalling the thread, so it should be avoided when­ever pos­si­ble. Com­ple­tion ports have a mech­a­nism built in to make block­ing less hurt­ful by start­ing up a wait­ing thread when an­other one blocks, but it is still bet­ter to avoid it all to­gether.

This in­cludes mem­ory al­lo­ca­tion. Stan­dard sys­tem al­lo­ca­tors usu­ally have sev­eral points where it needs to lock to allow con­cur­rent use, so ap­pli­ca­tions should make use of cus­tom al­lo­ca­tors like are­nas and pools where pos­si­ble.

This means I/O should al­ways be per­formed asyn­chro­nously, lock-free al­go­rithms used when avail­able, and any re­main­ing locks should be as op­ti­mally placed as pos­si­ble. Care­ful ap­pli­ca­tion de­sign plan­ning goes a long way here. The tough­est area I’ve dis­cov­ered is data­base ac­cess—as far as I have seen, there have been zero well de­signed data­base client li­braries. Every one that I’ve seen has forced you to block at some point.

Ide­ally, the only place the ap­pli­ca­tion would block is when re­triev­ing com­ple­tion pack­ets.

Buffer size and alignment

I/O rou­tines like to lock the pages of the buffers you pass in. That is, it will pin them in phys­i­cal mem­ory so that they can’t be paged out to a swap file.

The re­sult is if you pass in a 20 byte buffer, on most sys­tems it will lock a full 4096 byte page in mem­ory. Even worse, if the 20 byte buffer has 10 bytes in one page and 10 bytes in an­other, it will lock both pages—8192 bytes of mem­ory for a 20 byte I/O. If you have a large num­ber of con­cur­rent op­er­a­tions this can waste a lot of mem­ory!

Be­cause of this, I/O buffers should get spe­cial treat­ment. Func­tions like malloc() and operator new() should not be used be­cause they have no oblig­a­tion to pro­vide such op­ti­mal align­ment for I/O. I like to use VirtualAlloc to al­lo­cate large blocks of 1MiB, and di­vide this up into smaller fixed-sized (usu­ally page-sized, or 4KiB) blocks to be put into a free list.

If buffers are not a mul­ti­ple of the sys­tem page size, extra care should be taken to al­lo­cate buffers in a way that keeps them in sep­a­rate pages from non-buffer data. This will make sure page lock­ing will incur the least amount of over­head while per­form­ing I/O.

Limit the number of I/Os

Sys­tem calls and com­ple­tion ports have some ex­pense, so lim­it­ing the num­ber of I/O calls you do can help to in­crease through­put. We can use scat­ter/gather op­er­a­tions to chain sev­eral of those page-sized blocks into one sin­gle I/O.

A scat­ter op­er­a­tion is tak­ing data from one source, like a socket, and scat­ter­ing it into mul­ti­ple buffers. In­versely a gather op­er­a­tion takes data from mul­ti­ple buffers and gath­ers it into one des­ti­na­tion.

For sock­ets, this is easy—we just use the nor­mal WSASend and WSARecv func­tions, pass­ing in mul­ti­ple WSABUF struc­tures.

For files it is a lit­tle more com­plex. Here the WriteFileGather and ReadFileScatter func­tions are used, but some spe­cial care must be taken. These func­tions re­quire page-aligned and -sized buffers to be used, and the num­ber of bytes read/writ­ten must be a mul­ti­ple of the disk’s sec­tor size. The sec­tor size can be ob­tained with Get­Disk­Free­Space.

Non-blocking I/O

Asyn­chro­nous op­er­a­tions are key here, but non-block­ing I/O still has a place in the world of high per­for­mance.

Once an asyn­chro­nous op­er­a­tion com­pletes, we can issue non-block­ing re­quests to process any re­main­ing data. Fol­low­ing this pat­tern re­duces the amount of strain on the com­ple­tion port and helps to keep your op­er­a­tion con­text hot in the cache for as long as pos­si­ble.

Care should be taken to not let non-block­ing op­er­a­tions con­tinue on for too long, though. If data is re­ceived on a socket fast enough and we take so long to process it that there is al­ways more, it could starve other com­ple­tion no­ti­fi­ca­tions wait­ing to be de­queued.

Throughput or concurrency

A ker­nel has a lim­ited amount of non-paged mem­ory avail­able to it, and lock­ing one or more pages for each I/O call is a real easy way use it all up. Some­times if we ex­pect an ex­treme num­ber of con­cur­rent con­nec­tions or if we want to limit mem­ory usage, it can be ben­e­fi­cial to delay lock­ing these pages until ab­solutely re­quired.

An un­doc­u­mented fea­ture of WSARecv is that you can re­quest a 0-byte re­ceive, which will com­plete when data has ar­rived. Then you can issue an­other WSARecv or use non-block­ing I/O to pull out what­ever is avail­able. This lets us get no­ti­fied when data can be re­ceived with­out ac­tu­ally lock­ing mem­ory.

Doing this is very much a choice of through­put or con­cur­rency—it will use more CPU, re­duc­ing through­put. But it will allow your ap­pli­ca­tion to han­dle a larger num­ber of con­cur­rent op­er­a­tions. It is most ben­e­fi­cial in a low mem­ory sys­tem, or on 32-bit Win­dows when an ex­treme num­ber of con­cur­rent op­er­a­tions will be used. 64-bit Win­dows has a much larger non-paged pool, so it shouldn’t pre­sent a prob­lem if you feed it enough phys­i­cal mem­ory.

Unbuffered I/O

If you are using the file sys­tem a lot, your ap­pli­ca­tion might be wait­ing on the syn­chro­nous op­er­at­ing sys­tem cache. In this case, en­abling un­buffered I/O will let file op­er­a­tions by­pass the cache and com­plete more asyn­chro­nously.

This is done by call­ing CreateFile with the FILE_FLAG_NO_BUFFERING flag. Note that with this flag, all file ac­cess must be sec­tor aligned—read/write off­sets and sizes. Buffers must also be sec­tor aligned.

Op­er­at­ing sys­tem caching can have good ef­fects, so this isn’t al­ways ad­van­ta­geous. But if you’ve got a spe­cific I/O pat­tern or if you do your own caching, it can give a sig­nif­i­cant per­for­mance boost. This is an easy thing to turn on and off, so take some bench­marks.

Up­date: this sub­ject con­tin­ued in I/O Im­prove­ments in Win­dows Vista.

Visual Studio 2010 Beta 1 in four days

Vi­sual Stu­dio 2010 Beta 1 is being launched for MSDN sub­scribers in four days on the 18th, and for the gen­eral pub­lic on the 20th!

I/O completion ports made easy

I de­scribed the ba­sics of I/O com­ple­tion ports in my last post, but there is still the ques­tion of what the eas­i­est way to use them. Here I’ll show a call­back-based ap­pli­ca­tion de­sign that I’ve found makes a fully asyn­chro­nous pro­gram re­ally sim­ple to do.

I touched briefly on at­tach­ing our own con­text data to the OVERLAPPED struc­ture we pass along with I/O op­er­a­tions. It’s this same idea that I’ll ex­pand on here. This time, we de­fine a generic struc­ture to use with all our op­er­a­tions, and how our threads will han­dle them while de­queu­ing pack­ets:

struct io_context
{
  OVERLAPPED ovl;
  void (*on_completion)(DWORD error, DWORD transferred,
                        struct io_context *ctx);
};

OVERLAPPED *ovl;
ULONG_PTR completionkey;
DWORD transferred;

BOOL ret = GetQueuedCompletionStatus(iocp, &transferred,
   &completionkey, &ovl, INFINITE);

if(ret)
{
  struct io_context *ctx = (struct io_context*)ovl;
  ctx->on_completion(ERROR_SUCCESS, transferred, ctx);
}
else if(ovl)
{
  DWORD err = GetLastError();

  struct io_context *ctx = (struct io_context*)ovl;
  ctx->on_completion(err, transferred, ctx);
}
else
{
  // error out
}

With this, all our I/O op­er­a­tions will have a call­back as­so­ci­ated with them. When a com­ple­tion packet is de­queued it gets the error in­for­ma­tion, if any, and runs the call­back. Hav­ing every I/O op­er­a­tion use a sin­gle call­back mech­a­nism greatly sim­pli­fies the de­sign of the en­tire pro­gram.

Lets say our app was read­ing a file and send­ing out it’s con­tents. We also want it to prefetch the next buffer so we can start send­ing right away. Here’s our con­nec­tion con­text:

struct connection_context
{
  HANDLE file;
  SOCKET sock;

  WSABUF readbuf;
  WSABUF sendbuf;

  struct io_context readctx;
  struct io_context sendctx;
};

A struc­ture like this is nice be­cause ini­ti­at­ing an I/O op­er­a­tion will need no al­lo­ca­tions. Note that we need two io_­con­text mem­bers be­cause we’re doing a read and send con­cur­rently.

Now the code to use it:

#define BUFFER_SIZE 4096

void begin_read(struct connection_context *ctx)
{
  if(ctx->readbuf.buf)
  {
    // only begin a read if one isn't already running.
    return;
  }

  ctx->readbuf.buf = malloc(BUFFER_SIZE);
  ctx->readbuf.len = 0;

  // zero out io_context structure.
  memset(&ctx->readctx, 0, sizeof(ctx->readctx));

  // set completion callback.
  ctx->readctx.on_completion = read_finished;

  ReadFile(ctx->file, ctx->readbuf.buf, BUFFER_SIZE,
           NULL, &ctx->readctx.ovl);
}

void read_finished(DWORD error, DWORD transferred,
                   struct io_context *ioctx)
{
  // get our connection context.
  struct connection_context *ctx =
     (struct connection_context*)((char*)ioctx -
        offsetof(struct connection_context, readctx));

  if(error != ERROR_SUCCESS)
  {
    // handle error.
    return;
  }

  if(!transferred)
  {
    // reached end of file, close out connection.
    free(ctx->readbuf.buf);
    ctx->readbuf.buf = 0;
    return;
  }

  // send out however much we read from the file.

  ctx->readbuf.len = transferred;

  begin_send(ctx);
}

This gives us a very ob­vi­ous chain of events: read_finished is called when a read com­pletes. Since we only get an io_context struc­ture in our call­back, we need to ad­just the pointer to get our full connection_context.

Send­ing is easy too:

void begin_send(struct connection_context *ctx)
{
  if(ctx->sendbuf.buf)
  {
    // only begin a send if one
    // isn't already running.
    return;
  }

  if(!ctx->recvbuf.len)
  {
    // only begin a send if the
    // read buffer has something.
    return;
  }

  // switch buffers.
  ctx->sendbuf = ctx->readbuf;

  // clear read buffer.
  ctx->readbuf.buf = NULL;
  ctx->readbuf.len = 0;

  // zero out io_context structure.
  memset(&ctx->sendctx, 0, sizeof(ctx->sendctx));

  // set completion callback.
  ctx->sendctx.on_completion = send_finished;

  WSASend(ctx->sock, &ctx->sendbuf, 1, NULL, 0,
          &ctx->sendctx.ovl, NULL);

  // start reading next buffer.
  begin_read(ctx);
}

void send_finished(DWORD error, DWORD transferred,
                   struct io_context *ioctx)
{
  // get our connection context.
  struct connection_context *ctx =
     (struct connection_context*)((char*)ioctx -
        offsetof(struct connection_context, sendctx));

  if(error != ERROR_SUCCESS)
  {
    // handle error.
    return;
  }

  // success, clear send buffer and start next send.

  free(ctx->sendbuf.buf);
  ctx->sendbuf.buf = NULL;

  begin_send(ctx);
}

Pretty much more of the same. Again for brevity I’m leav­ing out some error check­ing code and as­sum­ing the buffer gets sent out in full. I’m also as­sum­ing a sin­gle-threaded de­sign—socket and file func­tions them­selves are thread-safe and have noth­ing to worry about, but the buffer man­age­ment code here would need some extra lock­ing since it could be run con­cur­rently. But the idea should be clear.

Up­date: this sub­ject con­tin­ued in Tips for ef­fi­cient I/O.

High Performance I/O on Windows

I/O com­ple­tion ports were first in­tro­duced in Win­dows NT 4.0 as a highly scal­able, multi-proces­sor ca­pa­ble al­ter­na­tive to the then-typ­i­cal prac­tices of using se­lect, WSAWait­For­Mul­ti­pleEvents, WSAA­sync­S­e­lect, or even run­ning a sin­gle thread per client. The most op­ti­mal way to per­form I/O on Win­dows—short of writ­ing a ker­nel-mode dri­ver—is to use I/O com­ple­tion ports.

A re­cent post on Slash­dot claimed sock­ets have run their course, which I think is ab­solutely not true! The au­thor seems to be­lieve the Berke­ley sock­ets API is the only way to per­form socket I/O, which is non­sense. Much more mod­ern, scal­able and high per­for­mance APIs exist today such as I/O com­ple­tion ports on Win­dows, epoll on Linux, and kqueue on FreeBSD. In light of this I thought I’d write a lit­tle about com­ple­tion ports here.

The old ways of mul­ti­plex­ing I/O still work pretty well for sce­nar­ios with a low num­ber of con­cur­rent con­nec­tions, but when writ­ing a server dae­mon to han­dle a thou­sand or even tens of thou­sands of con­cur­rent clients at once, we need to use some­thing dif­fer­ent. In this sense the old de facto stan­dard Berke­ley sock­ets API has run its course, be­cause the over­head of man­ag­ing so many con­nec­tions is sim­ply too great and makes using mul­ti­ple proces­sors hard.

An I/O com­ple­tion port is a multi-proces­sor aware queue. You cre­ate a com­ple­tion port, bind file or socket han­dles to it, and start asyn­chro­nous I/O op­er­a­tions. When they com­plete—ei­ther suc­cess­fully or with an error—a com­ple­tion packet is queued up on the com­ple­tion port, which the ap­pli­ca­tion can de­queue from mul­ti­ple threads. The com­ple­tion port uses some spe­cial voodoo to make sure only a spe­cific num­ber of threads can run at once—if one thread blocks in ker­nel-mode, it will au­to­mat­i­cally start up an­other one.

First you need to cre­ate a com­ple­tion port with Cre­ateIo­Com­ple­tion­Port:

HANDLE iocp = CreateIoCompletionPort(INVALID_HANDLE_VALUE,
   NULL, 0, 0);

It’s im­por­tant to note that Num­berOf­Con­cur­rent­Threads is not the total num­ber of threads that can ac­cess the com­ple­tion port—you can have as many as you want. This in­stead con­trols the num­ber of threads it will allow to run con­cur­rently. Once you’ve reached this num­ber, it will block all other threads. If one of the run­ning threads blocks for any rea­son in ker­nel-mode, the com­ple­tion port will au­to­mat­i­cally start up one of the wait­ing threads. Spec­i­fy­ing 0 for this is equiv­a­lent to the num­ber of log­i­cal proces­sors in the sys­tem.

Next is cre­at­ing and as­so­ci­at­ing a file or socket han­dle, using Cre­ate­File, WSASocket, and Cre­ateIo­Com­ple­tion­Port:

#define OPERATION_KEY 1

HANDLE file = CreateFile(L"file.txt", GENERIC_READ,
   FILE_SHARE_READ, NULL, OPEN_EXISTING,
   FILE_FLAG_OVERLAPPED, NULL);

SOCKET sock = WSASocket(AF_INET, SOCK_STREAM, IPPROTO_TCP,
   NULL, 0, WSA_FLAG_OVERLAPPED);

CreateIoCompletionPort(file, iocp, OPERATION_KEY, 0);
CreateIoCompletionPort((HANDLE)sock, iocp, OPERATION_KEY, 0);

Files and sock­ets must be opened with the FILE_FLAG_OVERLAPPED and WSA_FLAG_OVERLAPPED flags be­fore they are used asyn­chro­nously.

Reusing CreateIoCompletionPort for as­so­ci­at­ing file/socket han­dles is weird de­sign choice from Mi­crosoft but that’s how it’s done. The CompletionKey pa­ra­me­ter can be any­thing you want, it is a value pro­vided when pack­ets are de­queued. I de­fine a OPERATION_KEY here to use as the CompletionKey, the sig­nif­i­cance of which I’ll get to later.

Next we have to start up some I/O op­er­a­tions. I’ll skip set­ting up the socket and go right to send­ing data. We start these op­er­a­tions using Read­File and WSASend:

OVERLAPPED readop, sendop;
WSABUF sendwbuf;
char readbuf[256], sendbuf[256];

memset(&readop, 0, sizeof(readop));
memset(&sendop, 0, sizeof(sendop));

sendwbuf.len = sizeof(sendbuf);
sendwbuf.buf = sendbuf;

BOOL readstatus = ReadFile(file, readbuf,
   sizeof(readbuf), NULL, &readop);

if(!readstatus)
{
  DWORD readerr = GetLastError();

  if(readerr != ERROR_IO_PENDING)
  {
    // error reading.
  }
}

int writestatus = WSASend(sock, &sendwbuf, 1, NULL,
   0, &sendop, NULL);

if(writestatus)
{
  int writeerr = WSAGetLastError();

  if(writeerr != WSA_IO_PENDING)
  {
    // error sending.
  }
}

Every I/O op­er­a­tion using a com­ple­tion port has an OVERLAPPED struc­ture as­so­ci­ated with it. Win­dows uses this in­ter­nally in un­spec­i­fied ways, only say­ing we need to zero them out be­fore start­ing an op­er­a­tion. The OVERLAPPED struc­ture will be given back to us when we de­queue the com­ple­tion pack­ets, and can be used to pass along our own con­text data.

I have left out the stan­dard error check­ing up until now for brevity’s sake, but this one doesn’t work quite like one might ex­pect so it is im­por­tant here. When start­ing an I/O op­er­a­tion, an error might not re­ally be an error. If the func­tion suc­ceeds all is well, but if the func­tion fails, it is im­por­tant to check the error code with Get­LastEr­ror or WSAGet­LastEr­ror.

If these func­tions re­turn ERROR_IO_PENDING or WSA_IO_PENDING, the func­tion ac­tu­ally still com­pleted suc­cess­fully. All these error codes mean is an asyn­chro­nous op­er­a­tion has been started and com­ple­tion is pend­ing, as op­posed to com­plet­ing im­me­di­ately. A com­ple­tion packet will be queued up re­gard­less of the op­er­a­tion com­plet­ing asyn­chro­nously or not.

De­queu­ing pack­ets from a com­ple­tion port is han­dled by the GetQueuedCompletionStatus func­tion:

This func­tion de­queues com­ple­tion pack­ets, con­sist­ing of the com­ple­tion key we spec­i­fied in CreateIoCompletionPort and the OVERLAPPED struc­ture we gave while start­ing the I/O. If the I/O trans­ferred any data, it will re­trieve how many bytes were trans­ferred too. Again the error han­dling is a bit weird on this one, hav­ing three error states.

This can be run from as many threads as you like, even a sin­gle one. It is com­mon prac­tice to run a pool of twice the num­ber of threads as there are log­i­cal proces­sors avail­able, to keep the CPU ac­tive with the afore­men­tioned func­tion­al­ity of start­ing a new thread if a run­ning one blocks.

Un­less you are going for a sin­gle-threaded de­sign, I rec­om­mend start­ing two threads per log­i­cal CPU. Even if your app is de­signed to be 100% asyn­chro­nous, you will still run into block­ing when lock­ing shared data and even get un­avoid­able hid­den block­ing I/Os like read­ing in paged out mem­ory. Keep­ing two threads per log­i­cal CPU will keep the proces­sor busy with­out over­load­ing the OS with too much con­text switch­ing.

This is all well and good, but two I/O op­er­a­tions were ini­ti­ated—a file read and a socket send. We need a way to tell their com­ple­tion pack­ets apart. This is why we need to at­tach some state to the OVERLAPPED struc­ture when we call those func­tions:

struct my_context
{
  OVERLAPPED ovl;
  int isread;
};

struct my_context readop, sendop;

memset(&readop.ovl, 0, sizeof(readop.ovl));
memset(&sendop.ovl, 0, sizeof(sendop.ovl));

readop.isread = 1;
sendop.isread = 0;

ReadFile(file, readbuf, sizeof(readbuf), NULL, &readop.ovl);
WSASend(sock, &sendwbuf, 1, NULL, 0, &sendop.ovl, NULL);

Now we can tell the op­er­a­tions apart when we de­queue them:

OVERLAPPED *ovl;
ULONG_PTR completionkey;
DWORD transferred;

GetQueuedCompletionStatus(iocp, &transferred,
   &completionkey, &ovl, INFINITE);

struct my_context *ctx = (struct my_context*)ovl;

if(ctx->isread)
{
  // read completed.
}
else
{
  // send completed.
}

The last im­por­tant thing to know is how to queue up your own com­ple­tion pack­ets. This is use­ful if you want to split an op­er­a­tion up to be run on the thread pool, or if you want to exit a thread wait­ing on a call to GetQueuedCompletionStatus. To do this, we use the PostQueuedCompletionStatus func­tion:

#define EXIT_KEY 0

struct my_context ctx;

PostQueuedCompletionStatus(iocp, 0, OPERATION_KEY, &ctx.ovl);
PostQueuedCompletionStatus(iocp, 0, EXIT_KEY, NULL);

Here we post two things onto the queue. The first, we post our own struc­ture onto the queue, to be processed by our thread pool. The sec­ond, we give a new com­ple­tion key: EXIT_KEY. The thread which processes this packet can test if the com­ple­tion key is EXIT_KEY to know when it needs to stop de­queu­ing pack­ets and shut down.

Other than the com­ple­tion port han­dle, Win­dows does not use any of the pa­ra­me­ters given to PostQueuedCompletionStatus. They are en­tirely for our use, to be de­queued with GetQueuedCompletionStatus.

That’s all I have to write for now, and should be every­thing one would need to get started learn­ing these high per­for­mance APIs! I will make an­other post shortly de­tail­ing some good pat­terns for com­ple­tion port usage, and some op­ti­miza­tion tips to en­sure ef­fi­cient usage of these I/O APIs.

Up­date: this sub­ject con­tin­ued in I/O com­ple­tion ports made easy.