int64.org

May 2009 Archives

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.

Live Action Avatar pics

I love Avatar: The Last Air­ben­der—such a fan­tas­tic car­toon. USA Today posted some shots of M. Night Shya­malan's live ac­tion adap­ta­tion The Last Air­ben­der. I've never seen a kids movie from Shya­malan, so I'm not sure if that is good or bad for this. His past work has been fairly hit or miss with me. But I have hope, and ap­par­ently Nick­elodeon does too -- they al­ready signed him on to write and di­rect a full tril­ogy.

Noah Ringer, who plays Aang, ac­tu­ally holds a black belt in taek­wondo. Dev Patel of Slum­dog Mil­lion­aire fame will play Prince Zuko, and he also has a black belt in taek­wondo. I'm in­ter­ested to see how Shya­malan puts that to good use. This first movie will only be book one, so un­for­tu­nately Toph won't be around.

Blankets

A few days ago I did some­thing I haven't done in over 10 years: picked up some comics and a graphic novel.

Today I fin­ished the graphic novel Blan­kets by Craig Thomp­son, an au­to­bi­og­ra­phy of the au­thor's life from child­hood on through high school and a lit­tle bit of adult­hood. It tells par­al­lel sto­ries of broth­er­hood and first love.

It was a joy to read, filled with beau­ti­ful art­work and an en­thralling story. Every page evoca­tive of what it's like grow­ing up, of that over­whelm­ing feel­ing of falling in love for the first time. This is a great book for any­one -- even if you don't like comics, I im­plore you to pick this up.

This is ac­tu­ally the first graphic novel I've read. De­spite hav­ing the ca­pac­ity to read more than your run-of-the-mill X-Men or Fan­tas­tic Four comics as a pre­teen (I dis­tinctly re­mem­ber read­ing my first Stephen King novel It and get­ting my feet wet pro­gram­ming Hy­per­Card around that time), I can't re­call ever read­ing a graphic novel or even being aware of their ex­is­tence. I rarely went to comic book stores for more than Magic cards, in­stead choos­ing to bor­row them from a friend's vast col­lec­tion.

After a cou­ple years of watch­ing The To­tally Rad Show, it fi­nally sunk in to me to go grab some comics. I chose Blan­kets specif­i­cally be­cause of the TRS guys rav­ing about it. Thanks guys!

I re­mem­bered a girl I be­friended when I was a child, who was liv­ing with her dad down the street from my house over sum­mer break. Hardly a foot­note in my life's story, I never saw her after that one sum­mer. Funny, the mem­o­ries this book brought for­ward.

The Political Compass

A cou­ple years ago the µTor­rent guys pointed me to­ward the Po­lit­i­cal Com­pass, and I have since had a lot of fun with it.

The Po­lit­i­cal Com­pass gives you a se­ries of ide­olo­gies to choose from, and uses them to map you on two axes: an eco­nomic scale (left/right) and a so­cial scale (au­thor­i­tar­ian/lib­er­tar­ian).

Many of the ques­tions in the test forces one to take a deeper view at their own ide­olo­gies. I know there were a cou­ple on there that made me ques­tion my­self. If you take it truth­fully—ig­nor­ing any po­lit­i­cal par­ties that have slighted you, ig­nor­ing any po­lit­i­cal cor­rect­ness, and sim­ply an­swer­ing how you ac­tu­ally feel, you might learn some­thing about your­self.

The ide­olo­gies pro­posed are often on a far axis, forc­ing you to choose be­tween ex­tremes. Some of them are vague, forc­ing you to think it out. I al­most uni­ver­sally have peo­ple paste me some of the ques­tions with a big WTF, some­times even ac­cus­ing the test of being slanted against them.

It al­ways fas­ci­nates me to have other peo­ple take it, be­cause by the end most of them re­al­ize the guy they had been root­ing for—Obama, Mc­Cain, Ron Paul, who­ever—is ac­tu­ally pretty far from their views. Many De­moc­rats re­al­ize they are a good deal far­ther left than they thought, and most Re­pub­li­cans find they are quite a bit more lib­er­tar­ian than they be­lieved.

The com­pass is not re­ally a de­fin­i­tive an­swer for what party you should vote for, I wouldn't rec­om­mend any­one vote solely be­cause of it. But it can offer a start­ing point point for peo­ple, to fil­ter the feel-good pol­i­tics that try to ap­peal to every­one from the ac­tual is­sues that peo­ple dis­agree with.

In a cou­ple cases the peo­ple I've had take it re­al­ized they are ac­tu­ally polar op­po­sites of the guy they voted for, one of them thank­ing me a few weeks af­ter­ward as it had caused him to read up on his choice and no­tice he had been fooled by those same feel-good pol­i­tics, say­ing "I can't be­lieve I al­most voted for that idiot!"

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.

C++ ORM framework for SQLite

Over the past week I’ve been rewrit­ing my rather dated SQLite wrap­per to have an ef­fi­cient, mod­ern C++ feel. The basic wrap­per is there, but I was look­ing for some­thing a lit­tle more this time.

While look­ing at the prob­lem I de­cided I was spend­ing too much time writ­ing boil­er­plate SQL for all my types so I de­cided to look at ex­ist­ing ORM frame­works. I’m pretty picky about my C++ though, and couldn’t find any­thing I liked so I started writ­ing my own. In­stead of cre­at­ing a tool to gen­er­ate C++, I wanted to take a pure ap­proach using na­tive C++ types and tem­plate metapro­gram­ming.

What I ended up with is not a full ORM frame­work, and I’m not par­tic­u­larly in­ter­ested in mak­ing it one. All I’m aim­ing for is re­mov­ing boil­er­plate code while leav­ing it easy to ex­tend it for more com­plex queries. Here’s what I’ve got so far:

struct my_object
{
  int id;
  std::string value;
  boost::posix_time::ptime time;
};

typedef boost::mpl::vector<
  sqlite3x::column<
    my_object, int, &my_object::id,
    sqlite3x::primary_key, sqlite3x::auto_increment
  >,
  sqlite3x::column<
    my_object, std::string, &my_object::value,
    sqlite3x::unique_key
  >,
  sqlite3x::column<
    my_object, boost::posix_time::ptime, &my_object::time
  >
> my_object_columns;

typedef sqlite3x::table<
  my_object,
  my_object_columns
> my_object_table;

Using it is pretty sim­ple. It uses the pri­mary key as ex­pected, gen­er­at­ing the proper WHERE con­di­tions and even ex­tract­ing the type to let find() and oth­ers spec­ify only the pri­mary key:

sqlite3x::connection con("test.db3");

my_object_table my_objects(con, "t_objects");

my_objects.add(my_object());
my_objects.edit(my_object());
my_objects.remove(int());
my_objects.exists(int());
my_objects.find(int());

One ben­e­fit of the ap­proach taken is it makes work­ing with sin­gle- and mul­ti­ple-in­her­i­tance just as easy:

struct my_derived :
  my_object
{
  float extra;
};

typedef boost::mpl::copy<
  boost::mpl::vector<
    sqlite3x::column<my_derived, float, &my_object::extra>
  >,
  boost::mpl::back_inserter<my_object_columns>
> my_derived_columns;

typedef sqlite3x::table<
  my_derived,
  my_derived_columns
> my_object_table;

The next thing on the list was sup­port­ing types not known na­tively to sqlite3x. I did not want to have the headache of sub-ta­bles, so I took the easy route and im­ple­mented basic se­ri­al­iza­tion sup­port:

struct my_derived :
  my_object
{
  std::vector<boost::uuid> uuids;
};

struct uuids_serializer
{
  static void serialize(std::vector<boost::uint8_t> &buffer,
     const std::vector<boost::uuid> &uuids);

  template<typename Iterator>
  static Iterator deserialize(std::vector<boost::uuid> &uuids,
     Iterator first, Iterator last);
};

typedef boost::mpl::copy<
  boost::mpl::vector<
    sqlite3x::column<
      my_derived, float, &my_object::extra,
      sqlite3x::serializer<uuids_serializer>
    >
  >,
  boost::mpl::back_inserter<my_object_columns>
> my_derived_columns;

A few things aren’t fin­ished, like spec­i­fy­ing in­dexes and sup­port for multi-col­umn pri­mary keys.

Over­all though, I’m pretty happy with it. The ma­jor­ity of what I use SQLite for doesn’t re­quire many com­plex queries, so this should greatly help lower the amount of code I have to man­age.

Best of all this ORM code is in an en­tirely iso­lated header file—if you don’t want it, just don’t in­clude it and you’ll still have ac­cess to all the basic SQLite func­tions. Even with it in­cluded I kept to the C++ mantra of “dont pay for what you don’t use”—as it is en­tirely tem­plate-dri­ven, code will only be gen­er­ated if you ac­tu­ally use it.

Once I’m fin­ished the code will re­place what I have up on the SQLite wrap­per page, but until then it will exist in the sub­ver­sion repos­i­tory only.

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.

Check out Cuba Central

There’s this nice lit­tle Cuban place in Lit­tle Tokyo called Cuba Cen­tral. I don’t know if it’s just the times I’m going there, but every time I grab din­ner I’m amazed the place isn’t packed. The ropa vieja — holy crap, it looks so de­cep­tively sim­ple but what­ever they throw in to make that sauce is in­cred­i­ble. Give them some busi­ness, grab some good food!